Abstract Syntax
***************

The abstract syntax is one of the several intermediate representations which are used in compilers.  It represents the input text without all the punctuation such as {, }, ,, ; etc. which have no computation meaning, but which are required by the concrete syntax to express the structure of the text.

Now that the text is parsed, the structure is simply given by the tree itself.

This section considers only the case of Yacc parsers.

Symbols
=======

Obviously, when the scanner meets a string or an integer, it ``returns'' a string or an integer.  What should it do about identifiers.

There are several solutions, the most obvious one being just returning the string which composes the identifier.  But this is very inefficient: you will allocate a new string each time you meet an identifier, even if you see the same one a million times, you need to strcmp to check whether two identifiers are equal etc.

An excellent alternative, which is widely used in computer science, consists in mapping all the strings which are equal to a unique one.  In Tiger, this unique string is named a symbol.

Building the Parse Tree
=======================

We will use the action and the semantic values of the Yacc parsers in order to generate the parse tree.  To this end we first have to augment the definition of the %union with all the types of information we will need while building the tree.  Something like:

     %union yystype
     {
       /* Tokens. */
       int ival;
       char *str;
       symbol_t *symbol;

       /* Non terminal. */
       var_t *var;
       ty_t *ty;
       field_t *field;
       exp_t *exp;
     }

then you precise what are the type of the semantic values of the non terminals:

     %type <var> lvalue biglvalue
     %type <exp> exp
     %type <ty> ty
     %type <field> tyfield

and add the right actions to each rule:

     exp:
       INT      { $$ = exp_int_new ($1) }
     | STRING   { $$ = exp_string_new ($1) };

Using Locations
===============

This section was co-written by Cyrille Belfort.

When the abstract syntax tree is built, the validity of the program being compiled is not yet guaranteed, in particular type checking is yet to be performed.  Therefore, since we have to report accurate error messages to the user, we must find a means to keep track of the locations of the tokens, and of the extend of larger constructs.

Bison provides such a service, via so called locations.  It keeps track for you of the extend of constructs.  Unless specified by the user, it uses an aggregate which contains:

       int first_line;
       int first_column;
       int last_line;
       int last_column;

Of course you need to tell your parser the location of the tokens, which you do via yylloc, as you do for semantic values with yylval.  This phase is delicate and it is a pity that Flex doesn't provide a direct support for this.

We can use C++ class to implement locations.

With much intellectual work and some intuition, using a class which provides tools helping manipulate one line and one column seems te be interesting: calling this class Position shows that we are next to sanity.  Some hours later our guardian angel appears to us ostentatiously and tells us: ``Position is good but something is missing, your tokens should have a beginning position but none without an end indicator''.  That is the reason why we did a location. Let us show it to you:

     class Position
     {
     public:
       //some usefull/useless constante to remmember
       //where does lines and columns begin

     	static const int	initial_line = 1;
     	static const int	initial_column = 1;

       //we should be able to construct the class
       //i think it wouldn't compile without a constructor

     	Position() : filename ("none"),
     		     line (initial_line),
      		     column (initial_column)
     	{
     	}

       //an assignment operator

     	const Position&
     	operator =(const Position& pos)
     	{
     	//no you can do it by yourself
     	{

       //column modification

     	inline
     	void
     	column_add(/*what could be here?*/)
     	{
     	//nothing could be easier
     	}

       //line modification it's a litle bit harder: one more code line
     	inline
     	void
     	line_add(/*something's missing, isn't it?*/)
     	{
     	//a brain could help filling this
     	}

      //did you notice we worked without any column or line

       public:
     	std::string	filename;
     	int		line;
     	int		column;
     }

You can add operators like +, +=, << but be carefull you shouldn't forget there are columns and lines.

So Position is good for healthy people. Now here is a Location example

     class Location
     {
     public:

       //this is a construtor we did it for you because
       //it's special: it calls on other construtors

     	Location() : begin(),
     		     end()
     	{
     	}

     	Position	begin;
     	Position	end;

       //we will only tell you what should be used to help:
       //a step : begin = end
       //column adds to end
       //line adds to end
       //word begin = end and end+ = 1
     }

As usually you can (and should) add some operators : +=, +, <<.

With those classes you are ready to set good locations in your scanner. But remember: nothing is error safe so do it carefully.  Here is a (simple) use of location.  YYLTYPE is Location, so yylloc is a Location.

     extern YYLTYPE  yylloc;

       //some/many lines
       //we only show it on some key words:

       	"if"	{ yylloc.word(yyleng); return IF; }
     	"then"  { yylloc.word(yyleng); return THEN; }

       //for those who don't understand the word function : begin goes to
       //last end, end goes to the end of the token

Now, in your Bison grammar file, you may use @$, @1, @2 etc. just as you use $$ and the like.  In particular, each node of the abstract syntax tree should be decorated with its location, i.e.:

     exp:
         NIL			{ $$ = new absyn::NilExp (@$); }
       | lvalue ASSIGN exp   { $$ = new absyn::AssignExp (@$, $1, $3); }
       | IF exp THEN exp	{ $$ = new absyn::IfExp (@$, *$2, *$4); }

It is quite easy to check that you computed properly the locations: just verify that the location of the result of your parsing corresponds to the full program.

You can also specify your own structure (for C-like parsers), and even a (better?) C++ class actually. You must not forget the mandatory members which are expected by Bison:

To use this feature, you need to define the structure you want to use for locations, for instance:

     struct position_s
     {
       string filename;
       int first_line;
       int first_column;
       int last_line;
       int last_column;
     };

then you teach Bison which structure it must use for locations: just #define YYLTYPE struct position_s in your parser.  And of course, be sure that your scanner can ``see'' this definition too.

Using Bison in C++
==================

Bison does not support C++ in the sense that it does not provide a reified interface.  Nonetheless, since it produces C code, it is possible to use C++ code in your parser.  Actually, you can just program as if C++ was supported.

Nonetheless, there is an important shortcoming due to the use of a C union to implement %union.  You cannot write:

     %union yystype
     {
       /* Tokens. */
       int ival;
       string str;
       Symbol symbol;

       /* Non terminal. */
       Var var;
       Ty ty;
       Field field;
       Exp exp;
     }

because it is illegal in C++ to put an object with a constructor into a union:

     parsetiger.y:32: member `class string yystype::str' with constructor \
                      not allowed in union

nevertheless, it is allowed to use pointers to objects:

     %union yystype
     {
       /* Tokens. */
       int ival;
       string *str;
       Symbol *symbol;

       /* Non terminal. */
       Var *var;
       Ty *ty;
       Field *field;
       Exp *exp;
     }

unfortunately this means that if you wanted to work this references, you will have to cripple your semantic actions with dereferences, and new:

     exp:
       NIL
        { $$ = new NilExp (@$) }
     | lvalue ASSIGN exp
        { $$ =  new AssignExp (@$, *$1, *$3) }
     | IF exp THEN exp
        { $$ = new IfExp (@$, *$2, *$4) }

You will notice that anyway in the case of Exp and the like, since it is an abstract class, the C++ requires that you use a pointer.