3 ms·
Is it possible to parse left-recursive binary expressions with this? Like: expr = expr + expr expr = expr.method(args) I'm trying to write a parser u
by zaptheimpaler 8y ago
Is it possible to parse left-recursive binary expressions with this?
Like:
expr = expr + expr
expr = expr.method(args)
I'm trying to write a parser using a parser combinator library, and left-recursive things are turning out to be really tricky.
- panic 8y agoYeah, there's explicit support for expressions (left recursive and right recursive) using '.operators', which creates a group of operators at the same precedence level: expr = identifier : var .operators postfix '.' identifier '(' args ')' : method-call .operators infix left '+' : plus
- disconcision 8y agoHave you considered Generalized Parser Combinators? https://epsil.github.io/gll/ https://epsil.github.io/gll/
- curun1r 8y agoOne thing that helped me work around left-recursive restrictions is to stop thinking in terms of full expressions and to start thinking in terms of expressions that begin with terminals and then the suffixes that follow. This means that instead of an expr expanding to the left, it expands to the right. Let's say you're parsing: 1 + 5 + 7 You can choose to look at it as 7 plus the expression (1+5) or you can choose to look at it as the literal 1 with a +5 suffix that then has a +7 suffix. So in this simplified example, instead of defining: expr = literal | expr + expr you'd define expr as: expr = literal (+ expr)* That shift in how I thought about the language I was creating basically ended all the left-recursive problems I was having with my parser generator library.