KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > beaver > comp > Action


1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2  * This file is part of Beaver Parser Generator. *
3  * Copyright (C) 2003,2004 Alexander Demenchuk <alder@softanvil.com>. *
4  * All rights reserved. *
5  * See the file "LICENSE" for the terms and conditions for copying, *
6  * distribution and modification of Beaver. *
7  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

8
9 package beaver.comp;
10
11 import java.util.Arrays JavaDoc;
12 import java.util.Comparator JavaDoc;
13
14 import beaver.comp.util.BitSet;
15 import beaver.comp.util.Log;
16 import beaver.spec.Grammar;
17 import beaver.spec.GrammarSymbol;
18 import beaver.spec.NonTerminal;
19 import beaver.spec.Production;
20 import beaver.spec.Terminal;
21
22 /**
23  * This class abstracts an action that is performed by an automaton when it's in some state and
24  * a specified symbol has arrived.
25  */

26 class Action
27 {
28     static final Comparator JavaDoc LOOKAHEAD_ID_COMPARATOR = new Comparator JavaDoc()
29     {
30         public int compare(Object JavaDoc o1, Object JavaDoc o2)
31         {
32             return ((Action) o1).lookahead.id - ((Action) o2).lookahead.id;
33         }
34     };
35     
36     /**
37      * Action types
38      */

39     static class Type
40     {
41         static class Conflict extends Type
42         {
43             static class ShiftReduce extends Conflict
44             {
45                 ShiftReduce(Shift shift_act, Reduce reduce_act, State state, String JavaDoc reason)
46                 {
47                     super("shift-reduce", makeDescription(shift_act, reduce_act, state, reason));
48                 }
49                 
50                 static private String JavaDoc makeDescription(Shift shift_act, Reduce reduce_act, State state, String JavaDoc reason)
51                 {
52                     StringBuffer JavaDoc text = new StringBuffer JavaDoc(256)
53                         .append("\n\tshift ")
54                         .append(shift_act.lookahead.name)
55                         .append(" in:");
56                     for (Configuration conf = state.conf_set.first_conf; conf != null; conf = conf.next)
57                     {
58                         if (conf.dot < conf.rule.rhs.items.length && conf.rule.rhs.items[conf.dot].symbol == shift_act.lookahead)
59                         {
60                             text.append("\n\t\t").append(conf);
61                         }
62                     }
63                     text.append("\n\tor reduce:\n\t\t")
64                         .append(reduce_act.rule.toString());
65                     int line = reduce_act.rule.getFirstLine();
66                     if (line > 0)
67                     {
68                         text.append(" @ ").append(line);
69                     }
70                     text.append("\n\t- ")
71                         .append(reason);
72                     
73                     return text.toString();
74                 }
75             }
76             
77             static class ReduceReduce extends Conflict
78             {
79                 ReduceReduce(Reduce act1, Reduce act2, State state, String JavaDoc reason)
80                 {
81                     super("reduce-reduce", makeDescription(act1, act2, state, reason));
82                 }
83                 
84                 static private String JavaDoc makeDescription(Reduce act1, Reduce act2, State state, String JavaDoc reason)
85                 {
86                     StringBuffer JavaDoc text = new StringBuffer JavaDoc(256)
87                         .append("\n\treduce\t")
88                         .append(act1.rule);
89                     int line;
90                     if ((line = act1.rule.getFirstLine()) > 0)
91                         text.append(" @ ").append(line);
92                     text.append("\n\tor\t")
93                         .append(act2.rule);
94                     if ((line = act2.rule.getFirstLine()) > 0)
95                         text.append(" @ ").append(line);
96                     text.append("\n\ton ")
97                         .append(act1.lookahead.name)
98                         .append(" - ")
99                         .append(reason);
100                     return text.toString();
101                 }
102             }
103             
104             private String JavaDoc descr;
105             
106             Conflict(String JavaDoc type, String JavaDoc details)
107             {
108                 super(0, type + " conflict");
109                 descr = details;
110             }
111             
112             public String JavaDoc toString()
113             {
114                 return new StringBuffer JavaDoc(super.toString().length() + 2 + descr.length())
115                     .append(super.toString())
116                     .append(": ")
117                     .append(descr)
118                     .toString();
119             }
120         }
121         
122         static final Type SHIFT = new Type(1, "SHIFT");
123         static final Type REDUCE = new Type(2, "REDUCE");
124         static final Type ACCEPT = new Type(3, "ACCEPT");
125         static final Type RESOLVED = new Type(-1, "RESOLVED");
126         static final Type NOT_USED = new Type(-2, "NOT USED");
127
128         private int id;
129         private String JavaDoc name;
130
131         Type(int id, String JavaDoc name)
132         {
133             this.id = id;
134             this.name = name;
135         }
136
137         boolean isRemovable()
138         {
139             return id < 0;
140         }
141
142         boolean isResolved()
143         {
144             return id <= 0;
145         }
146
147         public String JavaDoc toString()
148         {
149             return name;
150         }
151     }
152
153     /**
154      * SHIFT action
155      */

156     static class Shift extends Action
157     {
158         State state;
159
160         Shift(GrammarSymbol lookahead, State state)
161         {
162             super(Type.SHIFT, lookahead);
163             this.state = state;
164         }
165
166         /**
167          * Tries to resolve a shift-reduce conflict using terminal/production precedence and associativity.
168          *
169          * @param act action that conflicts with this one
170          * @return true if conflict has been resolved
171          */

172         boolean resolveConflict(Action act, State act_state, Log log)
173         {
174             if (!(act instanceof Reduce))
175                 throw new IllegalArgumentException JavaDoc("shift-reduce expected, \"" + act + "\" found");
176             
177             Reduce reduce_act = (Reduce) act;
178             Terminal reduce_prec_sym = reduce_act.rule.prec_sym;
179
180             if (this.lookahead instanceof NonTerminal)
181             {
182                 act.type = new Type.Conflict.ShiftReduce(this, reduce_act, act_state, lookahead.name + " is a non-terminal");
183                 return false;
184             }
185             Terminal shift_prec_sym = (Terminal) this.lookahead;
186
187             if (shift_prec_sym.prec > reduce_prec_sym.prec)
188             {
189                 if (reduce_prec_sym.prec < 0)
190                 {
191                     log.warning("Resolved Shift-Reduce conflict by selecting (" + this.toString() + ") over (" + act.toString() + ") using precedence.");
192                 }
193                 act.type = Type.RESOLVED;
194                 return true;
195             }
196             if (shift_prec_sym.prec < reduce_prec_sym.prec)
197             {
198                 if (shift_prec_sym.prec < 0)
199                 {
200                     log.warning("Resolved Shift-Reduce conflict by selecting (" + act.toString() + ") over (" + this.toString() + ") using precedence.");
201                 }
202                 this.type = Type.RESOLVED;
203                 return true;
204             }
205             //
206
// here shift_prec_sym.prec == reduce_prec_sym.prec
207
//
208
if (shift_prec_sym.assoc == Terminal.Associativity.RIGHT)
209             {
210                 act.type = Type.RESOLVED;
211                 return true;
212             }
213             if (shift_prec_sym.assoc == Terminal.Associativity.LEFT)
214             {
215                 this.type = Type.RESOLVED;
216                 return true;
217             }
218
219             act.type = new Type.Conflict.ShiftReduce(this, reduce_act, act_state, shift_prec_sym.prec > 0 ? lookahead.name + " is nonassociative" : "insufficient precedence information");
220             return false;
221         }
222
223         /**
224          * @return state ID - always a positive number in the [1..N_states] range
225          */

226         short getId()
227         {
228             return (short) state.id;
229         }
230
231         public String JavaDoc toString()
232         {
233             return lookahead + ": " + type + "; goto " + state.id;
234         }
235     }
236
237     /**
238      * REDUCE actions
239      */

240     static class Reduce extends Action
241     {
242         /**
243          * An instance of this class creates REDUCE actions for configurations with the "dot"
244          * after the last RHS symbol.
245          */

246         static class Maker extends BitSet.Processor
247         {
248             Terminal[] terminals;
249             State state;
250             Production rule;
251
252             Maker(Terminal[] terminals, State first_state)
253             {
254                 this.terminals = terminals;
255                 this.state = first_state;
256             }
257
258             /**
259              * Adds all of the reduce actions.
260              * <p/>
261              * A reduce action is added for each element of the lookaheads set of a configuration
262              * which has its "dot" at the extreme right.
263              */

264             void buildReduceActions()
265             {
266                 for (; state != null; state = state.next)
267                 {
268                     for (Configuration conf = state.conf_set.first_conf; conf != null; conf = conf.next)
269                     {
270                         if (conf.dot == conf.rule.rhs.items.length)
271                         {
272                             rule = conf.rule;
273                             conf.lookaheads.forEachElementRun(this);
274                         }
275                     }
276                 }
277             }
278
279             /**
280              * Creates REDUCE actions for each lookahead symbol of the "complete" production configuration.
281              *
282              * @param index index of the terminal
283              */

284             protected void process(int index)
285             {
286                 state.actions.add(new Reduce(terminals[index], rule));
287             }
288         }
289
290         Production rule;
291
292         Reduce(Terminal lookahead, Production rule)
293         {
294             super(Type.REDUCE, lookahead);
295             this.rule = rule;
296         }
297
298         /**
299          * Tries to resolve a reduce-reduce conflict using production precedence and associativity.
300          *
301          * @param act action that conflicts with this one
302          * @return true if conflict has been resolved
303          */

304         boolean resolveConflict(Action act, State act_state, Log log)
305         {
306             if (!(act instanceof Reduce))
307                 throw new IllegalArgumentException JavaDoc("reduce-reduce expected");
308
309             Terminal my_prec_sym = rule.prec_sym;
310             Reduce reduce_act = (Reduce) act;
311             Terminal act_prec_sym = reduce_act.rule.prec_sym;
312
313             if (my_prec_sym.prec > act_prec_sym.prec)
314             {
315                 act.type = Type.RESOLVED;
316                 return true;
317             }
318             if (my_prec_sym.prec < act_prec_sym.prec)
319             {
320                 this.type = Type.RESOLVED;
321                 return true;
322             }
323             // else my_prec_sym.prec == act_prec_sym.prec
324
act.type = new Type.Conflict.ReduceReduce(this, reduce_act, act_state, "equal precedence");
325             return false;
326         }
327
328         /**
329          * @return a negative number, which complement is a rule ID
330          */

331         short getId()
332         {
333             return (short) ~rule.id;
334         }
335
336         public String JavaDoc toString()
337         {
338             return lookahead != null ? lookahead + ": " + type + " " + rule : "[any]: REDUCE " + rule;
339         }
340     }
341
342     /**
343      * ACCEPT action
344      */

345     static class Accept extends Action
346     {
347         private short id;
348
349         Accept(Grammar grammar)
350         {
351             super(Type.ACCEPT, grammar.goal_symbol);
352             id = (short) ~ grammar.rules.length;
353         }
354
355         /**
356          * @return a negative number which does not match any REDUCE action
357          */

358         short getId()
359         {
360             return id;
361         }
362     }
363
364     /**
365      * Instances of this class represent linked lists of actions in a state.
366      */

367     static class List
368     {
369         static final Comparator JavaDoc NUM_ACTIONS_CMP = new Comparator JavaDoc()
370         {
371             public int compare(Object JavaDoc o1, Object JavaDoc o2)
372             {
373                 return ((Action.List) o2).num_actions - ((Action.List) o1).num_actions;
374             }
375         };
376         
377         State state;
378         Action first;
379         Action last;
380         int num_actions;
381
382         List(State state)
383         {
384             this.state = state;
385         }
386
387         void add(Action act)
388         {
389             if (last == null)
390                 last = first = act;
391             else
392                 last = last.next = act;
393             num_actions++;
394         }
395
396         /**
397          * Tries to resolve shift-reduce and reduce-reduce conflicts by delegating actual resolution to
398          * either Shift or Reduce actions. If the conflict is resolved one of the two conflicting actions
399          * will be marked as RESOLVED and removed at the end.
400          * <p/>
401          * Note: that the process that build this list initially guarantees that SHIFTs always go before
402          * REDUCEs.
403          *
404          * @param log Logger that will accept conflict reports
405          *
406          * @return number of unresolved conflicts
407          */

408         int resolveConflicts(Log log)
409         {
410             int num_conflicts = 0;
411             if (first != null && num_actions > 1)
412             {
413                 for (Action act = first; act != last; act = act.next)
414                 {
415                     if (!act.type.isResolved())
416                     {
417                         for (Action cmp = act.next; cmp != null; cmp = cmp.next)
418                         {
419                             if (cmp.lookahead == act.lookahead && !act.resolveConflict(cmp, state, log))
420                             {
421                                 num_conflicts++;
422                             }
423                         }
424                     }
425                 }
426                 removeResolvedActions();
427             }
428             return num_conflicts;
429         }
430         
431         void reportConflicts(Log log)
432         {
433             if (first != null && num_actions > 1)
434             {
435                 for (Action act = first; act != null; act = act.next)
436                 {
437                     if (act.type instanceof Type.Conflict)
438                     {
439                         log.error(act.type.toString());
440                     }
441                 }
442             }
443         }
444
445         private void removeResolvedActions()
446         {
447             while (first != null && first.type.isRemovable())
448             {
449                 first = first.next;
450                 num_actions--;
451             }
452             last = first;
453             for (Action next = first.next; next != null; next = next.next)
454             {
455                 if (next.type.isRemovable())
456                 {
457                     num_actions--;
458                 }
459                 else
460                 {
461                     last = last.next = next;
462                 }
463             }
464             last.next = null;
465         }
466
467         /**
468          * Marked productions attached to REDUCE rules as "reducible". Prepares assertion check that
469          * all productions in the grammar are reducible (it's an error if some are not).
470          */

471         void markReducibleProductions()
472         {
473             for (Action act = first; act != null; act = act.next)
474             {
475                 if (act.type == Type.REDUCE)
476                 {
477                     ((Reduce) act).rule.is_reducible = true;
478                 }
479             }
480         }
481
482         /**
483          * Checks whether the list of actions contains several REDUCE actions with the same production.
484          * Find which production is used the most often (if more then one) and replaces those multiple
485          * REDUCE actions with a single DEFAULT action.
486          * <p/>
487          * Replaced actions are not removed. They will be used to check for possible collisions when
488          * automaton action tables are built.
489          *
490          * @param default_symbol synthetic symbol that is placed instead of the action lookahead
491          */

492         void compress()
493         {
494             Production maxrule = null;
495             int maxcnt = 0;
496
497             for (Action act = first; act != null; act = act.next)
498             {
499                 if (act.type == Type.REDUCE)
500                 {
501                     Production rule = ((Reduce) act).rule;
502                     if (rule == maxrule) continue;
503                     int cnt = 1;
504                     for (Action cmp = act.next; cmp != null; cmp = cmp.next)
505                     {
506                         if (cmp.type == Type.REDUCE && ((Reduce) cmp).rule == rule)
507                         {
508                             cnt++;
509                         }
510                     }
511                     if (cnt > maxcnt)
512                     {
513                         maxrule = rule;
514                         maxcnt = cnt;
515                     }
516                 }
517             }
518
519             if (maxcnt > 1)
520             {
521                 Action act = first;
522                 while (act.type != Type.REDUCE || ((Reduce) act).rule != maxrule)
523                 {
524                     act = act.next;
525                 }
526                 act.lookahead = null;
527                 for (act = act.next; act != null; act = act.next)
528                 {
529                     if (act.type == Type.REDUCE && ((Reduce) act).rule == maxrule)
530                     {
531                         act.type = Type.NOT_USED;
532                     }
533                 }
534             }
535         }
536
537         /**
538          * Split list of actions into list of actions with terminal lookahead symbol and another
539          * list with nonterminal lookahead actions. In the end current list keeps only actions
540          * "removed" by compression.
541          *
542          * @param terminal_actions initially empty list for actions with Terminal lookahead
543          * @param nonterminal_actions initially empty list for actions with NonTerminal lookahead
544          * @return default action
545          */

546         Action split(List terminal_actions, List nonterminal_actions)
547         {
548             Action default_act = null, first_not_used = null, last_not_used = null;
549             this.num_actions = 0;
550             for (Action act = first; act != null; act = act.next)
551             {
552                 if (act.type.isRemovable())
553                 {
554                     if (last_not_used == null)
555                         last_not_used = first_not_used = act;
556                     else
557                         last_not_used = last_not_used.next = act;
558                     num_actions++;
559                 }
560                 else
561                 {
562                     if (act.lookahead instanceof NonTerminal)
563                         nonterminal_actions.add(act);
564                     else if (act.lookahead instanceof Terminal)
565                         terminal_actions.add(act);
566                     else // default
567
{
568                         if (default_act != null)
569                             throw new IllegalStateException JavaDoc("multiple default actions in state " + state.id + " actions list");
570                         default_act = act;
571                     }
572                 }
573             }
574             first = first_not_used;
575             last = last_not_used;
576
577             if (last_not_used != null)
578                 last_not_used.next = null;
579
580             if (default_act != null)
581                 default_act.next = null;
582
583             if (terminal_actions.last != null)
584                 terminal_actions.last.next = null;
585
586             if (nonterminal_actions.last != null)
587                 nonterminal_actions.last.next = null;
588             
589             terminal_actions.sort();
590             nonterminal_actions.sort();
591
592             return default_act;
593         }
594
595         /**
596          * Sorts the list of actions, so that they are ordered by a lookahead symbol ID,
597          */

598         void sort()
599         {
600             if (num_actions > 1)
601             {
602                 Action[] actions = new Action[num_actions];
603                 int i = 0;
604                 for (Action act = first; act != null; act = act.next)
605                 {
606                     actions[i++] = act;
607                 }
608                 Arrays.sort(actions, LOOKAHEAD_ID_COMPARATOR);
609                 
610                 Action act = first = actions[i = 0];
611                 while (++i < num_actions)
612                 {
613                     act = act.next = actions[i];
614                 }
615                 (last = act).next = null;
616             }
617         }
618     }
619
620     /** Next action in a state */
621     Action next;
622
623     /** Action type */
624     Type type;
625
626     /** The lookahead symbol */
627     GrammarSymbol lookahead;
628
629     Action(Type type, GrammarSymbol lookahead)
630     {
631         this.type = type;
632         this.lookahead = lookahead;
633     }
634
635     short getId()
636     {
637         return 0;
638     }
639
640     boolean resolveConflict(Action act, State state, Log log)
641     {
642         throw new IllegalStateException JavaDoc("only shift-reduce or reduce-reduce conflicts are expected");
643     }
644
645     public String JavaDoc toString()
646     {
647         return lookahead + ": " + type;
648     }
649 }
650
Popular Tags