Discussion of parsing expression grammars and packrat parsing

PEG C/C++ parser generator with basic, direct left-recursion support

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

(Continue reading)

headers

Roman Redziejowski | 3 Jun 20:40

Re: PEG C/C++ parser generator with basic, direct left-recursion support

Hi,

I am doing this:

sum <- term ( ( PLUS / MINUS ) term )*

term <- value ( ( DIV / MUL / MOD) value )*

value <- etc.

and define order of applying operations in the semantics.
This is probably not politically correct, but works.

Have fun!
Roman

Marcus Nordenstam 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 <at> lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg

_______________________________________________
PEG mailing list
PEG <at> lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

headers

Francisco Mota | 4 Jun 05:47

Re: PEG C/C++ parser generator with basic, direct left-recursion support

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 <marcus <at> 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 <at> lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

_______________________________________________
PEG mailing list
PEG <at> lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

headers

Peter Goodman | 5 Jun 19:40

Re: PEG C/C++ parser generator with basic, direct left-recursion support

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 <fmota91 <at> 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 <marcus <at> 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 <at> lists.csail.mit.edu
>> https://lists.csail.mit.edu/mailman/listinfo/peg
>
>
> _______________________________________________
> PEG mailing list
> PEG <at> lists.csail.mit.edu
> https://lists.csail.mit.edu/mailman/listinfo/peg
>
>

headers

Dustin Voss | 3 Jul 03:57

Re: PEG C/C++ parser generator with basic, direct left-recursion support

I have PL/0 as a sample grammar for my Dylan PEG parser at
http://www.opendylan.org/cgi-bin/viewvc.cgi/trunk/libraries/utilities/peg-parser/. The
notation is straightforward. I can also send you the Dylan language grammar if you are interested, but it
is basically an adaptation of the LL(1) (or whatever) grammar, and is not optimized for efficient PEG
parsing. (I do not remember if I recreated the PL/0 grammar as PEG from the ground up, but...come on...PL/0
can be parsed by a coin-sorting machine.)

On Jun 3, 2010, at 8:45 AM, Marcus Nordenstam 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 <at> lists.csail.mit.edu
> https://lists.csail.mit.edu/mailman/listinfo/peg