June 15, 2004
Sample invalid parse
This is a sample of an invalid parse using the bug pointed out in the sample derivation. This is a parse of the string abecc, which is not licensed by the grammar and so it should not be possible to derive it.
1) [b,1,-1,-1,2] (A6)
2) [S,-1,-1,-1,-1] (A5)
3) [S,1,2,-1,-1] (I2,1,2)
4) [Y,-1,-1,-1,-1] (A5)
5) [Y,1,2,-1,-1] (I13,3,4)
6) [c,3,-1,-1,4] (A6)
7) [S,1,2,3,4] (I4,5,6)
8) [Y,1,2,3,4] (I13,7,4) <--- This is the faulty step
9) [c,4,-1,-1,5] (A6)
10) [S,1,2,3,5] (I3,8,9)
11) [X,-1,-1,-1,-1] (A5)
12) [X,1,2,3,5] (I13,10,11)
13) [a,0,-1,-1,1] (A6)
14) [S,0,2,3,5] (I1,13,12)
15) [e,2,-1,-1,3] (A6)
16) [S,2,-1,-1,3] (I5,15)
17) [S,0,-1,-1,5] (I6,14,16)
This derivation is analagous to the parse tree depicted below, which is invalid because the local tree circled in red does not exist in the grammar.
