KickJava   Java API By Example, From Geeks To Geeks.

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


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 FIRST-set for a nonterminal is the collection of terminals that
12     appear on first position of the right side of all rules where that
13     nonterminal appears on the left side.
14     <p>
15     <b>Algorithm:</b><br>
16     Search all rules that contain the nonterminal on left side.
17     Scan the right side of all these rules until a terminal or a non-nullable
18     nonterminal appears. The terminal goes to FIRST, the FIRST sets of
19     all scanned nonterminals go to FIRST. This implies that one must
20     collect FIRST sets recursively, for every scanned nonterminal.
21
22     @author (c) 2000, Fritz Ritzberger
23 */

24
25 class FirstSets extends UniqueAggregatingHashtable
26 {
27     /**
28         Calculate Map of FIRST sets of all nonterminals contained in syntax.
29         The FIRST sets will then be lists within this Map that provides the
30         nonterminal as key.
31         @param syntax the grammar to scan.
32         @param nullAble Map containing Boolean true or false for nullability of every nonterminal.
33         @param nonterminals pre-built list of nonterminals
34     */

35     public FirstSets(Syntax syntax, Nullable nullAble, List nonterminals)
36         throws ParserBuildException
37     {
38         // collect FIRST sets into this Hashtable where each
39
// nonterminal has a List of FIRST-symbols
40
Map done = new Hashtable(nonterminals.size()); // avoid recursion
41
for (int i = 0; i < nonterminals.size(); i++) {
42             String JavaDoc nonterm = (String JavaDoc) nonterminals.get(i);
43             generateFirstSet(syntax, nullAble, nonterm, done);
44         }
45     }
46
47     private void generateFirstSet(Syntax syntax, Nullable nullAble, String JavaDoc nonterminal, Map done)
48         throws ParserBuildException
49     {
50         if (get(nonterminal) != null)
51             return; // alreay done
52

53         if (done.get(nonterminal) != null)
54             return;
55         done.put(nonterminal, nonterminal); // avoid endless loops
56
//System.err.println("generateFirstSet("+nonterminal+")");
57

58         // The FIRST set of a nonterminal are all symbols
59
// that are on first position of the right side of all rules
60
// where the nonterminal is on the left side.
61
for (int k = 0; k < syntax.size(); k++) {
62             Rule rule = syntax.getRule(k);
63             String JavaDoc nonterm = rule.getNonterminal(); // left side of derivation
64

65             if (nonterminal.equals(nonterm)) { // this rule derives the nonterminal
66
// if left side is empty, add NULL to FIRST of nonterminal
67
if (rule.rightSize() <= 0) {
68                     put(nonterm, Nullable.NULL);
69                 }
70                 else { // there are symbols on left side
71
boolean nullable = true; // enable loop until nullable
72

73                     // While nullable, add the symbol, shift to the next and
74
// check if it is nullable again.
75
for (int i = 0; nullable && i < rule.rightSize(); i++) {
76                         String JavaDoc symbol = rule.getRightSymbol(i);
77                         
78                         nullable = false; // assume it is a terminal
79

80                         if (Token.isTerminal(symbol)) {
81                             put(nonterm, symbol);
82                         }
83                         else {
84                             // If there is a nonterminal on first position, add its FIRST set
85
// FIRST set of this nonterminal, but without null-word.
86
try {
87                                 generateFirstSet(syntax, nullAble, symbol, done); // enter recursion
88

89                                 List list = (List) get(symbol); // get the results
90
for (int j = 0; list != null && j < list.size(); j++) {
91                                     String JavaDoc s = (String JavaDoc) list.get(j);
92                                     put(nonterm, s);
93                                 }
94
95                                 nullable = nullAble.isNullable(symbol);
96                             }
97                             catch (Exception JavaDoc ex) {
98                                 throw new ParserBuildException(ex.getMessage()+" <- "+nonterm);
99                             }
100                         } // end if terminal
101
} // end for all symbols of rule
102

103                     // If the last added symbol is the last of the rule and
104
// is a nonterminal and is nullable, add null to FIRST set.
105
//if (nullable) {
106
// Sets.addToSets(this, nonterm, Nullable.NULL);
107
//}
108

109                 } // end if rule size > 1
110
} // end for al rules of syntax
111
}
112     }
113
114     /** Overridden to check for equality of key and value: Exception is thrown when so. */
115     public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
116         if (key.equals(value))
117             throw new IllegalArgumentException JavaDoc("Can not be FIRST of its own: key="+key+", value="+value);
118             
119         return super.put(key, value);
120     }
121
122
123
124     /** Test main */
125     public static void main(String JavaDoc [] args) {
126         // nonterminals
127
List nonterm = new ArrayList();
128         nonterm.add("S"); nonterm.add("T"); nonterm.add("F"); nonterm.add("L");
129
130         // rules
131
List sx = new ArrayList();
132
133         List r = new ArrayList();
134         r.add("S"); r.add("T"); r.add("'*'"); r.add("F");
135         sx.add(r);
136
137         r = new ArrayList();
138         r.add("S"); r.add("T");
139         sx.add(r);
140
141         r = new ArrayList();
142         r.add("T"); r.add("F");
143         sx.add(r);
144
145         /* test empty derivation */
146         r = new ArrayList();
147         r.add("F");
148         sx.add(r);
149
150         r = new ArrayList();
151         r.add("F");
152         r.add("'1'");
153         sx.add(r);
154
155         Syntax syntax = new Syntax(sx);
156         try {
157             FirstSets f = new FirstSets(syntax, new Nullable(syntax, nonterm), nonterm);
158             String JavaDoc s = "S";
159             System.err.println("FIRST("+s+") = "+f.get(s));
160         }
161         catch (Exception JavaDoc e) {
162             e.printStackTrace();
163         }
164     }
165
166 }
Popular Tags