Parsing arbitrary expressions as strings

[purplefox]

Hi @alecthomas

I am trying to create a parser which, in one area, parses a list of arbitrary expressions (which can contain any character apart from semicolon) separated by semicolons. I'm struggling to get the expressions to be lexed as single tokens so they can be captured, since as they can be more or less anything the token definitions overlap with other things such as Ident, strings etc.

Any thoughts on how this can be accomplished? Please note I am not trying to parse the expressions themselves, I am happy to just select anything between the semicolons as strings. I can get this to work by surrounding the expressions with double quotes (because then they match the String token), but I don't want this in the actual language as I think it's uglier than using semicolons.

Here's a test that demonstrates the issue:

type CreatePipeline struct {
	Name      string            `"create" "pipeline" @Ident "as"`
	Operators []*OperatorHolder `"(" @@ ")" ("->" "(" @@ ")")*`
}

type OperatorHolder struct {
	FieldsOperator *FieldsOperator `"fields" @@ |`
}

type FieldsOperator struct {
	FieldExpressions []string `@String ("," @String)*`
}

func TestParse(t *testing.T) {

	lex := lexer.MustSimple([]lexer.SimpleRule{
		{"Comment", `(?:#|//)[^\n]*\n?`},
		{"String", `"(\\"|[^"])*"`},
		{"Pipe", `->`},
		{"Ident", `[a-zA-Z]\w*`},
		{"Number", `(?:\d*\.)?\d+`},
		{"Punct", `[();]`},
		{"Expr", `[^\s^;]+`},
		{"Whitespace", `[ \t\n\r]+`},
	})

	parser, err := participle.Build[CreatePipeline](
		participle.Lexer(lex),
		participle.Elide("Comment", "Whitespace"),
		participle.UseLookahead(2),
	)
	require.NoError(t, err)

	s := "create pipeline test_pipeline as (fields f1; f2 + 3; trim(f5,3))"

	cpParsed, err := parser.ParseString("", s)
	require.NoError(t, err, s)

	cpExpected := &CreatePipeline{
		Name: "test_pipeline",
		Operators: []*OperatorHolder{
			{FieldsOperator: &FieldsOperator{
				FieldExpressions: []string{"\"f1\"", "\"f2 + 3\"", "\"trim(f5,3)\""},
			}},
		},
	}
	require.Equal(t, cpExpected, cpParsed)
}

Thanks in advance for the help!

[alecthomas]

Hey Tim!

Your best bet is probably ~<expr> though you'll need to account for nested (). You might need something like @~(";"|"(")|@@ where the left expression parses into one field and the right @@ is parsed into a separate field that parses (<expr>) recursively.

~<expr> Match any token that is not the start of the expression (eg: @~";" matches anything but the ; character into the field).

[purplefox]

Hi Alec, thanks for the reply!
I got a bit further here, and managed to parse expressions separated by ";" into strings, but, as you implied, the brackets seem to be the problem - it doesn't know when to stop parsing the expressions as ")" can be part of an expression too.
Any more hints from your side? :)

func TestParseFoo(t *testing.T) {
	type Expr struct {
		StringField string `@~";" (@~";")*`
	}
	type CreatePipeline struct {
		Name        string  `"create" "pipeline" @Ident "as"`
		Expressions []*Expr `("(")* @@ (";" @@)* (")")*`
	}

	lex := lexer.MustSimple([]lexer.SimpleRule{
		{"Comment", `(?:#|//)[^\n]*\n?`},
		{"String", `"(\\"|[^"])*"`},
		{"Pipe", `->`},
		{"Ident", `[a-zA-Z]\w*`},
		{"Number", `(?:\d*\.)?\d+`},
		{"Punct", `[-[!@#$%^&*()+_={}\|:;"'<,>.?/]|]`},
		{"Whitespace", `[ \t\n\r]+`},
	})

	parser, err := participle.Build[CreatePipeline](
		participle.Lexer(lex),
		participle.Elide("Comment", "Whitespace"),
		participle.UseLookahead(2),
	)
	require.NoError(t, err)

	cpExpected := &CreatePipeline{
		Name: "test_p",
		Expressions: []*Expr{
			{"some_func(ident1+x,ident2,ident3)"},
			{"quux(\"a b\")"},
			{"ident6,ident7,ident8"},
		},
	}

	s := "create pipeline test_p as (some_func(ident1+x,ident2,ident3);quux(\"a b\");ident6,ident7,ident8)"
	cpParsed, err := parser.ParseString("", s)
	require.NoError(t, err, s)
	require.Equal(t, cpExpected, cpParsed)

	s = "create pipeline test_p as some_func(ident1+x,ident2,ident3);quux(\"a b\");ident6,ident7,ident8"
	cpParsed, err = parser.ParseString("", s)
	require.NoError(t, err, s)
	require.Equal(t, cpExpected, cpParsed)
}

I also experimented with creating a recursive expression structure which keeps track of the nested brackets, but didn't get too far with that - that seems to be (at least partially) parsing the expression itself, which is something I wanted to avoid.

[purplefox]

Here's my attempt with a recursive expression structure:

func TestParseBrackets(t *testing.T) {

	type Expr struct {
		SubExpr    *Expr  `("(")* @@ (")")* |`
		ExprString string `@~(";"|"(") (@~(";"|"("))*`
	}

	lex := lexer.MustSimple([]lexer.SimpleRule{
		{"Comment", `(?:#|//)[^\n]*\n?`},
		{"String", `"(\\"|[^"])*"`},
		{"Pipe", `->`},
		{"Ident", `[a-zA-Z]\w*`},
		{"Number", `(?:\d*\.)?\d+`},
		{"Punct", `[-[!@#$%^&*()+_={}\|:;"'<,>.?/]|]`},
		{"Whitespace", `[ \t\n\r]+`},
	})

	parser, err := participle.Build[Expr](
		participle.Lexer(lex),
		participle.Elide("Comment", "Whitespace"),
		participle.UseLookahead(2),
	)
	require.NoError(t, err)

	cpExpected := &Expr{
		SubExpr:    nil,
		ExprString: "",
	}

	s := "some_func(ident1+x,ident2,ident3)"
	cpParsed, err := parser.ParseString("", s)
	require.NoError(t, err, s)
	require.Equal(t, cpExpected, cpParsed)
}

[alecthomas]

Yeah I don't thin there's any way around handling the (...) explicitly in the parser at the bare minimum. You should be able to ignore the structure of everything else though. Another option if all else fails is to implement the Parseable interface and manually handle the parsing for this node.

[purplefox]

Thanks for the tips!

I ended up implementing Parseable in the end. Basically counting the brackets and capturing the expressions into a []string. I'm sure it's possible to do this using some clever recursion using structs but I found it a bit simpler for my brain this way:

Here's the code if you're interested :)

func parseExpressions(lex *lexer.PeekingLexer) []string {
	var sb strings.Builder
	bracketCount := 0
	var exprs []string
outer:
	for {
		tok := lex.Peek()
		tokVal := tok.Value

		include := true
		switch tokVal {
		case "(":
			bracketCount++
		case ")":
			if bracketCount == 0 {
				exprs = append(exprs, sb.String())
				break outer
			}
			bracketCount--
		case ",":
			if bracketCount == 0 {
				exprs = append(exprs, sb.String())
				sb.Reset()
				include = false
			}
		default:
			// There are some operators, where we need to add a space around them in the resulting expression-
			// whitespace is removed so otherwise the token will be munged into surrounding tokens.
			// e.g. 'f3 as foo' would end up as "f3asfoo"
			// 's1 contains "foo"' would end up as s1contains"foo"
			if tokVal == "as" || tokVal == "contains" || tokVal == "matches" {
				sb.WriteString(" ")
				sb.WriteString(tokVal)
				sb.WriteString(" ")
				include = false
			}
		}
		if include {
			sb.WriteString(tokVal)
		}
		lex.Next()
	}
	return exprs
}