7
$\begingroup$

Is there a simple and intuitive explanation for the fact that the following parsing expression (where S is the starting symbol, $ denotes end-of-string and / is ordered choice)

S <- X $
X <- 'a' X 'a' / 'aa'

only matches strings of 'a's with a length that is a power of 2? (The same grammar interpreted as a CFG would match strings of 'a's with a length that is a multiple of two.)

And how can PEGs be suitable for the specification of computer languages if ordered choice makes the language defined by a PEG that unintuitive to understand?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Not that I don't agree with your point (I do), but what more do you expect as an answer than a proof that this grammar indeed recognizes $\{a^{2^n}\mid n\geq 1\}$? On the other hand people have been using PEGs for programming languages (e.g. Fortress, Java and C), and there are lots of implementations around, so just like Turing-complete languages and other unsafe tools people do useful stuff with it nevertheless. $\endgroup$
    – Sylvain
    Commented May 22, 2011 at 20:42
  • 3
    $\begingroup$ PS: A similar question was answered by Christophe Grand on the PEG mailing-list a few years ago. $\endgroup$
    – Sylvain
    Commented May 22, 2011 at 21:05
  • $\begingroup$ There is also interesting discussion on LtU lambda-the-ultimate.org/node/3039#comment-44356 (good comment about ambiguity: "PEGs define away ambiguity, which means that you don't know where the real ambiguity is"). $\endgroup$
    – Vag
    Commented May 25, 2011 at 10:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.