View Javadoc

    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;
    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 stack  = new ArrayList();
    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 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 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 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 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 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 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 toString( )
    464     {
    465         StringBuffer buffer = new StringBuffer();
    466         String 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 }