On Tue, Apr 28, 2009 at 10:10:26AM +0200, Alexander Bernauer wrote:
> 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---
I tried, but I can't see a problem with this; I think you're
correct.
Anybody else?
-Robin
--
They say: "The first AIs will be built by the military as weapons."
And I'm thinking: "Does it even occur to you to try for something
other than the default outcome?" See http://shrunklink.com/cdiz
http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
