KickJava   Java API By Example, From Geeks To Geeks.

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


1 package fri.patterns.interpreter.parsergenerator.parsertables;
2
3 import java.util.*;
4 import fri.patterns.interpreter.parsergenerator.Token;
5 import fri.patterns.interpreter.parsergenerator.ParserTables;
6 import fri.patterns.interpreter.parsergenerator.syntax.*;
7
8 /**
9     SLR bottom-up parser syntax node.
10     The build() method of an no-arg-constructed node is used to fill a
11     state node list. The empty list passed to build() will be filled
12     with all state nodes after.
13     <p>
14     Every syntax node provides a fill() method to populate the corresponding
15     line (node-index) within PARSE-ACTION and GOTO tables.
16     <p>
17     After construction the syntax node has state entries represented by
18     RuleStateItem instances.
19     <p>
20     The state of a rule is represented by a dot "." at start, between symbols,
21     or at end. To shift an item means to move the dot to left.
22     
23     @author (c) 2000, Fritz Ritzberger
24 */

25
26 class SLRSyntaxNode
27 {
28     /** Contains all rule state entries. */
29     protected Hashtable entries = new Hashtable();
30
31     private int kernels = 0;
32     private Integer JavaDoc hashCache = null;
33
34
35     /** Do-nothing-constructor, used to call the build() method. */
36     public SLRSyntaxNode() {
37     }
38     
39     /** Factory-method to create a SLRSyntaxNode, to be overridden by other node types. */
40     protected SLRSyntaxNode createSyntaxNode() {
41         return new SLRSyntaxNode();
42     }
43     
44     /** Factory-method to create a RuleStateItem, to be overridden by other node types. */
45     protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule) {
46         return new RuleStateItem(ruleIndex, rule);
47     }
48
49
50     /**
51         Construction of start node and all further state nodes.
52         After this call the syntaxNodes list is filled with all state-bound nodes.
53         @param syntax the grammar, including START rule.
54         @param syntaxNodes ampty list that holds all syntax nodes after this call.
55         @param kernels empty hashtable for internal buffering.
56         @return the syntaxNodes list, now filled.
57     */

58     public List build(Syntax syntax, List syntaxNodes, Hashtable kernels) {
59         // insert first rule as state item
60
RuleStateItem item = createRuleStateItem(0, syntax.getRule(0));
61         entries.put(item, item);
62         closure(syntax); // calculate followers
63

64         syntaxNodes.add(this); // now add startnode to list of syntax nodes
65

66         generateSyntaxNodes(syntaxNodes, syntax, kernels); // generate all other nodes
67

68         //System.err.println("Built "+syntaxNodes.size()+" states.");
69
return syntaxNodes;
70     }
71
72     
73     /**
74         Generates syntax nodes into passed list, whereby every node represents one possible state.
75         Every generated node gets appended to list and can generate new nodes by itself.
76         @param syntaxNodes list of nodes
77         @param syntax the grammar rules
78     */

79     protected void generateSyntaxNodes(List syntaxNodes, Syntax syntax, Hashtable kernels) {
80         // newly appended nodes will be found and processed
81
for (int i = 0; i < syntaxNodes.size(); i++) {
82             SLRSyntaxNode node = (SLRSyntaxNode)syntaxNodes.get(i);
83             node.generateSyntaxNodesFromItems(syntaxNodes, syntax, kernels);
84         }
85     }
86     
87     /**
88         Generates follower nodes from rule state items into list. The followers are referenced
89         by their originators (GOTO-references).
90         @param syntaxNodes list of nodes
91         @param syntax the grammar rules
92     */

93     protected void generateSyntaxNodesFromItems(List syntaxNodes, Syntax syntax, Hashtable kernels) {
94         for (Enumeration e = entries.elements(); e.hasMoreElements(); ) {
95             RuleStateItem item = (RuleStateItem)e.nextElement();
96             String JavaDoc pending = item.getPendingSymbol();
97
98             if (item.followNodeIndex < 0 && pending != null) { // further states are possible
99
// create a kernel item
100
SLRSyntaxNode node = createSyntaxNode();
101                 List tmp = node.addShiftedItems(pending, entries); // get entries that have been taken
102

103                 // look if it is already in list
104
Integer JavaDoc kernelIndex = (Integer JavaDoc)kernels.get(node);
105                 int index = kernelIndex != null ? kernelIndex.intValue() : -1;
106
107                 // if not in list, add it, compute closure
108
if (index < 0) {
109                     index = syntaxNodes.size();
110                     kernels.put(node, new Integer JavaDoc(index));
111                     syntaxNodes.add(node);
112                     node.closure(syntax);
113                 }
114
115                 // link originator entries to new or found node
116
for (int i = 0; i < tmp.size(); i++) {
117                     Tuple t = (Tuple)tmp.get(i);
118                     linkParentItemToChild(t.o1, index, syntaxNodes, t.o2);
119                 }
120             }
121         }
122     }
123     
124
125     /**
126         Adopt all rule-states from originator node, which have the passed symbol
127         as pending to the right of dot. This is done when a new node was generated,
128         which happens when the dot is moved to the right.
129         All adopted items together form the kernel of the syntax node.
130         The number of kernel items is calculated, which is important when searching
131         existing nodes.
132         @param symbol the symbol that must be the pending symbol right of the dot within rule state item
133         @param originatorEntries map containing all rule state items of the originator node (as value).
134         @return a Tuple list containing pairs of original and new item, the new item is the shifted one.
135     */

136     protected List addShiftedItems(String JavaDoc symbol, Hashtable originatorEntries) {
137         List list = new ArrayList();
138         for (Enumeration e = originatorEntries.elements(); e.hasMoreElements(); ) {
139             RuleStateItem item = (RuleStateItem) e.nextElement();
140             String JavaDoc pending = item.getPendingSymbol();
141             
142             if (pending != null && symbol.equals(pending)) {
143                 RuleStateItem newitem = item.shift();
144                 this.entries.put(newitem, newitem);
145                 list.add(new Tuple(item, newitem)); // return all derived originator items
146
}
147         }
148         
149         kernels = list.size(); // remember count of kernel items
150

151         return list; // return list of entries that were shifted
152
}
153
154
155     /**
156         Store the follow state (node index) within rule state item.
157         This is a sparate protected method as LALR nodes do further work here.
158     */

159     protected void linkParentItemToChild(RuleStateItem parent, int newIndex, List syntaxNodes, RuleStateItem child) {
160         parent.followNodeIndex = newIndex;
161     }
162
163
164
165     /**
166         Closure - do for all rule states:
167         Adopt all rules from grammar that derive one of the pending nonterminals
168         (right of dot) within entries list. This is done recursively, appending
169         new rules at end, so that they can adopt further rules.
170         The closure method calls <i>addRulesDerivingPendingNonTerminal()</i>.
171     */

172     protected void closure(Syntax syntax) {
173         // put Hashtable to List for sequential work
174
List todo = new ArrayList(entries.size() * 2);
175         for (Enumeration e = entries.elements(); e.hasMoreElements(); )
176             todo.add(e.nextElement());
177
178         // loop todo list and find every added new item
179
for (int i = 0; i < todo.size(); i++) {
180             RuleStateItem rsi = (RuleStateItem)todo.get(i);
181             String JavaDoc nonterm = rsi.getPendingNonTerminal();
182             if (nonterm != null)
183                 addRulesDerivingPendingNonTerminal(rsi, nonterm, syntax, todo);
184         }
185     }
186     
187     /**
188         Closure call for one rule state item. All rules in grammar that have passed
189         nonterm on left side get appended to todo list and put into item entries when not already in entries.
190     */

191     protected void addRulesDerivingPendingNonTerminal(RuleStateItem item, String JavaDoc nonterm, Syntax syntax, List todo) {
192         // make the closure for one item:
193
// if pointer before a nonterminal, add all rules that derive it
194
for (int i = 0; i < syntax.size(); i++) {
195             Rule rule = syntax.getRule(i);
196             
197             if (rule.getNonterminal().equals(nonterm)) {
198                 RuleStateItem rsi = createRuleStateItem(i, rule);
199
200                 if (entries.containsKey(rsi) == false) {
201                     entries.put(rsi, rsi); // real entry list
202
todo.add(rsi); // work list
203
}
204             }
205         }
206     }
207
208
209
210     /**
211         Fill the line of GOTO table this state corresponds to.
212         @param state the index of this state within list
213         @return Hashtable with all terminals/nonterminals to handle, and their follower states.
214     */

215     public Hashtable fillGotoLine(int state) {
216         Hashtable h = new Hashtable(entries.size() * 3 / 2); // load factor 0.75
217

218         // fill one row of GOTO-table
219
for (Enumeration e = entries.elements(); e.hasMoreElements(); ) {
220             // store temporary
221
RuleStateItem item = (RuleStateItem)e.nextElement();
222             String JavaDoc symbol = item.getPendingSymbol();
223             
224             if (symbol != null) { // if pointer not at end of rule
225
//System.err.println("Regel-Zustand: "+item);
226
setTableLine("GOTO", state, h, item, new Integer JavaDoc(item.followNodeIndex), symbol);
227             }
228         }
229         return h;
230     }
231
232
233     /**
234         Fill the line of PARSE-ACTION table this state corresponds to.
235         @param state the index of this state within list
236         @param firstSets all FIRST-sets of all nonterminals
237         @param followSets all FOLLOW-sets of all nonterminals
238         @return Hashtable with all terminals to handle, and their actions.
239     */

240     public Hashtable fillParseActionLine(int state, FirstSets firstSets, FollowSets followSets) {
241         // fill one row of PARSE-ACTION-table
242
Hashtable h = new Hashtable(entries.size() * 10);
243         
244         for (Enumeration e = entries.elements(); e.hasMoreElements(); ) {
245             // store temporary
246
RuleStateItem item = (RuleStateItem)e.nextElement();
247             String JavaDoc symbol = item.getPendingSymbol();
248             
249             if (symbol != null) { // pointer not at end of rule, SHIFT
250
if (Token.isTerminal(symbol)) { // enter SHIFT at terminal symbol
251
// first-set of terminal is terminal
252
setParseTableLine(state, h, item, ParserTables.SHIFT, symbol);
253                 }
254                 else { // put SHIFT at all terminals of FIRST-set
255
List firstSet = getNontermShiftSymbols(firstSets, item.getNonterminal());
256                     
257                     if (firstSet != null) { // LALR will return null, SLR not null
258
for (int i = 0; i < firstSet.size(); i++) {
259                             String JavaDoc terminal = (String JavaDoc) firstSet.get(i);
260                             setParseTableLine(state, h, item, ParserTables.SHIFT, terminal);
261                         }
262                     }
263                 }
264             }
265             else { // pointer at end, REDUCE to rule number
266
for (Iterator reduceSymbols = getReduceSymbols(followSets, item); reduceSymbols.hasNext(); ) {
267                     String JavaDoc terminal = (String JavaDoc) reduceSymbols.next();
268                     
269                     if (item.ruleIndex == 0) // is startnode
270
setParseTableLine(state, h, item, ParserTables.ACCEPT, terminal);
271                     else // ruleIndex > 0 means REDUCE
272
setParseTableLine(state, h, item, new Integer JavaDoc(item.ruleIndex), terminal);
273                 }
274             }
275         }
276         return h;
277     }
278
279     /**
280         Returns all symbols for which SHIFT must be put into PARSE-ACTION table for a nonterminal.
281         For SLR this is the FIRST set of the nonterminal.
282     */

283     protected List getNontermShiftSymbols(FirstSets firstSets, String JavaDoc nonterm) {
284         return (List) firstSets.get(nonterm);
285     }
286
287     /**
288         Returns all symbols for which REDUCE must be put into PARSE-ACTION table.
289         For SLR this is the FOLLOW set of the nonterminal.
290     */

291     protected Iterator getReduceSymbols(FollowSets followSets, RuleStateItem item) {
292         return ((List) followSets.get(item.getNonterminal())).iterator();
293     }
294
295
296
297
298     /**
299         Set a position in PARSE-ACTION table.
300         This is the place where SHIFT/REDUCE and REDUCE/REDUCE conflicts are solved.
301     */

302     protected void setParseTableLine(int state, Hashtable line, RuleStateItem item, Integer JavaDoc action, String JavaDoc terminal) {
303         // set one action into a parse-table row and resolve conflicts
304

305         if (setTableLine("PARSE-ACTION", state, line, item, action, terminal) == false) {
306             // shift/reduce or reduce/reduce conflict
307
Object JavaDoc o = line.get(terminal);
308             
309             if (action.equals(ParserTables.SHIFT) || o.equals(ParserTables.SHIFT)) {
310                 // prefer SHIFT operation
311
line.put(terminal, ParserTables.SHIFT);
312                 System.err.println("WARNING: shift/reduce conflict, SHIFT is preferred.");
313             }
314             else {
315                 System.err.println("WARNING: reduce/reduce conflict, rule with smaller index is preferred.");
316                 // prefer rule with smaller index
317
if (((Integer JavaDoc)o).intValue() > action.intValue())
318                     line.put(terminal, action);
319             }
320         }
321     }
322     
323     
324     /**
325         Set a position in one of the tables.
326         Here SHIFT/SHIFT, SHIFT/REDUCE and REDUCE/REDUCE conflicts are detected.
327         @return true when no conflict was detected
328     */

329     protected boolean setTableLine(String JavaDoc table, int state, Hashtable line, RuleStateItem item, Integer JavaDoc action, String JavaDoc terminal) {
330         // set one action into a table row and detect conflicts
331
Object JavaDoc o = line.get(terminal);
332         if (o == null) { // no conflict
333
line.put(terminal, action);
334         }
335         else { // conflict?
336
if (o.equals(action) == false) { // conflict!
337
System.err.println("========================================================");
338                 System.err.println("WARNING: "+table+" state "+state+", terminal "+
339                         terminal+" is "+
340                         displayAction(o)+" and was overwritten by action "+
341                         displayAction(action));
342                 System.err.println("... from rule state: "+item);
343                 System.err.println("... current state:\n"+this);
344                 System.err.println("========================================================");
345                 return false;
346             }
347         }
348         return true;
349     }
350     
351     private String JavaDoc displayAction(Object JavaDoc action) {
352         if (action.equals(ParserTables.SHIFT))
353             return "SHIFT";
354         return "REDUCE("+action.toString()+")";
355     }
356     
357
358     /**
359         The count of kernel items must be equal. All kernel items must exist in passed node.
360         @param o new node that contains only kernel items (which do not have dot at start).
361     */

362     public boolean equals(Object JavaDoc o) {
363         //System.err.println("SLRSyntaxNode.equals: \n"+this+"\n with \n"+o);
364
SLRSyntaxNode node = (SLRSyntaxNode)o;
365         
366         if (node.kernels != kernels)
367             return false;
368         
369         // look if all entries are in the other node
370
for (Enumeration e = entries.elements(); e.hasMoreElements(); ) {
371             RuleStateItem item = (RuleStateItem)e.nextElement();
372             // kernel items have pointer not at start
373
if (item.pointerPosition > 1 && node.entries.containsKey(item) == false)
374                 return false;
375         }
376         return true;
377     }
378
379     /** Returns the hashcodes of all rule state items, associated by ^. The result gets buffered on first call. */
380     public int hashCode() {
381         if (hashCache == null) {
382             int result = 0;
383             for (Enumeration e = entries.elements(); e.hasMoreElements(); )
384                 result ^= e.nextElement().hashCode();
385             hashCache = new Integer JavaDoc(result);
386         }
387         return hashCache.intValue();
388     }
389
390
391     /** Outputs this syntax node with all its rule state entries sorted. */
392     public String JavaDoc toString() {
393         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
394         // we want a sorted output of items, order by ruleIndex
395
List list = new ArrayList(entries.size());
396         for (Enumeration e = entries.elements(); e.hasMoreElements(); ) {
397             RuleStateItem rsi = (RuleStateItem)e.nextElement();
398             int index = -1;
399             for (int i = 0; index == -1 && i < list.size(); i++) {
400                 RuleStateItem rsi1 = (RuleStateItem) list.get(i);
401                 if (rsi1.ruleIndex > rsi.ruleIndex || rsi1.ruleIndex == rsi.ruleIndex && rsi.pointerPosition > 1)
402                     index = i;
403             }
404             if (index < 0)
405                 list.add(rsi);
406             else
407                 list.add(index, rsi);
408         }
409         for (int i = 0; i < list.size(); i++) {
410             sb.append(" ");
411             sb.append(list.get(i).toString());
412             sb.append("\n");
413         }
414         return sb.toString();
415     }
416
417
418
419     // Helper that hold two RuleStateItems
420
private class Tuple
421     {
422         RuleStateItem o1, o2;
423         
424         Tuple(RuleStateItem o1, RuleStateItem o2) {
425             this.o1 = o1;
426             this.o2 = o2;
427         }
428     }
429
430
431
432     /**
433         Rule state entry item class, contained within SLR syntax node.
434     */

435     protected class RuleStateItem
436     {
437         Rule rule;
438         int pointerPosition = 1;
439         int ruleIndex;
440         int followNodeIndex = -1;
441         protected Integer JavaDoc hashCache = null;
442         
443         
444         /** Constructor with syntax rule index and rule. */
445         public RuleStateItem(int ruleIndex, Rule rule) {
446             this.rule = rule;
447             this.ruleIndex = ruleIndex;
448         }
449         
450         /** Internal construction of shifted rule states. */
451         protected RuleStateItem(RuleStateItem orig) {
452             this.rule = orig.rule;
453             this.pointerPosition = orig.pointerPosition;
454             this.ruleIndex = orig.ruleIndex;
455         }
456
457         
458         /** Factory-method, to be overridden by subclasses. */
459         protected RuleStateItem createRuleStateItem(RuleStateItem orig) {
460             return new RuleStateItem(orig);
461         }
462         
463         /** Returns the nonterminal on the left side of the rule. */
464         String JavaDoc getNonterminal() {
465             return rule.getNonterminal();
466         }
467         
468         /** Returns a new shifted rule state item (dot has moved one position right). */
469         RuleStateItem shift() {
470             RuleStateItem clone = createRuleStateItem(this);
471             clone.pointerPosition++;
472             return clone;
473         }
474         
475         /** Returns null when no nonterminal is after dot, else the nonterminal to the right of the dot. */
476         String JavaDoc getPendingNonTerminal() {
477             if (pointerPosition > rule.rightSize())
478                 return null;
479                 
480             String JavaDoc symbol = getPendingSymbol();
481             if (Token.isTerminal(symbol))
482                 return null; // is a terminal
483

484             return symbol;
485         }
486         
487         /** Return pending symbol if pointer position is not at end, else null. */
488         String JavaDoc getPendingSymbol() {
489             if (pointerPosition > rule.rightSize())
490                 return null;
491
492             return rule.getRightSymbol(pointerPosition - 1);
493         }
494
495         /** The rule number and dot position must match for equality. */
496         public boolean equals(Object JavaDoc o) {
497             RuleStateItem item = (RuleStateItem)o;
498             return ruleIndex == item.ruleIndex && pointerPosition == item.pointerPosition;
499         }
500     
501         /** Returns rule index * 13 + position of dot. */
502         public int hashCode() {
503             if (hashCache == null)
504                 hashCache = new Integer JavaDoc(ruleIndex * 13 + pointerPosition);
505             return hashCache.intValue();
506         }
507     
508         /** String representation of rule state, showing index, rule and dot position. */
509         public String JavaDoc toString() {
510             StringBuffer JavaDoc sb = new StringBuffer JavaDoc("(Rule "+ruleIndex+") "+getNonterminal()+" : ");
511             int i = 0;
512             for (; i < rule.rightSize(); i++) {
513                 if (i == pointerPosition - 1)
514                     sb.append(".");
515                 sb.append(rule.getRightSymbol(i));
516                 sb.append(" ");
517             }
518             if (i == pointerPosition - 1)
519                 sb.append(".");
520             if (followNodeIndex >= 0)
521                 sb.append(" -> State "+followNodeIndex);
522             return sb.toString();
523         }
524     
525     }
526
527 }
Popular Tags