# Beaver - a LALR Parser Generator

## Building ASTs

### Making Symbols

Action routines create and return `beaver.Symbol`s, which become directly accessible via symbol aliases. So, if the AST nodes descend from `beaver.Symbol` and fulfill nonterminal symbols' contract (they must call Symbol's protected default constructor), they - the nodes - can be created and returned directly by action routines. Once a node was returned by an action routine, parser shifts it on the stack and it becomes accessible as a symbol of some other production's right-hand side. Now that production action routine will be able to reference it and, in its turn, attach to the higher level node it creates.

For example look at the following classes that define nodes for the AST of a simple expression:

    Symbol
        Node
            Expr
                NumExpr
                BinExpr
                    MultExpr
                    DivExpr
                    PlusExpr
                    MinusExpr

The two interesting classes are `NumExpr` and `BinExpr`

    public class NumExpr extends Expr {
        public final int value;

        public NumExpr(Number value) {
            super(); // "I'm a nonterminal"
            this.value = value.intValue();
        }
    }

    public abstract class BinExpr extends Expr {
        public final Expr l;
        public final Expr r;

        protected BinExpr(Expr left, Expr right) {
            super(); // "I'm a nonterminal too"
            l = left;
            r = right;
        }
    }

Having these AST classes in mind we can build a tree as part of the translation process like this:

    %%

    %left RPAREN;
    %left MULT, DIV;
    %left PLUS, MINUS;

    %typeof NUMBER = "Number";
    %typeof expr = "Expr";

    %%

    expr = expr.a MULT  expr.b   {: return new MultExpr (a, b); :}
         | expr.a DIV   expr.b   {: return new DivExpr  (a, b); :}
         | expr.a PLUS  expr.b   {: return new PlusExpr (a, b); :}
         | expr.a MINUS expr.b   {: return new MinusExpr(a, b); :}
         | NUMBER.n              {: return new NumExpr  (n);    :}
         | LPAREN expr.e RPAREN  {: return e; :}
         ;

For further details take a look at `examples/expr/tree`, where this case is implemented, and which also shows the `TreeWalker` for this AST and how a simple stack based calculator is using the walker to actually do calculations. There is also another walker in the example that prints the tree and all the information it can get from the AST nodes.