Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re: Operator Associativity and Eliminating Left-Recursion in Parse::RecDescent

by blokhead (Monsignor)
on Jun 06, 2006 at 20:02 UTC ( #553902=note: print w/ replies, xml ) Need Help??


in reply to Operator Associativity and Eliminating Left-Recursion in Parse::RecDescent

ikegami++ .. I recently tried to get a sane parse tree from a grammar which (like your example scenario) was the result of left-recursion elimination on left-associative grammar rules. I found it to be highly nontrivial.

I was at least aware of the first two approaches you presented (though it would have taken me a long time to get approach #3a working), but it had not occured to me to use an accumulation paradigm like you do in #3c. This is a standard trick in making recursive functions tail-recursive (pass forward the intermediate results as an argument, instead of passing back the intermediate results as a return value).

I probably wouldn't have thought to apply this trick to parsing, though. If you're a theorist like me and view parsing through the lens of formal languages, then passing information from parent rule to child rule is not a natural approach. Good thing there are still practitioners out there ;)

blokhead


Comment on Re: Operator Associativity and Eliminating Left-Recursion in Parse::RecDescent

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://553902]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (8)
As of 2014-07-29 22:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (229 votes), past polls