Question: How to create a recursive grouping parser

[aacebedo]

Hi there,

I am playing with participle (which I found amazing) and I am searching the best solution for a small parsing problem.
I am trying to create a parser able to process in-depth grouped expressions, for instance:

a
a+b
a+b+c
a+(b+c)
(a+(b+c))+d
etc...

I created a simple grammar by considering a structure like this:
Expressions are composed of operands and operators, and an operand can be an expression. I ended with the following working code:

type KeySpecifier struct {
	DeviceID string `(DeviceIDStart @DeviceName DeviceIDEnd)?`
	Key      string `@NormalKey|@ModifierKey`
}

type Operand struct {
	Expr *Expr         `"("@@")"`
	Key  *KeySpecifier `|@@`
}

type Expr struct {
	Left  Operand   `@@`
	Op    *Operator `(@@`
	Right *Expr     ` @@)?`
}

type Operator struct {
	And *string `  @And`
	Or  *string `| @Or`
}

type KeyCombination struct {
	//Keys []*KeySpecifier `@@(Operator@@)?`
	Keys Expr `@@`
}

type Parser struct{}

func NewParser() *Parser {
	return &Parser{}
}

func (p *Parser) Parse(toParse string) (res *KeyCombination, err error) {
	def := lexer.MustStateful(lexer.Rules{
		"Root": {
			{`Whitespace`, `\s+`, nil},
			{"GroupStart", `\(`, nil},
			{"GroupEnd", `\)`, nil},
			{"DeviceIDStart", `\[`, lexer.Push("DeviceID")},
			lexer.Include("Keys"),
			lexer.Include("Operators"),
		},
		"DeviceID": {
			{"DeviceName", `[[[:alpha:]\d]+`, nil},
			{"DeviceIDEnd", `\]`, lexer.Pop()},
		},
		"Keys": {
			{"ModifierKey", `[Aa]lt([Gg]r)?|[Cc]trl|[Ss]hift`, nil},
			{"Word", `[[[:alpha:]\d]{2,}`, nil},
			{"NormalKey", `[[[:alpha:]\d]{1}`, nil},
		},
		"Operators": {
			{"And", `\+`, nil},
			{"Or", `\|`, nil},
		},
	})

	parser := participle.MustBuild(&KeyCombination{}, participle.Lexer(def), participle.Elide("Whitespace", "Word"))
	res = &KeyCombination{}
	err = parser.ParseString("", toParse, res)

	if err != nil {
		res = nil
	}
	return
}

However I don't like the unbalanced Expr struct (With Left AND Right not being operands. It does not succeed to parse if I change the following to balance the structure:

type Operand struct {
	Expr *Expr         `"@@|("@@")"`
	Key  *KeySpecifier `|@@`
}

type Expr struct {
	Left  Operand   `@@`
	Op    *Operator `(@@`
	Right *Operand  ` @@)?`
}

Any ideas to solve this ?

[alecthomas]

Hello!

I'm glad you're enjoying Participle :)

I suspect part of the confusion is due to your use of a stateful lexer. You almost certainly don't need one for this grammar, a basic lexer and parser can handle this.

Have you checked out the _examples folder? The expr and expr2 folders in particular would be good places to start.

[alecthomas]

simpleexpr might be the best example.

[aacebedo]

Thank you. Took a look to the examples, those will be very helpful !