Convert PEG to BNF

Parsing expression grammars (PEGs) are unambiguous and have a superficially similar syntax to BNF, but include three important differences:

• The ordered choice operator e1 / e2 / e3.

• The and predicate &.

• The not operator !.

I have a few questions:

• Are the languages recognized by PEGs all context-free?

• If the answer to (1) is no, are there any expressive grammar formalisms guaranteed to produce only unambiguous grammars? In particular, would dropping & and ! yield only context-free grammars?

• If all PEGs are context-free, can they converted into an equivalent BNF via an algorithm?

The context is that I'd like to compute generating functions for a PEG library using the Chomsky–Schützenberger enumeration theorem. This seems to require a specification of the grammar in a standard form similar to BNF.

• Are the languages recognized by PEGs all context-free?

No, as is pointed out by Brian Ford in his 2004 paper introducing PEGs, from which is the following short quote:

Theorem: The class of PELs includes non-context-free languages.

Proof: The classic example language $a^nb^nc^n$ is not context-free,
but we can recognize it with a PEG $G = (\{A, B, D\}, \{a, b, c\}, R, D)$,
where R contains the following definitions:
$$A \leftarrow aAb / ε$$
$$B \leftarrow bBc / ε$$
$$D \leftarrow \&(A !b) a^∗ B !.$$

 

• If the answer to (1) is no, are there any expressive grammar formalisms guaranteed to produce only unambiguous grammars? In particular, would dropping $\&$ and $!$ yield only context-free grammars?

Even without $!$ (and therefore without $\&$, since it is formally defined in terms of $!$), you would still have to deal with the implicit complement hidden in the definition of ordered choice. I don't have a concrete example of ordered choice leading to a non-CFL, but I would try to find one by starting with two CFGs $L_1$ and $L_2$ whose difference is not a CFL and which can be converted to PEGs $P_1$ and $P_2$. Now, if $\mathbb{c}$ is some symbol not in either language, then the PEG $P_2 / P_1\mathbb{c}$ should recognize $L_2 \cup (L_1- L_2)\mathbb{c}$, which is not a CFL.

• If all PEGs are context-free, can they converted into an equivalent BNF via an algorithm?

If my conjecture above is correct, then this question is not applicable, but in any case there is no algorithm I know of to convert between PEGs and CFGs, and I believe that equivalence of a PEG and a CFG is undecidable. This fact complicates the proof procedure I propose above. :)

StackExchange Computer Science Q#70696, answer score: 6