KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > codehaus > groovy > syntax > parser > ExpressionStack


1 /*
2  $Id: ExpressionStack.java,v 1.3 2004/04/30 09:57:46 cpoirier Exp $
3
4  Copyright 2003 (C) James Strachan and Bob Mcwhirter. All Rights Reserved.
5
6  Redistribution and use of this software and associated documentation
7  ("Software"), with or without modification, are permitted provided
8  that the following conditions are met:
9
10  1. Redistributions of source code must retain copyright
11     statements and notices. Redistributions must also contain a
12     copy of this document.
13
14  2. Redistributions in binary form must reproduce the
15     above copyright notice, this list of conditions and the
16     following disclaimer in the documentation and/or other
17     materials provided with the distribution.
18
19  3. The name "groovy" must not be used to endorse or promote
20     products derived from this Software without prior written
21     permission of The Codehaus. For written permission,
22     please contact info@codehaus.org.
23
24  4. Products derived from this Software may not be called "groovy"
25     nor may "groovy" appear in their names without prior written
26     permission of The Codehaus. "groovy" is a registered
27     trademark of The Codehaus.
28
29  5. Due credit should be given to The Codehaus -
30     http://groovy.codehaus.org/
31
32  THIS SOFTWARE IS PROVIDED BY THE CODEHAUS AND CONTRIBUTORS
33  ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
34  NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
35  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
36  THE CODEHAUS OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
37  INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
38  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
39  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
41  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
42  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
43  OF THE POSSIBILITY OF SUCH DAMAGE.
44
45  */
46
47 package org.codehaus.groovy.syntax.parser;
48
49 import java.util.ArrayList JavaDoc;
50
51 import org.codehaus.groovy.control.CompilationFailedException;
52 import org.codehaus.groovy.syntax.*;
53 import org.codehaus.groovy.GroovyBugError;
54
55
56
57 /**
58  * A combination stack and helper class for parsing groovy expression.
59  * <p>
60  * Expressions are a little trickier to parse than the statements above.
61  * As a result, we are now doing a hybrid LL/LR parse at the expression
62  * level.
63  *
64  * @author <a HREF="mailto:cpoirier@dreaming.org">Chris Poirier</a>
65  */
66
67 public class ExpressionStack
68 {
69     private ArrayList JavaDoc stack = new ArrayList JavaDoc();
70     private Parser parser = null;
71     private int open = 0;
72
73
74     ExpressionStack( Parser context )
75     {
76         this.parser = context;
77     }
78
79
80
81   //---------------------------------------------------------------------------
82 // PRIMARY OPERATIONS
83
84
85    /**
86     * Returns true if the stack is empty.
87     */
88
89     boolean isEmpty()
90     {
91         return stack.isEmpty();
92     }
93
94
95
96    /**
97     * Returns true if the stack is in a state that can be considered
98     * a complete expression, provided lookahead is amenable, of course.
99     */
100
101     public boolean isComplete()
102     {
103         return size() == 1 && topIsAnExpression();
104     }
105
106
107
108    /**
109     * Returns true if the stack can be completed without further shifts.
110     * Used by Parser.la(ExpressionStack) to determine when ambiguous tokens
111     * can't be read across a newline. The algorithm will guess true if it
112     * isn't sure. If it returns false, you can rely on that analysis.
113     */
114
115     public boolean canComplete()
116     {
117         //
118 // We can immediately return false if there is anything
119 // open or if the top is not an expression...
120
121         if( open > 0 || !topIsAnExpression() )
122         {
123             return false;
124         }
125
126
127         //
128 // If it is complete, it can complete...
129
130         if( size() == 1 )
131         {
132             return true;
133         }
134
135
136         //
137 // For everything else, we guess true. It is most likely
138 // the case, because of the way the parser moves complex
139 // stuff off to LL routines and validates the ordering of
140 // nodes pushed on the stack, that if the top is an expression,
141 // and nothing is "open" (ie. unmatched parenthesis, early
142 // stage ternary operators), the stack can be reduced back
143 // to the root without further shifts. Our guarantee is
144 // that our guess true might be wrong, but that we will only
145 // return false when we are sure, so, no harm done...
146
147         return true;
148     }
149
150
151
152    /**
153     * Returns the number of elements in the stack.
154     */
155
156     int size()
157     {
158         return stack.size();
159     }
160
161
162
163    /**
164     * Pushes a node onto the stack.
165     */
166
167     void push( CSTNode node )
168     {
169         if( (node.isA(Types.LEFT_PARENTHESIS) || node.isA(Types.QUESTION)) && node.size() == 1 )
170         {
171             open++;
172         }
173
174         stack.add( node );
175     }
176
177
178
179    /**
180     * Pops the node from the top of the stack.
181     */
182
183     CSTNode pop()
184     {
185         CSTNode node = (CSTNode)stack.remove( stack.size() - 1 );
186
187         if( (node.isA(Types.LEFT_PARENTHESIS) || node.isA(Types.QUESTION)) && node.size() == 1 )
188         {
189             open--;
190         }
191
192         return node;
193     }
194
195
196
197    /**
198     * Returns the top node from the stack without removing it.
199     */
200
201     CSTNode top()
202     {
203         return top(0);
204     }
205
206
207
208    /**
209     * Returns some node from the stack. <code>offset</code> is counted
210     * from the top of the stack.
211     */
212
213     CSTNode top( int offset )
214     {
215         if( offset < stack.size() )
216         {
217             return (CSTNode)stack.get( stack.size() - 1 - offset );
218         }
219         else
220         {
221             return Token.NULL;
222         }
223     }
224
225
226
227
228   //---------------------------------------------------------------------------
229 // PARSER OPERATIONS
230
231
232    /**
233     * Shifts some number of (non-newline) tokens from the stream to the top
234     * of the stack. They are pushed in order.
235     */
236
237     void shift( int count ) throws SyntaxException, CompilationFailedException
238     {
239         for( int i = 0; i < count; i++ )
240         {
241             push( parser.consume() );
242         }
243     }
244
245
246
247    /**
248     * Shifts a token from the stream to the top of the stack.
249     */
250
251     void shift() throws SyntaxException, CompilationFailedException
252     {
253         push( parser.consume() );
254     }
255
256
257
258    /**
259     * Performs a reduce by taking some number of <code>CSTNode</code>s
260     * from the top of the stack, and making one of them a
261     * <code>Reduction</code> with the others as children, then pushes
262     * that new node back onto the stack.
263     */
264
265     void reduce( int count, int rootOffset, boolean mark )
266     {
267         if( count <= rootOffset || rootOffset < 0 || count > size() )
268         {
269             throw new GroovyBugError( "error in call to ExpressionStack.reduce(): count=" + count + ", rootOffset=" + rootOffset );
270         }
271
272         CSTNode root = null;
273         CSTNode[] children = new CSTNode[count-1];
274
275         for( int child = count - 2, element = 0; element < count; element++ )
276         {
277             if( element == rootOffset )
278             {
279                 root = pop();
280             }
281             else
282             {
283                 children[child--] = pop();
284             }
285         }
286
287         root = root.asReduction();
288         for( int i = 0; i < children.length; i++ )
289         {
290             root.add( children[i] );
291         }
292
293         if( mark )
294         {
295             root.markAsExpression();
296         }
297
298         push( root );
299
300     }
301
302
303
304
305   //---------------------------------------------------------------------------
306 // TESTS
307
308
309    /**
310     * Return true if the stack is at the start of an expression. True if
311     * either the stack is empty or the top token is a left parenthesis.
312     */
313
314     boolean atStartOfExpression()
315     {
316         return isEmpty() || (top().isA(Types.LEFT_PARENTHESIS) && !top().hasChildren());
317     }
318
319
320
321    /**
322     * Returns true if the top element of the stack is an operator.
323     */
324
325     boolean topIsAnOperator( )
326     {
327         return ExpressionSupport.isAnOperator( top(), false );
328     }
329
330
331
332    /**
333     * Returns true if the element at the specified offset from the top
334     * of the stack is an operator.
335     */
336
337     boolean topIsAnOperator( int offset, boolean unknownReturns )
338     {
339         return ExpressionSupport.isAnOperator( top(offset), unknownReturns );
340     }
341
342
343
344    /**
345     * Returns true if the top element of the stack is a modifiable expression.
346     */
347
348     boolean topIsAModifiableExpression()
349     {
350         return ExpressionSupport.isAModifiableExpression( top() );
351     }
352
353
354
355    /**
356     * Returns true if the top element of the stack is an expression.
357     */
358
359     boolean topIsAnExpression( )
360     {
361         return top().isAnExpression();
362     }
363
364
365
366   //---------------------------------------------------------------------------
367 // SUGAR
368
369
370    /**
371     * Shifts if the specified flag is true, reports an error otherwise.
372     */
373
374     void shiftIf( boolean flag, String JavaDoc error ) throws SyntaxException, CompilationFailedException
375     {
376         if( flag )
377         {
378             push( parser.consume() );
379         }
380         else
381         {
382             parser.error( error );
383         }
384     }
385
386
387
388    /**
389     * Shifts unless the specified flag is true, reports an error otherwise.
390     */
391
392     void shiftUnless( boolean flag, String JavaDoc error ) throws SyntaxException, CompilationFailedException
393     {
394         if( flag )
395         {
396             parser.error( error );
397         }
398         else
399         {
400             push( parser.consume() );
401         }
402     }
403
404
405
406    /**
407     * Shifts if the top of the stack is an expression, reports an error
408     * otherwise.
409     */
410
411     void shiftIfTopIsAnExpression( String JavaDoc error ) throws SyntaxException, CompilationFailedException
412     {
413         shiftIf( ExpressionSupport.isAnExpression(top(), false), error );
414     }
415
416
417
418    /**
419     * Shifts if the top of the stack is a operator, reports an
420     * error otherwise.
421     */
422
423     void shiftIfTopIsAnOperator( String JavaDoc error ) throws SyntaxException, CompilationFailedException
424     {
425         shiftIf( ExpressionSupport.isAnOperator(top(), false), error );
426     }
427
428
429
430    /**
431     * Shifts unless the top of the stack is an expression, reports an
432     * error otherwise.
433     */
434
435     void shiftUnlessTopIsAnExpression( String JavaDoc error ) throws SyntaxException, CompilationFailedException
436     {
437         shiftUnless( ExpressionSupport.isAnExpression(top(), false), error );
438     }
439
440
441
442    /**
443     * Shifts unless the top of the stack is an operator, reports an
444     * error otherwise.
445     */
446
447     void shiftUnlessTopIsAnOperator( String JavaDoc error ) throws SyntaxException, CompilationFailedException
448     {
449         shiftUnless( ExpressionSupport.isAnOperator(top(), false), error );
450     }
451
452
453
454
455   //---------------------------------------------------------------------------
456 // OUTPUT
457
458
459    /**
460     * Creates a string representation of the stack.
461     */
462
463     public String JavaDoc toString( )
464     {
465         StringBuffer JavaDoc buffer = new StringBuffer JavaDoc();
466         String JavaDoc newline = System.getProperty( "line.separator", "\n" );
467         int count = stack.size();
468
469         buffer.append( "ExpressionStack with " ).append( size() ).append( " elements" ).append( newline );
470         for( int i = count - 1; i >= 0; i-- )
471         {
472             buffer.append( top(i).toString() ).append( newline );
473         }
474
475         return buffer.toString();
476     }
477
478 }
479
Popular Tags