Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

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

by blokhead (Monsignor)
on Jun 06, 2006 at 20:02 UTC ( [id://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

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (3)
As of 2024-03-28 17:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found