KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > fri > patterns > interpreter > parsergenerator > parsertables > LRParserTables


1 package fri.patterns.interpreter.parsergenerator.parsertables;
2
3 import java.util.Hashtable JavaDoc;
4 import fri.patterns.interpreter.parsergenerator.syntax.Syntax;
5
6 /**
7     Parser table generator for LR interpretation.
8     <p>
9     The init() method is overridden, as LR parsing does not need
10     FOLLOW-sets, and it needs nullability before building syntax nodes.
11
12     @see fri.patterns.interpreter.parsergenerator.parsertables.SLRParserTables
13     @author (c) 2000, Fritz Ritzberger
14 */

15
16 public class LRParserTables extends SLRParserTables
17 {
18     /** Calls super. */
19     public LRParserTables(Syntax syntax)
20         throws ParserBuildException
21     {
22         super(syntax);
23     }
24     
25     /** Factory method: constructing a root node for LR syntax nodes. */
26     protected LRSyntaxNode createStartNode(Nullable nullable, FirstSets firstSets) {
27         return new LRSyntaxNode(nullable, firstSets);
28     }
29
30     /**
31         Modifiying the SLR-generation as FIRST-sets and Nullable are needed
32         before building syntax nodes, FOLLOW-sets are not needed at all.
33     */

34     protected void init()
35         throws ParserBuildException
36     {
37         Nullable nullable = new Nullable(syntax, nonterminals);
38         firstSets = new FirstSets(syntax, nullable, nonterminals);
39
40         syntaxNodes = createStartNode(nullable, firstSets).build(syntax, syntaxNodes, new Hashtable JavaDoc());
41         
42         gotoTable = generateGoto(syntaxNodes);
43         
44         parseTable = generateParseAction(syntaxNodes);
45     }
46
47
48
49     /** Test main dumping parser tables. */
50     public static void main(String JavaDoc [] args) {
51         String JavaDoc [][] syntax = {
52             { "S", "L", "'='", "R" },
53             { "S", "R" },
54             { "L", "'*'", "R" },
55             { "L", "'id'" },
56             { "R", "L", },
57         };
58
59         try {
60             LRParserTables p = new LRParserTables(new Syntax(syntax));
61             p.dump(System.err);
62         }
63         catch (Exception JavaDoc e) {
64             e.printStackTrace();
65         }
66     }
67     
68 }
69
70 /*
71 (Rule 0) <START> :
72 (Rule 1) S : '=' R
73 (Rule 2) S :
74 (Rule 3) L : R
75 (Rule 4) L :
76 (Rule 5) R :
77
78 FIRST(L) = ['*', 'id']
79 FIRST(S) = ['*', 'id']
80 FIRST(R) = ['*', 'id']
81 FIRST(<START>) = ['*', 'id']
82
83 State 0
84   (Rule 0) <START> : .S LOOKAHEAD["EoI"] -> State 5
85   (Rule 1) S : .L '=' R LOOKAHEAD["EoI"] -> State 4
86   (Rule 2) S : .R LOOKAHEAD["EoI"] -> State 3
87   (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 2
88   (Rule 3) L : .'*' R LOOKAHEAD['='] -> State 2
89   (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 1
90   (Rule 4) L : .'id' LOOKAHEAD['='] -> State 1
91   (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 4
92
93 State 1
94   (Rule 4) L : 'id' . ['=']
95   (Rule 4) L : 'id' . ["EoI"]
96
97 State 2
98   (Rule 3) L : '*' .R LOOKAHEAD['='] -> State 6
99   (Rule 3) L : '*' .R LOOKAHEAD["EoI"] -> State 6
100   (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 2
101   (Rule 3) L : .'*' R LOOKAHEAD['='] -> State 2
102   (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 1
103   (Rule 4) L : .'id' LOOKAHEAD['='] -> State 1
104   (Rule 5) R : .L LOOKAHEAD['='] -> State 7
105   (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 7
106
107 State 3
108   (Rule 2) S : R . ["EoI"]
109
110 State 4
111   (Rule 1) S : L .'=' R LOOKAHEAD["EoI"] -> State 8
112   (Rule 5) R : L . ["EoI"]
113
114 State 5
115   (Rule 0) <START> : S . ["EoI"]
116
117 State 6
118   (Rule 3) L : '*' R . ['=']
119   (Rule 3) L : '*' R . ["EoI"]
120
121 State 7
122   (Rule 5) R : L . ["EoI"]
123   (Rule 5) R : L . ['=']
124
125 State 8
126   (Rule 1) S : L '=' .R LOOKAHEAD["EoI"] -> State 11
127   (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 10
128   (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 9
129   (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 12
130
131 State 9
132   (Rule 4) L : 'id' . ["EoI"]
133
134 State 10
135   (Rule 3) L : '*' .R LOOKAHEAD["EoI"] -> State 13
136   (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 10
137   (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 9
138   (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 12
139
140 State 11
141   (Rule 1) S : L '=' R . ["EoI"]
142
143 State 12
144   (Rule 5) R : L . ["EoI"]
145
146 State 13
147   (Rule 3) L : '*' R . ["EoI"]
148
149
150 GOTO TABLE
151 ==========
152       | <START> S L R '=' '*' 'id'
153 ________________________________________________________________
154     0 | - 5 4 3 - 2 1
155     1 | - - - - - - -
156     2 | - - 7 6 - 2 1
157     3 | - - - - - - -
158     4 | - - - - 8 - -
159     5 | - - - - - - -
160     6 | - - - - - - -
161     7 | - - - - - - -
162     8 | - - 12 11 - 10 9
163     9 | - - - - - - -
164    10 | - - 12 13 - 10 9
165    11 | - - - - - - -
166    12 | - - - - - - -
167    13 | - - - - - - -
168
169 PARSE-ACTION TABLE
170 ==================
171       | '=' '*' 'id' <EOF>
172 ________________________________________
173     0 | - SH SH -
174     1 | 4 - - 4
175     2 | - SH SH -
176     3 | - - - 2
177     4 | SH - - 5
178     5 | - - - AC
179     6 | 3 - - 3
180     7 | 5 - - 5
181     8 | - SH SH -
182     9 | - - - 4
183    10 | - SH SH -
184    11 | - - - 1
185    12 | - - - 5
186    13 | - - - 3
187
188 */
Popular Tags