KickJava   Java API By Example, From Geeks To Geeks.

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


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.syntax.*;
6
7 /**
8     LR bottom-up parser syntax node. This node type contains lookahead-sets
9     within its items, calculated from FIRST sets and nullability.
10
11     @see fri.patterns.interpreter.parsergenerator.parsertables.SLRSyntaxNode
12     @author (c) 2000, Fritz Ritzberger
13 */

14
15 class LRSyntaxNode extends SLRSyntaxNode
16 {
17     /** LR node must know about nullability. */
18     protected Nullable nullable;
19     
20     /** LR node must know FIRST sets. */
21     protected FirstSets firstSets;
22     
23
24     /** Construction of node with FIRST-sets and nullability of all nonterminals in syntax. */
25     public LRSyntaxNode(Nullable nullable, FirstSets firstSets) {
26         this.nullable = nullable;
27         this.firstSets = firstSets;
28     }
29     
30     
31     /** Factory-method that constructs a LRSyntaxNode. */
32     protected SLRSyntaxNode createSyntaxNode() {
33         return new LRSyntaxNode(nullable, firstSets);
34     }
35     
36     /**
37         Factory-method that constructs a LRRuleStateItem.
38         A start-lookahead gets appended to the item when it is the start node.
39     */

40     protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule) {
41         LRRuleStateItem item = new LRRuleStateItem(ruleIndex, rule);
42         addStartLookahead(item, ruleIndex);
43         return item;
44     }
45     
46     /** When start node (ruleIndex == 0), add EPSILON lookahead. */
47     protected void addStartLookahead(LRRuleStateItem item, int ruleIndex) {
48         if (ruleIndex == 0) {
49             List list = new ArrayList();
50             list.add(Token.EPSILON);
51             item.addLookahead(list.iterator());
52         }
53     }
54
55     /**
56         Method called from closure, adopt all rules that derive the pending nonterminal.
57         Default lookaheads are calculated here.
58     */

59     protected void addRulesDerivingPendingNonTerminal(RuleStateItem itm, String JavaDoc nonterm, Syntax syntax, List newItems) {
60         // make the closure for one item:
61
// if pointer before a nonterminal, add all rules that derive it
62

63         LRRuleStateItem item = (LRRuleStateItem)itm;
64         List lookahead = null;
65
66         for (int i = 0; i < syntax.size(); i++) {
67             Rule rule = syntax.getRule(i);
68             
69             if (rule.getNonterminal().equals(nonterm)) {
70                 LRRuleStateItem rsi = (LRRuleStateItem) createRuleStateItem(i, rule);
71                 
72                 if (lookahead == null) // calculate lookahead, all new items get the same lookahead
73
item.calculateLookahead(
74                             lookahead = new ArrayList(),
75                             nullable,
76                             firstSets);
77                 
78                 rsi.addLookahead(lookahead.iterator()); // merge lookaheads
79

80                 // look if new item is already contained, add when not
81
if (entries.containsKey(rsi) == false) {
82                     entries.put(rsi, rsi);
83                     newItems.add(rsi);
84                 }
85             }
86         }
87     }
88
89
90     /**
91         Returns all symbols for which SHIFT must be put into PARSE-ACTION table for a nonterminal.
92         For LR and LALR this returns null.
93     */

94     protected List getNontermShiftSymbols(FirstSets firstSets, String JavaDoc nonterm) {
95         return null;
96     }
97
98     /**
99         Returns all symbols for which REDUCE must be put into PARSE-ACTION table.
100         For LR and LALR this returns the lookahead of the passed item.
101     */

102     protected Iterator getReduceSymbols(FollowSets followSets, RuleStateItem item) {
103         return ((LRRuleStateItem) item).lookahead.keySet().iterator();
104     }
105
106
107
108
109     /**
110         Rule state entry item class, contained within LR syntax node.
111         Adds calculation and adoption of lookaheads functionality to super class.
112     */

113     protected class LRRuleStateItem extends RuleStateItem
114     {
115         Hashtable lookahead = new Hashtable();
116         
117         public LRRuleStateItem(int ruleIndex, Rule rule) {
118             super(ruleIndex, rule);
119         }
120         
121         /** Internal clone constructor, lookahead gets copied by cloning. */
122         protected LRRuleStateItem(RuleStateItem orig) {
123             super(orig);
124             lookahead = (Hashtable) ((LRRuleStateItem) orig).lookahead.clone();
125         }
126
127         /** Factory-method to create LRRuleStateItem. */
128         protected RuleStateItem createRuleStateItem(RuleStateItem orig) {
129             return new LRRuleStateItem(orig);
130         }
131         
132         /**
133             Add (new) lookaheads when not already contained.
134             @return true when change occured (needed in LALR).
135         */

136         boolean addLookahead(Iterator propagation) {
137             // merge lookaheads
138
boolean ret = false; // assume no changes
139

140             while (propagation.hasNext()) {
141                 Object JavaDoc la = propagation.next();
142                 
143                 if (lookahead.get(la) == null) {
144                     lookahead.put(la, la);
145                     ret = true; // there were changes
146
}
147             }
148             return ret;
149         }
150         
151         /**
152             Calculate the lookahead for a rule state. The result is returned in
153             newLookahead argument. These go to lookahead: FIRST set of second symbol after
154             the dot (terminal is taken itself), and all FIRST sets of following
155             symbols as long as they are nullable (terminal is not nullable).
156             When symbols all were nullable, the lookahead of this item also goes to lookahead.
157             @return true when all symbols after the dot in the rule were nullable.
158                     In LALR the originator item then propagates its lookaheads to this one.
159         */

160         boolean calculateLookahead(List newLookahead, Nullable nullable, FirstSets firstSets) {
161             // consider all nullable symbols after the one past the dot
162
// and add their first symbols to lookahead set.
163

164             for (int i = pointerPosition; i < rule.rightSize(); i++) { // when pointer at start, it has value 1
165
String JavaDoc symbol = rule.getRightSymbol(i);
166                 
167                 if (Token.isTerminal(symbol)) {
168                     newLookahead.add(symbol);
169                     return false; // originator lookahead not visible
170
}
171                 else {
172                     List firstSet = (List) firstSets.get(symbol);
173                     
174                     for (int j = 0; j < firstSet.size(); j++) {
175                         String JavaDoc la = (String JavaDoc) firstSet.get(j);
176                         newLookahead.add(la);
177                     }
178                     
179                     if (nullable.isNullable(symbol) == false)
180                         return false;
181                 }
182             }
183             
184             // if we get here everything was nullable, add all lookaheads of this item
185
for (Enumeration e = lookahead.keys(); e.hasMoreElements(); )
186                 newLookahead.add((String JavaDoc)e.nextElement());
187             
188             return true; // originator lookahead is visible
189
}
190
191         /** Rule index, dot position and lookahead must be equal. */
192         public boolean equals(Object JavaDoc o) {
193             if (super.equals(o) == false)
194                 return false;
195                 
196             LRRuleStateItem item = (LRRuleStateItem)o;
197             if (item.lookahead.equals(lookahead) == false)
198                 return false;
199
200             return true;
201         }
202
203         /** All lookahead hashcodes are associated by ^, plus rule index * 13 + dot position. */
204         public int hashCode() {
205             if (hashCache == null) {
206                 int result = 0;
207                 for (Enumeration e = lookahead.keys(); e.hasMoreElements(); )
208                     result ^= e.nextElement().hashCode();
209                 hashCache = new Integer JavaDoc(ruleIndex * 13 + pointerPosition + result);
210             }
211             return hashCache.intValue();
212         }
213
214         /** String representation from super, lookahead appended. */
215         public String JavaDoc toString() {
216             String JavaDoc s = super.toString();
217             int i = s.lastIndexOf("->");
218             if (i > 0)
219                 s = s.substring(0, i) + "LOOKAHEAD" + hashToStr(lookahead) + " " + s.substring(i);
220             else
221                 s = s + " " + hashToStr(lookahead);
222             return s;
223         }
224         
225         // output of hashtable keys, separated by ", ".
226
private String JavaDoc hashToStr(Hashtable l) {
227             StringBuffer JavaDoc sb = new StringBuffer JavaDoc("[");
228             for (Enumeration e = l.keys(); e.hasMoreElements(); ) {
229                 String JavaDoc s = (String JavaDoc)e.nextElement();
230                 sb.append(s);
231                 if (e.hasMoreElements())
232                     sb.append(", ");
233                 else
234                 if (l.size() == 1 && s.length() <= 0) // only Epsilon
235
sb.append(" ");
236             }
237             sb.append("]");
238             return sb.toString();
239         }
240
241     } // end class RuleStateItem
242

243 }
Popular Tags