- 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. :)