KickJava   Java API By Example, From Geeks To Geeks.

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


1 package fri.patterns.interpreter.parsergenerator.parsertables;
2
3 import java.util.*;
4 import java.io.PrintStream JavaDoc;
5 import fri.patterns.interpreter.parsergenerator.Token;
6 import fri.patterns.interpreter.parsergenerator.syntax.*;
7
8 /**
9     A table generator, building SLR bottom-up parser tables from a syntax.
10     <p>
11     An artifical START-node gets inserted. Lists of nonterminals and terminals are created.
12     Syntax nodes are created, from which the parser GOTO and PARSE-ACTION tables get built.
13     <p>
14     This class contains dump methods for syntax nodes and FIRST/FOLLOW sets.
15     
16     @author (c) 2000, Fritz Ritzberger
17 */

18
19 public class SLRParserTables extends AbstractParserTables
20 {
21     protected transient List syntaxNodes = new ArrayList();
22     protected transient FirstSets firstSets;
23     protected transient FollowSets followSets;
24
25
26     /**
27         Appends START symbol and retrieves all symbols. Calls init then.
28         All parser table types run through this constructor.
29     */

30     public SLRParserTables(Syntax syntax)
31         throws ParserBuildException
32     {
33         this.syntax = addStartSymbol(syntax); // add START symbol to begin
34
getAllSymbols();
35         init();
36     }
37     
38
39     /** Builds SLR bottom-up parser tables. */
40     protected void init()
41         throws ParserBuildException
42     {
43         syntaxNodes = new SLRSyntaxNode().build(syntax, syntaxNodes, new Hashtable());
44         
45         gotoTable = generateGoto(syntaxNodes);
46
47         Nullable nullAble = new Nullable(syntax, nonterminals);
48         firstSets = new FirstSets(syntax, nullAble, nonterminals);
49         followSets = new FollowSets(syntax, nullAble, firstSets);
50         
51         parseTable = generateParseAction(syntaxNodes);
52     }
53
54
55     // Looks for top level rules and inserts a START rule pointing to it.
56
// Inserts a default rule pointing to the first rule when none found.
57
private Syntax addStartSymbol(Syntax syntax)
58         throws ParserBuildException
59     {
60         String JavaDoc startSym = null;
61         List startRules = syntax.findStartRules();
62         
63         if (startRules.size() <= 0) { // no toplevel rule
64
//throw new ParserBuildException("Grammatik hat keine Start-Regel!");
65
Rule rule = syntax.getRule(0);
66             System.err.println("WARNING: Grammar has no top level rule, taking first rule >"+rule+"<");
67             startSym = rule.getNonterminal();
68         }
69         else
70         if (startRules.size() > 1) { // more than one toplevel rules
71
for (int i = 0; i < startRules.size(); i++) { // check if all start rules have the same nonterminal on left side
72
Rule r = (Rule) startRules.get(i);
73                 String JavaDoc nt = r.getNonterminal();
74
75                 if (startSym == null)
76                     startSym = nt;
77                 else
78                 if (startSym.equals(nt) == false)
79                     throw new ParserBuildException("Grammar has more than one toplevel rules: "+startRules);
80             }
81         }
82         else { // exactly one toplevel rule found
83
startSym = ((Rule) startRules.get(0)).getNonterminal();
84         }
85         
86         Rule start = new Rule("<START>", 1);
87         start.addRightSymbol(startSym);
88         syntax.insertRule(0, start);
89         
90         return syntax;
91     }
92
93
94     /** Returns all symbols (terminals and nonterminals). Builds lists. Called only once on construction. */
95     protected List getAllSymbols()
96         throws ParserBuildException
97     {
98         // collect nonterminals unique
99
for (int i = 0; i < syntax.size(); i++) {
100             Rule rule = syntax.getRule(i);
101             String JavaDoc nonterm = rule.getNonterminal(); // left side of derivation
102

103             if (Nullable.isNull(nonterm))
104                 throw new ParserBuildException("ERROR: Empty nonterminal: >"+nonterm+"<");
105
106             if (nonterminals.indexOf(nonterm) < 0) // insert unique
107
nonterminals.add(nonterm);
108         }
109
110         // collect terminals unique
111
for (int j = 0; j < syntax.size(); j++) {
112             Rule rule = syntax.getRule(j);
113
114             for (int i = 0; i < rule.rightSize(); i++) {
115                 String JavaDoc symbol = rule.getRightSymbol(i);
116                 
117                 if (Nullable.isNull(symbol))
118                     throw new ParserBuildException("ERROR: Empty terminal: >"+symbol+"<");
119
120                 if (Token.isTerminal(symbol)) {
121                     if (terminals.indexOf(symbol) < 0) {
122                         terminals.add(symbol);
123                         terminalsWithoutEpsilon.add(symbol);
124                     }
125                 }
126                 else // throw error if nonterminal is not present
127
if (nonterminals.indexOf(symbol) < 0)
128                     throw new ParserBuildException("ERROR: Every nonterminal must have a rule. symbol: >"+symbol+"<, rule: "+rule);
129             }
130         }
131
132         // check for sanity
133
if (terminals.size() <= 0)
134             throw new ParserBuildException("ERROR: No terminal found: "+syntax);
135
136         if (nonterminals.size() <= 0)
137             throw new ParserBuildException("ERROR: No nonterminal found: "+syntax);
138
139         // add nonterminals to symbols
140
for (int i = 0; i < nonterminals.size(); i++)
141             symbols.add(nonterminals.get(i));
142
143         // add terminals without EpSiLoN to symbols
144
for (int i = 0; i < terminals.size(); i++)
145             symbols.add(terminals.get(i));
146
147         // add "Epsilon" Symbol to Terminals
148
terminals.add(Token.EPSILON);
149
150         return symbols;
151     }
152     
153     
154     /** Creates GOTO table of follow states. */
155     protected List generateGoto(List syntaxNodes) {
156         //System.err.println("got "+syntaxNodes.size()+" states");
157
this.gotoTable = new ArrayList(syntaxNodes.size());
158         
159         Map hash = new Hashtable(syntaxNodes.size());
160
161         for (int i = 0; i < syntaxNodes.size(); i++) {
162             SLRSyntaxNode node = (SLRSyntaxNode) syntaxNodes.get(i);
163
164             Map h = node.fillGotoLine(i);
165             
166             if (h.size() <= 0)
167                 gotoTable.add(null);
168             else
169                 insertTableLine(i, h, gotoTable, hash);
170         }
171
172         return gotoTable;
173     }
174     
175     
176     /**
177         Erzeugen der Parse-Action-Tabelle fuer shift/reduce Aktionen.
178     */

179     protected List generateParseAction(List syntaxNodes) {
180         this.parseTable = new ArrayList(syntaxNodes.size());
181
182         Map hash = new Hashtable(syntaxNodes.size());
183         
184         for (int i = 0; i < syntaxNodes.size(); i++) {
185             SLRSyntaxNode node = (SLRSyntaxNode) syntaxNodes.get(i);
186
187             Map h = node.fillParseActionLine(i, firstSets, followSets);
188
189             if (h.size() <= 0)
190                 parseTable.add(null);
191             else
192                 insertTableLine(i, h, parseTable, hash);
193         }
194
195         return parseTable;
196     }
197
198     
199     /**
200         Compression of tables: Look for an identical table line.
201         @return identical line Zeile, or passed line when not found.
202     */

203     protected void insertTableLine(
204         int i,
205         Map line,
206         List table,
207         Map hash)
208     {
209         Integer JavaDoc itg = (Integer JavaDoc) hash.get(line);
210         if (itg == null) {
211             table.add(line);
212             hash.put(line, new Integer JavaDoc(i));
213         }
214         else {
215             table.add(table.get(itg.intValue()));
216         }
217     }
218
219
220
221     /** Enable garbage collection of builder variables. CAUTION: dump methods work reduced after this call. */
222     public void freeSyntaxNodes() {
223         syntaxNodes = null;
224         symbols = null;
225         terminals = null;
226     }
227     
228     
229
230     // dump methods to print parser information
231

232     /** Overridden to report better. */
233     public void report(PrintStream JavaDoc out) {
234         System.err.println("Parser Generator is "+getClass());
235         super.report(out);
236         out.println("states: "+(syntaxNodes != null ? syntaxNodes.size() : -1));
237     }
238
239
240     /** Implements ParserTables: output of rules, FIRST/FOLLOW sets, syntax nodes, GOTO-table, PARSE-ACTON-table. */
241     public void dump(PrintStream JavaDoc out) {
242         dumpSyntax(out);
243         dumpFirstSet(out);
244         dumpFollowSet(out);
245         dumpSyntaxNodes(out);
246         dumpGoto(out);
247         dumpParseAction(out);
248     }
249     
250     public void dumpSyntaxNodes(PrintStream JavaDoc out) {
251         if (syntaxNodes != null) {
252             for (int i = 0; i < syntaxNodes.size(); i++)
253                 dumpSyntaxNode(i, (SLRSyntaxNode) syntaxNodes.get(i), out);
254             out.println();
255         }
256     }
257     
258     public void dumpSyntaxNode(int i, SLRSyntaxNode node, PrintStream JavaDoc out) {
259         out.println("State "+i);
260         out.println(node.toString());
261     }
262     
263     public void dumpFirstSet(PrintStream JavaDoc out) {
264         if (firstSets != null)
265             dumpSet("FIRST", firstSets, out);
266     }
267     
268     public void dumpFollowSet(PrintStream JavaDoc out) {
269         if (followSets != null)
270             dumpSet("FOLLOW", followSets, out);
271     }
272     
273     public void dumpSet(String JavaDoc header, Map set, PrintStream JavaDoc out) {
274         for (Iterator it = set.keySet().iterator(); it.hasNext(); ) {
275             String JavaDoc nonterm = (String JavaDoc) it.next();
276             out.println(header+"("+nonterm+") = "+set.get(nonterm));
277         }
278         out.println();
279     }
280     
281     
282     
283     /** Test main dumping arithmetic expression tables. */
284     public static void main(String JavaDoc [] args) {
285         String JavaDoc [][] syntax = {
286             { "EXPR", "TERM" },
287             { "EXPR", "EXPR", "'+'", "TERM" },
288             { "EXPR", "EXPR", "'-'", "TERM" },
289             { "TERM", "FAKT", },
290             { "TERM", "TERM", "'*'", "FAKT" },
291             { "TERM", "TERM", "'/'", "FAKT" },
292             { "FAKT", "`number`", },
293             { "FAKT", "'('", "EXPR", "')'" },
294         };
295         
296         try {
297             SLRParserTables p = new SLRParserTables(new Syntax(syntax));
298             p.dump(System.err);
299         }
300         catch (Exception JavaDoc e) {
301             e.printStackTrace();
302         }
303     }
304     
305 }
306
307 /*
308 (Rule 0) <START> : EXPR
309 (Rule 1) EXPR : TERM
310 (Rule 2) EXPR : EXPR '+' TERM
311 (Rule 3) EXPR : EXPR '-' TERM
312 (Rule 4) TERM : FAKT
313 (Rule 5) TERM : TERM '*' FAKT
314 (Rule 6) TERM : TERM '/' FAKT
315 (Rule 7) FAKT : "[0-9]+"
316 (Rule 8) FAKT : '(' EXPR ')'
317
318 FIRST(EXPR) = ["[0-9]+", '(']
319 FIRST(FAKT) = ["[0-9]+", '(']
320 FIRST(<START>) = ["[0-9]+", '(']
321 FIRST(TERM) = ["[0-9]+", '(']
322
323 FOLLOW(FAKT) = [Epsilon, '+', '-', ')', '*', '/']
324 FOLLOW(EXPR) = [Epsilon, '+', '-', ')']
325 FOLLOW(<START>) = [Epsilon]
326 FOLLOW(TERM) = [Epsilon, '+', '-', ')', '*', '/']
327
328 State 0
329   (Rule 0) <START> : .EXPR -> State 2
330   (Rule 1) EXPR : .TERM -> State 1
331   (Rule 2) EXPR : .EXPR '+' TERM -> State 2
332   (Rule 3) EXPR : .EXPR '-' TERM -> State 2
333   (Rule 4) TERM : .FAKT -> State 4
334   (Rule 5) TERM : .TERM '*' FAKT -> State 1
335   (Rule 6) TERM : .TERM '/' FAKT -> State 1
336   (Rule 7) FAKT : ."[0-9]+" -> State 5
337   (Rule 8) FAKT : .'(' EXPR ')' -> State 3
338
339 State 1
340   (Rule 1) EXPR : TERM .
341   (Rule 5) TERM : TERM .'*' FAKT -> State 7
342   (Rule 6) TERM : TERM .'/' FAKT -> State 6
343
344 State 2
345   (Rule 0) <START> : EXPR .
346   (Rule 2) EXPR : EXPR .'+' TERM -> State 9
347   (Rule 3) EXPR : EXPR .'-' TERM -> State 8
348
349 State 3
350   (Rule 1) EXPR : .TERM -> State 1
351   (Rule 2) EXPR : .EXPR '+' TERM -> State 10
352   (Rule 3) EXPR : .EXPR '-' TERM -> State 10
353   (Rule 4) TERM : .FAKT -> State 4
354   (Rule 5) TERM : .TERM '*' FAKT -> State 1
355   (Rule 6) TERM : .TERM '/' FAKT -> State 1
356   (Rule 7) FAKT : ."[0-9]+" -> State 5
357   (Rule 8) FAKT : '(' .EXPR ')' -> State 10
358   (Rule 8) FAKT : .'(' EXPR ')' -> State 3
359
360 State 4
361   (Rule 4) TERM : FAKT .
362
363 State 5
364   (Rule 7) FAKT : "[0-9]+" .
365
366 State 6
367   (Rule 6) TERM : TERM '/' .FAKT -> State 11
368   (Rule 7) FAKT : ."[0-9]+" -> State 5
369   (Rule 8) FAKT : .'(' EXPR ')' -> State 3
370
371 State 7
372   (Rule 5) TERM : TERM '*' .FAKT -> State 12
373   (Rule 7) FAKT : ."[0-9]+" -> State 5
374   (Rule 8) FAKT : .'(' EXPR ')' -> State 3
375
376 State 8
377   (Rule 3) EXPR : EXPR '-' .TERM -> State 13
378   (Rule 4) TERM : .FAKT -> State 4
379   (Rule 5) TERM : .TERM '*' FAKT -> State 13
380   (Rule 6) TERM : .TERM '/' FAKT -> State 13
381   (Rule 7) FAKT : ."[0-9]+" -> State 5
382   (Rule 8) FAKT : .'(' EXPR ')' -> State 3
383
384 State 9
385   (Rule 2) EXPR : EXPR '+' .TERM -> State 14
386   (Rule 4) TERM : .FAKT -> State 4
387   (Rule 5) TERM : .TERM '*' FAKT -> State 14
388   (Rule 6) TERM : .TERM '/' FAKT -> State 14
389   (Rule 7) FAKT : ."[0-9]+" -> State 5
390   (Rule 8) FAKT : .'(' EXPR ')' -> State 3
391
392 State 10
393   (Rule 2) EXPR : EXPR .'+' TERM -> State 9
394   (Rule 3) EXPR : EXPR .'-' TERM -> State 8
395   (Rule 8) FAKT : '(' EXPR .')' -> State 15
396
397 State 11
398   (Rule 6) TERM : TERM '/' FAKT .
399
400 State 12
401   (Rule 5) TERM : TERM '*' FAKT .
402
403 State 13
404   (Rule 3) EXPR : EXPR '-' TERM .
405   (Rule 5) TERM : TERM .'*' FAKT -> State 7
406   (Rule 6) TERM : TERM .'/' FAKT -> State 6
407
408 State 14
409   (Rule 2) EXPR : EXPR '+' TERM .
410   (Rule 5) TERM : TERM .'*' FAKT -> State 7
411   (Rule 6) TERM : TERM .'/' FAKT -> State 6
412
413 State 15
414   (Rule 8) FAKT : '(' EXPR ')' .
415
416
417 GOTO TABLE
418 ==========
419       | <START> EXPR TERM FAKT '+' '-' '*' '/' "[0-9]+" '(' ')'
420 ________________________________________________________________________________________________
421     0 | - 2 1 4 - - - - 5 3 -
422     1 | - - - - - - 7 6 - - -
423     2 | - - - - 9 8 - - - - -
424     3 | - 10 1 4 - - - - 5 3 -
425     4 | - - - - - - - - - - -
426     5 | - - - - - - - - - - -
427     6 | - - - 11 - - - - 5 3 -
428     7 | - - - 12 - - - - 5 3 -
429     8 | - - 13 4 - - - - 5 3 -
430     9 | - - 14 4 - - - - 5 3 -
431    10 | - - - - 9 8 - - - - 15
432    11 | - - - - - - - - - - -
433    12 | - - - - - - - - - - -
434    13 | - - - - - - 7 6 - - -
435    14 | - - - - - - 7 6 - - -
436    15 | - - - - - - - - - - -
437
438 PARSE-ACTION TABLE
439 ==================
440       | '+' '-' '*' '/' "[0-9]+" '(' ')' <EOF>
441 ________________________________________________________________________
442     0 | - - - - SH SH - -
443     1 | 1 1 SH SH - - 1 1
444     2 | SH SH - - - - - AC
445     3 | - - - - SH SH - -
446     4 | 4 4 4 4 - - 4 4
447     5 | 7 7 7 7 - - 7 7
448     6 | - - - - SH SH - -
449     7 | - - - - SH SH - -
450     8 | - - - - SH SH - -
451     9 | - - - - SH SH - -
452    10 | SH SH - - - - SH -
453    11 | 6 6 6 6 - - 6 6
454    12 | 5 5 5 5 - - 5 5
455    13 | 3 3 SH SH - - 3 3
456    14 | 2 2 SH SH - - 2 2
457    15 | 8 8 8 8 - - 8 8
458
459 */
Popular Tags