001: package fri.patterns.interpreter.parsergenerator.parsertables;
002:
003: import java.util.*;
004: import fri.patterns.interpreter.parsergenerator.syntax.*;
005:
006: /**
007: LR bottom-up parser syntax node. This node type contains an
008: algorithm to propagate lookahead-sets of items to dependent items
009: after syntax nodes were constructed.
010:
011: @see fri.patterns.interpreter.parsergenerator.parsertables.LRSyntaxNode
012: @author (c) 2000, Fritz Ritzberger
013: */
014:
015: class LALRSyntaxNode extends LRSyntaxNode {
016: /** Construction of node with FIRST-sets and nullability of all nonterminals in syntax. */
017: public LALRSyntaxNode(Nullable nullable, FirstSets firstSets) {
018: super (nullable, firstSets);
019: }
020:
021: /** Factory-method that constructs a LALRSyntaxNode. */
022: protected SLRSyntaxNode createSyntaxNode() {
023: return new LALRSyntaxNode(nullable, firstSets);
024: }
025:
026: /**
027: Factory-method that constructs a LALRRuleStateItem.
028: A start-lookahead gets appended to the item when it is the start node.
029: */
030: protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule) {
031: LALRRuleStateItem item = new LALRRuleStateItem(ruleIndex, rule);
032: addStartLookahead(item, ruleIndex);
033: return item;
034: }
035:
036: /** Calls super. After build lookaheads get propagated. */
037: public List build(Syntax syntax, List syntaxNodes, Hashtable kernels) {
038: syntaxNodes = super .build(syntax, syntaxNodes, kernels);
039:
040: // propagate lookaheads
041: for (int i = 0; i < syntaxNodes.size(); i++) {
042: LALRSyntaxNode node = (LALRSyntaxNode) syntaxNodes.get(i);
043: for (Enumeration e = node.entries.elements(); e
044: .hasMoreElements();) {
045: LALRRuleStateItem item = (LALRRuleStateItem) e
046: .nextElement();
047: item.propagateLookaheads(null);
048: }
049: }
050: return syntaxNodes;
051: }
052:
053: /**
054: Method called from closure, adopt all rules that derive the pending nonterminal.
055: Default lookaheads are calculated here. Items that need lookahead propagation
056: are located here.
057: */
058: protected void addRulesDerivingPendingNonTerminal(
059: RuleStateItem itm, String nonterm, Syntax syntax,
060: List newItems) {
061: // make the closure for one item:
062: // if pointer before a nonterminal, add all rules that derive it
063:
064: LALRRuleStateItem item = (LALRRuleStateItem) itm;
065: boolean needsPropagation = false;
066: List lookahead = null;
067:
068: for (int i = 0; i < syntax.size(); i++) {
069: Rule rule = syntax.getRule(i);
070:
071: if (rule.getNonterminal().equals(nonterm)) {
072: LALRRuleStateItem rsi = (LALRRuleStateItem) createRuleStateItem(
073: i, rule);
074:
075: // look if new item is already contained
076: LALRRuleStateItem existing = (LALRRuleStateItem) entries
077: .get(rsi);
078: if (existing != null) {
079: rsi = existing;
080: } else { // if not contained, add it
081: entries.put(rsi, rsi); // real list
082: newItems.add(rsi); // work list
083: }
084:
085: if (lookahead == null)
086: // calculate lookahead of originator and if it needs to propagate changes in
087: // its lookahead to the new items (has nullable nonterms until end)
088: needsPropagation = item.calculateLookahead(
089: lookahead = new ArrayList(), nullable,
090: firstSets);
091:
092: rsi.addLookahead(lookahead.iterator()); // merge lookaheads
093:
094: if (needsPropagation) // if lookahead is visible from this item,
095: item.addPropagate(rsi); // add to propagate list
096: }
097: }
098: }
099:
100: /**
101: Called from closure, connect a rule state item to its follower.
102: Lookahead-Propagation gets prepared by linking parent to child.
103: */
104: protected void linkParentItemToChild(RuleStateItem parent,
105: int newIndex, List syntaxNodes, RuleStateItem child) {
106: LALRRuleStateItem pnt = (LALRRuleStateItem) parent;
107: pnt.followNodeIndex = newIndex;
108:
109: LALRSyntaxNode node = (LALRSyntaxNode) syntaxNodes
110: .get(newIndex);
111:
112: // find corresponding item
113: LALRRuleStateItem rsi = (LALRRuleStateItem) node.entries
114: .get(child);
115:
116: // probably will have to propagate lookaheads to shifted item
117: pnt.addPropagate(rsi);
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: boolean needsPropagation = false;
126: Stack propagateItems = new Stack();
127:
128: public LALRRuleStateItem(int ruleIndex, Rule rule) {
129: super (ruleIndex, rule);
130: }
131:
132: protected LALRRuleStateItem(RuleStateItem orig) {
133: super (orig);
134: }
135:
136: /** Factory-method creating LALRRuleStateItem. */
137: protected RuleStateItem createRuleStateItem(RuleStateItem orig) {
138: return new LALRRuleStateItem(orig);
139: }
140:
141: /** Add an item that need lookahead propagation by this one. */
142: void addPropagate(RuleStateItem item) {
143: propagateItems.push(item);
144: needsPropagation = true;
145: }
146:
147: /** Accept incoming lookahead and propagate the own lookahead. */
148: void propagateLookaheads(Iterator originatorLookahead) {
149: boolean change = false;
150:
151: /// return when if nothing to propagate
152: if (needsPropagation == false
153: && (originatorLookahead == null || originatorLookahead
154: .hasNext() == false))
155: return;
156:
157: if (originatorLookahead != null)
158: change = addLookahead(originatorLookahead); // accept lookahead
159:
160: // if changed or need it, propagate across all linked items
161: if (change || needsPropagation) {
162: needsPropagation = false;
163:
164: for (int i = 0; i < propagateItems.size(); i++) {
165: LALRRuleStateItem item = (LALRRuleStateItem) propagateItems
166: .get(i);
167: item.propagateLookaheads(lookahead.keySet()
168: .iterator());
169: }
170: }
171: }
172:
173: /** Rule index and position of dot must be equal. */
174: public boolean equals(Object o) {
175: RuleStateItem item = (RuleStateItem) o;
176: return ruleIndex == item.ruleIndex
177: && pointerPosition == item.pointerPosition;
178: }
179:
180: /** The ruleIndex * 13 + dot poisition. */
181: public int hashCode() {
182: if (hashCache == null)
183: hashCache = new Integer(ruleIndex * 13
184: + pointerPosition);
185: return hashCache.intValue();
186: }
187:
188: } // end class LALRRuleStateItem
189:
190: }
|