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

11–20 of 31 posts

Re: Fixing left and mutual recursions in grammars

#11

Post by tgv »

mrkeen wrote: post #6
brightprogramer wrote: post #3

Earlier quoted context omitted.

Precedence is more of a way to remove ambiguity from grammar. Grammars are just hard to figure out in one go.

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.

Re: Fixing left and mutual recursions in grammars

#12

Post by Rochus »

tempodox wrote: post #4

An interesting and worthwhile topic. This kind of problem pops up regularly. Those diagrams are really handy, does anyone know how they were made? I'm always looking for alternatives / companions to the Railroad Diagram Generator ( https://rr.red-dove.com/ui ).

These diagrams indeed look good. But actually I never use those for parser construction, but consider EBNF more useful, especially also when analyzing and correcting a grammar. I was surprised that there was no decent editor to develop grammars which has built-in support to find and show issues in the grammar like left recursion or ambiguities (at least I didn't find one), so I implemented my own: https://github.com/rochus-keller/ebnfstudio/. I used it in all of my programming language projects to create LL(n) versions including some pretty complicated grammars like Simula or Verilog.

Re: Fixing left and mutual recursions in grammars

#13

Post by aardshark »

tempodox wrote: post #4

An interesting and worthwhile topic. This kind of problem pops up regularly. Those diagrams are really handy, does anyone know how they were made? I'm always looking for alternatives / companions to the Railroad Diagram Generator ( https://rr.red-dove.com/ui ).

draw.io can do similar diagramming. You can generate diagrams programmatically through their CSV format.

Unfortunately documentation for using it programmatically is a bit lacking, but you can for example host a CSV somewhere and use their editor to load it. It's all client side so will automatically update.

Re: Fixing left and mutual recursions in grammars

#14

Post by upghost »

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…

Thanks, I've been looking for this for a long time!

Re: Fixing left and mutual recursions in grammars

#16

Post by werdnapk »

tempodox wrote: post #4

An interesting and worthwhile topic. This kind of problem pops up regularly. Those diagrams are really handy, does anyone know how they were made? I'm always looking for alternatives / companions to the Railroad Diagram Generator ( https://rr.red-dove.com/ui ).

Isn't Graphviz [1] the standard tool for this?

[1] https://graphviz.org/

Re: Fixing left and mutual recursions in grammars

#17

Post by fjfaase »

It is possible to write a (top-down) parser that can deal with the left recursion without having to rewrite the grammar itself. Simply split the left recursive ones and not. Then first try to accept a non-left recursive rule and if that succeeds, use the result to try to parse any of the left recursive ones. (If I am not mistaken, this also works for mutual recursion of left recursive rules.) I have implemented this several times.

Re: Fixing left and mutual recursions in grammars

#18

Post by Rusky »

fjfaase wrote: post #17

It is possible to write a (top-down) parser that can deal with the left recursion without having to rewrite the grammar itself. Simply split the left recursive ones and not. Then first try to accept a non-left recursive rule and if that succeeds, use the result to try to parse any of the left recursive ones. (If I am not mistaken, this also works for mutual recursion of left recursive rules.) I have implemented this…

Exactly. This is essentially converting the parser to bottom-up just for these rules. It's how Pratt parsing/precedence climbing works.

I wrote this post on the connection: https://www.abubalay.com/blog/2021/12/31/lr-control-flow

Re: Fixing left and mutual recursions in grammars

#20

Post by Rusky »

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 | ε)

Post reply on HN