Copyright © 1998, Compiler Resources, Inc.
Parser Stack Overflow FAQ

Yacc++® and the Language Objects Library

Parser Stack Overflow

Parser stack overflows can be avoided in several ways.

  1. Read Tutorial REMOVE in the Tutorial Guide

    Long lists from regular expression rules can leave a lot of stuff on the parser stack. If you use REMOVE declarations, you will prevent stack overflows. For example, if you have:

        program : line+ ;

    and there can be a million lines, you don't want to create a parser object with a stack of size million. If you can use a REMOVE declaration:

        remove line;

    the stack will never have more than one entry for the above grammar.

    If you are uncertain what non-terminals and tokens are overflowing your parser stack, compile with traces enabled and you will be able to see what is on the stack.

    Please read Tutorial Debug in the Tutorial Guide to learn how to enable traces and view output.

  2. Explicit Parser Stack Management

    In addition to using REMOVE declarations, you can selectively remove entries on a case by case basis in your action code. The following example shows a REMOVE declaration and an explicit removal in action code.

    //  COMMA is a syntactic element only.  There is no semantic information associated with it.
    //  Use the remove declaration as there is no reason to have COMMA occupy space on the parser stack.
    
    remove COMMA;
    
    ItemList  : Item  (COMMA Item
                       {                 
                          // Do what you need to do with the semantic information associated with
                          // each Item as you parse.  Then delete it.
    
                          ... your important stuff with item ...
    
                          //  These item lists can be very, very long so remove it 
                          //  from the parser stack as soon as we are done with each Item
    
                         --yy_psr_left;  // At Yacc++ Rev 2.3, this is yy_psr_left_pop();
                                         // At previous Rev 2.x releases, use --yy_psr_left explicitly.
                       }
                       )*
    

  3. Review Your Parser Constructor

    Your parser constructor sets the size of the parser stack according to your specifications. The size of the parser stack determines the maximum length of a production that can be reduced.

    Is your parser creation using default arguments for the size of the parser stack? It is the 4th argument (left maximum) that is of interest.

        yy_psr_prog_obj(
            yy_lex_ptr      yy_this_lex_obj_ptr,
            int             yy_psr_new_class = yy_psr_dflt_class_,
            int             yy_psr_new_start = yy_psr_dflt_start_,
            int             yy_psr_new_left_max = yy_psr_left_max_,
            int             yy_psr_new_rt_max = yy_psr_rt_max_,
            int             yy_psr_new_rdc_max = yy_psr_rdc_max_
            );
    

    The following parser constructor uses default arguments:

         yy_parser = new yy_psr_prog_obj(yy_lexer, 
                            yy_psr_obj::yy_psr_dflt_class_, 
                            yy_psr_obj::yy_psr_dflt_start_);
    

    The size of the parser stack in the default case is yy_psr_left_max_ 8192 which may be too small for your application. (The size is the lowest common denominator, that is the largest size that DOS can handle).

         //  yy_psr_left_max_    is the default value for the length of a production
         //                      which can be reduced.
         // 
         enum yy_psr_left_max_enum { yy_psr_left_max_ = 8192 };
    

    You can explicitly set it to a larger size at the time of parser creation. For example:

         //  Create a parser object
    
        yy_parser = new yy_psr_prog_obj(yy_lexer, 
                            yy_psr_obj::yy_psr_dflt_class_, 
                            yy_psr_obj::yy_psr_dflt_start_,
                            yy_psr_obj::yy_psr_left_max_ * 2
                    );
    
  4. Revision 2.3

    Revision 2.3 is in beta as of this writing (August 1998). We've changed the parser stack to automatically grow to prevent overflows, as the lexer does. We recommend you continue to manage your parser stack usage efficiently as in previous revisions for optimal space management.

    There is still some discussion if "hiding" unnecessary usage of stack space by extending, extending, extending... is always a good thing. Opinions?


    Last updated on August 11, 1998. To send email to Compiler Resources, Inc.

    Return to Yacc++ Home Page