KickJava   Java API By Example, From Geeks To Geeks.

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


1 package fri.patterns.interpreter.parsergenerator.parsertables;
2
3 import java.util.*;
4 import fri.patterns.interpreter.parsergenerator.syntax.*;
5
6 /**
7     LR bottom-up parser syntax node. This node type contains an
8     algorithm to propagate lookahead-sets of items to dependent items
9     after syntax nodes were constructed.
10     
11     @see fri.patterns.interpreter.parsergenerator.parsertables.LRSyntaxNode
12     @author (c) 2000, Fritz Ritzberger
13 */

14
15 class LALRSyntaxNode extends LRSyntaxNode
16 {
17     /** Construction of node with FIRST-sets and nullability of all nonterminals in syntax. */
18     public LALRSyntaxNode(Nullable nullable, FirstSets firstSets) {
19         super(nullable, firstSets);
20     }
21     
22     
23     /** Factory-method that constructs a LALRSyntaxNode. */
24     protected SLRSyntaxNode createSyntaxNode() {
25         return new LALRSyntaxNode(nullable, firstSets);
26     }
27     
28     /**
29         Factory-method that constructs a LALRRuleStateItem.
30         A start-lookahead gets appended to the item when it is the start node.
31     */

32     protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule) {
33         LALRRuleStateItem item = new LALRRuleStateItem(ruleIndex, rule);
34         addStartLookahead(item, ruleIndex);
35         return item;
36     }
37
38     /** Calls super. After build lookaheads get propagated. */
39     public List build(Syntax syntax, List syntaxNodes, Hashtable kernels) {
40         syntaxNodes = super.build(syntax, syntaxNodes, kernels);
41         
42         // propagate lookaheads
43
for (int i = 0; i < syntaxNodes.size(); i++) {
44             LALRSyntaxNode node = (LALRSyntaxNode) syntaxNodes.get(i);
45             for (Enumeration e = node.entries.elements(); e.hasMoreElements(); ) {
46                 LALRRuleStateItem item = (LALRRuleStateItem) e.nextElement();
47                 item.propagateLookaheads(null);
48             }
49         }
50         return syntaxNodes;
51     }
52         
53     /**
54         Method called from closure, adopt all rules that derive the pending nonterminal.
55         Default lookaheads are calculated here. Items that need lookahead propagation
56         are located here.
57     */

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

62         LALRRuleStateItem item = (LALRRuleStateItem) itm;
63         boolean needsPropagation = false;
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                 LALRRuleStateItem rsi = (LALRRuleStateItem) createRuleStateItem(i, rule);
71                 
72                 // look if new item is already contained
73
LALRRuleStateItem existing = (LALRRuleStateItem)entries.get(rsi);
74                 if (existing != null) {
75                     rsi = existing;
76                 }
77                 else { // if not contained, add it
78
entries.put(rsi, rsi); // real list
79
newItems.add(rsi); // work list
80
}
81                 
82                 if (lookahead == null)
83                     // calculate lookahead of originator and if it needs to propagate changes in
84
// its lookahead to the new items (has nullable nonterms until end)
85
needsPropagation = item.calculateLookahead(
86                             lookahead = new ArrayList(),
87                             nullable,
88                             firstSets);
89                 
90                 rsi.addLookahead(lookahead.iterator()); // merge lookaheads
91

92                 if (needsPropagation) // if lookahead is visible from this item,
93
item.addPropagate(rsi); // add to propagate list
94
}
95         }
96     }
97
98
99     /**
100         Called from closure, connect a rule state item to its follower.
101         Lookahead-Propagation gets prepared by linking parent to child.
102     */

103     protected void linkParentItemToChild(RuleStateItem parent, int newIndex, List syntaxNodes, RuleStateItem child) {
104         LALRRuleStateItem pnt = (LALRRuleStateItem) parent;
105         pnt.followNodeIndex = newIndex;
106
107         LALRSyntaxNode node = (LALRSyntaxNode) syntaxNodes.get(newIndex);
108         
109         // find corresponding item
110
LALRRuleStateItem rsi = (LALRRuleStateItem) node.entries.get(child);
111
112         // probably will have to propagate lookaheads to shifted item
113
pnt.addPropagate(rsi);
114     }
115
116
117
118
119
120     /**
121         Rule state entry item class, contained within LALR syntax node.
122         Lookahead propagation is implemented here.
123     */

124     protected class LALRRuleStateItem extends LRRuleStateItem
125     {
126         boolean needsPropagation = false;
127         Stack propagateItems = new Stack();
128         
129         public LALRRuleStateItem(int ruleIndex, Rule rule) {
130             super(ruleIndex, rule);
131         }
132         
133         protected LALRRuleStateItem(RuleStateItem orig) {
134             super(orig);
135         }
136
137         /** Factory-method creating LALRRuleStateItem. */
138         protected RuleStateItem createRuleStateItem(RuleStateItem orig) {
139             return new LALRRuleStateItem(orig);
140         }
141         
142         /** Add an item that need lookahead propagation by this one. */
143         void addPropagate(RuleStateItem item) {
144             propagateItems.push(item);
145             needsPropagation = true;
146         }
147         
148         /** Accept incoming lookahead and propagate the own lookahead. */
149         void propagateLookaheads(Iterator originatorLookahead) {
150             boolean change = false;
151             
152             /// return when if nothing to propagate
153
if (needsPropagation == false && (originatorLookahead == null || originatorLookahead.hasNext() == false))
154                 return;
155             
156             if (originatorLookahead != null)
157                 change = addLookahead(originatorLookahead); // accept lookahead
158

159             // if changed or need it, propagate across all linked items
160
if (change || needsPropagation) {
161                 needsPropagation = false;
162             
163                 for (int i = 0; i < propagateItems.size(); i++) {
164                     LALRRuleStateItem item = (LALRRuleStateItem) propagateItems.get(i);
165                     item.propagateLookaheads(lookahead.keySet().iterator());
166                 }
167             }
168         }
169         
170         /** Rule index and position of dot must be equal. */
171         public boolean equals(Object JavaDoc o) {
172             RuleStateItem item = (RuleStateItem)o;
173             return ruleIndex == item.ruleIndex && pointerPosition == item.pointerPosition;
174         }
175
176         /** The ruleIndex * 13 + dot poisition. */
177         public int hashCode() {
178             if (hashCache == null)
179                 hashCache = new Integer JavaDoc(ruleIndex * 13 + pointerPosition);
180             return hashCache.intValue();
181         }
182
183     } // end class LALRRuleStateItem
184

185 }
Popular Tags