C++ PEG library with left recursion support
Peter Goodman <peter.goodman <at> gmail.com>
2011-01-03 22:38:11 GMT
Over the holidays I have been working on a very simple C++ PEG
implementation. So far, it looks like I have properly handled left
recursion, even in light of right recursion. In fact, the parser
allows one to choose the associativity of right recursive rules in the
presence of left recursion. Here is an example calculator that I have
made using the library: http://codepad.org/YAj17QGg
The goals of the parser include:
- proper support for left recursion, especially in the presence of
- a "dynamic" feel to the definition of grammars (unfortunately,
getting this goal means doing some annoying stuff like T<'x'>() for a
terminal and E<>() for epsilon).
- simplicity - this is more of a proof of concept rather than being
meant for widespread use. As such, I make the assumption that the
token stream is actually a pre-allocated array that can be indexed and
that the length of the token stream is known in advance of parsing.
Soon, I hope to make a write-up about how I supported left recursion
and publicly release the code.
Things of note:
- I have not done any analysis on the runtime performance of my
approach with left recursion, but I expect it to be worst-case O(n^2)
where n is the length of the token stream.
Happy new year,
70 Winston Circle,