Hi I think I found two bugs in the PEG paper [1]. I tried to contact Bryan but he is not responding. Maybe someone here can either show me what I am doing wrong or confirm the bugs. I searched the mailing list archives and didn't find anything. Still I am pretty sure that something is wrong.
First, section 3.4 defines a PEG for the context free language
L = {a^n b^n c^n | n > 0 } like this:
---8<---
A <- aAb/e
B <- bBc/e
D <- &(A !b) a* B !.
--->8---
(e means epsilon)
But this grammar matches the word "aabc" which is not an element of L.
The idea of the grammar is that the predicate ensures that there are as
many 'a's as 'b's without consuming any. 'a*' then consumes all counted
'a's and lets 'B' consume the same amount of 'b's and 'c's afterwards.
Given the word "aabc" though, 'A' matches the empty string and 'b!'
matches the first 'a', thus the predicate matches. Then 'a*' consumes
both 'a's which were not counted this time. In the end 'B' matches 'bc'.
I think the grammar should be fixed like
---8<---
A <- aAb/e
B <- bBc/e
D <- &(Ac) a* B !.
--->8---
Second, in section 4.2.1 I think there is bug in the definition
of the helper function f. The second theorem states that "all sequence
[...] expressions [...] contain only nonterminals as their
subexpressions [...]"
As a counter-example assume the following grammar
---8<---
V_T = {a,b}
V_N = {S}
e_S = S
R = {(S, a/b)}
--->8---
According to the definitions of the stage 1 grammar we need to compute
'f(a/b)' which is by rule 3 'A / !A f(b)' with 'A <- f(a)'. By rule 1
'f(a) = a' and 'f(b) = b' which results in the rule set
R_1 = {(A, a), (S, A/!A b), ...}
Now the rule for S contains a sequence with a terminal, which
contradicts the theorem.
As far as I can see rule 3 should be defined as
'f(e_1/e_2) = A / !A B' with 'A <- f(e_1)' and 'B <- f(e_2)'
[1] Parsing Expression Grammars: A Recognition-Based Syntactic Foundation
(PDF). POPL, January 2004,
http://pdos.csail.mit.edu/~baford/packrat/popl04/peg-popl04.pdf
regards
--
Alexander Bernauer
Research Group for Distributed Systems
Department of Computer Science
ETH Zürich, Switzerland
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
