001: package fri.patterns.interpreter.parsergenerator.parsertables;
002:
003: import java.util.*;
004: import fri.patterns.interpreter.parsergenerator.Token;
005: import fri.patterns.interpreter.parsergenerator.syntax.*;
006:
007: /**
008: LR bottom-up parser syntax node. This node type contains lookahead-sets
009: within its items, calculated from FIRST sets and nullability.
010:
011: @see fri.patterns.interpreter.parsergenerator.parsertables.SLRSyntaxNode
012: @author (c) 2000, Fritz Ritzberger
013: */
014:
015: class LRSyntaxNode extends SLRSyntaxNode {
016: /** LR node must know about nullability. */
017: protected Nullable nullable;
018:
019: /** LR node must know FIRST sets. */
020: protected FirstSets firstSets;
021:
022: /** Construction of node with FIRST-sets and nullability of all nonterminals in syntax. */
023: public LRSyntaxNode(Nullable nullable, FirstSets firstSets) {
024: this .nullable = nullable;
025: this .firstSets = firstSets;
026: }
027:
028: /** Factory-method that constructs a LRSyntaxNode. */
029: protected SLRSyntaxNode createSyntaxNode() {
030: return new LRSyntaxNode(nullable, firstSets);
031: }
032:
033: /**
034: Factory-method that constructs a LRRuleStateItem.
035: A start-lookahead gets appended to the item when it is the start node.
036: */
037: protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule) {
038: LRRuleStateItem item = new LRRuleStateItem(ruleIndex, rule);
039: addStartLookahead(item, ruleIndex);
040: return item;
041: }
042:
043: /** When start node (ruleIndex == 0), add EPSILON lookahead. */
044: protected void addStartLookahead(LRRuleStateItem item, int ruleIndex) {
045: if (ruleIndex == 0) {
046: List list = new ArrayList();
047: list.add(Token.EPSILON);
048: item.addLookahead(list.iterator());
049: }
050: }
051:
052: /**
053: Method called from closure, adopt all rules that derive the pending nonterminal.
054: Default lookaheads are calculated here.
055: */
056: protected void addRulesDerivingPendingNonTerminal(
057: RuleStateItem itm, String nonterm, Syntax syntax,
058: List newItems) {
059: // make the closure for one item:
060: // if pointer before a nonterminal, add all rules that derive it
061:
062: LRRuleStateItem item = (LRRuleStateItem) itm;
063: List lookahead = null;
064:
065: for (int i = 0; i < syntax.size(); i++) {
066: Rule rule = syntax.getRule(i);
067:
068: if (rule.getNonterminal().equals(nonterm)) {
069: LRRuleStateItem rsi = (LRRuleStateItem) createRuleStateItem(
070: i, rule);
071:
072: if (lookahead == null) // calculate lookahead, all new items get the same lookahead
073: item.calculateLookahead(
074: lookahead = new ArrayList(), nullable,
075: firstSets);
076:
077: rsi.addLookahead(lookahead.iterator()); // merge lookaheads
078:
079: // look if new item is already contained, add when not
080: if (entries.containsKey(rsi) == false) {
081: entries.put(rsi, rsi);
082: newItems.add(rsi);
083: }
084: }
085: }
086: }
087:
088: /**
089: Returns all symbols for which SHIFT must be put into PARSE-ACTION table for a nonterminal.
090: For LR and LALR this returns null.
091: */
092: protected List getNontermShiftSymbols(FirstSets firstSets,
093: String nonterm) {
094: return null;
095: }
096:
097: /**
098: Returns all symbols for which REDUCE must be put into PARSE-ACTION table.
099: For LR and LALR this returns the lookahead of the passed item.
100: */
101: protected Iterator getReduceSymbols(FollowSets followSets,
102: RuleStateItem item) {
103: return ((LRRuleStateItem) item).lookahead.keySet().iterator();
104: }
105:
106: /**
107: Rule state entry item class, contained within LR syntax node.
108: Adds calculation and adoption of lookaheads functionality to super class.
109: */
110: protected class LRRuleStateItem extends RuleStateItem {
111: Hashtable lookahead = new Hashtable();
112:
113: public LRRuleStateItem(int ruleIndex, Rule rule) {
114: super (ruleIndex, rule);
115: }
116:
117: /** Internal clone constructor, lookahead gets copied by cloning. */
118: protected LRRuleStateItem(RuleStateItem orig) {
119: super (orig);
120: lookahead = (Hashtable) ((LRRuleStateItem) orig).lookahead
121: .clone();
122: }
123:
124: /** Factory-method to create LRRuleStateItem. */
125: protected RuleStateItem createRuleStateItem(RuleStateItem orig) {
126: return new LRRuleStateItem(orig);
127: }
128:
129: /**
130: Add (new) lookaheads when not already contained.
131: @return true when change occured (needed in LALR).
132: */
133: boolean addLookahead(Iterator propagation) {
134: // merge lookaheads
135: boolean ret = false; // assume no changes
136:
137: while (propagation.hasNext()) {
138: Object la = propagation.next();
139:
140: if (lookahead.get(la) == null) {
141: lookahead.put(la, la);
142: ret = true; // there were changes
143: }
144: }
145: return ret;
146: }
147:
148: /**
149: Calculate the lookahead for a rule state. The result is returned in
150: newLookahead argument. These go to lookahead: FIRST set of second symbol after
151: the dot (terminal is taken itself), and all FIRST sets of following
152: symbols as long as they are nullable (terminal is not nullable).
153: When symbols all were nullable, the lookahead of this item also goes to lookahead.
154: @return true when all symbols after the dot in the rule were nullable.
155: In LALR the originator item then propagates its lookaheads to this one.
156: */
157: boolean calculateLookahead(List newLookahead,
158: Nullable nullable, FirstSets firstSets) {
159: // consider all nullable symbols after the one past the dot
160: // and add their first symbols to lookahead set.
161:
162: for (int i = pointerPosition; i < rule.rightSize(); i++) { // when pointer at start, it has value 1
163: String symbol = rule.getRightSymbol(i);
164:
165: if (Token.isTerminal(symbol)) {
166: newLookahead.add(symbol);
167: return false; // originator lookahead not visible
168: } else {
169: List firstSet = (List) firstSets.get(symbol);
170:
171: for (int j = 0; j < firstSet.size(); j++) {
172: String la = (String) firstSet.get(j);
173: newLookahead.add(la);
174: }
175:
176: if (nullable.isNullable(symbol) == false)
177: return false;
178: }
179: }
180:
181: // if we get here everything was nullable, add all lookaheads of this item
182: for (Enumeration e = lookahead.keys(); e.hasMoreElements();)
183: newLookahead.add((String) e.nextElement());
184:
185: return true; // originator lookahead is visible
186: }
187:
188: /** Rule index, dot position and lookahead must be equal. */
189: public boolean equals(Object o) {
190: if (super .equals(o) == false)
191: return false;
192:
193: LRRuleStateItem item = (LRRuleStateItem) o;
194: if (item.lookahead.equals(lookahead) == false)
195: return false;
196:
197: return true;
198: }
199:
200: /** All lookahead hashcodes are associated by ^, plus rule index * 13 + dot position. */
201: public int hashCode() {
202: if (hashCache == null) {
203: int result = 0;
204: for (Enumeration e = lookahead.keys(); e
205: .hasMoreElements();)
206: result ^= e.nextElement().hashCode();
207: hashCache = new Integer(ruleIndex * 13
208: + pointerPosition + result);
209: }
210: return hashCache.intValue();
211: }
212:
213: /** String representation from super, lookahead appended. */
214: public String toString() {
215: String s = super .toString();
216: int i = s.lastIndexOf("->");
217: if (i > 0)
218: s = s.substring(0, i) + "LOOKAHEAD"
219: + 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 hashToStr(Hashtable l) {
227: StringBuffer sb = new StringBuffer("[");
228: for (Enumeration e = l.keys(); e.hasMoreElements();) {
229: String s = (String) e.nextElement();
230: sb.append(s);
231: if (e.hasMoreElements())
232: sb.append(", ");
233: else if (l.size() == 1 && s.length() <= 0) // only Epsilon
234: sb.append(" ");
235: }
236: sb.append("]");
237: return sb.toString();
238: }
239:
240: } // end class RuleStateItem
241:
242: }
|