Re: Parsing Expression Grammar

Russ Cox <rsc@swtch.com>
2 Sep 2005 14:20:00 -0400

          From comp.compilers

Related articles
Parsing Expression Grammar skjaero@gmail.com (2005-08-31)
Re: Parsing Expression Grammar lfinsto1@gwdg.de (Laurence Finston) (2005-09-02)
Re: Parsing Expression Grammar rsc@swtch.com (Russ Cox) (2005-09-02)
Re: Parsing Expression Grammar cfc@shell01.TheWorld.com (Chris F Clark) (2005-09-02)
Re: Parsing Expression Grammar pohjalai@cc.helsinki.fi (A Pietu Pohjalainen) (2005-09-02)
Re: Parsing Expression Grammar owong@castortech.com (Oliver Wong) (2005-09-03)
Re: Parsing Expression Grammar pohjalai@cc.helsinki.fi (A Pietu Pohjalainen) (2005-09-07)
Re: Parsing Expression Grammar paul@highpersoft.com (Paul Mann) (2005-09-07)
Re: Parsing Expression Grammar wclodius@lanl.gov (2005-09-10)
[25 later articles]
| List of all articles for this month |

From: Russ Cox <rsc@swtch.com>
Newsgroups: comp.compilers
Date: 2 Sep 2005 14:20:00 -0400
Organization: Compilers Central
References: 05-08-115
Keywords: parse

> Does anybody have working examples of a Parsing Expression Grammar
> (http://en.wikipedia.org/wiki/Parsing_expression_grammar) for a Java
> like language? I know the Rats! package generates parsers based on
> PEG, but since Rats! is GPL`d I can`t use it for commercial use. It
> would help to actually see the set of needed production rules for the
> Java language as a base for designing a new language.


The PEG for Java that Bryan Ford used in his thesis is at
http://pdos.csail.mit.edu/~baford/packrat/thesis/java/Java.pappy.


> The reason for this is that I have a working VM implementation that I
> need to test feed with bytecode samples, so it makes sense to start
> bringing in the compiler step. As opposed to LL and RL parsers, PEG
> parsers seem both more efficient AND unambiguous and handle context
> free languages. I was wondering if Java, apart from the usual dangling
> else conflicts, has been frame already in a PEG?


I am unconvinced that PEG parsers are much better than LALR(1) parsers
on efficiency grounds. They're linear-time, but the constant is
non-trivial. They're unambiguous, but I think it's just as difficult
to write what you mean as it is in grammars with ambiguity (and at
least the latter can tell you that there's a problem!). One thing
PEGs definitely do well (and this is at least one reason why Bryan
worked on them) is that they are composable: you can take any terminal
symbol in a PEG, replace it with a non-terminal with its own PEG
grammar, and you get a bigger, but still valid, PEG grammar. This is
not true of LALR(1) and (most of?) its ilk.


Russ


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.