001: package fri.patterns.interpreter.parsergenerator.parsertables;
002:
003: import java.util.*;
004: import fri.util.collections.UniqueAggregatingHashtable;
005: import fri.patterns.interpreter.parsergenerator.Token;
006: import fri.patterns.interpreter.parsergenerator.syntax.*;
007:
008: /**
009: Map of all FOLLOW-sets of a SLR syntax. Key is nonterminal.
010: <p>
011: The FIRST-set for a nonterminal is the collection of terminals that
012: appear on first position of the right side of all rules where that
013: nonterminal appears on the left side.
014: <p>
015: <b>Algorithm:</b><br>
016: Search all rules that contain the nonterminal on left side.
017: Scan the right side of all these rules until a terminal or a non-nullable
018: nonterminal appears. The terminal goes to FIRST, the FIRST sets of
019: all scanned nonterminals go to FIRST. This implies that one must
020: collect FIRST sets recursively, for every scanned nonterminal.
021:
022: @author (c) 2000, Fritz Ritzberger
023: */
024:
025: class FirstSets extends UniqueAggregatingHashtable {
026: /**
027: Calculate Map of FIRST sets of all nonterminals contained in syntax.
028: The FIRST sets will then be lists within this Map that provides the
029: nonterminal as key.
030: @param syntax the grammar to scan.
031: @param nullAble Map containing Boolean true or false for nullability of every nonterminal.
032: @param nonterminals pre-built list of nonterminals
033: */
034: public FirstSets(Syntax syntax, Nullable nullAble, List nonterminals)
035: throws ParserBuildException {
036: // collect FIRST sets into this Hashtable where each
037: // nonterminal has a List of FIRST-symbols
038: Map done = new Hashtable(nonterminals.size()); // avoid recursion
039: for (int i = 0; i < nonterminals.size(); i++) {
040: String nonterm = (String) nonterminals.get(i);
041: generateFirstSet(syntax, nullAble, nonterm, done);
042: }
043: }
044:
045: private void generateFirstSet(Syntax syntax, Nullable nullAble,
046: String nonterminal, Map done) throws ParserBuildException {
047: if (get(nonterminal) != null)
048: return; // alreay done
049:
050: if (done.get(nonterminal) != null)
051: return;
052: done.put(nonterminal, nonterminal); // avoid endless loops
053: //System.err.println("generateFirstSet("+nonterminal+")");
054:
055: // The FIRST set of a nonterminal are all symbols
056: // that are on first position of the right side of all rules
057: // where the nonterminal is on the left side.
058: for (int k = 0; k < syntax.size(); k++) {
059: Rule rule = syntax.getRule(k);
060: String nonterm = rule.getNonterminal(); // left side of derivation
061:
062: if (nonterminal.equals(nonterm)) { // this rule derives the nonterminal
063: // if left side is empty, add NULL to FIRST of nonterminal
064: if (rule.rightSize() <= 0) {
065: put(nonterm, Nullable.NULL);
066: } else { // there are symbols on left side
067: boolean nullable = true; // enable loop until nullable
068:
069: // While nullable, add the symbol, shift to the next and
070: // check if it is nullable again.
071: for (int i = 0; nullable && i < rule.rightSize(); i++) {
072: String symbol = rule.getRightSymbol(i);
073:
074: nullable = false; // assume it is a terminal
075:
076: if (Token.isTerminal(symbol)) {
077: put(nonterm, symbol);
078: } else {
079: // If there is a nonterminal on first position, add its FIRST set
080: // FIRST set of this nonterminal, but without null-word.
081: try {
082: generateFirstSet(syntax, nullAble,
083: symbol, done); // enter recursion
084:
085: List list = (List) get(symbol); // get the results
086: for (int j = 0; list != null
087: && j < list.size(); j++) {
088: String s = (String) list.get(j);
089: put(nonterm, s);
090: }
091:
092: nullable = nullAble.isNullable(symbol);
093: } catch (Exception ex) {
094: throw new ParserBuildException(ex
095: .getMessage()
096: + " <- " + nonterm);
097: }
098: } // end if terminal
099: } // end for all symbols of rule
100:
101: // If the last added symbol is the last of the rule and
102: // is a nonterminal and is nullable, add null to FIRST set.
103: //if (nullable) {
104: // Sets.addToSets(this, nonterm, Nullable.NULL);
105: //}
106:
107: } // end if rule size > 1
108: } // end for al rules of syntax
109: }
110: }
111:
112: /** Overridden to check for equality of key and value: Exception is thrown when so. */
113: public Object put(Object key, Object value) {
114: if (key.equals(value))
115: throw new IllegalArgumentException(
116: "Can not be FIRST of its own: key=" + key
117: + ", value=" + value);
118:
119: return super .put(key, value);
120: }
121:
122: /** Test main */
123: public static void main(String[] args) {
124: // nonterminals
125: List nonterm = new ArrayList();
126: nonterm.add("S");
127: nonterm.add("T");
128: nonterm.add("F");
129: nonterm.add("L");
130:
131: // rules
132: List sx = new ArrayList();
133:
134: List r = new ArrayList();
135: r.add("S");
136: r.add("T");
137: r.add("'*'");
138: r.add("F");
139: sx.add(r);
140:
141: r = new ArrayList();
142: r.add("S");
143: r.add("T");
144: sx.add(r);
145:
146: r = new ArrayList();
147: r.add("T");
148: r.add("F");
149: sx.add(r);
150:
151: /* test empty derivation */
152: r = new ArrayList();
153: r.add("F");
154: sx.add(r);
155:
156: r = new ArrayList();
157: r.add("F");
158: r.add("'1'");
159: sx.add(r);
160:
161: Syntax syntax = new Syntax(sx);
162: try {
163: FirstSets f = new FirstSets(syntax, new Nullable(syntax,
164: nonterm), nonterm);
165: String s = "S";
166: System.err.println("FIRST(" + s + ") = " + f.get(s));
167: } catch (Exception e) {
168: e.printStackTrace();
169: }
170: }
171:
172: }
|