# The semantics of Parsing Expression Grammars

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?

• 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. – Sylvain May 22 '11 at 20:42
• PS: A similar question was answered by Christophe Grand on the PEG mailing-list a few years ago. – Sylvain May 22 '11 at 21:05
• 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"). – Vag May 25 '11 at 10:02