Re: Parsing Expression Grammar

All this thread on PEGs has convinced me of giving them a better look.
But something isn't quite clear; in his ICFP'03 paper, Bryan Ford
presented an unambiguous CFG that could not be recognized by his packrat
parser:


                                                    P -> x P x | x


(this CFG is especially interesting for it has a quadratic parsing time
complexity using an Earley parser).
      I have tried "P <- x P x / x" to see what would happen, and indeed,
the packrat parser is only able to parse sequences of 2^n - 1 "x"
symbols, n > 0.


This problem does not seem to be addressed in his POPL'04 paper; the
well-formed definition, if I understand it correctly, is only concerned
about left recursion and does not reject the above grammar.
      Now, strictly speaking, the language recognized by "P <- x P x / x"
*is* {x^(2^n - 1) | n > 0} (and that's quite an achievement in itself),
but I find it a bit misleading due to the CFG generative habits.
Looking at this, I also wonder whether there exist a PEG for the CFL
{ww^R | w \in {a,b}^*}.


All this to get to the conclusion that the immediate translation of a
CFG into a PEG by replacing "|" with "/" will not necesseraly yield the
expected result. Even the simple grammar "S -> Ac, A -> a| ab" should
not be translated "S <- Ac, A <- a / ab" but "S <- Ac, A <- ab / a",
otherwise input "abc" would not be accepted.


Russ Cox wrote:
  > 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 definitely an excellent property.


--
Regards,


      Sylvain

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