Sérgio Medeiros and colleagues have published a paper that fleshes out their previously unpublished algorithm that I used for IronMeta‘s left-recursion handling, along with a very kind mention of IronMeta itself.
Tag: parsing
Parsing Expression Grammars and Left Recursion
Parsing Expression Grammars are a form of context-free grammars with ordered choice. This reduces ambiguity in the grammar and makes writing simple recursive-descent parsers (and parser generators) quite easy. With memoization, you can parse in linear time. The resulting parser is called a Packrat Parser.
The only problem is handling left-recursion. If you have grammar rules like this:
Expression = Expression "+" Term
| Term
your recursive-descent parser will recurse until it runs out of stack.
I just noticed a paper on detecting and handling left-recursion: Packrat Parsers can Handle Left Recursion. It’s a nifty technique, but it somewhat reduces the simplicity of the resulting program.
For a finger exercise a while ago I wrote a pretty basic packrat parser generator and used it to implement a C preprocessor. Source is here. When my supply of circular tuits increases I’ll have to look at implementing the stuff from the paper.