KickJava   Java API By Example, From Geeks To Geeks.

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


1 package fri.patterns.interpreter.parsergenerator.parsertables;
2
3 import fri.patterns.interpreter.parsergenerator.syntax.Syntax;
4
5 /**
6     Parser table generator for LALR interpretation.
7
8     @see fri.patterns.interpreter.parsergenerator.parsertables.LRParserTables
9     @author (c) 2000, Fritz Ritzberger
10 */

11
12 public class LALRParserTables extends LRParserTables
13 {
14     /** Calls super. */
15     public LALRParserTables(Syntax syntax)
16         throws ParserBuildException
17     {
18         super(syntax);
19     }
20     
21     /** Factory method: constructing a root node for LALR syntax nodes. */
22     protected LRSyntaxNode createStartNode(Nullable nullable, FirstSets firstSets) {
23         return new LALRSyntaxNode(nullable, firstSets);
24     }
25
26
27     /** Test main dumping parser tables. */
28     public static void main(String JavaDoc [] args) {
29         /*
30         String [][] syntax = {
31             { "EXPR", "TERM" },
32             { "EXPR", "EXPR", "'+'", "TERM" },
33             { "EXPR", "EXPR", "'-'", "TERM" },
34             { "TERM", "FAKT", },
35             { "TERM", "TERM", "'*'", "FAKT" },
36             { "TERM", "TERM", "'/'", "FAKT" },
37             { "FAKT", "\"[0-9]+\"", },
38             { "FAKT", "'('", "EXPR", "')'" },
39         };
40         */

41         String JavaDoc [][] syntax = {
42             { "S", "L", "'='", "R" },
43             { "S", "R" },
44             { "L", "'*'", "R" },
45             { "L", "'id'" },
46             { "R", "L", },
47         };
48
49         try {
50             LALRParserTables p = new LALRParserTables(new Syntax(syntax));
51             p.dump(System.err);
52         }
53         catch (Exception JavaDoc e) {
54             e.printStackTrace();
55         }
56     }
57     
58 }
59
60
61 /*
62 (Rule 0) <START> :
63 (Rule 1) S : '=' R
64 (Rule 2) S :
65 (Rule 3) L : R
66 (Rule 4) L :
67 (Rule 5) R :
68
69 FIRST(L) = ['*', 'id']
70 FIRST(S) = ['*', 'id']
71 FIRST(R) = ['*', 'id']
72 FIRST(<START>) = ['*', 'id']
73
74 State 0
75   (Rule 0) <START> : .S LOOKAHEAD["EoI"] -> State 5
76   (Rule 1) S : .L '=' R LOOKAHEAD["EoI"] -> State 4
77   (Rule 2) S : .R LOOKAHEAD["EoI"] -> State 3
78   (Rule 3) L : .'*' R LOOKAHEAD['=', "EoI"] -> State 2
79   (Rule 4) L : .'id' LOOKAHEAD['=', "EoI"] -> State 1
80   (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 4
81
82 State 1
83   (Rule 4) L : 'id' . ['=', "EoI"]
84
85 State 2
86   (Rule 3) L : '*' .R LOOKAHEAD['=', "EoI"] -> State 6
87   (Rule 3) L : .'*' R LOOKAHEAD['=', "EoI"] -> State 2
88   (Rule 4) L : .'id' LOOKAHEAD['=', "EoI"] -> State 1
89   (Rule 5) R : .L LOOKAHEAD['=', "EoI"] -> State 7
90
91 State 3
92   (Rule 2) S : R . ["EoI"]
93
94 State 4
95   (Rule 1) S : L .'=' R LOOKAHEAD["EoI"] -> State 8
96   (Rule 5) R : L . ["EoI"]
97
98 State 5
99   (Rule 0) <START> : S . ["EoI"]
100
101 State 6
102   (Rule 3) L : '*' R . ['=', "EoI"]
103
104 State 7
105   (Rule 5) R : L . ['=', "EoI"]
106
107 State 8
108   (Rule 1) S : L '=' .R LOOKAHEAD["EoI"] -> State 9
109   (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 2
110   (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 1
111   (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 7
112
113 State 9
114   (Rule 1) S : L '=' R . ["EoI"]
115
116
117 GOTO TABLE
118 ==========
119       | <START> S L R '=' '*' 'id'
120 ________________________________________________________________
121     0 | - 5 4 3 - 2 1
122     1 | - - - - - - -
123     2 | - - 7 6 - 2 1
124     3 | - - - - - - -
125     4 | - - - - 8 - -
126     5 | - - - - - - -
127     6 | - - - - - - -
128     7 | - - - - - - -
129     8 | - - 7 9 - 2 1
130     9 | - - - - - - -
131
132 PARSE-ACTION TABLE
133 ==================
134       | '=' '*' 'id' <EOF>
135 ________________________________________
136     0 | - SH SH -
137     1 | 4 - - 4
138     2 | - SH SH -
139     3 | - - - 2
140     4 | SH - - 5
141     5 | - - - AC
142     6 | 3 - - 3
143     7 | 5 - - 5
144     8 | - SH SH -
145     9 | - - - 1
146
147 */

148
149
150
151 /*
152 (Rule 0) <START> : EXPR
153 (Rule 1) EXPR : TERM
154 (Rule 2) EXPR : EXPR '+' TERM
155 (Rule 3) EXPR : EXPR '-' TERM
156 (Rule 4) TERM : FAKT
157 (Rule 5) TERM : TERM '*' FAKT
158 (Rule 6) TERM : TERM '/' FAKT
159 (Rule 7) FAKT : "[0-9]+"
160 (Rule 8) FAKT : '(' EXPR ')'
161
162 FIRST(EXPR) = ["[0-9]+", '(']
163 FIRST(FAKT) = ["[0-9]+", '(']
164 FIRST(<START>) = ["[0-9]+", '(']
165 FIRST(TERM) = ["[0-9]+", '(']
166
167 State 0
168   (Rule 0) <START> : .EXPR LOOKAHEAD["EoI"] -> State 2
169   (Rule 1) EXPR : .TERM LOOKAHEAD['+', '-', "EoI"] -> State 1
170   (Rule 2) EXPR : .EXPR '+' TERM LOOKAHEAD['+', '-', "EoI"] -> State 2
171   (Rule 3) EXPR : .EXPR '-' TERM LOOKAHEAD['+', '-', "EoI"] -> State 2
172   (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 4
173   (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 1
174   (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 1
175   (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 5
176   (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 3
177
178 State 1
179   (Rule 1) EXPR : TERM . ['+', '-', ')', "EoI"]
180   (Rule 5) TERM : TERM .'*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 7
181   (Rule 6) TERM : TERM .'/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 6
182
183 State 2
184   (Rule 0) <START> : EXPR . ["EoI"]
185   (Rule 2) EXPR : EXPR .'+' TERM LOOKAHEAD['+', '-', "EoI"] -> State 9
186   (Rule 3) EXPR : EXPR .'-' TERM LOOKAHEAD['+', '-', "EoI"] -> State 8
187
188 State 3
189   (Rule 1) EXPR : .TERM LOOKAHEAD['+', '-', ')'] -> State 1
190   (Rule 2) EXPR : .EXPR '+' TERM LOOKAHEAD['+', '-', ')'] -> State 10
191   (Rule 3) EXPR : .EXPR '-' TERM LOOKAHEAD['+', '-', ')'] -> State 10
192   (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', ')', '/', '*'] -> State 4
193   (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', ')', '/', '*'] -> State 1
194   (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', ')', '/', '*'] -> State 1
195   (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*'] -> State 5
196   (Rule 8) FAKT : '(' .EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 10
197   (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*'] -> State 3
198
199 State 4
200   (Rule 4) TERM : FAKT . ['+', '-', ')', '/', '*', "EoI"]
201
202 State 5
203   (Rule 7) FAKT : "[0-9]+" . ['+', '-', ')', '/', '*', "EoI"]
204
205 State 6
206   (Rule 6) TERM : TERM '/' .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 11
207   (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
208   (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
209
210 State 7
211   (Rule 5) TERM : TERM '*' .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 12
212   (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
213   (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
214
215 State 8
216   (Rule 3) EXPR : EXPR '-' .TERM LOOKAHEAD['+', '-', ')', "EoI"] -> State 13
217   (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 4
218   (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 13
219   (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 13
220   (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
221   (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
222
223 State 9
224   (Rule 2) EXPR : EXPR '+' .TERM LOOKAHEAD['+', '-', ')', "EoI"] -> State 14
225   (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 4
226   (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 14
227   (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 14
228   (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
229   (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
230
231 State 10
232   (Rule 2) EXPR : EXPR .'+' TERM LOOKAHEAD['+', '-', ')'] -> State 9
233   (Rule 3) EXPR : EXPR .'-' TERM LOOKAHEAD['+', '-', ')'] -> State 8
234   (Rule 8) FAKT : '(' EXPR .')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 15
235
236 State 11
237   (Rule 6) TERM : TERM '/' FAKT . ['+', '-', ')', '/', '*', "EoI"]
238
239 State 12
240   (Rule 5) TERM : TERM '*' FAKT . ['+', '-', ')', '/', '*', "EoI"]
241
242 State 13
243   (Rule 3) EXPR : EXPR '-' TERM . ['+', '-', ')', "EoI"]
244   (Rule 5) TERM : TERM .'*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 7
245   (Rule 6) TERM : TERM .'/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 6
246
247 State 14
248   (Rule 2) EXPR : EXPR '+' TERM . ['+', '-', ')', "EoI"]
249   (Rule 5) TERM : TERM .'*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 7
250   (Rule 6) TERM : TERM .'/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 6
251
252 State 15
253   (Rule 8) FAKT : '(' EXPR ')' . ['+', '-', ')', '/', '*', "EoI"]
254
255
256 GOTO TABLE
257 ==========
258       | <START> EXPR TERM FAKT '+' '-' '*' '/' "[0-9]+ '(' ')'
259 ________________________________________________________________________________________________
260     0 | - 2 1 4 - - - - 5 3 -
261     1 | - - - - - - 7 6 - - -
262     2 | - - - - 9 8 - - - - -
263     3 | - 10 1 4 - - - - 5 3 -
264     4 | - - - - - - - - - - -
265     5 | - - - - - - - - - - -
266     6 | - - - 11 - - - - 5 3 -
267     7 | - - - 12 - - - - 5 3 -
268     8 | - - 13 4 - - - - 5 3 -
269     9 | - - 14 4 - - - - 5 3 -
270    10 | - - - - 9 8 - - - - 15
271    11 | - - - - - - - - - - -
272    12 | - - - - - - - - - - -
273    13 | - - - - - - 7 6 - - -
274    14 | - - - - - - 7 6 - - -
275    15 | - - - - - - - - - - -
276
277 PARSE-ACTION TABLE
278 ==================
279       | '+' '-' '*' '/' "[0-9]+ '(' ')' <EOF>
280 ________________________________________________________________________
281     0 | - - - - SH SH - -
282     1 | 1 1 SH SH - - 1 1
283     2 | SH SH - - - - - AC
284     3 | - - - - SH SH - -
285     4 | 4 4 4 4 - - 4 4
286     5 | 7 7 7 7 - - 7 7
287     6 | - - - - SH SH - -
288     7 | - - - - SH SH - -
289     8 | - - - - SH SH - -
290     9 | - - - - SH SH - -
291    10 | SH SH - - - - SH -
292    11 | 6 6 6 6 - - 6 6
293    12 | 5 5 5 5 - - 5 5
294    13 | 3 3 SH SH - - 3 3
295    14 | 2 2 SH SH - - 2 2
296    15 | 8 8 8 8 - - 8 8
297
298 */
Popular Tags