View Javadoc
1   /*
2    * Copyright (c) 2003, 2005, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.  Oracle designates this
8    * particular file as subject to the "Classpath" exception as provided
9    * by Oracle in the LICENSE file that accompanied this code.
10   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   * version 2 for more details (a copy is included in the LICENSE file that
15   * accompanied this code).
16   *
17   * You should have received a copy of the GNU General Public License version
18   * 2 along with this work; if not, write to the Free Software Foundation,
19   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20   *
21   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22   * or visit www.oracle.com if you need additional information or have any
23   * questions.
24   */
25  
26  
27  package com.sun.java_cup.internal.runtime;
28  
29  import java.util.Stack;
30  
31  /** This class implements a temporary or "virtual" parse stack that
32   *  replaces the top portion of the actual parse stack (the part that
33   *  has been changed by some set of operations) while maintaining its
34   *  original contents.  This data structure is used when the parse needs
35   *  to "parse ahead" to determine if a given error recovery attempt will
36   *  allow the parse to continue far enough to consider it successful.  Once
37   *  success or failure of parse ahead is determined the system then
38   *  reverts to the original parse stack (which has not actually been
39   *  modified).  Since parse ahead does not execute actions, only parse
40   *  state is maintained on the virtual stack, not full Symbol objects.
41   *
42   * @see     com.sun.java_cup.internal.runtime.lr_parser
43   * @author  Frank Flannery
44   */
45  
46  public class virtual_parse_stack {
47    /*-----------------------------------------------------------*/
48    /*--- Constructor(s) ----------------------------------------*/
49    /*-----------------------------------------------------------*/
50  
51    /** Constructor to build a virtual stack out of a real stack. */
52    public virtual_parse_stack(Stack shadowing_stack) throws java.lang.Exception
53      {
54        /* sanity check */
55        if (shadowing_stack == null)
56          throw new Exception(
57            "Internal parser error: attempt to create null virtual stack");
58  
59        /* set up our internals */
60        real_stack = shadowing_stack;
61        vstack     = new Stack();
62        real_next  = 0;
63  
64        /* get one element onto the virtual portion of the stack */
65        get_from_real();
66      }
67  
68    /*-----------------------------------------------------------*/
69    /*--- (Access to) Instance Variables ------------------------*/
70    /*-----------------------------------------------------------*/
71  
72    /** The real stack that we shadow.  This is accessed when we move off
73     *  the bottom of the virtual portion of the stack, but is always left
74     *  unmodified.
75     */
76    protected Stack real_stack;
77  
78    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
79  
80    /** Top of stack indicator for where we leave off in the real stack.
81     *  This is measured from top of stack, so 0 would indicate that no
82     *  elements have been "moved" from the real to virtual stack.
83     */
84    protected int real_next;
85  
86    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
87  
88    /** The virtual top portion of the stack.  This stack contains Integer
89     *  objects with state numbers.  This stack shadows the top portion
90     *  of the real stack within the area that has been modified (via operations
91     *  on the virtual stack).  When this portion of the stack becomes empty we
92     *  transfer elements from the underlying stack onto this stack.
93     */
94    protected Stack vstack;
95  
96    /*-----------------------------------------------------------*/
97    /*--- General Methods ---------------------------------------*/
98    /*-----------------------------------------------------------*/
99  
100   /** Transfer an element from the real to the virtual stack.  This assumes
101    *  that the virtual stack is currently empty.
102    */
103   protected void get_from_real()
104     {
105       Symbol stack_sym;
106 
107       /* don't transfer if the real stack is empty */
108       if (real_next >= real_stack.size()) return;
109 
110       /* get a copy of the first Symbol we have not transfered */
111       stack_sym = (Symbol)real_stack.elementAt(real_stack.size()-1-real_next);
112 
113       /* record the transfer */
114       real_next++;
115 
116       /* put the state number from the Symbol onto the virtual stack */
117       vstack.push(new Integer(stack_sym.parse_state));
118     }
119 
120   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
121 
122   /** Indicate whether the stack is empty. */
123   public boolean empty()
124     {
125       /* if vstack is empty then we were unable to transfer onto it and
126          the whole thing is empty. */
127       return vstack.empty();
128     }
129 
130   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
131 
132   /** Return value on the top of the stack (without popping it). */
133   public int top() throws java.lang.Exception
134     {
135       if (vstack.empty())
136         throw new Exception(
137                   "Internal parser error: top() called on empty virtual stack");
138 
139       return ((Integer)vstack.peek()).intValue();
140     }
141 
142   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
143 
144   /** Pop the stack. */
145   public void pop() throws java.lang.Exception
146     {
147       if (vstack.empty())
148         throw new Exception(
149                   "Internal parser error: pop from empty virtual stack");
150 
151       /* pop it */
152       vstack.pop();
153 
154       /* if we are now empty transfer an element (if there is one) */
155       if (vstack.empty())
156         get_from_real();
157     }
158 
159   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
160 
161   /** Push a state number onto the stack. */
162   public void push(int state_num)
163     {
164       vstack.push(new Integer(state_num));
165     }
166 
167   /*-----------------------------------------------------------*/
168 
169 }