Java > Open Source Codes > com > sun > java_cup > internal > runtime > lr_parser


1                     
2 package com.sun.java_cup.internal.runtime;
3
4 import java.util.Stack ;
5
6 /** This class implements a skeleton table driven LR parser. In general,
7  * LR parsers are a form of bottom up shift-reduce parsers. Shift-reduce
8  * parsers act by shifting input onto a parse stack until the Symbols
9  * matching the right hand side of a production appear on the top of the
10  * stack. Once this occurs, a reduce is performed. This involves removing
11  * the Symbols corresponding to the right hand side of the production
12  * (the so called "handle") and replacing them with the non-terminal from
13  * the left hand side of the production. <p>
14  *
15  * To control the decision of whether to shift or reduce at any given point,
16  * the parser uses a state machine (the "viable prefix recognition machine"
17  * built by the parser generator). The current state of the machine is placed
18  * on top of the parse stack (stored as part of a Symbol object representing
19  * a terminal or non terminal). The parse action table is consulted
20  * (using the current state and the current lookahead Symbol as indexes) to
21  * determine whether to shift or to reduce. When the parser shifts, it
22  * changes to a new state by pushing a new Symbol (containing a new state)
23  * onto the stack. When the parser reduces, it pops the handle (right hand
24  * side of a production) off the stack. This leaves the parser in the state
25  * it was in before any of those Symbols were matched. Next the reduce-goto
26  * table is consulted (using the new state and current lookahead Symbol as
27  * indexes) to determine a new state to go to. The parser then shifts to
28  * this goto state by pushing the left hand side Symbol of the production
29  * (also containing the new state) onto the stack.<p>
30  *
31  * This class actually provides four LR parsers. The methods parse() and
32  * debug_parse() provide two versions of the main parser (the only difference
33  * being that debug_parse() emits debugging trace messages as it parses).
34  * In addition to these main parsers, the error recovery mechanism uses two
35  * more. One of these is used to simulate "parsing ahead" in the input
36  * without carrying out actions (to verify that a potential error recovery
37  * has worked), and the other is used to parse through buffered "parse ahead"
38  * input in order to execute all actions and re-synchronize the actual parser
39  * configuration.<p>
40  *
41  * This is an abstract class which is normally filled out by a subclass
42  * generated by the JavaCup parser generator. In addition to supplying
43  * the actual parse tables, generated code also supplies methods which
44  * invoke various pieces of user supplied code, provide access to certain
45  * special Symbols (e.g., EOF and error), etc. Specifically, the following
46  * abstract methods are normally supplied by generated code:
47  * <dl compact>
48  * <dt> short[][] production_table()
49  * <dd> Provides a reference to the production table (indicating the index of
50  * the left hand side non terminal and the length of the right hand side
51  * for each production in the grammar).
52  * <dt> short[][] action_table()
53  * <dd> Provides a reference to the parse action table.
54  * <dt> short[][] reduce_table()
55  * <dd> Provides a reference to the reduce-goto table.
56  * <dt> int start_state()
57  * <dd> Indicates the index of the start state.
58  * <dt> int start_production()
59  * <dd> Indicates the index of the starting production.
60  * <dt> int EOF_sym()
61  * <dd> Indicates the index of the EOF Symbol.
62  * <dt> int error_sym()
63  * <dd> Indicates the index of the error Symbol.
64  * <dt> Symbol do_action()
65  * <dd> Executes a piece of user supplied action code. This always comes at
66  * the point of a reduce in the parse, so this code also allocates and
67  * fills in the left hand side non terminal Symbol object that is to be
68  * pushed onto the stack for the reduce.
69  * <dt> void init_actions()
70  * <dd> Code to initialize a special object that encapsulates user supplied
71  * actions (this object is used by do_action() to actually carry out the
72  * actions).
73  * </dl>
74  *
75  * In addition to these routines that <i>must</i> be supplied by the
76  * generated subclass there are also a series of routines that <i>may</i>
77  * be supplied. These include:
78  * <dl>
79  * <dt> Symbol scan()
80  * <dd> Used to get the next input Symbol from the scanner.
81  * <dt> Scanner getScanner()
82  * <dd> Used to provide a scanner for the default implementation of
83  * scan().
84  * <dt> int error_sync_size()
85  * <dd> This determines how many Symbols past the point of an error
86  * must be parsed without error in order to consider a recovery to
87  * be valid. This defaults to 3. Values less than 2 are not
88  * recommended.
89  * <dt> void report_error(String message, Object info)
90  * <dd> This method is called to report an error. The default implementation
91  * simply prints a message to System.err and where the error occurred.
92  * This method is often replaced in order to provide a more sophisticated
93  * error reporting mechanism.
94  * <dt> void report_fatal_error(String message, Object info)
95  * <dd> This method is called when a fatal error that cannot be recovered from
96  * is encountered. In the default implementation, it calls
97  * report_error() to emit a message, then throws an exception.
98  * <dt> void syntax_error(Symbol cur_token)
99  * <dd> This method is called as soon as syntax error is detected (but
100  * before recovery is attempted). In the default implementation it
101  * invokes: report_error("Syntax error", null);
102  * <dt> void unrecovered_syntax_error(Symbol cur_token)
103  * <dd> This method is called if syntax error recovery fails. In the default
104  * implementation it invokes:<br>
105  * report_fatal_error("Couldn't repair and continue parse", null);
106  * </dl>
107  *
108  * @see com.sun.java_cup.internal.runtime.Symbol
109  * @see com.sun.java_cup.internal.runtime.Symbol
110  * @see com.sun.java_cup.internal.runtime.virtual_parse_stack
111  * @version last updated: 7/3/96
112  * @author Frank Flannery
113  */
114
115 public abstract class lr_parser {
116
117   /*-----------------------------------------------------------*/
118   /*--- Constructor(s) ----------------------------------------*/
119   /*-----------------------------------------------------------*/
120
121   /** Simple constructor. */
122   public lr_parser()
123     {
124       /* nothing to do here */
125     }
126
127   /** Constructor that sets the default scanner. [CSA/davidm] */
128   public lr_parser(Scanner s) {
129     this(); /* in case default constructor someday does something */
130     setScanner(s);
131   }
132
133   /*-----------------------------------------------------------*/
134   /*--- (Access to) Static (Class) Variables ------------------*/
135   /*-----------------------------------------------------------*/
136
137   /** The default number of Symbols after an error we much match to consider
138    * it recovered from.
139    */
140   protected final static int _error_sync_size = 3;
141
142   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
143
144   /** The number of Symbols after an error we much match to consider it
145    * recovered from.
146    */
147   protected int error_sync_size() {return _error_sync_size; }
148
149   /*-----------------------------------------------------------*/
150   /*--- (Access to) Instance Variables ------------------------*/
151   /*-----------------------------------------------------------*/
152
153   /** Table of production information (supplied by generated subclass).
154    * This table contains one entry per production and is indexed by
155    * the negative-encoded values (reduce actions) in the action_table.
156    * Each entry has two parts, the index of the non-terminal on the
157    * left hand side of the production, and the number of Symbols
158    * on the right hand side.
159    */
160   public abstract short[][] production_table();
161
162   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
163
164   /** The action table (supplied by generated subclass). This table is
165    * indexed by state and terminal number indicating what action is to
166    * be taken when the parser is in the given state (i.e., the given state
167    * is on top of the stack) and the given terminal is next on the input.
168    * States are indexed using the first dimension, however, the entries for
169    * a given state are compacted and stored in adjacent index, value pairs
170    * which are searched for rather than accessed directly (see get_action()).
171    * The actions stored in the table will be either shifts, reduces, or
172    * errors. Shifts are encoded as positive values (one greater than the
173    * state shifted to). Reduces are encoded as negative values (one less
174    * than the production reduced by). Error entries are denoted by zero.
175    *
176    * @see com.sun.java_cup.internal.runtime.lr_parser#get_action
177    */
178   public abstract short[][] action_table();
179
180   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
181
182   /** The reduce-goto table (supplied by generated subclass). This
183    * table is indexed by state and non-terminal number and contains
184    * state numbers. States are indexed using the first dimension, however,
185    * the entries for a given state are compacted and stored in adjacent
186    * index, value pairs which are searched for rather than accessed
187    * directly (see get_reduce()). When a reduce occurs, the handle
188    * (corresponding to the RHS of the matched production) is popped off
189    * the stack. The new top of stack indicates a state. This table is
190    * then indexed by that state and the LHS of the reducing production to
191    * indicate where to "shift" to.
192    *
193    * @see com.sun.java_cup.internal.runtime.lr_parser#get_reduce
194    */
195   public abstract short[][] reduce_table();
196
197   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
198
199   /** The index of the start state (supplied by generated subclass). */
200   public abstract int start_state();
201
202   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
203
204   /** The index of the start production (supplied by generated subclass). */
205   public abstract int start_production();
206
207   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
208
209   /** The index of the end of file terminal Symbol (supplied by generated
210    * subclass).
211    */
212   public abstract int EOF_sym();
213
214   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
215
216   /** The index of the special error Symbol (supplied by generated subclass). */
217   public abstract int error_sym();
218
219   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
220
221   /** Internal flag to indicate when parser should quit. */
222   protected boolean _done_parsing = false;
223
224   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
225
226   /** This method is called to indicate that the parser should quit. This is
227    * normally called by an accept action, but can be used to cancel parsing
228    * early in other circumstances if desired.
229    */
230   public void done_parsing()
231     {
232       _done_parsing = true;
233     }
234
235   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
236   /* Global parse state shared by parse(), error recovery, and
237    * debugging routines */
238   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
239
240   /** Indication of the index for top of stack (for use by actions). */
241   protected int tos;
242
243   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
244
245   /** The current lookahead Symbol. */
246   protected Symbol cur_token;
247
248   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
249
250   /** The parse stack itself. */
251   protected Stack stack = new Stack ();
252
253   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
254
255   /** Direct reference to the production table. */
256   protected short[][] production_tab;
257
258   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
259
260   /** Direct reference to the action table. */
261   protected short[][] action_tab;
262
263   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
264
265   /** Direct reference to the reduce-goto table. */
266   protected short[][] reduce_tab;
267
268   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
269
270   /** This is the scanner object used by the default implementation
271    * of scan() to get Symbols. To avoid name conflicts with existing
272    * code, this field is private. [CSA/davidm] */
273   private Scanner _scanner;
274
275   /**
276    * Simple accessor method to set the default scanner.
277    */
278   public void setScanner(Scanner s) { _scanner = s; }
279
280   /**
281    * Simple accessor method to get the default scanner.
282    */
283   public Scanner getScanner() { return _scanner; }
284
285   /*-----------------------------------------------------------*/
286   /*--- General Methods ---------------------------------------*/
287   /*-----------------------------------------------------------*/
288
289   /** Perform a bit of user supplied action code (supplied by generated
290    * subclass). Actions are indexed by an internal action number assigned
291    * at parser generation time.
292    *
293    * @param act_num the internal index of the action to be performed.
294    * @param parser the parser object we are acting for.
295    * @param stack the parse stack of that object.
296    * @param top the index of the top element of the parse stack.
297    */
298   public abstract Symbol do_action(
299     int act_num,
300     lr_parser parser,
301     Stack stack,
302     int top)
303     throws java.lang.Exception ;
304
305   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
306
307   /** User code for initialization inside the parser. Typically this
308    * initializes the scanner. This is called before the parser requests
309    * the first Symbol. Here this is just a placeholder for subclasses that
310    * might need this and we perform no action. This method is normally
311    * overridden by the generated code using this contents of the "init with"
312    * clause as its body.
313    */
314   public void user_init() throws java.lang.Exception { }
315
316   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
317
318   /** Initialize the action object. This is called before the parser does
319    * any parse actions. This is filled in by generated code to create
320    * an object that encapsulates all action code.
321    */
322   protected abstract void init_actions() throws java.lang.Exception ;
323
324   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
325
326   /** Get the next Symbol from the input (supplied by generated subclass).
327    * Once end of file has been reached, all subsequent calls to scan
328    * should return an EOF Symbol (which is Symbol number 0). By default
329    * this method returns getScanner().next_token(); this implementation
330    * can be overriden by the generated parser using the code declared in
331    * the "scan with" clause. Do not recycle objects; every call to
332    * scan() should return a fresh object.
333    */
334   public Symbol scan() throws java.lang.Exception {
335     return getScanner().next_token();
336   }
337
338   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
339
340   /** Report a fatal error. This method takes a message string and an
341    * additional object (to be used by specializations implemented in
342    * subclasses). Here in the base class a very simple implementation
343    * is provided which reports the error then throws an exception.
344    *
345    * @param message an error message.
346    * @param info an extra object reserved for use by specialized subclasses.
347    */
348   public void report_fatal_error(
349     String message,
350     Object info)
351     throws java.lang.Exception
352     {
353       /* stop parsing (not really necessary since we throw an exception, but) */
354       done_parsing();
355
356       /* use the normal error message reporting to put out the message */
357       report_error(message, info);
358
359       /* throw an exception */
360       throw new Exception ("Can't recover from previous error(s)");
361     }
362
363   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
364
365   /** Report a non fatal error (or warning). This method takes a message
366    * string and an additional object (to be used by specializations
367    * implemented in subclasses). Here in the base class a very simple
368    * implementation is provided which simply prints the message to
369    * System.err.
370    *
371    * @param message an error message.
372    * @param info an extra object reserved for use by specialized subclasses.
373    */
374   public void report_error(String message, Object info)
375     {
376       System.err.print(message);
377       if (info instanceof Symbol)
378     if (((Symbol)info).left != -1)
379     System.err.println(" at character " + ((Symbol)info).left +
380                " of input");
381     else System.err.println("");
382       else System.err.println("");
383     }
384
385   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
386
387   /** This method is called when a syntax error has been detected and recovery
388    * is about to be invoked. Here in the base class we just emit a
389    * "Syntax error" error message.
390    *
391    * @param cur_token the current lookahead Symbol.
392    */
393   public void syntax_error(Symbol cur_token)
394     {
395       report_error("Syntax error", cur_token);
396     }
397
398   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
399
400   /** This method is called if it is determined that syntax error recovery
401    * has been unsuccessful. Here in the base class we report a fatal error.
402    *
403    * @param cur_token the current lookahead Symbol.
404    */
405   public void unrecovered_syntax_error(Symbol cur_token)
406     throws java.lang.Exception
407     {
408       report_fatal_error("Couldn't repair and continue parse", cur_token);
409     }
410
411   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
412
413   /** Fetch an action from the action table. The table is broken up into
414    * rows, one per state (rows are indexed directly by state number).
415    * Within each row, a list of index, value pairs are given (as sequential
416    * entries in the table), and the list is terminated by a default entry
417    * (denoted with a Symbol index of -1). To find the proper entry in a row
418    * we do a linear or binary search (depending on the size of the row).
419    *
420    * @param state the state index of the action being accessed.
421    * @param sym the Symbol index of the action being accessed.
422    */
423   protected final short get_action(int state, int sym)
424     {
425       short tag;
426       int first, last, probe;
427       short[] row = action_tab[state];
428
429       /* linear search if we are < 10 entries */
430       if (row.length < 20)
431         for (probe = 0; probe < row.length; probe++)
432       {
433         /* is this entry labeled with our Symbol or the default? */
434         tag = row[probe++];
435         if (tag == sym || tag == -1)
436           {
437             /* return the next entry */
438             return row[probe];
439           }
440       }
441       /* otherwise binary search */
442       else
443     {
444       first = 0;
445       last = (row.length-1)/2 - 1; /* leave out trailing default entry */
446       while (first <= last)
447         {
448           probe = (first+last)/2;
449           if (sym == row[probe*2])
450         return row[probe*2+1];
451           else if (sym > row[probe*2])
452         first = probe+1;
453           else
454             last = probe-1;
455         }
456
457       /* not found, use the default at the end */
458       return row[row.length-1];
459     }
460
461       /* shouldn't happened, but if we run off the end we return the
462      default (error == 0) */
463       return 0;
464     }
465
466   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
467
468   /** Fetch a state from the reduce-goto table. The table is broken up into
469    * rows, one per state (rows are indexed directly by state number).
470    * Within each row, a list of index, value pairs are given (as sequential
471    * entries in the table), and the list is terminated by a default entry
472    * (denoted with a Symbol index of -1). To find the proper entry in a row
473    * we do a linear search.
474    *
475    * @param state the state index of the entry being accessed.
476    * @param sym the Symbol index of the entry being accessed.
477    */
478   protected final short get_reduce(int state, int sym)
479     {
480       short tag;
481       short[] row = reduce_tab[state];
482
483       /* if we have a null row we go with the default */
484       if (row == null)
485         return -1;
486
487       for (int probe = 0; probe < row.length; probe++)
488     {
489       /* is this entry labeled with our Symbol or the default? */
490       tag = row[probe++];
491       if (tag == sym || tag == -1)
492         {
493           /* return the next entry */
494           return row[probe];
495         }
496     }
497       /* if we run off the end we return the default (error == -1) */
498       return -1;
499     }
500
501   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
502
503   /** This method provides the main parsing routine. It returns only when
504    * done_parsing() has been called (typically because the parser has
505    * accepted, or a fatal error has been reported). See the header
506    * documentation for the class regarding how shift/reduce parsers operate
507    * and how the various tables are used.
508    */
509   public Symbol parse() throws java.lang.Exception
510     {
511       /* the current action code */
512       int act;
513
514       /* the Symbol/stack element returned by a reduce */
515       Symbol lhs_sym = null;
516
517       /* information about production being reduced with */
518       short handle_size, lhs_sym_num;
519
520       /* set up direct reference to tables to drive the parser */
521
522       production_tab = production_table();
523       action_tab = action_table();
524       reduce_tab = reduce_table();
525
526       /* initialize the action encapsulation object */
527       init_actions();
528
529       /* do user initialization */
530       user_init();
531
532       /* get the first token */
533       cur_token = scan();
534
535       /* push dummy Symbol with start state to get us underway */
536       stack.removeAllElements();
537       stack.push(new Symbol(0, start_state()));
538       tos = 0;
539
540       /* continue until we are told to stop */
541       for (_done_parsing = false; !_done_parsing; )
542     {
543       /* Check current token for freshness. */
544       if (cur_token.used_by_parser)
545         throw new Error ("Symbol recycling detected (fix your scanner).");
546
547       /* current state is always on the top of the stack */
548
549       /* look up action out of the current state with the current input */
550       act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
551
552       /* decode the action -- > 0 encodes shift */
553       if (act > 0)
554         {
555           /* shift to the encoded state by pushing it on the stack */
556           cur_token.parse_state = act-1;
557           cur_token.used_by_parser = true;
558           stack.push(cur_token);
559           tos++;
560
561           /* advance to the next Symbol */
562           cur_token = scan();
563         }
564       /* if its less than zero, then it encodes a reduce action */
565       else if (act < 0)
566         {
567           /* perform the action for the reduce */
568           lhs_sym = do_action((-act)-1, this, stack, tos);
569
570           /* look up information about the production */
571           lhs_sym_num = production_tab[(-act)-1][0];
572           handle_size = production_tab[(-act)-1][1];
573
574           /* pop the handle off the stack */
575           for (int i = 0; i < handle_size; i++)
576         {
577           stack.pop();
578           tos--;
579         }
580           
581           /* look up the state to go to from the one popped back to */
582           act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
583
584           /* shift to that state */
585           lhs_sym.parse_state = act;
586           lhs_sym.used_by_parser = true;
587           stack.push(lhs_sym);
588           tos++;
589         }
590       /* finally if the entry is zero, we have an error */
591       else if (act == 0)
592         {
593           /* call user syntax error reporting routine */
594           syntax_error(cur_token);
595
596           /* try to error recover */
597           if (!error_recovery(false))
598         {
599           /* if that fails give up with a fatal syntax error */
600           unrecovered_syntax_error(cur_token);
601
602           /* just in case that wasn't fatal enough, end parse */
603           done_parsing();
604         } else {
605           lhs_sym = (Symbol)stack.peek();
606         }
607         }
608     }
609       return lhs_sym;
610     }
611
612   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
613
614   /** Write a debugging message to System.err for the debugging version
615    * of the parser.
616    *
617    * @param mess the text of the debugging message.
618    */
619   public void debug_message(String mess)
620     {
621       System.err.println(mess);
622     }
623
624   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
625
626   /** Dump the parse stack for debugging purposes. */
627   public void dump_stack()
628     {
629       if (stack == null)
630     {
631       debug_message("# Stack dump requested, but stack is null");
632       return;
633     }
634
635       debug_message("============ Parse Stack Dump ============");
636
637       /* dump the stack */
638       for (int i=0; i<stack.size(); i++)
639     {
640       debug_message("Symbol: " + ((Symbol)stack.elementAt(i)).sym +
641             " State: " + ((Symbol)stack.elementAt(i)).parse_state);
642     }
643       debug_message("==========================================");
644     }
645
646   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
647
648   /** Do debug output for a reduce.
649    *
650    * @param prod_num the production we are reducing with.
651    * @param nt_num the index of the LHS non terminal.
652    * @param rhs_size the size of the RHS.
653    */
654   public void debug_reduce(int prod_num, int nt_num, int rhs_size)
655     {
656       debug_message("# Reduce with prod #" + prod_num + " [NT=" + nt_num +
657                 ", " + "SZ=" + rhs_size + "]");
658     }
659
660   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
661
662   /** Do debug output for shift.
663    *
664    * @param shift_tkn the Symbol being shifted onto the stack.
665    */
666   public void debug_shift(Symbol shift_tkn)
667     {
668       debug_message("# Shift under term #" + shift_tkn.sym +
669             " to state #" + shift_tkn.parse_state);
670     }
671
672   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
673
674   /** Do debug output for stack state. [CSA]
675    */
676   public void debug_stack() {
677       StringBuffer sb=new StringBuffer ("## STACK:");
678       for (int i=0; i<stack.size(); i++) {
679       Symbol s = (Symbol) stack.elementAt(i);
680       sb.append(" <state "+s.parse_state+", sym "+s.sym+">");
681       if ((i%3)==2 || (i==(stack.size()-1))) {
682           debug_message(sb.toString());
683           sb = new StringBuffer (" ");
684       }
685       }
686   }
687
688   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
689
690   /** Perform a parse with debugging output. This does exactly the
691    * same things as parse(), except that it calls debug_shift() and
692    * debug_reduce() when shift and reduce moves are taken by the parser
693    * and produces various other debugging messages.
694    */
695   public Symbol debug_parse()
696     throws java.lang.Exception
697     {
698       /* the current action code */
699       int act;
700
701       /* the Symbol/stack element returned by a reduce */
702       Symbol lhs_sym = null;
703
704       /* information about production being reduced with */
705       short handle_size, lhs_sym_num;
706
707       /* set up direct reference to tables to drive the parser */
708       production_tab = production_table();
709       action_tab = action_table();
710       reduce_tab = reduce_table();
711
712       debug_message("# Initializing parser");
713
714       /* initialize the action encapsulation object */
715       init_actions();
716
717       /* do user initialization */
718       user_init();
719
720       /* the current Symbol */
721       cur_token = scan();
722
723       debug_message("# Current Symbol is #" + cur_token.sym);
724
725       /* push dummy Symbol with start state to get us underway */
726       stack.removeAllElements();
727       stack.push(new Symbol(0, start_state()));
728       tos = 0;
729
730       /* continue until we are told to stop */
731       for (_done_parsing = false; !_done_parsing; )
732     {
733       /* Check current token for freshness. */
734       if (cur_token.used_by_parser)
735         throw new Error ("Symbol recycling detected (fix your scanner).");
736
737       /* current state is always on the top of the stack */
738       //debug_stack();
739
740       /* look up action out of the current state with the current input */
741       act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
742
743       /* decode the action -- > 0 encodes shift */
744       if (act > 0)
745         {
746           /* shift to the encoded state by pushing it on the stack */
747           cur_token.parse_state = act-1;
748           cur_token.used_by_parser = true;
749           debug_shift(cur_token);
750           stack.push(cur_token);
751           tos++;
752
753           /* advance to the next Symbol */
754           cur_token = scan();
755               debug_message("# Current token is " + cur_token);
756         }
757       /* if its less than zero, then it encodes a reduce action */
758       else if (act < 0)
759         {
760           /* perform the action for the reduce */
761           lhs_sym = do_action((-act)-1, this, stack, tos);
762
763           /* look up information about the production */
764           lhs_sym_num = production_tab[(-act)-1][0];
765           handle_size = production_tab[(-act)-1][1];
766
767           debug_reduce((-act)-1, lhs_sym_num, handle_size);
768
769           /* pop the handle off the stack */
770           for (int i = 0; i < handle_size; i++)
771         {
772           stack.pop();
773           tos--;
774         }
775           
776           /* look up the state to go to from the one popped back to */
777           act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
778           debug_message("# Reduce rule: top state " +
779                  ((Symbol)stack.peek()).parse_state +
780                  ", lhs sym " + lhs_sym_num + " -> state " + act);
781
782           /* shift to that state */
783           lhs_sym.parse_state = act;
784           lhs_sym.used_by_parser = true;
785           stack.push(lhs_sym);
786           tos++;
787
788           debug_message("# Goto state #" + act);
789         }
790       /* finally if the entry is zero, we have an error */
791       else if (act == 0)
792         {
793           /* call user syntax error reporting routine */
794           syntax_error(cur_token);
795
796           /* try to error recover */
797           if (!error_recovery(true))
798         {
799           /* if that fails give up with a fatal syntax error */
800           unrecovered_syntax_error(cur_token);
801
802           /* just in case that wasn't fatal enough, end parse */
803           done_parsing();
804         } else {
805           lhs_sym = (Symbol)stack.peek();
806         }
807         }
808     }
809       return lhs_sym;
810     }
811
812   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
813   /* Error recovery code */
814   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
815
816   /** Attempt to recover from a syntax error. This returns false if recovery
817    * fails, true if it succeeds. Recovery happens in 4 steps. First we
818    * pop the parse stack down to a point at which we have a shift out
819    * of the top-most state on the error Symbol. This represents the
820    * initial error recovery configuration. If no such configuration is
821    * found, then we fail. Next a small number of "lookahead" or "parse
822    * ahead" Symbols are read into a buffer. The size of this buffer is
823    * determined by error_sync_size() and determines how many Symbols beyond
824    * the error must be matched to consider the recovery a success. Next,
825    * we begin to discard Symbols in attempt to get past the point of error
826    * to a point where we can continue parsing. After each Symbol, we attempt
827    * to "parse ahead" though the buffered lookahead Symbols. The "parse ahead"
828    * process simulates that actual parse, but does not modify the real
829    * parser's configuration, nor execute any actions. If we can parse all
830    * the stored Symbols without error, then the recovery is considered a
831    * success. Once a successful recovery point is determined, we do an
832    * actual parse over the stored input -- modifying the real parse
833    * configuration and executing all actions. Finally, we return the the
834    * normal parser to continue with the overall parse.
835    *
836    * @param debug should we produce debugging messages as we parse.
837    */
838   protected boolean error_recovery(boolean debug)
839     throws java.lang.Exception
840     {
841       if (debug) debug_message("# Attempting error recovery");
842
843       /* first pop the stack back into a state that can shift on error and
844      do that shift (if that fails, we fail) */
845       if (!find_recovery_config(debug))
846     {
847       if (debug) debug_message("# Error recovery fails");
848       return false;
849     }
850
851       /* read ahead to create lookahead we can parse multiple times */
852       read_lookahead();
853
854       /* repeatedly try to parse forward until we make it the required dist */
855       for (;;)
856     {
857       /* try to parse forward, if it makes it, bail out of loop */
858       if (debug) debug_message("# Trying to parse ahead");
859       if (try_parse_ahead(debug))
860         {
861           break;
862         }
863
864       /* if we are now at EOF, we have failed */
865       if (lookahead[0].sym == EOF_sym())
866         {
867           if (debug) debug_message("# Error recovery fails at EOF");
868           return false;
869         }
870
871       /* otherwise, we consume another Symbol and try again */
872       if (debug)
873       debug_message("# Consuming Symbol #" + cur_err_token().sym);
874       restart_lookahead();
875     }
876
877       /* we have consumed to a point where we can parse forward */
878       if (debug) debug_message("# Parse-ahead ok, going back to normal parse");
879
880       /* do the real parse (including actions) across the lookahead */
881       parse_lookahead(debug);
882
883       /* we have success */
884       return true;
885     }
886
887   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
888
889   /** Determine if we can shift under the special error Symbol out of the
890    * state currently on the top of the (real) parse stack.
891    */
892   protected boolean shift_under_error()
893     {
894       /* is there a shift under error Symbol */
895       return get_action(((Symbol)stack.peek()).parse_state, error_sym()) > 0;
896     }
897
898   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
899
900   /** Put the (real) parse stack into error recovery configuration by
901    * popping the stack down to a state that can shift on the special
902    * error Symbol, then doing the shift. If no suitable state exists on
903    * the stack we return false
904    *
905    * @param debug should we produce debugging messages as we parse.
906    */
907   protected boolean find_recovery_config(boolean debug)
908     {
909       Symbol error_token;
910       int act;
911
912       if (debug) debug_message("# Finding recovery state on stack");
913
914       /* Remember the right-position of the top symbol on the stack */
915       int right_pos = ((Symbol)stack.peek()).right;
916       int left_pos = ((Symbol)stack.peek()).left;
917
918       /* pop down until we can shift under error Symbol */
919       while (!shift_under_error())
920     {
921       /* pop the stack */
922       if (debug)
923         debug_message("# Pop stack by one, state was # " +
924                       ((Symbol)stack.peek()).parse_state);
925           left_pos = ((Symbol)stack.pop()).left;
926       tos--;
927
928       /* if we have hit bottom, we fail */
929       if (stack.empty())
930         {
931           if (debug) debug_message("# No recovery state found on stack");
932           return false;
933         }
934     }
935
936       /* state on top of the stack can shift under error, find the shift */
937       act = get_action(((Symbol)stack.peek()).parse_state, error_sym());
938       if (debug)
939     {
940       debug_message("# Recover state found (#" +
941             ((Symbol)stack.peek()).parse_state + ")");
942       debug_message("# Shifting on error to state #" + (act-1));
943     }
944
945       /* build and shift a special error Symbol */
946       error_token = new Symbol(error_sym(), left_pos, right_pos);
947       error_token.parse_state = act-1;
948       error_token.used_by_parser = true;
949       stack.push(error_token);
950       tos++;
951
952       return true;
953     }
954
955   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
956
957   /** Lookahead Symbols used for attempting error recovery "parse aheads". */
958   protected Symbol lookahead[];
959
960   /** Position in lookahead input buffer used for "parse ahead". */
961   protected int lookahead_pos;
962
963   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
964
965   /** Read from input to establish our buffer of "parse ahead" lookahead
966    * Symbols.
967    */
968   protected void read_lookahead() throws java.lang.Exception
969     {
970       /* create the lookahead array */
971       lookahead = new Symbol[error_sync_size()];
972
973       /* fill in the array */
974       for (int i = 0; i < error_sync_size(); i++)
975     {
976       lookahead[i] = cur_token;
977       cur_token = scan();
978     }
979
980       /* start at the beginning */
981       lookahead_pos = 0;
982     }
983
984   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
985
986   /** Return the current lookahead in our error "parse ahead" buffer. */
987   protected Symbol cur_err_token() { return lookahead[lookahead_pos]; }
988
989   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
990
991   /** Advance to next "parse ahead" input Symbol. Return true if we have
992    * input to advance to, false otherwise.
993    */
994   protected boolean advance_lookahead()
995     {
996       /* advance the input location */
997       lookahead_pos++;
998
999       /* return true if we didn't go off the end */
1000      return lookahead_pos < error_sync_size();
1001    }
1002
1003  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1004
1005  /** Reset the parse ahead input to one Symbol past where we started error
1006   * recovery (this consumes one new Symbol from the real input).
1007   */
1008  protected void restart_lookahead() throws java.lang.Exception
1009    {
1010      /* move all the existing input over */
1011      for (int i = 1; i < error_sync_size(); i++)
1012    lookahead[i-1] = lookahead[i];
1013
1014      /* read a new Symbol into the last spot */
1015      cur_token = scan();
1016      lookahead[error_sync_size()-1] = cur_token;
1017
1018      /* reset our internal position marker */
1019      lookahead_pos = 0;
1020    }
1021
1022  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1023
1024  /** Do a simulated parse forward (a "parse ahead") from the current
1025   * stack configuration using stored lookahead input and a virtual parse
1026   * stack. Return true if we make it all the way through the stored
1027   * lookahead input without error. This basically simulates the action of
1028   * parse() using only our saved "parse ahead" input, and not executing any
1029   * actions.
1030   *
1031   * @param debug should we produce debugging messages as we parse.
1032   */
1033  protected boolean try_parse_ahead(boolean debug)
1034    throws java.lang.Exception
1035    {
1036      int act;
1037      short lhs, rhs_size;
1038
1039      /* create a virtual stack from the real parse stack */
1040      virtual_parse_stack vstack = new virtual_parse_stack(stack);
1041
1042      /* parse until we fail or get past the lookahead input */
1043      for (;;)
1044    {
1045      /* look up the action from the current state (on top of stack) */
1046      act = get_action(vstack.top(), cur_err_token().sym);
1047
1048      /* if its an error, we fail */
1049      if (act == 0) return false;
1050
1051      /* > 0 encodes a shift */
1052      if (act > 0)
1053        {
1054          /* push the new state on the stack */
1055          vstack.push(act-1);
1056
1057          if (debug) debug_message("# Parse-ahead shifts Symbol #" +
1058               cur_err_token().sym + " into state #" + (act-1));
1059
1060          /* advance simulated input, if we run off the end, we are done */
1061          if (!advance_lookahead()) return true;
1062        }
1063      /* < 0 encodes a reduce */
1064      else
1065        {
1066          /* if this is a reduce with the start production we are done */
1067          if ((-act)-1 == start_production())
1068        {
1069          if (debug) debug_message("# Parse-ahead accepts");
1070          return true;
1071        }
1072
1073          /* get the lhs Symbol and the rhs size */
1074          lhs = production_tab[(-act)-1][0];
1075          rhs_size = production_tab[(-act)-1][1];
1076
1077          /* pop handle off the stack */
1078          for (int i = 0; i < rhs_size; i++)
1079        vstack.pop();
1080
1081          if (debug)
1082        debug_message("# Parse-ahead reduces: handle size = " +
1083              rhs_size + " lhs = #" + lhs + " from state #" + vstack.top());
1084
1085          /* look up goto and push it onto the stack */
1086          vstack.push(get_reduce(vstack.top(), lhs));
1087          if (debug)
1088        debug_message("# Goto state #" + vstack.top());
1089        }
1090    }
1091    }
1092
1093  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1094
1095  /** Parse forward using stored lookahead Symbols. In this case we have
1096   * already verified that parsing will make it through the stored lookahead
1097   * Symbols and we are now getting back to the point at which we can hand
1098   * control back to the normal parser. Consequently, this version of the
1099   * parser performs all actions and modifies the real parse configuration.
1100   * This returns once we have consumed all the stored input or we accept.
1101   *
1102   * @param debug should we produce debugging messages as we parse.
1103   */
1104  protected void parse_lookahead(boolean debug)
1105    throws java.lang.Exception
1106    {
1107      /* the current action code */
1108      int act;
1109
1110      /* the Symbol/stack element returned by a reduce */
1111      Symbol lhs_sym = null;
1112
1113      /* information about production being reduced with */
1114      short handle_size, lhs_sym_num;
1115
1116      /* restart the saved input at the beginning */
1117      lookahead_pos = 0;
1118
1119      if (debug)
1120    {
1121      debug_message("# Reparsing saved input with actions");
1122      debug_message("# Current Symbol is #" + cur_err_token().sym);
1123      debug_message("# Current state is #" +
1124            ((Symbol)stack.peek()).parse_state);
1125    }
1126
1127      /* continue until we accept or have read all lookahead input */
1128      while(!_done_parsing)
1129    {
1130      /* current state is always on the top of the stack */
1131
1132      /* look up action out of the current state with the current input */
1133      act =
1134        get_action(((Symbol)stack.peek()).parse_state, cur_err_token().sym);
1135
1136      /* decode the action -- > 0 encodes shift */
1137      if (act > 0)
1138        {
1139          /* shift to the encoded state by pushing it on the stack */
1140          cur_err_token().parse_state = act-1;
1141          cur_err_token().used_by_parser = true;
1142          if (debug) debug_shift(cur_err_token());
1143          stack.push(cur_err_token());
1144          tos++;
1145
1146          /* advance to the next Symbol, if there is none, we are done */
1147          if (!advance_lookahead())
1148        {
1149          if (debug) debug_message("# Completed reparse");
1150
1151          /* scan next Symbol so we can continue parse */
1152          // BUGFIX by Chris Harris <ckharris@ucsd.edu>:
1153 // correct a one-off error by commenting out
1154 // this next line.
1155 /*cur_token = scan();*/
1156
1157          /* go back to normal parser */
1158          return;
1159        }
1160          
1161          if (debug)
1162        debug_message("# Current Symbol is #" + cur_err_token().sym);
1163        }
1164      /* if its less than zero, then it encodes a reduce action */
1165      else if (act < 0)
1166        {
1167          /* perform the action for the reduce */
1168          lhs_sym = do_action((-act)-1, this, stack, tos);
1169
1170          /* look up information about the production */
1171          lhs_sym_num = production_tab[(-act)-1][0];
1172          handle_size = production_tab[(-act)-1][1];
1173
1174          if (debug) debug_reduce((-act)-1, lhs_sym_num, handle_size);
1175
1176          /* pop the handle off the stack */
1177          for (int i = 0; i < handle_size; i++)
1178        {
1179          stack.pop();
1180          tos--;
1181        }
1182          
1183          /* look up the state to go to from the one popped back to */
1184          act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
1185
1186          /* shift to that state */
1187          lhs_sym.parse_state = act;
1188          lhs_sym.used_by_parser = true;
1189          stack.push(lhs_sym);
1190          tos++;
1191           
1192          if (debug) debug_message("# Goto state #" + act);
1193
1194        }
1195      /* finally if the entry is zero, we have an error
1196         (shouldn't happen here, but...)*/
1197      else if (act == 0)
1198        {
1199          report_fatal_error("Syntax error", lhs_sym);
1200          return;
1201        }
1202    }
1203
1204    
1205    }
1206
1207  /*-----------------------------------------------------------*/
1208
1209  /** Utility function: unpacks parse tables from strings */
1210  protected static short[][] unpackFromStrings(String [] sa)
1211    {
1212      // Concatanate initialization strings.
1213 StringBuffer sb = new StringBuffer (sa[0]);
1214      for (int i=1; i<sa.length; i++)
1215    sb.append(sa[i]);
1216      int n=0; // location in initialization string
1217 int size1 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
1218      short[][] result = new short[size1][];
1219      for (int i=0; i<size1; i++) {
1220        int size2 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
1221        result[i] = new short[size2];
1222        for (int j=0; j<size2; j++)
1223          result[i][j] = (short) (sb.charAt(n++)-2);
1224      }
1225      return result;
1226    }
1227}
1228
1229

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags