Java > Open Source Codes > org > jacorb > idl > runtime > lr_parser


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags