<blockquote>
  <p>Despite their considerable expressive power, all <a href="https://en.wikipedia.org/wiki/Parsing_expression_grammar" rel="nofollow">PEG</a>s 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.  </p>
  
  <p>Bryan Ford, "<a href="http://www.brynosaurus.com/pub/lang/peg.pdf" rel="nofollow">Parsing Expression Grammars: A Recognition-Based Syntactic Foundation</a>", 2002.</p>
</blockquote>

<p>Is there a context-free language that is not expressible as a PEG?</p>

<hr>

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

CC BY-SA 3.0
2016-05-19T12:43:35.167Z
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
CC BY-SA 3.0
2016-05-19T12:51:55.767Z
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
CC BY-SA 3.0
2016-05-19T14:17:59.633Z
You are right - that appears to recognize the language.
Ulrik Rasmussen
CC BY-SA 3.0
2016-05-19T16:44:46.463Z
This is as far as I know an open problem.
Sylvain
CC BY-SA 3.0
2016-05-20T11:18:03.873Z
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](http://theory.stanford.edu/~virgi/cs367/papers/leecfg.pdf): "a fast, practical CFG parser would yield a fast, practical BMM [Boolean matrix multiplication] algorithm, which is not believed to exist".
Ulrik Rasmussen
<fl.formal-languages><open-problem><grammars><context-free><parsing>
Does PEG contain CFG?
Ulrik Rasmussen
# Does PEG contain CFG?

(Asked by: username_0 on 2016-05-19)

> Despite their considerable expressive power, all [PEG](https://en.wikipedia.org/wiki/Parsing_expression_grammar)s 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](http://www.brynosaurus.com/pub/lang/peg.pdf)", 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$.

**Tags:** fl.formal-languages, open-problem, grammars, context-free, parsing

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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$.  
> **username_0**: You are right - that appears to recognize the language.  
> **username_2**: This is as far as I know an open problem.  
> **username_0**: 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](http://theory.stanford.edu/~virgi/cs367/papers/leecfg.pdf): "a fast, practical CFG parser would yield a fast, practical BMM [Boolean matrix multiplication] algorithm, which is not believed to exist".  

---

## 0 answers

