Hello, 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 right recursion - 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, Peter Goodman, http://ioreader.com 70 Winston Circle, Montreal, Quebec H9S 4X6 _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
