Re: implementation for Parsing Expression Grammar?

On Sun, 11 May 2008 09:36:08 -0700 (PDT), "xahlee@[EMAIL PROTECTED]
"
<xahlee@[EMAIL PROTECTED]
> wrote:

> George Neuner wrote:
>«What's your point?  The limitations of regular expressions are well
>known.»
>
>Hi George,
>
>Please see:
> http://xahlee.org/cmaci/notation/pattern_matching_vs_pattern_spec.html
>
>At the bottom, i gave a account of the origin of my realization.
>You'll see how it ties to formal systems (e.g. automatic theorem
>proving) as well as a lisp source code reformatter.
>
>  Xah
>  xah@[EMAIL PROTECTED]
>? http://xahlee.org/

Ok.  But I think PEG is overkill.

PEG is predicated LL(k) where k is potentially infinite and where
backtracking occurs on failure.  In power it is roughly equivalent to
GLR in that it handles unambiguous grammars that have long ambiguous
prefixes.  But it is not well understood and there are very few PEG
tools.  In particular existing tools can't always tell you whether
your grammar really is ambiguous rather than just containing ambiguous
prefixes.  PEG grammars have to be unambiguous in totality but any
particular substring can approach human language complexity.

Neither LL(k) for fixed k or LR has that problem.  LR(1) is sufficient
to describe almost all existing programming languages and most
existing data description languages are LL.  Any of the LR or LL
parser tools are likely all you'll need to design a useful language.


If you really want to play with PEG-like grammars, ANTLR v3 offers
LL(*) which is similar.  I suggest you read Terence Parr's thesis
which explains his approach to predicated LL(k) and his Powerpoint
slides on the LL(*) method:

http://www.antlr.org/papers/parr.phd.thesis.pdf
http://www.antlr.org/papers/Coverity-LL-star.ppt

Parr claims LL(*) is power equivalent to PEG and GLR, but more
practical to use.  I haven't seen independent review of the method and
I haven't tried it (I've designed several programming and data
languages but never needed anything approaching PEG complexity).

George
--
for email reply remove "/" from address