Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fixing left and mutual recursions in grammars

brightprogrammer.in

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Fixing left and mutual recursions in grammars

#21

Post by nsajko »

Rusky wrote: post #20
earleybird wrote: post #10

Use an Earley parser. A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. The worst case ambiguous I've worked with is UBDA (Earley, 1970). UBDA produces the equivalent of all the permutations of a binary tree - which is Catalan(n). If you generate all the combinations as you parse it won't complete before the heat death of the universe for fairly short s…

> A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. It's not linear for all unambiguous grammars- only deterministic grammars, which can also be parsed with something faster like LR or even hand-written Pratt. (An example of an unambiguous but nondeterministic grammar is this one for palindromes, which Earley parses in quadratic time: P -> 0 P 0 | 1 P 1…

Pratt's method only targets the operator precedence languages, not the DCFL. So much less powerful than LR parsing.

Re: Fixing left and mutual recursions in grammars

#22

Post by PaulHoule »

mrkeen wrote: post #2

Imo this missed the punchline. I banged my head on the table for days trying to fix a left-recursive grammar, just by moving bits around and hoping. The key is precedence ! Parse loose expressions first (plus, minus, etc), these loose expressions can in turn call into tighter expressions (mul, div), and so on down to parentheses. Parentheses do form a loop - that is, they call all the way back to the top - but at lon…

I like a lot of things about PEG but the way they support precedence is for the birds. I'd really love to see a PEG toolkit built as if developer experience matters but the problem with parser generators is that anybody who can write a parsed generator understands how to work around the problems with parser generators -- so we don't get parser generators that fit the needs of developers who don't know a lot of CS theory.

Re: Fixing left and mutual recursions in grammars

#23

Post by froh »

earleybird wrote: post #10

Use an Earley parser. A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. The worst case ambiguous I've worked with is UBDA (Earley, 1970). UBDA produces the equivalent of all the permutations of a binary tree - which is Catalan(n). If you generate all the combinations as you parse it won't complete before the heat death of the universe for fairly short s…

tell me more about your use name :-)

Re: Fixing left and mutual recursions in grammars

#24

Post by mrkeen »

tgv wrote: post #11
mrkeen wrote: post #6

Earlier quoted context omitted.

I appreciate the dismissal, but I stand by what I said. I used to think 'precedence was just for removing ambiguity', so I didn't pay attention to it. Then I discovered it was the key to structuring grammars to avoid left recursion, and everything changed for me. I've used it successfully in the past and I'll do so in the future.

I think you're not using the word precedence properly. It seems as if you're trying to explicitly instruct a top-down parser. E.g., the precedence in these two grammars (for simple arithmetic expressions) is identical S -> F | S + F F -> T | F * T T -> 0 | 1 | 2 | ... S -> F | F + S F -> T | T * F T -> 0 | 1 | 2 | ... but one recurses on the left side, and the other on the right.

> It seems as if you're trying to explicitly instruct a top-down parser.

My mistake, that didn't even occur to me! I only ever use parser combinators so I just read grammars as if they were the code, and vice-versa.

e.g. you could implement the grammar on the upper line as the code on the lower line:

  S -> F  |   F          +     S
  s  = f  (f >> char '+' >> s)
The two grammars you posted both 'look good' just by eyeballing them, neither needs 'fixing' (per the article title). They have identical precedence and identical don't-recurse-infinitely properties.

Re: Fixing left and mutual recursions in grammars

#25

Post by mrkeen »

brightprogramer wrote: post #7
mrkeen wrote: post #6

Earlier quoted context omitted.

I appreciate the dismissal, but I stand by what I said. I used to think 'precedence was just for removing ambiguity', so I didn't pay attention to it. Then I discovered it was the key to structuring grammars to avoid left recursion, and everything changed for me. I've used it successfully in the past and I'll do so in the future.

I see, I'd like to give it a try then. I'll try adding some precedence here. I don't know how, though. This calls for some reading...

I put it off as well, I figured precedence and associativity is something I'd learn later after I figured out how to stop my **ing grammars from looping forever. But it was right there in front of me!

When I looked at someone else's working code, they'd laid it out so that each layer could only call into the same layer or the next layer down:

  parseSum     = ...
  parseProduct = ...
  parseTerm    = ...
which should eliminate the mutual-infinite-recursion case, since the control flow can't ever go upward. And it didn't look like a co-incidence that they'd laid the code out from low-precedence mathematical operators to high-precedence mathematical operators.

The code I ended up using is something like

  parseSum = parseProduct then many('+' then parseProduct) // where 'many' means 0 or more.
But if you don't have 'many' in your grammar syntax, it looks like this would work instead:

  parseSum = parseProduct + parseSum
But the above is wrong for two reasons. Firstly, you need to have a '+', so there's no way to parse an expression that doesn't have a '+' in it. But it also right-associates and you end up with (1+(2+(3+4))) which is probably fine for addition (give or take some C-int-overflow-rules), but breaks division. I think you can fix both by putting the terminal case first, and then left-recursing after that:

  parseSum = parseProduct | parseSum + parseProduct
Then there's only one remaining issue to deal with - what do you do when you actually want to loop? Sums can contain products, and products can contain sums (as long as they're in parens.) Well, parens bind tighter than any other precedence, so they go straight to the bottom:

  parseSum     = ...
  parseProduct = ...
  parseTerm    = ...
  parseParens  = '(' parseSum ')'
So we've broken the no-upward-control-flow rule, but is it an infinite loop? The only case where control flow can go upward is if you consume a '(' first, so I say no.

Re: Fixing left and mutual recursions in grammars

#26

Post by Cadwhisker »

mrkeen wrote: post #2

Imo this missed the punchline. I banged my head on the table for days trying to fix a left-recursive grammar, just by moving bits around and hoping. The key is precedence ! Parse loose expressions first (plus, minus, etc), these loose expressions can in turn call into tighter expressions (mul, div), and so on down to parentheses. Parentheses do form a loop - that is, they call all the way back to the top - but at lon…

Debugging a complex PEG is a nightmarish task. I use various tools, but I couldn't find anything out there that will let you set a breakpoint in a file that's being parsed and let you explore the parsing state.

The most useful tools I found were adjacent to the cpp-peglib library: https://github.com/yhirose/cpp-peglib

This comes with a PEG playground: https://yhirose.github.io/cpp-peglib/

I really liked pegdebug: https://mqnc.github.io/pegdebug/

With sample output here: https://mqnc.github.io/pegdebug/example/output.html

pegdebug is nice for small sets of data, but it rapidly gets swamped by anything over about 50 lines.

If anyone has other suggestions for debugging PEGs, please reply and let me know,.

Re: Fixing left and mutual recursions in grammars

#27

Post by Rusky »

nsajko wrote: post #21
Rusky wrote: post #20

Earlier quoted context omitted.

> A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. It's not linear for all unambiguous grammars- only deterministic grammars, which can also be parsed with something faster like LR or even hand-written Pratt. (An example of an unambiguous but nondeterministic grammar is this one for palindromes, which Earley parses in quadratic time: P -> 0 P 0 | 1 P 1…

Pratt's method only targets the operator precedence languages, not the DCFL. So much less powerful than LR parsing.

That's true as Pratt described it. I mentioned it because it's a good example of the general idea of extending recursive descent to handle more deterministic grammars than vanilla LL.

Re: Fixing left and mutual recursions in grammars

#28

Post by earleybird »

Rusky wrote: post #20
earleybird wrote: post #10

Use an Earley parser. A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. The worst case ambiguous I've worked with is UBDA (Earley, 1970). UBDA produces the equivalent of all the permutations of a binary tree - which is Catalan(n). If you generate all the combinations as you parse it won't complete before the heat death of the universe for fairly short s…

> A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. It's not linear for all unambiguous grammars- only deterministic grammars, which can also be parsed with something faster like LR or even hand-written Pratt. (An example of an unambiguous but nondeterministic grammar is this one for palindromes, which Earley parses in quadratic time: P -> 0 P 0 | 1 P 1…

Yes, you are correct. Nondeterministic grammars are not linear but quadratic. In the case of your palindrome example (thanks btw, added to my grimoire of grammars) I believe the quadratic is: (3n^2 + 6n)/4 (I wish HN did MathJax)

I need to do a bit more digging in to the distinction between ambiguous and nondeterministic.

When implementing parsers I enjoy the directness afforded by an Earley parser. No rejigging the grammar to suit LL, LR etc. No gotcha's with PEGs choice operator, etc.

Most grammars I end up using for practical applications are linear - so far, quadratic has been a spectre from afar. :-)

Re: Fixing left and mutual recursions in grammars

#29

Post by kazinator »

If you are using a shift-reduce parser, you may have to fix right recursion instead.

If you have a right recursive construct, the parser stack usage will be proportional to the length of the instances of the construct. That can be a problem.

For instance:

   stuff : /* empty */
         | item stuff
         ;
If you have 10,000 items in a sequence of stuff, they all get pushed onto the stack which is then popped by a long cascade of rightmost reductions.

You have to refactor for left recursion.

I ran into this when parsing Lisp this way. Lisp lists are right recursive; they are naturally constructed from the right end, by consing onto the front. When you write the obvious parser rules, the list does not start being constructed until the closing parenthesis is seen, and the cascade of reductions pulls it out of the stack.

This is not a problem like runaway left recursion; it is an insidious bug that you won't even notice with small test cases.

Switching to left recursion means that you have to construct the list left-to-right somehow. Either the rules maintain a tail pointer somehow, or the list is consed up in reverse and then destructively reversed. A minor complication is support for the consing dot.

Re: Fixing left and mutual recursions in grammars

#30

Post by klik99 »

earleybird wrote: post #10

Use an Earley parser. A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. The worst case ambiguous I've worked with is UBDA (Earley, 1970). UBDA produces the equivalent of all the permutations of a binary tree - which is Catalan(n). If you generate all the combinations as you parse it won't complete before the heat death of the universe for fairly short s…

I came into comments to post this but I guess the earley bird gets the worm.

I have an Earley parser I’m very happy with which is in a project I’m going to open source soon, it’s nice to have a parser where you just don’t have to think about all those edge cases

Post reply on HN