Re: Parsing Expression Grammar

Russ Cox <>
2 Sep 2005 14:20:00 -0400

          From comp.compilers

Related articles
Parsing Expression Grammar (2005-08-31)
Re: Parsing Expression Grammar (Laurence Finston) (2005-09-02)
Re: Parsing Expression Grammar (Russ Cox) (2005-09-02)
Re: Parsing Expression Grammar (Chris F Clark) (2005-09-02)
Re: Parsing Expression Grammar (A Pietu Pohjalainen) (2005-09-02)
Re: Parsing Expression Grammar (Oliver Wong) (2005-09-03)
Re: Parsing Expression Grammar (A Pietu Pohjalainen) (2005-09-07)
Re: Parsing Expression Grammar (Paul Mann) (2005-09-07)
Re: Parsing Expression Grammar (2005-09-10)
[25 later articles]
| List of all articles for this month |

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

> Does anybody have working examples of a 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

> 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.


Post a followup to this message

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