Fixing left and mutual recursions in grammars
brightprogrammer.in
Fixing left and mutual recursions in grammars
1–10 of 31 posts
Re: Fixing left and mutual recursions in grammars
#2Imo 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 long as the parser makes progress i.e. can only proceed if it moves past a '(', no infinite loops and you're golden.
Re: Fixing left and mutual recursions in grammars
#3Imo 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…
Precedence is more of a way to remove ambiguity from grammar. Grammars are just hard to figure out in one go.
Re: Fixing left and mutual recursions in grammars
#4An 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).
Re: Fixing left and mutual recursions in grammars
#5An 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 ).
Use mermaid js : https://mermaid.js.org/syntax/stateDiagram.html
Re: Fixing left and mutual recursions in grammars
#6Imo 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…
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.
Re: Fixing left and mutual recursions in grammars
#7Earlier 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 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...
Re: Fixing left and mutual recursions in grammars
#8[deleted]
Re: Fixing left and mutual recursions in grammars
#9Imo 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 think you're semi-right here, but the term precedence is ambiguous.
Left recursion causes rules to be ambiguous. In ` | a`, it's always ambiguous if the input has ended. Thus the data structure that would be traversed can be a circular graph. In ` := a | , S := ε', the rules are unambiguous and the data structure that is traversed has the shape of a tree.
You get precedence rules by defining the shape of this tree, thus which rules will be visited before which.
However it doesn't have to be strict precedence. Some rules can have an ambiguous order as long as the execution still follows the shape of a tree.
For example, in my simple rule above, it doesn't matter if you visit the ε rule or the other rule first in your implementation (although it's less efficient to visit ε first).
So, I think precedence is a side-effect of doing this transformation.
Re: Fixing left and mutual recursions in grammars
#10Use 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 strings.