|
1
8
9 package net.sourceforge.chaperon.build;
10
11 import net.sourceforge.chaperon.build.conflict.ConflictList;
12 import net.sourceforge.chaperon.build.conflict.ReduceReduceConflict;
13 import net.sourceforge.chaperon.build.conflict.ShiftReduceConflict;
14 import net.sourceforge.chaperon.common.IntegerSet;
15 import net.sourceforge.chaperon.model.Violations;
16 import net.sourceforge.chaperon.model.grammar.Associativity;
17 import net.sourceforge.chaperon.model.grammar.Error;
18 import net.sourceforge.chaperon.model.grammar.Grammar;
19 import net.sourceforge.chaperon.model.symbol.SymbolSet;
20 import net.sourceforge.chaperon.model.symbol.Terminal;
21 import net.sourceforge.chaperon.process.ParserAutomaton;
22
23 import org.apache.commons.logging.Log;
24
25
31 public class ParserAutomatonBuilder
32 {
33 private static final EndOfFile EOF = new EndOfFile();
34 private Grammar grammar;
35 private SymbolSet tsymbols;
36 private SymbolSet ntsymbols;
37 private FirstSetCollection firstsets;
38 private ItemSetCollection itemsets;
39 private ParserAutomaton automaton;
40 private ConflictList conflicts = new ConflictList();
41 private Log log;
42
43
48 public ParserAutomatonBuilder(Grammar grammar)
49 {
50 this(grammar, null);
51 }
52
53
59 public ParserAutomatonBuilder(Grammar grammar, Log log)
60 {
61 this.grammar = (Grammar)grammar.clone();
62 this.log = log;
63
64 Violations violations = grammar.validate();
65
66 if ((violations!=null) && (violations.getViolationCount()>0))
67 throw new IllegalArgumentException  ("Grammar is not valid: "+violations.getViolation(0));
68
69 SymbolSet symbols = grammar.getSymbols();
70
71 tsymbols = symbols.getTerminals();
72 ntsymbols = symbols.getNonterminals();
73
74 if ((log!=null) && (log.isDebugEnabled()))
77 log.debug("Generating first sets");
78
79 firstsets = new FirstSetCollection(grammar, log);
80 if ((log!=null) && (log.isDebugEnabled()))
81 log.debug(firstsets.toString());
82
83 if ((log!=null) && (log.isDebugEnabled()))
85 log.debug("Building states and transitions");
86
87 itemsets = new ItemSetCollection(grammar, firstsets, log);
88 if ((log!=null) && (log.isDebugEnabled()))
89 log.debug(itemsets.toString());
90
91 if ((log!=null) && (log.isDebugEnabled()))
92 log.debug("Building parser automaton");
93
94 automaton =
95 new ParserAutomaton(tsymbols.getSymbolCount(), ntsymbols.getSymbolCount(),
96 grammar.getProductionCount(), 0, itemsets.getItemSetCount());
97
98 for (int i = 0; i<tsymbols.getSymbolCount(); i++)
100 automaton.setTerminal(i, tsymbols.getSymbol(i).getName());
101
102 for (int i = 0; i<ntsymbols.getSymbolCount(); i++)
104 automaton.setNonterminal(i, ntsymbols.getSymbol(i).getName());
105
106 for (int i = 0; i<grammar.getProductionCount(); i++)
108 {
109 automaton.setProductionSymbol(i, ntsymbols.indexOf(grammar.getProduction(i).getSymbol()));
110 automaton.setProductionLength(i, grammar.getProduction(i).getLength());
111 }
112
113 for (int state = 0; state<itemsets.getItemSetCount(); state++)
115 {
116 ItemSet I = itemsets.getItemSet(state);
117
118 SymbolSet shiftsymbols = I.getShiftSymbols(); SymbolSet reducesymbols = I.getReduceSymbols();
121 for (int symbol = 0; symbol<tsymbols.getSymbolCount(); symbol++)
122 {
123 IntegerSet reduceproductions = I.getReduceProductions(tsymbols.getSymbol(symbol));
124 int productionpriority = -1;
125 int highestproduction = -1;
126 for (int k = 0; k<reduceproductions.getCount(); k++)
127 {
128 ReduceReduceConflict reduceconflict = null;
129
130 if (k>0)
131 {
132 reduceconflict =
133 new ReduceReduceConflict(grammar, itemsets, state,
134 (Terminal)tsymbols.getSymbol(symbol),
135 reduceproductions.get(k-1), reduceproductions.get(k));
136
137 conflicts.addConflict(reduceconflict);
138 }
139
140 if (grammar.getPriority(grammar.getProduction(reduceproductions.get(k)))>productionpriority)
141 {
142 highestproduction = reduceproductions.get(k);
143 productionpriority = grammar.getPriority(grammar.getProduction(highestproduction));
144
145 if ((log!=null) && (reduceconflict!=null))
146 log.info(reduceconflict.toString());
147 }
148 else if (grammar.getPriority(grammar.getProduction(reduceproductions.get(k)))==productionpriority)
149 {
150 if (log!=null)
151 log.warn(reduceconflict.toString());
152 }
153 }
154
155 if (reduceproductions.getCount()>1)
156 if ((log!=null) && (log.isInfoEnabled()))
157 log.info("The parser will reduce the production "+
158 grammar.getProduction(highestproduction));
159
160 boolean errorreduce = reducesymbols.contains(Error.instance);
161
162 if (shiftsymbols.contains(tsymbols.getSymbol(symbol)))
163 {
164 if ((errorreduce) || (reducesymbols.contains(tsymbols.getSymbol(symbol))))
165 {
166 int tokenpriority = grammar.getPriority((Terminal)tsymbols.getSymbol(symbol));
167
168 ShiftReduceConflict shiftconflict =
169 new ShiftReduceConflict(grammar, itemsets, state,
170 (Terminal)tsymbols.getSymbol(symbol), highestproduction);
171
172 if (tokenpriority>productionpriority)
173 {
174 automaton.setShiftAction(state, symbol, I.getTransition(tsymbols.getSymbol(symbol)));
175
176 if (log!=null)
177 {
178 log.info(shiftconflict.toString());
179 log.info("The parser will shift");
180 }
181 }
182 else if (tokenpriority<productionpriority)
183 {
184 automaton.setReduceAction(state, symbol, highestproduction);
185
186 if (log!=null)
187 {
188 log.info(shiftconflict.toString());
189 log.info("The parser will reduce");
190 }
191 }
192 else
193 {
194 if (log!=null)
195 log.warn(shiftconflict.toString());
196
197 Associativity associativity =
198 grammar.getAssociativity((Terminal)tsymbols.getSymbol(symbol));
199 if (associativity.equals(Associativity.RIGHT))
200 {
201 automaton.setShiftAction(state, symbol, I.getTransition(tsymbols.getSymbol(symbol)));
203
204 if (log!=null)
205 log.warn("The parser will shift");
206 }
207 else if (associativity.equals(Associativity.LEFT))
208 {
209 automaton.setReduceAction(state, symbol, highestproduction);
211
212 if (log!=null)
213 log.warn("The parser will reduce");
214 }
215 else
216 {
217 automaton.setShiftAction(state, symbol, I.getTransition(tsymbols.getSymbol(symbol)));
219
220 if (log!=null)
221 log.warn("The parser will shift");
222 }
223 }
224 }
225 else
226 automaton.setShiftAction(state, symbol, I.getTransition(tsymbols.getSymbol(symbol)));
227 }
228 else if ((errorreduce) || (reducesymbols.contains(tsymbols.getSymbol(symbol))))
229 automaton.setReduceAction(state, symbol, highestproduction);
230 else
231 for (int i = 0; i<shiftsymbols.getSymbolCount(); i++)
232 if (shiftsymbols.getSymbol(i) instanceof Error )
233 automaton.setErrorAction(state, symbol, I.getTransition(shiftsymbols.getSymbol(i)));
234 }
235
236 if (reducesymbols.contains(EOF))
238 {
239 IntegerSet reduceproductions = I.getReduceProductions(EOF);
240 int productionpriority = -1;
241 int highestproduction = -1;
242 for (int k = 0; k<reduceproductions.getCount(); k++)
243 {
244 if (grammar.getPriority(grammar.getProduction(reduceproductions.get(k)))>productionpriority)
245 {
246 highestproduction = reduceproductions.get(k);
247 productionpriority = grammar.getPriority(grammar.getProduction(highestproduction));
248 }
249 }
250
251 if ((grammar.getProduction(highestproduction).getSymbol().equals(grammar.getStartSymbol())))
252 automaton.setAcceptAction(state, highestproduction);
253 else
254 automaton.setReduceAction(state, highestproduction);
255 }
256 else
257 for (int i = 0; i<shiftsymbols.getSymbolCount(); i++)
258 if (shiftsymbols.getSymbol(i) instanceof Error )
259 automaton.setErrorAction(state, I.getTransition(shiftsymbols.getSymbol(i)));
260
261 for (int symbol = 0; symbol<ntsymbols.getSymbolCount(); symbol++)
263 if (shiftsymbols.contains(ntsymbols.getSymbol(symbol)))
264 automaton.setTransition(state, symbol, I.getTransition(ntsymbols.getSymbol(symbol)));
265 }
266
267 if ((log!=null) && (log.isDebugEnabled()))
268 log.debug("Parser automaton:\n"+automaton.toString());
269 }
270
271
276 public ParserAutomaton getParserAutomaton()
277 {
278 return automaton;
279 }
280 }
281 |
Popular Tags |
Java API By Example, From Geeks To Geeks.