Re: Parsing Expression Grammar

> 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

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