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