Beaver - a LALR Parser Generator

Introduction How to Run It Specification Syntax Error Recovery Scanner API SF Project Download

Building ASTs

Making Symbols

Action routines create and return beaver.Symbols, 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.