Added the name of the file to the error report.
[repair.git] / Repair / RepairCompiler / java_cup / runtime / lr_parser.java
1                                     
2 package java_cup.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     java_cup.runtime.Symbol
109  * @see     java_cup.runtime.Symbol
110  * @see     java_cup.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 java_cup.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 java_cup.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     Symbol sym = getScanner().next_token();
336     return (sym!=null) ? sym : new Symbol(EOF_sym());
337   }
338
339   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
340
341   /** Report a fatal error.  This method takes a  message string and an 
342    *  additional object (to be used by specializations implemented in 
343    *  subclasses).  Here in the base class a very simple implementation 
344    *  is provided which reports the error then throws an exception. 
345    *
346    * @param message an error message.
347    * @param info    an extra object reserved for use by specialized subclasses.
348    */
349   public void report_fatal_error(
350     String   message, 
351     Object   info)
352     throws java.lang.Exception
353     {
354       /* stop parsing (not really necessary since we throw an exception, but) */
355       done_parsing();
356
357       /* use the normal error message reporting to put out the message */
358       report_error(message, info);
359
360       /* throw an exception */
361       throw new Exception("Can't recover from previous error(s)");
362     }
363
364   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
365
366   /** Report a non fatal error (or warning).  This method takes a message 
367    *  string and an additional object (to be used by specializations 
368    *  implemented in subclasses).  Here in the base class a very simple 
369    *  implementation is provided which simply prints the message to 
370    *  System.err. 
371    *
372    * @param message an error message.
373    * @param info    an extra object reserved for use by specialized subclasses.
374    */
375   public void report_error(String message, Object info)
376     {
377       System.err.print(message);
378       if (info instanceof Symbol)
379         if (((Symbol)info).left != -1)
380             //System.err.println(" at character " + ((Symbol)info).left + " of input");
381             System.err.println(" not expected here.");
382         else System.err.println("");
383       else System.err.println("");
384     }
385
386   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
387
388   /** This method is called when a syntax error has been detected and recovery 
389    *  is about to be invoked.  Here in the base class we just emit a 
390    *  "Syntax error" error message.  
391    *
392    * @param cur_token the current lookahead Symbol.
393    */
394   public void syntax_error(Symbol cur_token)
395     {
396       report_error("Syntax error", cur_token);
397     }
398
399   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
400
401   /** This method is called if it is determined that syntax error recovery 
402    *  has been unsuccessful.  Here in the base class we report a fatal error. 
403    *
404    * @param cur_token the current lookahead Symbol.
405    */
406   public void unrecovered_syntax_error(Symbol cur_token)
407     throws java.lang.Exception
408     {
409       report_fatal_error("Couldn't repair and continue parse", cur_token);
410     }
411
412   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
413
414   /** Fetch an action from the action table.  The table is broken up into
415    *  rows, one per state (rows are indexed directly by state number).  
416    *  Within each row, a list of index, value pairs are given (as sequential
417    *  entries in the table), and the list is terminated by a default entry 
418    *  (denoted with a Symbol index of -1).  To find the proper entry in a row 
419    *  we do a linear or binary search (depending on the size of the row).  
420    *
421    * @param state the state index of the action being accessed.
422    * @param sym   the Symbol index of the action being accessed.
423    */
424   protected final short get_action(int state, int sym)
425     {
426       short tag;
427       int first, last, probe;
428       short[] row = action_tab[state];
429
430       /* linear search if we are < 10 entries */
431       if (row.length < 20)
432         for (probe = 0; probe < row.length; probe++)
433           {
434             /* is this entry labeled with our Symbol or the default? */
435             tag = row[probe++];
436             if (tag == sym || tag == -1)
437               {
438                 /* return the next entry */
439                 return row[probe];
440               }
441           }
442       /* otherwise binary search */
443       else
444         {
445           first = 0; 
446           last = (row.length-1)/2 - 1;  /* leave out trailing default entry */
447           while (first <= last)
448             {
449               probe = (first+last)/2;
450               if (sym == row[probe*2])
451                 return row[probe*2+1];
452               else if (sym > row[probe*2])
453                 first = probe+1;
454               else
455                 last = probe-1;
456             }
457
458           /* not found, use the default at the end */
459           return row[row.length-1];
460         }
461
462       /* shouldn't happened, but if we run off the end we return the 
463          default (error == 0) */
464       return 0;
465     }
466
467   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
468
469   /** Fetch a state from the reduce-goto table.  The table is broken up into
470    *  rows, one per state (rows are indexed directly by state number).  
471    *  Within each row, a list of index, value pairs are given (as sequential
472    *  entries in the table), and the list is terminated by a default entry 
473    *  (denoted with a Symbol index of -1).  To find the proper entry in a row 
474    *  we do a linear search.  
475    *
476    * @param state the state index of the entry being accessed.
477    * @param sym   the Symbol index of the entry being accessed.
478    */
479   protected final short get_reduce(int state, int sym)
480     {
481       short tag;
482       short[] row = reduce_tab[state];
483
484       /* if we have a null row we go with the default */
485       if (row == null)
486         return -1;
487
488       for (int probe = 0; probe < row.length; probe++)
489         {
490           /* is this entry labeled with our Symbol or the default? */
491           tag = row[probe++];
492           if (tag == sym || tag == -1)
493             {
494               /* return the next entry */
495               return row[probe];
496             }
497         }
498       /* if we run off the end we return the default (error == -1) */
499       return -1;
500     }
501
502   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
503
504   /** This method provides the main parsing routine.  It returns only when 
505    *  done_parsing() has been called (typically because the parser has 
506    *  accepted, or a fatal error has been reported).  See the header 
507    *  documentation for the class regarding how shift/reduce parsers operate
508    *  and how the various tables are used.
509    */
510   public Symbol parse() throws java.lang.Exception
511     {
512       /* the current action code */
513       int act;
514
515       /* the Symbol/stack element returned by a reduce */
516       Symbol lhs_sym = null;
517
518       /* information about production being reduced with */
519       short handle_size, lhs_sym_num;
520
521       /* set up direct reference to tables to drive the parser */
522
523       production_tab = production_table();
524       action_tab     = action_table();
525       reduce_tab     = reduce_table();
526
527       /* initialize the action encapsulation object */
528       init_actions();
529
530       /* do user initialization */
531       user_init();
532
533       /* get the first token */
534       cur_token = scan(); 
535
536       /* push dummy Symbol with start state to get us underway */
537       stack.removeAllElements();
538       stack.push(new Symbol(0, start_state()));
539       tos = 0;
540
541       /* continue until we are told to stop */
542       for (_done_parsing = false; !_done_parsing; )
543         {
544           /* Check current token for freshness. */
545           if (cur_token.used_by_parser)
546             throw new Error("Symbol recycling detected (fix your scanner).");
547
548           /* current state is always on the top of the stack */
549
550           /* look up action out of the current state with the current input */
551           act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
552
553           /* decode the action -- > 0 encodes shift */
554           if (act > 0)
555             {
556               /* shift to the encoded state by pushing it on the stack */
557               cur_token.parse_state = act-1;
558               cur_token.used_by_parser = true;
559               stack.push(cur_token);
560               tos++;
561
562               /* advance to the next Symbol */
563               cur_token = scan();
564             }
565           /* if its less than zero, then it encodes a reduce action */
566           else if (act < 0)
567             {
568               /* perform the action for the reduce */
569               lhs_sym = do_action((-act)-1, this, stack, tos);
570
571               /* look up information about the production */
572               lhs_sym_num = production_tab[(-act)-1][0];
573               handle_size = production_tab[(-act)-1][1];
574
575               /* pop the handle off the stack */
576               for (int i = 0; i < handle_size; i++)
577                 {
578                   stack.pop();
579                   tos--;
580                 }
581               
582               /* look up the state to go to from the one popped back to */
583               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
584
585               /* shift to that state */
586               lhs_sym.parse_state = act;
587               lhs_sym.used_by_parser = true;
588               stack.push(lhs_sym);
589               tos++;
590             }
591           /* finally if the entry is zero, we have an error */
592           else if (act == 0)
593             {
594               /* call user syntax error reporting routine */
595               syntax_error(cur_token);
596
597               /* try to error recover */
598               if (!error_recovery(false))
599                 {
600                   /* if that fails give up with a fatal syntax error */
601                   unrecovered_syntax_error(cur_token);
602
603                   /* just in case that wasn't fatal enough, end parse */
604                   done_parsing();
605                 } else {
606                   lhs_sym = (Symbol)stack.peek();
607                 }
608             }
609         }
610       return lhs_sym;
611     }
612
613   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
614
615   /** Write a debugging message to System.err for the debugging version 
616    *  of the parser. 
617    *
618    * @param mess the text of the debugging message.
619    */
620   public void debug_message(String mess)
621     {
622       System.err.println(mess);
623     }
624
625   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
626
627   /** Dump the parse stack for debugging purposes. */
628   public void dump_stack()
629     {
630       if (stack == null)
631         {
632           debug_message("# Stack dump requested, but stack is null");
633           return;
634         }
635
636       debug_message("============ Parse Stack Dump ============");
637
638       /* dump the stack */
639       for (int i=0; i<stack.size(); i++)
640         {
641           debug_message("Symbol: " + ((Symbol)stack.elementAt(i)).sym +
642                         " State: " + ((Symbol)stack.elementAt(i)).parse_state);
643         }
644       debug_message("==========================================");
645     }
646
647   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
648
649   /** Do debug output for a reduce. 
650    *
651    * @param prod_num  the production we are reducing with.
652    * @param nt_num    the index of the LHS non terminal.
653    * @param rhs_size  the size of the RHS.
654    */
655   public void debug_reduce(int prod_num, int nt_num, int rhs_size)
656     {
657       debug_message("# Reduce with prod #" + prod_num + " [NT=" + nt_num + 
658                     ", " + "SZ=" + rhs_size + "]");
659     }
660
661   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
662
663   /** Do debug output for shift. 
664    *
665    * @param shift_tkn the Symbol being shifted onto the stack.
666    */
667   public void debug_shift(Symbol shift_tkn)
668     {
669       debug_message("# Shift under term #" + shift_tkn.sym + 
670                     " to state #" + shift_tkn.parse_state);
671     }
672
673   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
674
675   /** Do debug output for stack state. [CSA]
676    */
677   public void debug_stack() {
678       StringBuffer sb=new StringBuffer("## STACK:");
679       for (int i=0; i<stack.size(); i++) {
680           Symbol s = (Symbol) stack.elementAt(i);
681           sb.append(" <state "+s.parse_state+", sym "+s.sym+">");
682           if ((i%3)==2 || (i==(stack.size()-1))) {
683               debug_message(sb.toString());
684               sb = new StringBuffer("         ");
685           }
686       }
687   }
688
689   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
690
691   /** Perform a parse with debugging output.  This does exactly the
692    *  same things as parse(), except that it calls debug_shift() and
693    *  debug_reduce() when shift and reduce moves are taken by the parser
694    *  and produces various other debugging messages.  
695    */
696   public Symbol debug_parse()
697     throws java.lang.Exception
698     {
699       /* the current action code */
700       int act;
701
702       /* the Symbol/stack element returned by a reduce */
703       Symbol lhs_sym = null;
704
705       /* information about production being reduced with */
706       short handle_size, lhs_sym_num;
707
708       /* set up direct reference to tables to drive the parser */
709       production_tab = production_table();
710       action_tab     = action_table();
711       reduce_tab     = reduce_table();
712
713       debug_message("# Initializing parser");
714
715       /* initialize the action encapsulation object */
716       init_actions();
717
718       /* do user initialization */
719       user_init();
720
721       /* the current Symbol */
722       cur_token = scan(); 
723
724       debug_message("# Current Symbol is #" + cur_token.sym);
725
726       /* push dummy Symbol with start state to get us underway */
727       stack.removeAllElements();
728       stack.push(new Symbol(0, start_state()));
729       tos = 0;
730
731       /* continue until we are told to stop */
732       for (_done_parsing = false; !_done_parsing; )
733         {
734           /* Check current token for freshness. */
735           if (cur_token.used_by_parser)
736             throw new Error("Symbol recycling detected (fix your scanner).");
737
738           /* current state is always on the top of the stack */
739           //debug_stack();
740
741           /* look up action out of the current state with the current input */
742           act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
743
744           /* decode the action -- > 0 encodes shift */
745           if (act > 0)
746             {
747               /* shift to the encoded state by pushing it on the stack */
748               cur_token.parse_state = act-1;
749               cur_token.used_by_parser = true;
750               debug_shift(cur_token);
751               stack.push(cur_token);
752               tos++;
753
754               /* advance to the next Symbol */
755               cur_token = scan();
756               debug_message("# Current token is " + cur_token);
757             }
758           /* if its less than zero, then it encodes a reduce action */
759           else if (act < 0)
760             {
761               /* perform the action for the reduce */
762               lhs_sym = do_action((-act)-1, this, stack, tos);
763
764               /* look up information about the production */
765               lhs_sym_num = production_tab[(-act)-1][0];
766               handle_size = production_tab[(-act)-1][1];
767
768               debug_reduce((-act)-1, lhs_sym_num, handle_size);
769
770               /* pop the handle off the stack */
771               for (int i = 0; i < handle_size; i++)
772                 {
773                   stack.pop();
774                   tos--;
775                 }
776               
777               /* look up the state to go to from the one popped back to */
778               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
779               debug_message("# Reduce rule: top state " +
780                              ((Symbol)stack.peek()).parse_state +
781                              ", lhs sym " + lhs_sym_num + " -> state " + act); 
782
783               /* shift to that state */
784               lhs_sym.parse_state = act;
785               lhs_sym.used_by_parser = true;
786               stack.push(lhs_sym);
787               tos++;
788
789               debug_message("# Goto state #" + act);
790             }
791           /* finally if the entry is zero, we have an error */
792           else if (act == 0)
793             {
794               /* call user syntax error reporting routine */
795               syntax_error(cur_token);
796
797               /* try to error recover */
798               if (!error_recovery(true))
799                 {
800                   /* if that fails give up with a fatal syntax error */
801                   unrecovered_syntax_error(cur_token);
802
803                   /* just in case that wasn't fatal enough, end parse */
804                   done_parsing();
805                 } else {
806                   lhs_sym = (Symbol)stack.peek();
807                 }
808             }
809         }
810       return lhs_sym;
811     }
812
813   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
814   /* Error recovery code */
815   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
816
817   /** Attempt to recover from a syntax error.  This returns false if recovery 
818    *  fails, true if it succeeds.  Recovery happens in 4 steps.  First we
819    *  pop the parse stack down to a point at which we have a shift out
820    *  of the top-most state on the error Symbol.  This represents the
821    *  initial error recovery configuration.  If no such configuration is
822    *  found, then we fail.  Next a small number of "lookahead" or "parse
823    *  ahead" Symbols are read into a buffer.  The size of this buffer is 
824    *  determined by error_sync_size() and determines how many Symbols beyond
825    *  the error must be matched to consider the recovery a success.  Next, 
826    *  we begin to discard Symbols in attempt to get past the point of error
827    *  to a point where we can continue parsing.  After each Symbol, we attempt 
828    *  to "parse ahead" though the buffered lookahead Symbols.  The "parse ahead"
829    *  process simulates that actual parse, but does not modify the real 
830    *  parser's configuration, nor execute any actions. If we can  parse all 
831    *  the stored Symbols without error, then the recovery is considered a 
832    *  success.  Once a successful recovery point is determined, we do an
833    *  actual parse over the stored input -- modifying the real parse 
834    *  configuration and executing all actions.  Finally, we return the the 
835    *  normal parser to continue with the overall parse.
836    *
837    * @param debug should we produce debugging messages as we parse.
838    */
839   protected boolean error_recovery(boolean debug)
840     throws java.lang.Exception
841     {
842       if (debug) debug_message("# Attempting error recovery");
843
844       /* first pop the stack back into a state that can shift on error and 
845          do that shift (if that fails, we fail) */
846       if (!find_recovery_config(debug))
847         {
848           if (debug) debug_message("# Error recovery fails");
849           return false;
850         }
851
852       /* read ahead to create lookahead we can parse multiple times */
853       read_lookahead();
854
855       /* repeatedly try to parse forward until we make it the required dist */
856       for (;;)
857         {
858           /* try to parse forward, if it makes it, bail out of loop */
859           if (debug) debug_message("# Trying to parse ahead");
860           if (try_parse_ahead(debug))
861             {
862               break;
863             }
864
865           /* if we are now at EOF, we have failed */
866           if (lookahead[0].sym == EOF_sym()) 
867             {
868               if (debug) debug_message("# Error recovery fails at EOF");
869               return false;
870             }
871
872           /* otherwise, we consume another Symbol and try again */
873           // BUG FIX by Bruce Hutton
874           // Computer Science Department, University of Auckland,
875           // Auckland, New Zealand.
876           // It is the first token that is being consumed, not the one 
877           // we were up to parsing
878           if (debug) 
879               debug_message("# Consuming Symbol #" + lookahead[ 0 ].sym);
880           restart_lookahead();
881         }
882
883       /* we have consumed to a point where we can parse forward */
884       if (debug) debug_message("# Parse-ahead ok, going back to normal parse");
885
886       /* do the real parse (including actions) across the lookahead */
887       parse_lookahead(debug);
888
889       /* we have success */
890       return true;
891     }
892
893   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
894
895   /** Determine if we can shift under the special error Symbol out of the 
896    *  state currently on the top of the (real) parse stack. 
897    */
898   protected boolean shift_under_error()
899     {
900       /* is there a shift under error Symbol */
901       return get_action(((Symbol)stack.peek()).parse_state, error_sym()) > 0;
902     }
903
904   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
905
906   /** Put the (real) parse stack into error recovery configuration by 
907    *  popping the stack down to a state that can shift on the special 
908    *  error Symbol, then doing the shift.  If no suitable state exists on 
909    *  the stack we return false 
910    *
911    * @param debug should we produce debugging messages as we parse.
912    */
913   protected boolean find_recovery_config(boolean debug)
914     {
915       Symbol error_token;
916       int act;
917
918       if (debug) debug_message("# Finding recovery state on stack");
919
920       /* Remember the right-position of the top symbol on the stack */
921       int right_pos = ((Symbol)stack.peek()).right;
922       int left_pos  = ((Symbol)stack.peek()).left;
923
924       /* pop down until we can shift under error Symbol */
925       while (!shift_under_error())
926         {
927           /* pop the stack */
928           if (debug) 
929             debug_message("# Pop stack by one, state was # " +
930                           ((Symbol)stack.peek()).parse_state);
931           left_pos = ((Symbol)stack.pop()).left;        
932           tos--;
933
934           /* if we have hit bottom, we fail */
935           if (stack.empty()) 
936             {
937               if (debug) debug_message("# No recovery state found on stack");
938               return false;
939             }
940         }
941
942       /* state on top of the stack can shift under error, find the shift */
943       act = get_action(((Symbol)stack.peek()).parse_state, error_sym());
944       if (debug) 
945         {
946           debug_message("# Recover state found (#" + 
947                         ((Symbol)stack.peek()).parse_state + ")");
948           debug_message("# Shifting on error to state #" + (act-1));
949         }
950
951       /* build and shift a special error Symbol */
952       error_token = new Symbol(error_sym(), left_pos, right_pos);
953       error_token.parse_state = act-1;
954       error_token.used_by_parser = true;
955       stack.push(error_token);
956       tos++;
957
958       return true;
959     }
960
961   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
962
963   /** Lookahead Symbols used for attempting error recovery "parse aheads". */
964   protected Symbol lookahead[];
965
966   /** Position in lookahead input buffer used for "parse ahead". */
967   protected int lookahead_pos;
968
969   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
970
971   /** Read from input to establish our buffer of "parse ahead" lookahead 
972    *  Symbols. 
973    */
974   protected void read_lookahead() throws java.lang.Exception
975     {
976       /* create the lookahead array */
977       lookahead = new Symbol[error_sync_size()];
978
979       /* fill in the array */
980       for (int i = 0; i < error_sync_size(); i++)
981         {
982           lookahead[i] = cur_token;
983           cur_token = scan();
984         }
985
986       /* start at the beginning */
987       lookahead_pos = 0;
988     }
989
990   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
991
992   /** Return the current lookahead in our error "parse ahead" buffer. */
993   protected Symbol cur_err_token() { return lookahead[lookahead_pos]; }
994
995   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
996
997   /** Advance to next "parse ahead" input Symbol. Return true if we have 
998    *  input to advance to, false otherwise. 
999    */
1000   protected boolean advance_lookahead()
1001     {
1002       /* advance the input location */
1003       lookahead_pos++;
1004
1005       /* return true if we didn't go off the end */
1006       return lookahead_pos < error_sync_size();
1007     }
1008
1009   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1010
1011   /** Reset the parse ahead input to one Symbol past where we started error 
1012    *  recovery (this consumes one new Symbol from the real input). 
1013    */
1014   protected void restart_lookahead() throws java.lang.Exception
1015     {
1016       /* move all the existing input over */
1017       for (int i = 1; i < error_sync_size(); i++)
1018         lookahead[i-1] = lookahead[i];
1019
1020       /* read a new Symbol into the last spot */
1021       // BUG Fix by Bruce Hutton
1022       // Computer Science Department, University of Auckland,
1023       // Auckland, New Zealand. [applied 5-sep-1999 by csa]
1024       // The following two lines were out of order!!
1025       lookahead[error_sync_size()-1] = cur_token;
1026       cur_token = scan();
1027
1028       /* reset our internal position marker */
1029       lookahead_pos = 0;
1030     }
1031
1032   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1033
1034   /** Do a simulated parse forward (a "parse ahead") from the current 
1035    *  stack configuration using stored lookahead input and a virtual parse
1036    *  stack.  Return true if we make it all the way through the stored 
1037    *  lookahead input without error. This basically simulates the action of 
1038    *  parse() using only our saved "parse ahead" input, and not executing any 
1039    *  actions.
1040    *
1041    * @param debug should we produce debugging messages as we parse.
1042    */
1043   protected boolean try_parse_ahead(boolean debug)
1044     throws java.lang.Exception
1045     {
1046       int act;
1047       short lhs, rhs_size;
1048
1049       /* create a virtual stack from the real parse stack */
1050       virtual_parse_stack vstack = new virtual_parse_stack(stack);
1051
1052       /* parse until we fail or get past the lookahead input */
1053       for (;;)
1054         {
1055           /* look up the action from the current state (on top of stack) */
1056           act = get_action(vstack.top(), cur_err_token().sym);
1057
1058           /* if its an error, we fail */
1059           if (act == 0) return false;
1060
1061           /* > 0 encodes a shift */
1062           if (act > 0)
1063             {
1064               /* push the new state on the stack */
1065               vstack.push(act-1);
1066
1067               if (debug) debug_message("# Parse-ahead shifts Symbol #" + 
1068                        cur_err_token().sym + " into state #" + (act-1));
1069
1070               /* advance simulated input, if we run off the end, we are done */
1071               if (!advance_lookahead()) return true;
1072             }
1073           /* < 0 encodes a reduce */
1074           else
1075             {
1076               /* if this is a reduce with the start production we are done */
1077               if ((-act)-1 == start_production()) 
1078                 {
1079                   if (debug) debug_message("# Parse-ahead accepts");
1080                   return true;
1081                 }
1082
1083               /* get the lhs Symbol and the rhs size */
1084               lhs = production_tab[(-act)-1][0];
1085               rhs_size = production_tab[(-act)-1][1];
1086
1087               /* pop handle off the stack */
1088               for (int i = 0; i < rhs_size; i++)
1089                 vstack.pop();
1090
1091               if (debug) 
1092                 debug_message("# Parse-ahead reduces: handle size = " + 
1093                   rhs_size + " lhs = #" + lhs + " from state #" + vstack.top());
1094
1095               /* look up goto and push it onto the stack */
1096               vstack.push(get_reduce(vstack.top(), lhs));
1097               if (debug) 
1098                 debug_message("# Goto state #" + vstack.top());
1099             }
1100         }
1101     }
1102
1103   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1104
1105   /** Parse forward using stored lookahead Symbols.  In this case we have
1106    *  already verified that parsing will make it through the stored lookahead
1107    *  Symbols and we are now getting back to the point at which we can hand
1108    *  control back to the normal parser.  Consequently, this version of the
1109    *  parser performs all actions and modifies the real parse configuration.  
1110    *  This returns once we have consumed all the stored input or we accept.
1111    *
1112    * @param debug should we produce debugging messages as we parse.
1113    */
1114   protected void parse_lookahead(boolean debug)
1115     throws java.lang.Exception
1116     {
1117       /* the current action code */
1118       int act;
1119
1120       /* the Symbol/stack element returned by a reduce */
1121       Symbol lhs_sym = null;
1122
1123       /* information about production being reduced with */
1124       short handle_size, lhs_sym_num;
1125
1126       /* restart the saved input at the beginning */
1127       lookahead_pos = 0;
1128
1129       if (debug) 
1130         {
1131           debug_message("# Reparsing saved input with actions");
1132           debug_message("# Current Symbol is #" + cur_err_token().sym);
1133           debug_message("# Current state is #" + 
1134                         ((Symbol)stack.peek()).parse_state);
1135         }
1136
1137       /* continue until we accept or have read all lookahead input */
1138       while(!_done_parsing)
1139         {
1140           /* current state is always on the top of the stack */
1141
1142           /* look up action out of the current state with the current input */
1143           act = 
1144             get_action(((Symbol)stack.peek()).parse_state, cur_err_token().sym);
1145
1146           /* decode the action -- > 0 encodes shift */
1147           if (act > 0)
1148             {
1149               /* shift to the encoded state by pushing it on the stack */
1150               cur_err_token().parse_state = act-1;
1151               cur_err_token().used_by_parser = true;
1152               if (debug) debug_shift(cur_err_token());
1153               stack.push(cur_err_token());
1154               tos++;
1155
1156               /* advance to the next Symbol, if there is none, we are done */
1157               if (!advance_lookahead()) 
1158                 {
1159                   if (debug) debug_message("# Completed reparse");
1160
1161                   /* scan next Symbol so we can continue parse */
1162                   // BUGFIX by Chris Harris <ckharris@ucsd.edu>:
1163                   //   correct a one-off error by commenting out
1164                   //   this next line.
1165                   /*cur_token = scan();*/
1166
1167                   /* go back to normal parser */
1168                   return;
1169                 }
1170               
1171               if (debug) 
1172                 debug_message("# Current Symbol is #" + cur_err_token().sym);
1173             }
1174           /* if its less than zero, then it encodes a reduce action */
1175           else if (act < 0)
1176             {
1177               /* perform the action for the reduce */
1178               lhs_sym = do_action((-act)-1, this, stack, tos);
1179
1180               /* look up information about the production */
1181               lhs_sym_num = production_tab[(-act)-1][0];
1182               handle_size = production_tab[(-act)-1][1];
1183
1184               if (debug) debug_reduce((-act)-1, lhs_sym_num, handle_size);
1185
1186               /* pop the handle off the stack */
1187               for (int i = 0; i < handle_size; i++)
1188                 {
1189                   stack.pop();
1190                   tos--;
1191                 }
1192               
1193               /* look up the state to go to from the one popped back to */
1194               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
1195
1196               /* shift to that state */
1197               lhs_sym.parse_state = act;
1198               lhs_sym.used_by_parser = true;
1199               stack.push(lhs_sym);
1200               tos++;
1201                
1202               if (debug) debug_message("# Goto state #" + act);
1203
1204             }
1205           /* finally if the entry is zero, we have an error 
1206              (shouldn't happen here, but...)*/
1207           else if (act == 0)
1208             {
1209               report_fatal_error("Syntax error", lhs_sym);
1210               return;
1211             }
1212         }
1213
1214         
1215     }
1216
1217   /*-----------------------------------------------------------*/
1218
1219   /** Utility function: unpacks parse tables from strings */
1220   protected static short[][] unpackFromStrings(String[] sa)
1221     {
1222       // Concatanate initialization strings.
1223       StringBuffer sb = new StringBuffer(sa[0]);
1224       for (int i=1; i<sa.length; i++)
1225         sb.append(sa[i]);
1226       int n=0; // location in initialization string
1227       int size1 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
1228       short[][] result = new short[size1][];
1229       for (int i=0; i<size1; i++) {
1230         int size2 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
1231         result[i] = new short[size2];
1232         for (int j=0; j<size2; j++)
1233           result[i][j] = (short) (sb.charAt(n++)-2);
1234       }
1235       return result;
1236     }
1237 }
1238