<p>Is there a simple and intuitive explanation for the fact that the following parsing expression (where <code>S</code> is the starting symbol, <code>$</code> denotes end-of-string and <code>/</code> is ordered choice)</p>

<pre><code>S &lt;- X $
X &lt;- 'a' X 'a' / 'aa'
</code></pre>

<p>only matches strings of 'a's with a length that is a <strong>power</strong> of 2? (The same grammar interpreted as a CFG would match strings of 'a's with a length that is a <strong>multiple</strong> of two.)</p>

<p>And how can PEGs be suitable for the specification of computer languages if ordered choice makes the language defined by a PEG that unintuitive to understand?</p>

CC BY-SA 3.0
2011-05-22T20:42:53.927Z
Not that I don't agree with your point (I do), but what more do you expect as an answer than a proof that this grammar indeed recognizes $\{a^{2^n}\mid n\geq 1\}$?  On the other hand people have been using PEGs for programming languages (e.g. [Fortress](http://www.cs.cmu.edu/~aldrich/FOOL09/allen-abstract.html), [Java and C](http://www.romanredz.se/freesoft.htm)), and there are lots of [implementations](http://en.wikipedia.org/wiki/Parsing_expression_grammar#Implementations) around, so just like Turing-complete languages and other unsafe tools people do useful stuff with it nevertheless.
Sylvain
CC BY-SA 3.0
2011-05-22T21:05:19.673Z
PS: A similar question was answered by Christophe Grand on the [PEG mailing-list](http://www.mail-archive.com/peg@lists.csail.mit.edu/msg00110.html) a few years ago.
Sylvain
CC BY-SA 3.0
2011-05-25T10:02:27.103Z
There is also interesting discussion on LtU http://lambda-the-ultimate.org/node/3039#comment-44356 (good comment about ambiguity: "PEGs define away ambiguity, which means that you don't know where the real ambiguity is").
Vag
<fl.formal-languages><grammars><semantics><parsing>
The semantics of Parsing Expression Grammars
FloDo
# The semantics of Parsing Expression Grammars

(Asked by: username_0 on 2011-05-22)

Is there a simple and intuitive explanation for the fact that the following parsing expression (where S is the starting symbol, $ denotes end-of-string and / is ordered choice)
S <- X $
X <- 'a' X 'a' / 'aa'

only matches strings of 'a's with a length that is a power of 2? (The same grammar interpreted as a CFG would match strings of 'a's with a length that is a multiple of two.)
And how can PEGs be suitable for the specification of computer languages if ordered choice makes the language defined by a PEG that unintuitive to understand?

**Tags:** fl.formal-languages, grammars, semantics, parsing
> **Comments:**
> **username_1**: Not that I don't agree with your point (I do), but what more do you expect as an answer than a proof that this grammar indeed recognizes $\{a^{2^n}\mid n\geq 1\}$?  On the other hand people have been using PEGs for programming languages (e.g. [Fortress](http://www.cs.cmu.edu/~aldrich/FOOL09/allen-abstract.html), [Java and C](http://www.romanredz.se/freesoft.htm)), and there are lots of [implementations](http://en.wikipedia.org/wiki/Parsing_expression_grammar#Implementations) around, so just like Turing-complete languages and other unsafe tools people do useful stuff with it nevertheless.  
> **username_1**: PS: A similar question was answered by Christophe Grand on the [PEG mailing-list](http://www.mail-archive.com/peg@lists.csail.mit.edu/msg00110.html) a few years ago.  
> **username_2**: There is also interesting discussion on LtU http://lambda-the-ultimate.org/node/3039#comment-44356 (good comment about ambiguity: "PEGs define away ambiguity, which means that you don't know where the real ambiguity is").  

---

## 0 answers

