Re: Parsing Expression Grammar

Almost any grammar suitable to ANTLR (, PCCTS, or JavaCC) will be a
Parsing Expression Grammar, because any LL(1) grammar is also a
Parsing Expression Grammar (modulo some slight syntax issues). So, if
you want a "PEG" for Java. Find a Java grammar for ANTLR (or PCCTS)
and change the | operators into / operators and you are done.


A pure (unpredicated) LL(1) grammar, is simply a PEG where the
predicate operators are not used (and the alternatives are separated
by | rather than /).


In addition, any recursive descent parser generated from an LL(1)
grammar will be (atleast) as efficient as the corresponding packrat
parser, because there is no backtracking involved in a "pure" LL(1)
grammar and the memoization of a packrat parser is only to preserve
linear run time's in the presence of backtracking. thus, a packrat
parser and a recursive descent LL(1) parser do exactly the same steps
(omitting the memoization, which has no benefit) for an LL(1) grammar.


Moreover, the benefits listed for PEGs (unambiguity and linear time
requirements) are shared by LL(1) grammars.


Now, if you have an LR grammar for Java, say one for CUP or Yacc++,
there is more to do, because LR grammars are not subsets of PEGs.
However, almost all LL(1) grammars are LR(1) also. Thus, if you have
an LL(1) grammar, you can use your choice of parser generators: LL,
LR, or PEG.


There are also PEGs that are not LL grammars, but you don't need that
to parse Java. Therefore, the PEG technology is not a loss. In fact,
it is a good solution to some problems. Moreover, the algorithm for
processing PEGs is useful and provides some insight that wouldn't have
been seen if the technology hadn't been developed.


However, it is not necessary to rewrite all our grammars into PEG
form, LL(1) is perfectly adequate. The interesting case might come
from languages which don't have an LL(1) grammar (e.g. C++). For
them, it might be useful to have a PEG.


But, as a potential language designer, you need to think long and hard
about why you want to create a language which has no LL(1) grammar.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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