I have just created a toy implementation that can parse your above grammar. It handles direct left recursion and I'm quite sure it also handles indirect left recursion: http://ioreader.com/code/C++/peg/
Let me know if you would like an explanation of how the algorithm works or if you find an error in it! Best Regards, Peter Goodman, http://ioreader.com 70 Winston Circle, Montreal, Quebec H9S 4X6 On Thu, Jun 3, 2010 at 11:47 PM, Francisco Mota <fmot...@gmail.com> wrote: > With a PEG, you can define it in non-recursive terms. As such: > sum <- term ((PLUS / MINUS) term) * > term <- value ((DIV / MUL / MOD) term) * > valua <- float-constant / int-constant / POPEN sum PCLOSE > You can impose associativity on top of this as you desire. > > On Thu, Jun 3, 2010 at 10:45 AM, Marcus Nordenstam <mar...@exoticmatter.com> > wrote: >> >> Hello, >> >> I just saw this mailing list, and figured if there's anywhere people >> may know the answer to this question, it would be here. >> >> I've been using the peg/leg parser generator tool to make C++ PEG >> parsers (I modified it slightly so that it would generate C++ code >> instead of ANSI C). >> >> I'm trying to write a simple expression grammar using PEG and, like >> everyone else I guess, have run into the left recursion issue. The >> primary issue I have is the simplest kind, e.g.: >> >> sum <- sum PLUS term >> / sum MINUS term >> / term >> >> term <- term DIV value >> / term MUL value >> / term MOD value >> / value >> >> value <- float-constant >> / int-constant >> / POPEN sum PCLOSE >> >> note that I've written terminals in all caps above. >> >> Now I can rewrite the grammar to eliminate the left-recursion, but >> doesn't that change the associativity of the parse? That would be >> quite bad since this grammar is primarily for mathematical >> expressions... >> >> So my question is: is anyone aware of an implementation (preferably in >> C or C++) which could parse the above grammar? Even if it's not a >> perfect tool, anything would be a better starting point for me than >> having to implement one of the left-recursion PEG papers from scratch >> :-) >> >> cheers >> Marcus >> >> _______________________________________________ >> PEG mailing list >> PEG@lists.csail.mit.edu >> https://lists.csail.mit.edu/mailman/listinfo/peg > > > _______________________________________________ > PEG mailing list > PEG@lists.csail.mit.edu > https://lists.csail.mit.edu/mailman/listinfo/peg > > _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
