1 /*
2  * Copyright (c) 2003, 2017, 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. */
virtual_parse_stack(Stack<Symbol> shadowing_stack)52   public virtual_parse_stack(Stack<Symbol> 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<Symbol> 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<Integer> 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    */
get_from_real()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 = real_stack.get(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(stack_sym.parse_state);
118     }
119 
120   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
121 
122   /** Indicate whether the stack is empty. */
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). */
top()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 (vstack.peek());
140     }
141 
142   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
143 
144   /** Pop the stack. */
pop()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. */
push(int state_num)162   public void push(int state_num)
163     {
164       vstack.push(state_num);
165     }
166 
167   /*-----------------------------------------------------------*/
168 
169 }
170