Copyright © 1998, Compiler Resources, Inc.
Line Numbers in AST Trees

Yacc++^® and the Language Objects Library

Preserving Line Numbers in an AST Tree -- An Example

We assume you are already familiar with Tutorial AST in the Tutorial Guide.

Using Example ASTB in Tutorial AST, the following changes were made:

The AST classes were customized to preserve line numbers. See astb.yxx.
A new file was added that contains the definitions for the custom base constructors. See date_base_class.cpp. The makefile was changed to build the new file.
yy_mainb.cpp was changed to use an input file object. I created test cases as input with multiple line puzzles. See the default yy_main.cpp in the Language Objects Library for input from file and command line object changes.

astb.yxx

//////////////////////////////////////////////////////////////////////////////
//
//  Copyright (c) 1995-1998, Compiler Resources, Inc.
//  
//  FILENAME:           astb.yxx
//   
//  FILE DESCRIPTION:   grammar to parse a date word problem and determine
//                      the answer in a two pass approach using CONSTRUCT
//                      and AST trees.  The same date word problem is solved
//                      in a single pass approach in asta.yxx.
//  
//                      This is described in the Yacc++ Tutorial Guide,
//                      Tutorial: AST -- The ABC's of AST's
//  
//  MODIFICATION HISTORY:
//  
//    09/10/98  bz      preserve line numbers in AST tree for FAQ.
//    02/03/95  bz      initial coding.
//  
//////////////////////////////////////////////////////////////////////////////

class astb;

lexer

substr keyword  JANUARY = 1 
                FEBRUARY 
                MARCH 
                APRIL 
                MAY 
                JUNE 
                JULY 
                AUGUST
                SEPTEMBER 
                OCTOBER 
                NOVEMBER 
                DECEMBER
                ; 

keyword         BEFORE  AFTER ;
   
token           NUMBER
                ;

discard token   IDENTIFIER  WHITE_SPACE  UNKNOWN_CHARS
                ;

construct IDENTIFIER :: keyword

        // default is to inherit directly from yy_ast_obj
        // here we inherit from grammar specific date base class below

        base { public date_base_class }

        constructor initializer {
        date_base_class(yy_this_lex_ptr)
        }

        constructor body {
        // token type numbers explicitly declared to correspond to the month
        yy_symbol()->yy_sym_type(yy_symbol()->yy_sym_tkn_type()); 
        }
     ;

IDENTIFIER   :  ("a" .. "z" | "A" .. "Z")+
             ;

construct NUMBER :: symbol

        // default is to inherit directly from yy_ast_obj
        // here we inherit from grammar specific date base class below

        base { public date_base_class }

        constructor initializer {
        date_base_class(yy_this_lex_ptr)
        }

        constructor body {
        // want NUMBER converted from string to integer form
        // atoi stops on the 1st non-digit
        yy_symbol()->yy_sym_type(atoi(yy_symbol()->yy_sym_str()));
        }
     ;

NUMBER       :  ("0" .. "9")+ ("st" | "nd" | "rd" | "th")?
             ;
             
WHITE_SPACE  :   (" "             // space
             |    "\t"            // tab
             |    "\n"            // newline
                                  {  ++yy_buf_lineno();  }
                  )+
             ;

UNKNOWN_CHARS :   @   // discard any extraneous characters
              ;    

parser ::
    destructor {
        int i;

        //  delete the objects in the parser stack
        //  each object recursively deletes its children

        for (i = 1; i < yy_psr_last(); ++i) {
            if (yy_psr_ref(i).as_base_ptr != NULL) {
                delete yy_psr_ref(i).as_base_ptr;
                }
            }
    };

global {
#include "yy_sym.h"
class yy_export yy_lex_astb_obj;
class yy_export yy_psr_astb_obj;
typedef class date_base_class *base_ptr;
}

union {
    base_ptr    as_base_ptr;
    }

base construct date_base_class ::
    member {
      public:

//  By default there is no explicit constructor to the base class.  
//  Here we are adding one for the lexer and one for the parser
//  so that we can centralize the preserving of line # information 
//  in each leaf of the AST tree for the 2nd pass.  
//
//  Note that each AST construct needs to explicitly call its 
//  constructor passing along the pointer to its lexer or parser object.
//
        date_base_class(yy_psr_astb_obj *yy_this_psr_ptr);
        date_base_class(yy_lex_astb_obj *yy_this_lex_ptr);

        virtual yy_sym_ptr yy_symbol()      { return(NULL); }
        virtual int        cur_month()      { return(0); }
        virtual int        cur_day()        { return(0); }
        virtual int        cur_year()       { return(0); }
        virtual const char *display_month() { return(NULL); }
        virtual const char *display_day()   { return(NULL); }
        virtual int        cur_line()       { return(line_num); }

      protected:
        int line_num;
    }
;

//  a default AST gives just the type field
//      yy_type()
//  we explicitly add month, day, and year members.

construct date :: default

    base { public date_base_class }

    constructor initializer {
        month(yy_this_psr_ptr->yy_psr_ref(1).as_base_ptr->yy_symbol()),
        day(yy_this_psr_ptr->yy_psr_ref(2).as_base_ptr->yy_symbol()),
        year(yy_this_psr_ptr->yy_psr_ref(4).as_base_ptr->
                yy_symbol()->yy_sym_type()),
        date_base_class(yy_this_psr_ptr)
    }

    // delete token ASTs since date is a default (not an all) AST.
    // this delete does not interfere with the storing of symbols
    // for month and day since deletion of the token ASTs don't
    // automatically delete the symbols in their operands.

    constructor body {
        delete yy_this_psr_ptr->yy_psr_ref(1).as_base_ptr;
        delete yy_this_psr_ptr->yy_psr_ref(2).as_base_ptr;
        // no AST to delete for yy_psr_ref(3) which is a COMMA
        delete yy_this_psr_ptr->yy_psr_ref(4).as_base_ptr;
        }

    member {
      public:
        yy_sym_ptr month;
        yy_sym_ptr day;
        int        year;
        int        cur_month()      { return(month->yy_sym_type()); }
        int        cur_day()        { return(month->yy_sym_type()); }
        int        cur_year()       { return(year); }
        const char *display_month() { return(month->yy_sym_str()); }
        const char *display_day()   { return(day->yy_sym_str()); }
    }
;

//  an ALL AST has type member plus all operands from parser stack
//      yy_type 
//      yy_operand(0) .. yy_operand(yy_num_operands())
//
//  for date_before class
//  month        yy_operand(0).as_base_ptr to KEYWORD AST, 
//                  type field is month #
//  NUMBER       yy_operand(1).as_base_ptr to SYMBOL AST, 
//                  day stored in type
//  BEFORE       yy_operand(2).as_base_ptr to KEYWORD AST, not used
//  date_clauses yy_operand(3).as_base_ptr to tree of date ASTs
//

construct date_before :: all

    base { public date_base_class }

    constructor initializer {
        date_base_class(yy_this_psr_ptr)
        }

    member {
      public:
        int cur_month() { 
            return(yy_operand(0).as_base_ptr->yy_symbol()->yy_sym_type());
        }

        int cur_day() {
            return(yy_operand(1).as_base_ptr->yy_symbol()->yy_sym_type());
        }

        int cur_year() {
        //  if the month is later in the year, 
        //  then the year must be a year earlier

        if (cur_month() > yy_operand(3).as_base_ptr->cur_month()) {
            return(yy_operand(3).as_base_ptr->cur_year() - 1);
            }

        //  if the day is the same or later in the month, 
        //  then the year must be a year earlier

        else if ((cur_month() == yy_operand(3).as_base_ptr->cur_month()) && 
                (cur_day() >= yy_operand(3).as_base_ptr->cur_day())) {
            return(yy_operand(3).as_base_ptr->cur_year() - 1);
            }

        //  otherwise, it is the same year 
        return(yy_operand(3).as_base_ptr->cur_year());
        }

        const char *display_month() 
            { return(yy_operand(0).as_base_ptr->yy_symbol()->yy_sym_str()); }
        const char *display_day()
            { return(yy_operand(1).as_base_ptr->yy_symbol()->yy_sym_str()); }
    }
;

//  an ALL AST has type member plus all operands from parser stack
//      yy_type 
//      yy_operand(0) .. yy_operand(yy_num_operands())
//
//  for date_after class
//  month        yy_operand(0).as_base_ptr to KEYWORD AST, 
//                  type field is month #
//  NUMBER       yy_operand(1).as_base_ptr to SYMBOL AST, 
//                  day stored in type
//  AFTER        yy_operand(2).as_base_ptr to KEYWORD AST, not used
//  date_clauses yy_operand(3).as_base_ptr to tree of date ASTs
//

construct date_after :: all

    base { public date_base_class }

        constructor initializer {
        date_base_class(yy_this_psr_ptr)
        }

    member {
      public:
        int cur_month() { 
            return(yy_operand(0).as_base_ptr->yy_symbol()->yy_sym_type());
        }

        int cur_day() { 
            return(yy_operand(1).as_base_ptr->yy_symbol()->yy_sym_type());
        }

        int cur_year() { 
        //  if the month is earlier in the year, 
        //  then the year must be a year later

        if (cur_month() < yy_operand(3).as_base_ptr->cur_month()) {
            return(yy_operand(3).as_base_ptr->cur_year() + 1);
            }

        //  if the day is the same or earlier in the month, 
        //  then the year must be a year later

        else if ((cur_month() == yy_operand(3).as_base_ptr->cur_month()) && 
                (cur_day() <= yy_operand(3).as_base_ptr->cur_day())) {
            return(yy_operand(3).as_base_ptr->cur_year() + 1);
            }

        //  otherwise, it is the same year 
        return(yy_operand(3).as_base_ptr->cur_year());
        }

        const char *display_month() 
            { return(yy_operand(0).as_base_ptr->yy_symbol()->yy_sym_str()); }
        const char *display_day()
            { return(yy_operand(1).as_base_ptr->yy_symbol()->yy_sym_str()); }
    }
;

date_problem :  date_clauses
             ;

date_clauses :  date_before
             |  date_after
             |  date
             ;

date_before  :  month  NUMBER  BEFORE  date_clauses
             ;

date_after   :  month  NUMBER  AFTER  date_clauses
             ;

date         :  month  NUMBER  ","  NUMBER
             ;

month        :  JANUARY | FEBRUARY | MARCH | APRIL | MAY | JUNE | JULY |
                AUGUST | SEPTEMBER | OCTOBER | NOVEMBER | DECEMBER
             ;

date_base_class.cpp

#include "yy_stdio.h"
#include "yy_bool.h"
#include "yy_cmd.h"
#include "yy_errst.h"
#include "yy_inp.h"
#include "yy_mylex.h"
#include "yy_mypsr.h"
#include "yy_sym.h"

//
//  for AST creation from the parser
// 
date_base_class::date_base_class(yy_psr_astb_obj *yy_this_psr_ptr)
{ 
  line_num = yy_this_psr_ptr->yy_psr_cur_lex()->yy_lex_cur_inp()->yy_inp_cur_buf()->yy_buf_lineno();
}

//
//  for AST creation from the lexer
// 
date_base_class::date_base_class(yy_lex_astb_obj *yy_this_lex_ptr)
{ 
  line_num = yy_this_lex_ptr->yy_lex_cur_inp()->yy_inp_cur_buf()->yy_buf_lineno();
}

Last updated on September 10, 1998. To send email to Compiler Resources, Inc.

Return to Yacc++ Home Page

Yacc++® and the Language Objects Library

Preserving Line Numbers in an AST Tree -- An Example

astb.yxx

date_base_class.cpp

Yacc++^® and the Language Objects Library