|
1
8
9 package net.sourceforge.chaperon.process.extended;
10
11 import net.sourceforge.chaperon.common.Decoder;
12 import net.sourceforge.chaperon.common.SortedCharSet;
13 import net.sourceforge.chaperon.common.StringSet;
14 import net.sourceforge.chaperon.model.extended.Definition;
15 import net.sourceforge.chaperon.model.extended.Element;
16 import net.sourceforge.chaperon.model.extended.ExtendedGrammar;
17 import net.sourceforge.chaperon.model.extended.Pattern;
18 import net.sourceforge.chaperon.model.extended.PatternIterator;
19 import net.sourceforge.chaperon.model.extended.PatternSet;
20
21 import org.apache.commons.logging.Log;
22
23 import java.util.HashMap  ;
24
25
31 public class ExtendedParserAutomaton
32 {
33 public State first = null;
35 private ExtendedGrammar grammar;
36 private Log log;
37
38 private String [] symbols;
40 private PatternSet[] firstSets;
41 private PatternSet[] lastSets;
42 private boolean[] nullable;
43 private HashMap definitions = new HashMap ();
44
45
49
55 public ExtendedParserAutomaton(ExtendedGrammar grammar)
56 {
57 this(grammar, null);
58 }
59
60
68 public ExtendedParserAutomaton(ExtendedGrammar grammar, Log log)
69 {
70 this.grammar = grammar;
71 this.log = log;
72
73 symbols = new String [grammar.getDefinitionCount()];
74 firstSets = new PatternSet[grammar.getDefinitionCount()];
75 lastSets = new PatternSet[grammar.getDefinitionCount()];
76 nullable = new boolean[grammar.getDefinitionCount()];
77 definitions = new HashMap ();
78
79 for (int i = 0; i<grammar.getDefinitionCount(); i++)
80 {
81 symbols[i] = grammar.getDefinition(i).getSymbol();
82 firstSets[i] = grammar.getDefinition(i).getFirstSet();
83 lastSets[i] = grammar.getDefinition(i).getLastSet();
84 nullable[i] = grammar.getDefinition(i).isNullable();
85
86 for (PatternIterator pattern = firstSets[i].getPattern(); pattern.hasNext();)
87 definitions.put(pattern.next(), grammar.getDefinition(i));
88
89 for (PatternIterator pattern = lastSets[i].getPattern(); pattern.hasNext();)
90 definitions.put(pattern.next(), grammar.getDefinition(i));
91 }
92
93 grammar.update();
94
95 addState(getStartState());
98
99 for (State state = first; state!=null; state = state.next)
100 {
101 SortedCharSet limits = new SortedCharSet();
104 StringSet nonterminals = new StringSet();
105 PatternSet gotoPattern = new PatternSet();
106
107 for (Item item = state.first; item!=null; item = item.next)
108 {
109 if (item.position==Item.SHIFT)
110 {
111 if (item.pattern.getSymbol()!=null)
112 nonterminals.addString(item.pattern.getSymbol());
113
114 limits.addChar(item.pattern.getLimits());
115 }
116 else if (item.position==Item.GOTO)
117 gotoPattern.addPattern(item.pattern);
118
119 limits.addChar(item.lookahead.getLimits());
120 }
121
122 if ((limits.getCharCount()>=1) && (limits.getChar(0)>'\u0000'))
127 {
128 addShiftAction(state, '\u0000', (char)(limits.getChar(0)-1));
129 addReduceAction(state, '\u0000', (char)(limits.getChar(0)-1));
130 }
131
132 for (int j = 0; j<limits.getCharCount(); j++)
134 {
135 if ((j>0) && ((limits.getChar(j)-limits.getChar(j-1))>1))
136 {
137 addShiftAction(state, (char)(limits.getChar(j-1)+1), (char)(limits.getChar(j)-1));
138 addReduceAction(state, (char)(limits.getChar(j-1)+1), (char)(limits.getChar(j)-1));
139 }
140
141 addShiftAction(state, limits.getChar(j), limits.getChar(j));
142 addReduceAction(state, limits.getChar(j), limits.getChar(j));
143 }
144
145 if (limits.getCharCount()>=1)
147 {
148 addShiftAction(state, (char)(limits.getChar(limits.getCharCount()-1)+1), '\u4000');
149 addReduceAction(state, (char)(limits.getChar(limits.getCharCount()-1)+1), '\u4000');
150 }
151
152 if (limits.getCharCount()==0)
154 {
155 addShiftAction(state, '\u0000', '\u4000');
156 addReduceAction(state, '\u0000', '\u4000');
157 }
158
159 for (int j = 0; j<nonterminals.getStringCount(); j++)
161 addGotoAction(state, nonterminals.getString(j));
162
163 for (PatternIterator pattern = gotoPattern.getPattern(); pattern.hasNext();)
164 addGotoAction(state, pattern.next());
165
166 addReduceAction(state);
167 }
168 }
169
170 private boolean isNullable(String symbol)
171 {
172 for (int i = 0; i<symbols.length; i++)
173 if (symbols[i].equals(symbol))
174 return nullable[i];
175
176 return true;
177 }
178
179 private String getSymbol(Pattern pattern)
180 {
181 return ((Definition)definitions.get(pattern)).getSymbol();
182 }
183
184
189 private State getStartState()
190 {
191 if (grammar.getStartSymbol()==null)
192 throw new IllegalArgumentException ("Start symbol is not defined");
193
194 PatternSet firstSet = grammar.getFirstSet();
195
196 System.out.println("firstset = "+firstSet);
197
198 State state = new State(grammar);
199
200 for (PatternIterator pattern = firstSet.getPattern(); pattern.hasNext();)
201 {
202 Pattern firstPattern = pattern.next();
203 Item item =
204 new Item(((Definition)definitions.get(firstPattern)).getSymbol(), firstPattern, Item.SHIFT,
205 null);
206
207 state.addItem(item);
209 }
210
211 closure(state);
212
213 return state;
214 }
215
216 public ExtendedGrammar getExtendedGrammar()
217 {
218 return grammar;
219 }
220
221
228 public State addState(State newState)
229 {
230 if (first==null)
231 {
232 first = newState;
233 return newState;
234 }
235
236 for (State state = first; state!=null; state = state.next)
237 {
238 if (state.equals(newState))
239 return state;
240
241 if (state.next==null)
242 {
243 state.next = newState;
244 return newState;
245 }
246 }
247
248 return newState;
249 }
250
251
259 public int indexOf(State foreignState)
260 {
261 int index = 0;
262 for (State state = first; state!=null; state = state.next, index++)
263 if (state.equals(foreignState))
264 return index;
265
266 return -1;
267 }
268
269
276 public boolean contains(State foreignState)
277 {
278 for (State state = first; state!=null; state = state.next)
279 if (state.equals(foreignState))
280 return true;
281
282 return false;
283 }
284
285 public void closure(State state)
286 {
287 System.out.println("=====================================\nbefore:\n"+state);
288 for (Item item = state.first; item!=null; item = item.next)
289 {
290 System.out.println("item = "+item+" position="+item.position+" element="+
291 (item.pattern instanceof Element));
292 if ((item.position==Item.SHIFT) && (item.pattern instanceof Element))
293 {
294 System.out.println("add firstset");
295
296 String symbol = ((Element)item.pattern).getSymbol();
297 System.out.println("pattern="+item.pattern);
298
299 Definition definition = ((Definition)definitions.get(item.pattern));
300 PatternSet firstSet = grammar.getFirstSet(symbol);
301 for (PatternIterator pattern = firstSet.getPattern(); pattern.hasNext();)
302 {
303 Pattern firstPattern = pattern.next();
304
305 if (definition.getLastSet().contains(item.pattern))
307 state.addItem(new Item(symbol, firstPattern, Item.SHIFT, item.lookahead));
308
309 for (PatternIterator lookaheads = item.pattern.getSuccessors(); lookaheads.hasNext();)
310 {
311 Pattern lookahead = lookaheads.next();
312 if (!(lookahead instanceof Element))
313 state.addItem(new Item(symbol, firstPattern, Item.SHIFT, lookahead));
314 }
315
316 for (PatternIterator lookaheads = item.pattern.getAscendingSuccessors();
317 lookaheads.hasNext();)
318 {
319 Pattern lookahead = lookaheads.next();
320 if (!(lookahead instanceof Element))
321 state.addItem(new Item(symbol, firstPattern, Item.SHIFT, lookahead));
322 }
323 }
324 }
325 }
326
327 System.out.println("after:\n"+state+"\n");
328 }
329
330 private void addShiftAction(State state, char minimum, char maximum)
331 {
332 State newState = new State(grammar);
333 for (Item item = state.first; item!=null; item = item.next)
334 if ((item.position==Item.SHIFT) && (item.pattern.contains(minimum, maximum)))
335 {
336 newState.addItem(item.getFollowItem());
337
338 for (PatternIterator successors = item.pattern.getSuccessors(); successors.hasNext();)
339 newState.addItem(new Item(item.pattern, successors.next(), Item.SHIFT, item.lookahead));
340 }
341
342 if (!newState.isEmpty())
343 {
344 closure(newState);
345 newState = addState(newState);
346
347 state.addShiftAction(minimum, maximum, newState);
349 }
350 }
351
352 private void addGotoAction(State state, String symbol)
353 {
354 State newState = new State(grammar);
355 for (Item item = state.first; item!=null; item = item.next)
356 if ((item.position==Item.SHIFT) && (item.pattern instanceof Element) &&
357 (((Element)item.pattern).getSymbol().equals(symbol)))
358 {
359 newState.addItem(item.getFollowItem());
360
361 for (PatternIterator successors = item.pattern.getSuccessors(); successors.hasNext();)
362 newState.addItem(new Item(item.pattern, successors.next(), Item.SHIFT, item.lookahead));
363 }
364
365 if (!newState.isEmpty())
366 {
367 closure(newState);
368 newState = addState(newState);
369 state.addGotoAction(symbol, newState);
370 }
371 }
372
373 private void addGotoAction(State state, Pattern pattern)
374 {
375 State newState = new State(grammar);
376 for (Item item = state.first; item!=null; item = item.next)
377 if ((item.position==Item.GOTO) && (item.pattern==pattern))
378 newState.addItem(item.getFollowItem());
379
380 if (!newState.isEmpty())
381 {
382 closure(newState);
383 newState = addState(newState);
384 state.addGotoAction(pattern, newState);
385 }
386 }
387
388 private void addReduceAction(State state, char minimum, char maximum)
389 {
390 for (Item item = state.first; item!=null; item = item.next)
391 if (item.position==Item.SHIFT)
392 {
393 for (PatternIterator successors = item.pattern.getDescendingSuccessors();
394 successors.hasNext();)
395 if (successors.next().contains(minimum, maximum))
396 if ((item.pattern.getSymbol()!=null) && (isNullable(item.pattern.getSymbol())))
397 {
398 state.addLookaheadReduceAction(minimum, maximum, item.pattern.getSymbol(), 0);
399 break;
400 }
401 }
402 else if (item.position==Item.GOTO)
403 {
404 for (int k = 0; k<lastSets.length; k++)
405 if (lastSets[k].contains(item.pattern))
406 {
407 for (PatternIterator successors = item.pattern.getDescendingSuccessors();
408 successors.hasNext();)
409 if (successors.next().contains(minimum, maximum))
410 {
411 state.addLookaheadReduceAction(minimum, maximum, item.pattern, 0);
412
413 break;
414 }
415 }
416 }
417 else if (item.position==Item.REDUCE)
418 {
419 for (PatternIterator successors = item.pattern.getDescendingSuccessors();
420 successors.hasNext();)
421 if (successors.next().contains(minimum, maximum))
422 {
423 if (item.symbol!=null)
424 state.addLookaheadReduceAction(minimum, maximum, item.symbol, 2);
425 else
426 state.addLookaheadReduceAction(minimum, maximum, item.previous, 2);
427
428 break;
429 }
430 }
431 }
432
433 private void addReduceAction(State state)
434 {
435 for (Item item = state.first; item!=null; item = item.next)
436 if (item.position==Item.SHIFT)
437 {
438 if (grammar.getLastSet().contains(item.pattern))
439 if ((item.pattern instanceof Element) &&
440 (isNullable(((Element)item.pattern).getSymbol())))
441 state.addReduceAction(((Element)item.pattern).getSymbol(), 0);
442 }
443 else if (item.position==Item.GOTO)
444 {
445 for (int k = 0; k<lastSets.length; k++)
446 if (lastSets[k].contains(item.pattern))
447 {
448 if (grammar.getLastSet().contains(item.pattern))
449 state.addReduceAction(item.pattern, 0);
450 }
451 }
452 else if (item.position==Item.REDUCE)
453 {
454 if (grammar.getLastSet().contains(item.pattern))
455 {
456 if (item.symbol!=null)
457 state.addReduceAction(item.symbol, 2);
458 else
459 state.addReduceAction(item.previous, 2);
460 }
461 }
462 }
463
464
469 public String toString()
470 {
471 StringBuffer buffer = new StringBuffer ();
472
473 for (State state = first; state!=null; state = state.next)
474 {
475 buffer.append("State ");
476 buffer.append(indexOf(state));
477 buffer.append(":\n");
478 buffer.append(state.toString());
479
480 ShiftAction[] shiftActions = state.getShiftActions();
483 for (int index = 0; index<shiftActions.length; index++)
484 {
485 buffer.append("Shift ");
486 buffer.append(Decoder.toClass(shiftActions[index].minimum, shiftActions[index].maximum));
487 buffer.append(" -> State ");
488 buffer.append(indexOf(shiftActions[index].state));
489 buffer.append("\n");
490 }
491
492 LookaheadReduceAction[] lookaheadReduceActions = state.getLookaheadReduceActions();
493 for (int index = 0; index<lookaheadReduceActions.length; index++)
494 {
495 buffer.append("Reduce ");
496
497 if (lookaheadReduceActions[index].symbol!=null)
498 buffer.append(lookaheadReduceActions[index].symbol);
499 else
500 buffer.append(lookaheadReduceActions[index].pattern);
501
502 buffer.append(" for ");
503 buffer.append(Decoder.toClass(lookaheadReduceActions[index].minimum,
504 lookaheadReduceActions[index].maximum));
505
506 buffer.append("\n");
507 }
508
509 ReduceAction[] reduceActions = state.getReduceActions();
510 for (int index = 0; index<reduceActions.length; index++)
511 {
512 buffer.append("Reduce ");
513
514 if (reduceActions[index].symbol!=null)
515 buffer.append(reduceActions[index].symbol);
516 else
517 buffer.append(reduceActions[index].pattern);
518
519 buffer.append("\n");
520 }
521
522 GotoAction[] gotoactions = state.getGotoActions();
523 for (int index = 0; index<gotoactions.length; index++)
524 {
525 buffer.append("Goto ");
526
527 if (gotoactions[index].symbol!=null)
528 buffer.append(gotoactions[index].symbol);
529 else
530 buffer.append(gotoactions[index].pattern);
531
532 buffer.append(" -> State ");
533 buffer.append(indexOf(gotoactions[index].state));
534 buffer.append("\n");
535 }
536
537 buffer.append("\n");
538 }
539
540 return buffer.toString();
541 }
542 }
543 |
Popular Tags |
Java API By Example, From Geeks To Geeks.