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 FOLLOW-set for a nonterminal is the collection of terminals that
012: can appear behind that nonterminal on the right side of all rules.
013: <p>
014: <b>Algorithm:</b><br>
015: Search all rules that contain the nonterminal on right side.
016: Scan for a terminal after the nonterminal on right side until found
017: or one scanned nonterminal is not nullable. The FIRST set of every
018: scanned nonterminal goes to the FOLLOW set. When reaching the end
019: without having found a terminal or a non-nullable nonterminal, even
020: the FOLLOW set of the nonterminal on the left side of that rule goes
021: to FOLLOW.
022:
023: @author (c) 2000, Fritz Ritzberger
024: */
025:
026: class FollowSets extends UniqueAggregatingHashtable {
027: /**
028: Calculate FOLLOW-sets for all nonterminals contained in passed syntax.
029: The FOLLOW sets will then be Lists within a Map that provides the nonterminal
030: as key.
031: @param syntax the grammar
032: @param nullAble Map containing Boolean true when nonterminal (key) is nullable, else false.
033: @param firstSets ready-made FIRST sets for all nonterminals.
034: */
035: public FollowSets(Syntax syntax, Nullable nullAble,
036: FirstSets firstSets) throws ParserBuildException {
037: // collect FOLLOW sets into a Hashtable where each nonterminal has a list of FOLLOW symbols
038: generateFollow(syntax, nullAble, firstSets);
039:
040: // make a plain list from references to other FOLLOW sets
041: resolveSets();
042: }
043:
044: private void generateFollow(Syntax syntax, Nullable nullAble,
045: FirstSets firstSets) {
046: // The FOLLOW set of a nonterminal are all symbols that appear after the
047: // nonterminal on the right side of all rules. If the nonterminal stands
048: // at last position, add the FOLLOW set of the left side of this rule.
049:
050: // loop across all syntax rules
051: for (int rulePos = 0; rulePos < syntax.size(); rulePos++) {
052: Rule rule = syntax.getRule(rulePos);
053: String nonterm = rule.getNonterminal(); // left side of derivation
054:
055: if (rulePos == 0) { // START node, FOLLOW of start node is always epsilon
056: put(nonterm, Token.EPSILON);
057: // first rule is made programmatically, add Epsilon to FOLLOW
058: put(rule.getRightSymbol(0), Token.EPSILON);
059: } else {
060: List nonterms = new ArrayList(); // collect receiving nonterminals
061:
062: for (int i = 0; i < rule.rightSize(); i++) {
063: String symbol = rule.getRightSymbol(i);
064: boolean isTerminal = Token.isTerminal(symbol);
065:
066: if (nonterms.size() > 0) { // if there are receivers (not at first element)
067: // add symbol to FOLLOW sets of all nonterminals in local list
068: List l;
069: if (isTerminal) {
070: l = new ArrayList();
071: l.add(symbol); // terminal goes to FOLLOW set
072: } else {
073: l = (List) firstSets.get(symbol); // FIRST(symbol) goes to FOLLOW set
074: }
075: //System.err.println("rule "+rule+", adding to "+nonterms+" symbols "+v);
076: addToAllFollowSets(nonterms, l);
077: }
078:
079: if (isTerminal
080: || nullAble.isNullable(symbol) == false) { // if it is a terminal or can not be null
081: nonterms.clear(); // empty list of receiving nonterminals
082: }
083:
084: if (isTerminal == false) { // if it is a nonterminal
085: nonterms.add(symbol);
086:
087: if (i == rule.rightSize() - 1) { // at end
088: // add left side of rule to FOLLOW sets of all collected nonterminals
089: List l = new ArrayList();
090: l.add(nonterm);
091: addToAllFollowSets(nonterms, l);
092: }
093: }
094: } // end for all symbols
095: } // end if rule position 0
096: } // end for, loop across rules
097: }
098:
099: private void addToAllFollowSets(List nonterms, List symbols) {
100: for (int i = 0; i < nonterms.size(); i++) {
101: String nt = (String) nonterms.get(i);
102:
103: for (int j = 0; j < symbols.size(); j++) {
104: String s = (String) symbols.get(j);
105:
106: if (Nullable.isNull(s) == false) // do not add empty word
107: put(nt, s);
108: }
109: }
110: }
111:
112: private void resolveSets() throws ParserBuildException {
113: // Make plain lists of mixed reference lists: all nonterminals are resolved to their terminal lists
114: for (Enumeration e = keys(); e.hasMoreElements();) {
115: String key = (String) e.nextElement();
116: //System.err.println("nonterminal "+key+" = "+get(key));
117: List newList = resolveSetSymbol(key, new Hashtable());
118: replace(key, newList);
119: }
120: }
121:
122: private List resolveSetSymbol(String nonterm, Map done)
123: throws ParserBuildException {
124: if (done.get(nonterm) != null)
125: return null;
126: done.put(nonterm, nonterm); // avoid endless loops
127:
128: List values = (List) get(nonterm);
129: List newList = new ArrayList(values.size() * 2);
130:
131: for (int j = 0; j < values.size(); j++) {
132: String symbol = (String) values.get(j);
133:
134: if (Token.isTerminal(symbol) == false) { // resolve nonterminal
135: try {
136: List l = resolveSetSymbol(symbol, done);
137: for (int i = 0; l != null && i < l.size(); i++) {
138: String s = (String) l.get(i);
139: if (newList.indexOf(s) < 0)
140: newList.add(s);
141: }
142: } catch (Exception ex) {
143: throw new ParserBuildException("FOLLOW set error: "
144: + ex.getMessage() + " <- " + symbol);
145: }
146: } else { // add terminal
147: if (newList.indexOf(symbol) < 0)
148: newList.add(symbol);
149: }
150: }
151: return newList;
152: }
153:
154: /** Overridden to check for equality of key and value: Exception is thrown when so. */
155: public Object put(Object key, Object value) {
156: if (key.equals(value))
157: throw new IllegalArgumentException(
158: "Can not be FOLLOW of its own: key=" + key
159: + ", value=" + value);
160:
161: return super .put(key, value);
162: }
163:
164: /** Test main */
165: public static void main(String[] args) {
166: List nt = new ArrayList();
167: nt.add("S");
168: nt.add("T");
169: nt.add("F");
170: nt.add("L");
171:
172: List sx = new ArrayList();
173:
174: List r = new ArrayList();
175: r.add("S");
176: r.add("E");
177: sx.add(r);
178:
179: r = new ArrayList();
180: r.add("E");
181: r.add("T");
182: r.add("'*'");
183: r.add("F");
184: sx.add(r);
185:
186: r = new ArrayList();
187: r.add("E");
188: r.add("T");
189: sx.add(r);
190:
191: r = new ArrayList();
192: r.add("T");
193: r.add("F");
194: sx.add(r);
195:
196: r = new ArrayList();
197: r.add("F");
198: r.add("'1'");
199: sx.add(r);
200:
201: Syntax syntax = new Syntax(sx);
202: try {
203: Nullable nullAble = new Nullable(syntax, nt);
204: FollowSets f = new FollowSets(syntax, nullAble,
205: new FirstSets(syntax, nullAble, nt));
206: String s = "T";
207: System.err.println("FOLLOW(" + s + ") = " + f.get(s));
208: } catch (Exception e) {
209: e.printStackTrace();
210: }
211: }
212:
213: }
|