KickJava   Java API By Example, From Geeks To Geeks.

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


1 package fri.patterns.interpreter.parsergenerator.parsertables;
2
3 import java.util.*;
4 import fri.util.collections.UniqueAggregatingHashtable;
5 import fri.patterns.interpreter.parsergenerator.Token;
6 import fri.patterns.interpreter.parsergenerator.syntax.*;
7
8 /**
9     Map of all FOLLOW-sets of a SLR syntax. Key is nonterminal.
10     <p>
11     The FOLLOW-set for a nonterminal is the collection of terminals that
12     can appear behind that nonterminal on the right side of all rules.
13     <p>
14     <b>Algorithm:</b><br>
15     Search all rules that contain the nonterminal on right side.
16     Scan for a terminal after the nonterminal on right side until found
17     or one scanned nonterminal is not nullable. The FIRST set of every
18     scanned nonterminal goes to the FOLLOW set. When reaching the end
19     without having found a terminal or a non-nullable nonterminal, even
20     the FOLLOW set of the nonterminal on the left side of that rule goes
21     to FOLLOW.
22
23     @author (c) 2000, Fritz Ritzberger
24 */

25
26 class FollowSets extends UniqueAggregatingHashtable
27 {
28     /**
29         Calculate FOLLOW-sets for all nonterminals contained in passed syntax.
30         The FOLLOW sets will then be Lists within a Map that provides the nonterminal
31         as key.
32         @param syntax the grammar
33         @param nullAble Map containing Boolean true when nonterminal (key) is nullable, else false.
34         @param firstSets ready-made FIRST sets for all nonterminals.
35     */

36     public FollowSets(Syntax syntax, Nullable nullAble, FirstSets firstSets)
37         throws ParserBuildException
38     {
39         // collect FOLLOW sets into a Hashtable where each nonterminal has a list of FOLLOW symbols
40
generateFollow(syntax, nullAble, firstSets);
41
42         // make a plain list from references to other FOLLOW sets
43
resolveSets();
44     }
45
46     private void generateFollow(Syntax syntax, Nullable nullAble, FirstSets firstSets) {
47         // The FOLLOW set of a nonterminal are all symbols that appear after the
48
// nonterminal on the right side of all rules. If the nonterminal stands
49
// at last position, add the FOLLOW set of the left side of this rule.
50

51         // loop across all syntax rules
52
for (int rulePos = 0; rulePos < syntax.size(); rulePos++) {
53             Rule rule = syntax.getRule(rulePos);
54             String JavaDoc nonterm = rule.getNonterminal(); // left side of derivation
55

56             if (rulePos == 0) { // START node, FOLLOW of start node is always epsilon
57
put(nonterm, Token.EPSILON);
58                 // first rule is made programmatically, add Epsilon to FOLLOW
59
put(rule.getRightSymbol(0), Token.EPSILON);
60             }
61             else {
62                 List nonterms = new ArrayList(); // collect receiving nonterminals
63

64                 for (int i = 0; i < rule.rightSize(); i++) {
65                     String JavaDoc symbol = rule.getRightSymbol(i);
66                     boolean isTerminal = Token.isTerminal(symbol);
67                     
68                     if (nonterms.size() > 0) { // if there are receivers (not at first element)
69
// add symbol to FOLLOW sets of all nonterminals in local list
70
List l;
71                         if (isTerminal) {
72                             l = new ArrayList();
73                             l.add(symbol); // terminal goes to FOLLOW set
74
}
75                         else {
76                             l = (List) firstSets.get(symbol); // FIRST(symbol) goes to FOLLOW set
77
}
78                         //System.err.println("rule "+rule+", adding to "+nonterms+" symbols "+v);
79
addToAllFollowSets(nonterms, l);
80                     }
81                     
82                     if (isTerminal || nullAble.isNullable(symbol) == false) { // if it is a terminal or can not be null
83
nonterms.clear(); // empty list of receiving nonterminals
84
}
85
86                     if (isTerminal == false) { // if it is a nonterminal
87
nonterms.add(symbol);
88                         
89                         if (i == rule.rightSize() - 1) { // at end
90
// add left side of rule to FOLLOW sets of all collected nonterminals
91
List l = new ArrayList();
92                             l.add(nonterm);
93                             addToAllFollowSets(nonterms, l);
94                         }
95                     }
96                 } // end for all symbols
97
} // end if rule position 0
98
} // end for, loop across rules
99
}
100
101     private void addToAllFollowSets(List nonterms, List symbols) {
102         for (int i = 0; i < nonterms.size(); i++) {
103             String JavaDoc nt = (String JavaDoc) nonterms.get(i);
104
105             for (int j = 0; j < symbols.size(); j++) {
106                 String JavaDoc s = (String JavaDoc) symbols.get(j);
107
108                 if (Nullable.isNull(s) == false) // do not add empty word
109
put(nt, s);
110             }
111         }
112     }
113
114
115     private void resolveSets()
116         throws ParserBuildException
117     {
118         // Make plain lists of mixed reference lists: all nonterminals are resolved to their terminal lists
119
for (Enumeration e = keys(); e.hasMoreElements(); ) {
120             String JavaDoc key = (String JavaDoc) e.nextElement();
121             //System.err.println("nonterminal "+key+" = "+get(key));
122
List newList = resolveSetSymbol(key, new Hashtable());
123             replace(key, newList);
124         }
125     }
126     
127     private List resolveSetSymbol(String JavaDoc nonterm, Map done)
128         throws ParserBuildException
129     {
130         if (done.get(nonterm) != null)
131             return null;
132         done.put(nonterm, nonterm); // avoid endless loops
133

134         List values = (List) get(nonterm);
135         List newList = new ArrayList(values.size() * 2);
136         
137         for (int j = 0; j < values.size(); j++) {
138             String JavaDoc symbol = (String JavaDoc) values.get(j);
139             
140             if (Token.isTerminal(symbol) == false) { // resolve nonterminal
141
try {
142                     List l = resolveSetSymbol(symbol, done);
143                     for (int i = 0; l != null && i < l.size(); i++) {
144                         String JavaDoc s = (String JavaDoc) l.get(i);
145                         if (newList.indexOf(s) < 0)
146                             newList.add(s);
147                     }
148                 }
149                 catch (Exception JavaDoc ex) {
150                     throw new ParserBuildException("FOLLOW set error: "+ex.getMessage()+" <- "+symbol);
151                 }
152             }
153             else { // add terminal
154
if (newList.indexOf(symbol) < 0)
155                     newList.add(symbol);
156             }
157         }
158         return newList;
159     }
160
161
162     /** Overridden to check for equality of key and value: Exception is thrown when so. */
163     public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
164         if (key.equals(value))
165             throw new IllegalArgumentException JavaDoc("Can not be FOLLOW of its own: key="+key+", value="+value);
166             
167         return super.put(key, value);
168     }
169
170
171
172     /** Test main */
173     public static void main(String JavaDoc [] args) {
174         List nt = new ArrayList();
175         nt.add("S"); nt.add("T"); nt.add("F"); nt.add("L");
176
177         List sx = new ArrayList();
178
179         List r = new ArrayList();
180         r.add("S"); r.add("E");
181         sx.add(r);
182
183         r = new ArrayList();
184         r.add("E"); r.add("T"); r.add("'*'"); r.add("F");
185         sx.add(r);
186
187         r = new ArrayList();
188         r.add("E"); r.add("T");
189         sx.add(r);
190
191         r = new ArrayList();
192         r.add("T"); r.add("F");
193         sx.add(r);
194
195         r = new ArrayList();
196         r.add("F"); r.add("'1'");
197         sx.add(r);
198
199         Syntax syntax = new Syntax(sx);
200         try {
201             Nullable nullAble = new Nullable(syntax, nt);
202             FollowSets f = new FollowSets(syntax, nullAble, new FirstSets(syntax, nullAble, nt));
203             String JavaDoc s = "T";
204             System.err.println("FOLLOW("+s+") = "+f.get(s));
205         }
206         catch (Exception JavaDoc e) {
207             e.printStackTrace();
208         }
209     }
210
211 }
Popular Tags