Derivation of abaaabbbecccc using the sample grammar and inference rules:
Axioms
======
1) [S,-1,-1,-1,-1] (A5)
2) [X,-1,-1,-1,-1] (A5)
3) [Y,-1,-1,-1,-1] (A5)
4) [a2,0,-1,-1,1] (A6)
5) [b2,1,-1,-1,2] (A6)
6) [a1,2,-1,-1,3] (A6)
7) [a3,3,-1,-1,4] (A6)
8) [a4,4,-1,-1,5] (A6)
9) [b4,5,-1,-1,6] (A6)
10) [b3,6,-1,-1,7] (A6)
11) [b1,7,-1,-1,8] (A6)
12) [e,8,-1,-1,9] (A6)
13) [c4,9,-1,-1,10] (A6)
14) [c3,10,-1,-1,11] (A6)
15) [c1,11,-1,-1,12] (A6)
16) [c2,12,-1,-1,13] (A6)
Parse Tree Derivation
===== ==== ==========
17) [S2,5,6,-1,-1] (I2,9,1)
18) [Y,5,6,-1,-1] (I7,17,3)
19) [S1,5,6,9,10] (I4,18,13)
20) [X,5,6,9,10] (I13,19,2)
21) [S0,4,6,9,10] (I1,8,20)
22) [S2,6,7,-1,-1] (I2,10,1)
23) [S2,4,7,9,10] (I10,21,22)
24) [Y,4,7,9,10] (I13,23,3)
25) [S1,4,7,9,11] (I3,24,14)
26) [X,4,7,9,11] (I13,25,2)
27) [S0,3,7,9,11] (I1,7,26)
28) [S2,7,8,-1,-1] (I2,11,1)
29) [S2,3,8,9,11] (I10,27,28)
30) [Y,3,8,9,11] (I13,29,3)
31) [S1,3,8,9,12] (I3,30,15)
32) [X,3,8,9,12] (I13,31,2)
33) [S0,2,8,9,12] (I1,6,32)
34) [S2,1,2,-1,-1] (I2,5,1)
35) [Y,1,2,-1,-1] (I7,34,3)
36) [S1,1,2,12,13] (I4,35,16)
37) [X,1,2,12,13] (I13,36,2)
38) [S0,0,2,12,13] (I1,4,37)
39) [S0,0,8,9,13] (I6,38,33)
40) [S,8,-1,-1,9] (I5,12)
41) [S,0,-1,-1,13] (I6,39,40)
42) [S,0,-1,-1,13] (I13,41,1) (for completeness)
Some Other Items Generated
==== ===== ===== =========
43) [Y,5,6,9,10] (I13,19,3)
44) [Y,4,6,9,10] (I13,21,3)
45) [Y,6,7,-1,-1] (I7,22,3)
46) [Y,4,7,9,11] (I13,25,3)
47) [Y,3,7,9,11] (I13,27,3)
48) [Y,7,8,-1,-1] (I7,28,3)
49) [Y,3,8,9,12] (I13,31,3)
50) [Y,2,8,9,12] (I13,33,3)
51) [Y,1,2,12,13] (I13,36,3)
52) [Y,0,2,12,13] (I13,38,3)
53) [Y,0,8,9,13] (I13,39,3)
54) [Y,8,-1,-1,9] (I6,40,3)
55) [Y,0,-1,-1,13] (I6,41,3)
56) (etc.)
It has been observed that several of the "other" items generated are permissible by the rules of inference but are not licensed by the grammar. for example, item 43) is a valid inference, but it claims that the symbol Y has a yield of .....b...c..., which cannot be constructed using the local trees of the grammar.
This may mean that the items are insufficiently specific as they are stated, and that they need to bear some sort of reference to the entire local tree they represent; we'll probably need to eventually add that information anyway to get the parse forest.
We also discussed replacing the inference rules with a set of rules that are based on the form of the local trees. This would mean that inferences would only proceed in the 3rd dimension, but since a finite number of symbols implies a finite number of local trees in the normal form, there would still be a finite number of inference rules. This would force the inference rules to mimic the local trees and thereby relieve the problem. This approach also seems like it would be analagous to the way we've been building inference rules for 2-dimensional grammars.
Jim: comments?
Posted by kellyia at June 14, 2004 04:38 PM