Your next task is to construct a parser using a parser generator (e.g. Bison) that recognizes strings in the language whose grammars you will develop and the scanner that you have already done.  The parser should create an abstract syntax tree (AST) whose leaves are the necessary terminals and whose internal nodes are labeled with the kind of sentence represented by the sub tree.

You need to define, at this point, the structure of the abstract syntax tree based on the grammar you develop. For example, the C++ declaration "might" look like

enum node_c { PROGRAM, BLOCK, TYPE_DEF, VAR_DEF, … }

class Node {
    public:
            …
            node_c get_node_class();
            …

    protected:
            node_c node_class;
            …
};

class Program: public Node {
    public:
            Program(…) { node_class = PROGRAM; … }
            …

     protected:
            token_pair name;
            node *type_defs[];
            node *var_defs[];
            node *subprog_defs[];
            node *body;
            …
};
…

As you add phases to the compiler, you will need to go back and add new fields to the various node types in order to hold other information (type, size, etc.) that is gathered by subsequent phases. For now, though, it is sufficient to define only those fields required to represent the AST.

What you should turn in
1. The Parser-generator specification along with an updated (if necessary)
    Scanner.

2. A driver program that reads a program (such as the test programs) and prints
    out the AST. (follow the link for sample AST)

3. The grammar you use for your parser. (See the link for sample)

 

Parser  (Due: March 9, 2004)

Objective:

Sample Code:

Sample output:

Sample Grammar: