# Does PEG contain CFG?

Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable language classes, although a formal proof that there are context-free languages not expressible via PEGs appears surprisingly elusive.

Bryan Ford, "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation", 2002.

Is there a context-free language that is not expressible as a PEG?

As pointed out by Emil, my proposed language $a^n a^* b^n$ does not work. It can be expressed as the PEG $S \to a S b / a S / \varepsilon$.

• Ford also writes less ambiguously “it is not even proven yet that CFLs exist that cannot be recognized by a PEG”, so this would appear to be an open problem. – Emil Jeřábek May 19 '16 at 12:43
• I didn't read the paper closely, but if I understand the definition correctly, your language is recognized by the PEG $S\to aSb/aS/\epsilon$. – Emil Jeřábek May 19 '16 at 12:51
• You are right - that appears to recognize the language. – Ulrik Rasmussen May 19 '16 at 14:17
• This is as far as I know an open problem. – Sylvain May 19 '16 at 16:44
• By the way, the answer to the question is most probably that PEG does not contain CFG. PEGs can be recognized in linear time, but as shown by Lee: "a fast, practical CFG parser would yield a fast, practical BMM [Boolean matrix multiplication] algorithm, which is not believed to exist". – Ulrik Rasmussen May 20 '16 at 11:18