6
$\begingroup$

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$.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek supports Monica May 19 '16 at 12:43
  • 2
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek supports Monica May 19 '16 at 12:51
  • $\begingroup$ You are right - that appears to recognize the language. $\endgroup$ – Ulrik Rasmussen May 19 '16 at 14:17
  • 3
    $\begingroup$ This is as far as I know an open problem. $\endgroup$ – Sylvain May 19 '16 at 16:44
  • 2
    $\begingroup$ 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". $\endgroup$ – Ulrik Rasmussen May 20 '16 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.