Home | History | Annotate | Download | only in runtime 
      1 
      2 package java_cup.runtime;
      3 
      4 import java.util.Stack;
      5 
      6 /** This class implements a temporary or "virtual" parse stack that
      7  *  replaces the top portion of the actual parse stack (the part that
      8  *  has been changed by some set of operations) while maintaining its
      9  *  original contents.  This data structure is used when the parse needs
     10  *  to "parse ahead" to determine if a given error recovery attempt will
     11  *  allow the parse to continue far enough to consider it successful.  Once
     12  *  success or failure of parse ahead is determined the system then
     13  *  reverts to the original parse stack (which has not actually been
     14  *  modified).  Since parse ahead does not execute actions, only parse
     15  *  state is maintained on the virtual stack, not full symbol objects.
     16  *
     17  * @see     java_cup.runtime.lr_parser
     18  * @version last updated: 11/25/95
     19  * @author  Scott Hudson
     20  */
     21 
     22 public class virtual_parse_stack {
     23   /*-----------------------------------------------------------*/
     24   /*--- Constructor(s) ----------------------------------------*/
     25   /*-----------------------------------------------------------*/
     26 
     27   /** Constructor to build a virtual stack out of a real stack. */
     28   public virtual_parse_stack(Stack shadowing_stack) throws java.lang.Exception
     29     {
     30       /* sanity check */
     31       if (shadowing_stack == null)
     32     throw new Exception(
     33       "Internal parser error: attempt to create null virtual stack");
     34 
     35       /* set up our internals */
     36       real_stack = shadowing_stack;
     37       vstack     = new Stack();
     38       real_next  = 0;
     39 
     40       /* get one element onto the virtual portion of the stack */
     41       get_from_real();
     42     }
     43 
     44   /*-----------------------------------------------------------*/
     45   /*--- (Access to) Instance Variables ------------------------*/
     46   /*-----------------------------------------------------------*/
     47 
     48   /** The real stack that we shadow.  This is accessed when we move off
     49    *  the bottom of the virtual portion of the stack, but is always left
     50    *  unmodified.
     51    */
     52   protected Stack real_stack;
     53 
     54   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     55 
     56   /** Top of stack indicator for where we leave off in the real stack.
     57    *  This is measured from top of stack, so 0 would indicate that no
     58    *  elements have been "moved" from the real to virtual stack.
     59    */
     60   protected int real_next;
     61 
     62   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     63 
     64   /** The virtual top portion of the stack.  This stack contains Integer
     65    *  objects with state numbers.  This stack shadows the top portion
     66    *  of the real stack within the area that has been modified (via operations
     67    *  on the virtual stack).  When this portion of the stack becomes empty we
     68    *  transfer elements from the underlying stack onto this stack.
     69    */
     70   protected Stack vstack;
     71 
     72   /*-----------------------------------------------------------*/
     73   /*--- General Methods ---------------------------------------*/
     74   /*-----------------------------------------------------------*/
     75 
     76   /** Transfer an element from the real to the virtual stack.  This assumes
     77    *  that the virtual stack is currently empty.
     78    */
     79   protected void get_from_real()
     80     {
     81       symbol stack_sym;
     82 
     83       /* don't transfer if the real stack is empty */
     84       if (real_next >= real_stack.size()) return;
     85 
     86       /* get a copy of the first symbol we have not transfered */
     87       stack_sym = (symbol)real_stack.elementAt(real_stack.size()-1-real_next);
     88 
     89       /* record the transfer */
     90       real_next++;
     91 
     92       /* put the state number from the symbol onto the virtual stack */
     93       vstack.push(new Integer(stack_sym.parse_state));
     94     }
     95 
     96   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     97 
     98   /** Indicate whether the stack is empty. */
     99   public boolean empty()
    100     {
    101       /* if vstack is empty then we were unable to transfer onto it and
    102      the whole thing is empty. */
    103       return vstack.empty();
    104     }
    105 
    106   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    107 
    108   /** Return value on the top of the stack (without popping it). */
    109   public int top() throws java.lang.Exception
    110     {
    111       if (vstack.empty())
    112     throw new Exception(
    113           "Internal parser error: top() called on empty virtual stack");
    114 
    115       return ((Integer)vstack.peek()).intValue();
    116     }
    117 
    118   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    119 
    120   /** Pop the stack. */
    121   public void pop() throws java.lang.Exception
    122     {
    123       if (vstack.empty())
    124     throw new Exception(
    125           "Internal parser error: pop from empty virtual stack");
    126 
    127       /* pop it */
    128       vstack.pop();
    129 
    130       /* if we are now empty transfer an element (if there is one) */
    131       if (vstack.empty())
    132         get_from_real();
    133     }
    134 
    135   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    136 
    137   /** Push a state number onto the stack. */
    138   public void push(int state_num)
    139     {
    140       vstack.push(new Integer(state_num));
    141     }
    142 
    143   /*-----------------------------------------------------------*/
    144 
    145 };
    146