Manuel Abadia's ASP.NET stuff - ANTLR

ANTLR C# Overview - Part 3

Your DisplayName here! — Mon, 08 Jan 2007 07:41:33 GMT

Click here to see part 1 of this ANTLR Overview
Click here to see part 2 of this ANTLR Overview

To complete the overview of the main ANTLR runtime classes, we’ll study an example.

The following file contains a grammar for evaluating simple expressions:

grammar Expr;

options {

    language=CSharp;

    output=AST;

    ASTLabelType=CommonTree;

}

prog:   ( stat 

                {

if ($stat.tree != null){

    Console.WriteLine($stat.tree.ToStringTree());

} else {

    Console.WriteLine();

}

                } 

        )+ ;

stat:   expr NEWLINE        -> expr

    |   ID '=' expr NEWLINE -> ^('=' ID expr)

    |   NEWLINE           
    -> 

    ;

expr:   multExpr (('+'^^|'-'^^) multExpr)*

    ; 

multExpr

    :   atom ('*'^^ atom)*

    ; 

atom:   INT 

    |   ID

    |   '('! expr ')'!

    ;

ID  :   ('a'..'z'|'A'..'Z')+ ;

INT :   '0'..'9'+ ;

NEWLINE:'\r'? '\n' ;

WS  :   (' '|'\t')+ { Skip(); } ;

In this file, there are parse rules and lexer rules. Parser rules are lowercase and lexer rules are uppercase.

The tokens that will be recognized by the lexer are defined at the end of the file and are ID (identifier), INT (integer), NEWLINE (carriage return), WS (white space). Other tokens like ‘=’ don’t have a lexer rule but a rule will be generated implicity by ANTLR as we’ll see later.

The grammar start symbol is prog, that represents a program. A program is made of one ore more statements. A statement is:
• an expression following by a NEWLINE token.
• or an ID token, followed by an equal token and then followed by a NEWLINE token.
• or a NEWLINE token.

An expression is a multExpr that can be followed by the addition or substraction of more multExpr. A multExpr is an atom that can be followed by the multiplication of more atoms. Finally, an atom is an integer, an identifier or an expression enclosed in brackets.

This way of defining expressions is very common. As the grammar supports addition, substraction and multiplication, and the multiplication has higher precedence, the grammar rules are defined so the multiplication will appear later in a top down parse tree.

When we run ANTLR, it generates a Expr.Tokens file with the integer assigned to each token:

 
NEWLINE=4

ID=5

INT=6

WS=7

'='=8

'+'=9

'-'=10

'*'=11

'('=12

')'=13

The indexes 0 to 3 are reserved for special tokens (invalid, EOR, DOWN, UP). The tokens explicitly defined in the .g file are the first 4 shown above, but the others were created implicitly by ANTLR.

The first part of the Lexer starts defining this tokens:

public class ExprLexer :
Lexer 

{

    public const int T10
= 10;

    public const int T11
= 11;

    public const int T9
= 9;

    public const int INT
= 6;

    public const int EOF
= -1;

    public const int WS
= 7;

    public const int T12
= 12;

    public const int Tokens
= 14;

    public const int T8
= 8;

    public const int T13
= 13;

    public const int NEWLINE
= 4;

    public const int ID
= 5;

 

 

The tokens created implicitly get a name like TXXX, where XXX is the integer used to represent that token.

The methods present in the ExprLexer class are the constructors (that call a helper method called InitializeCyclicDFAs), the mTokens method and the mXXX methods, where XXX is one of the constants defined at the top of the class.

Remember that the mTokens method is called when the NextToken method is called, and what it does is to select one of the mXXX methods to call based on the input (using a DFA for this). The mTokens method of the ExprLexer is:

override public void mTokens() //
throws RecognitionException 

    {

        // Expr.g:1:10: (
T8 | T9 | T10 | T11 | T12 | T13 | ID | INT | NEWLINE | WS )

        int alt5 =
10;

        switch ( input.LA(1)
) 

        {

        case '=':

            alt5 = 1; break;

        case '+':

            alt5 = 2; break;

        case '-':

            alt5 = 3; break;

        case '*':

            alt5 = 4; break;

        case '(':

            alt5 = 5; break;

        case ')':

            alt5 = 6; break;

        case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G': case 'H': case 'I': 

        case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R': 

        case 'S': case 'T': case 'U': case 'V': case 'W': case 'X': case 'Y': case 'Z':

        case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i':

        case 'j': case 'k': case 'l': case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':

        case 's': case 't': case 'u': case 'v': case 'w': case 'x': case 'y': case 'z':

            alt5 = 7;

            break;

        case '0': case '1': case '2': case '3': case '4': 

        case '5': case '6': case '7': case '8': case '9':

            alt5 = 8;

            break;

        case '\n': case '\r':

            alt5 = 9;

            break;

        case '\t': case '
':

            alt5 = 10;

            break;

            default:

                NoViableAltException
nvae_d5s0 =

                    new NoViableAltException("1:1:
Tokens : ( T8 | T9 | T10 | T11 | T12 | T13 | ID | INT | NEWLINE | WS );", 5,
0, input);

                throw nvae_d5s0;

        }

        switch (alt5) 

        {

            case 1
:

                //
Expr.g:1:10: T8

                { mT8();
} break;

            case 2
:

                //
Expr.g:1:13: T9

                { mT9();
} break;

            case 3
:

                //
Expr.g:1:16: T10

                { mT10();
} break;

            case 4
:

                //
Expr.g:1:20: T11

                { mT11();
} break;

            case 5
:

                //
Expr.g:1:24: T12

                { mT12();
} break;

            case 6
:

                //
Expr.g:1:28: T13

                { mT13();
} break;

            case 7
:

                //
Expr.g:1:32: ID

                { mID();
} break;

            case 8
:

                //
Expr.g:1:35: INT

                { mINT();
} break;

            case 9
:

                //
Expr.g:1:39: NEWLINE

                { mNEWLINE();
} break;

            case 10
:

                //
Expr.g:1:47: WS

                { mWS();
} break;

        }

    }

In this sample the logic is really simple. It sets the alternative depending on the look ahead (first switch) and then calls to the corresponding mXXX method (second switch).

The code for the methods mXXX is also straightforward. For example, the code for the mT8 method (that has to match an equals character) is:

public void mT8() //
throws RecognitionException [2]

    {

        try {

            ruleNestingLevel++;

            int _type
= T8;

            int _start
= CharIndex;

            int _line
= Line;

            int _charPosition
= CharPositionInLine;

            int _channel
= Token.DEFAULT_CHANNEL;

            //
Expr.g:7:6: ( '=' )

            //
Expr.g:7:6: '='

            {

                Match('=');

            }

            if ((token
== null) && (ruleNestingLevel == 1)) {

                Emit(_type,
_line, _charPosition, _channel, _start, CharIndex - 1);

            }

        } finally {

            ruleNestingLevel--;

        }

    }

The code starts incrementing the ruleNestingLevel variable (that is used to emit tokens only in non fragment lexer rules) and setting the information about the token being generated using the current token type and channel and the properties of the Lexer class (CharIndex, Line, CharPositionInLine). Then it calls the Lexer method Match that checks if the current character is what was expected and creates the associated token. Finally the nesting level is left unchanged.>

The method mWS (that recognizes white spaces and tabs) is:

public void mWS() //
throws RecognitionException [2]

    {

        try {

            ruleNestingLevel++;

            int _type
= WS;

            int _start
= CharIndex;

            int _line
= Line;

            int _charPosition
= CharPositionInLine;

            int _channel
= Token.DEFAULT_CHANNEL;

            //
Expr.g:39:9: ( ( (' '|'\\t'))+ )

            //
Expr.g:39:9: ( (' '|'\\t'))+

            {

                //
Expr.g:39:9: ( (' '|'\\t'))+

                int cnt4
= 0;

                do 

                {

                    int alt4
= 2;

                    int LA4_0
= input.LA(1);

                    if (
(LA4_0 == '\t' || LA4_0 == '
') ){

    alt4 = 1;

}

                    switch (alt4) 

{

    case 1 :

        // Expr.g:39:10:
(' '|'\\t')

        {

            if (
input.LA(1) == '\t' || input.LA(1) == '
' ) {

                input.Consume();

            } else 
{

                MismatchedSetException
mse =

                    new MismatchedSetException(null,input);

                Recover(mse);    throw mse;

            }

        }

        break;

    default:

        if ( cnt4 >=
1 ) goto loop4;

            EarlyExitException eee =

                new EarlyExitException(4,
input);

            throw eee;

}

cnt4++;

                } while (true);

                loop4:

;    // Stops C# compiler whinging that
label 'loop4' has no statements

                Skip(); 

            }

            if (
(token == null) && (ruleNestingLevel == 1)
){

                Emit(_type,
_line, _charPosition, _channel, _start, CharIndex-1);

            }

        } finally {

            ruleNestingLevel--;

        }

    }

The method has the beginning and the end part like the previous one, but the recognition logic in the middle is a bit more complex. It has a counter initialized to 0 because the rule must find at least one white space or tab. It starts looking for a white space or tab and when it founds one consumes it. When there aren’t more white spaces or tabs, the code exits the do. If no character was consumed (the counter was 0), an execption is thrown. Otherwise, the code that followed the lexer rule is executed. The Skip methods assigns the SKIP_TOKEN to the token field so no token is emmited later.

The other methods in the lexer class are very similar to the ones we’ve studied.

Let’s move to the parser. The parser starts with the following code:

public class ExprParser :
Parser 

{

  public static readonly string[]
tokenNames = new string[] 

    {

        "<invalid>", 

        "<EOR>", 

        "<DOWN>", 

        "<UP>", 

        "NEWLINE", 

        "ID", 

        "INT", 

        "WS", 

        "'='", 

        "'+'", 

        "'-'", 

        "'*'", 

        "'('", 

        "')'"

    };

    public const int INT
= 6;

    public const int EOF
= -1;

    public const int WS
= 7;

    public const int NEWLINE
= 4;

    public const int ID
= 5;

that declares the tokens used in the lexer.

The class continues like this:

public ExprParser(ITokenStream input) 

            : base(input)

        {

            InitializeCyclicDFAs();

        }

    protected ITreeAdaptor adaptor
= new CommonTreeAdaptor();

    public ITreeAdaptor TreeAdaptor

    {

        get { return this.adaptor;
}

        set { this.adaptor
= value; }

    }

    override public string[]
TokenNames

    {

        get { return tokenNames;
}

    }

    override public string GrammarFileName

    {

        get { return "Expr.g";
}

    }

So the constructor is declared and an ITreeAdaptor is created (because we set the option to build an AST) and exposed as a property. The other properties expose information about this recognizer.

Then we have a nested class for each parser rule and a method for each parser rule that returns the previous nested class. For the prog rule we have:

public class prog_return :
ParserRuleReturnScope 

    {

        internal CommonTree
tree;

        override public object Tree

        {

            get { return tree;
}

        }

    };

    // $ANTLR start prog

    // Expr.g:9:1: prog : ( stat )+ ;

    public prog_return prog() //
throws RecognitionException [1]

    {   

        prog_return retval = new prog_return();

        retval.start = input.LT(1);

        CommonTree root_0 = null;

        stat_return stat1 = null;

        try 

        {

            //
Expr.g:9:9: ( ( stat )+ )

            //
Expr.g:9:9: ( stat )+

            {

                root_0
= (CommonTree)adaptor.GetNilNode();

                //
Expr.g:9:9: ( stat )+

                int cnt1
= 0;

                do 

                {

                    int alt1
= 2;

                    int LA1_0
= input.LA(1);

                    if (
((LA1_0 >= NEWLINE && LA1_0 <= INT) || LA1_0 == 12) )

{

    alt1 = 1;

}

                    switch (alt1) 

{

    case 1 :

        // Expr.g:9:11: stat

        {

            CommonTree root_1 = (CommonTree)adaptor.GetNilNode();

            PushFollow(FOLLOW_stat_in_prog43);

            stat1 = stat();

            followingStackPointer_--;

            adaptor.AddChild(root_1,
stat1.Tree);

            if (((CommonTree)stat1.tree)
!= null){

                Console.WriteLine(((CommonTree)stat1.tree).ToStringTree());

            } else {

                Console.WriteLine();

            }

            adaptor.AddChild(root_0,
root_1);

        }

        break;

    default:

        if ( cnt1 >=
1 ) goto loop1;

            EarlyExitException eee =

                new EarlyExitException(1,
input);

            throw eee;

}

cnt1++;

                } while (true);

                loop1:

;    // Stops C# compiler whinging that
label 'loop1' has no statements

            }

        }

        catch (RecognitionException
re) 

        {

            ReportError(re);

            Recover(input,re);

        }

        finally 

        {

            retval.stop = input.LT(-1);

                retval.tree
= (CommonTree)adaptor.RulePostProcessing(root_0);

                adaptor.SetTokenBoundaries(retval.Tree,
retval.start, retval.stop);

        }

        return retval;

    }

As explained in a previous article, the return classes generated when we have set the option to generate an AST inherit from ParserRuleReturnScope and have a Tree property with the AST generated for that rule.

The prog method starts creating the return value and setting the initial token for the AST. The method ends setting the last token for the AST and saves the resulting AST.

The core of the method starts after the try. The code starts creating a “nil” node. As the rule is prog : ( stat )+, the generated code is a do…while with a counter to check that at least the stat rule has been entered at least one. The basic structure of the generated code is similar to the one we studied in the lexer method mWS. If the token found is one of the first tokens that appear in a stat rule, the code goes to the case 1: of the switch.

A new “nil” node is created, the stat rule is invoked, and the AST generated by the stat rule is added as a child to “nil” node created previously. The BaseRecognizer class uses a stack to store the token types that can follow a rule invocation. Before calling a rule the follow set is pushed in this stack (PushFollow) and after the call, the follow set is removed from the stack(followingStackPointer_--). This is used when there is an error in the parsing process so ANTLR can continue execution adding a token or deleting a token.

The code that follows is the one that we included in the parser rule:

prog:   ( stat 

                {

if ($stat.tree != null){

    Console.WriteLine($stat.tree.ToStringTree());

} else {

    Console.WriteLine();

}

                } 

        )+ ;

Finally the first tree created at the top of the method (that contained a “nil” node) is combined with the tree obtained from the stat rule.

As the others methods are very similar we’re going to study only the generated method for the atom rule:

atom:   INT 

    |   ID

    |   '('! expr ')'!

    ;

    // $ANTLR start atom

    // Expr.g:31:1: atom : ( INT | ID |
'('! expr ')'! );

    public atom_return atom() //
throws RecognitionException [1]

    {   

        atom_return retval = new atom_return();

        retval.start = input.LT(1);

        CommonTree root_0 = null;

        IToken INT16 = null;

        IToken ID17 = null;

        IToken char_literal18 = null;

        IToken char_literal20 = null;

        expr_return expr19 = null;

        CommonTree INT16_tree=null;

        CommonTree ID17_tree=null;

        CommonTree char_literal18_tree=null;

        CommonTree char_literal20_tree=null;

        try 

        {

            //
Expr.g:31:9: ( INT | ID | '('! expr ')'! )

            int alt6
= 3;

            switch (
input.LA(1) ) 

            {

            case INT:

                alt6 =
1;

                break;

            case ID:

                alt6 =
2;

                break;

            case 12:

                alt6 =
3;

                break;

                default:

NoViableAltException nvae_d6s0 =

    new NoViableAltException("31:1:
atom : ( INT | ID | '('! expr ')'! );", 6, 0, input);

                    throw nvae_d6s0;

            }

            switch (alt6) 

            {

                case 1
:

                    //
Expr.g:31:9: INT

{

    root_0 = (CommonTree)adaptor.GetNilNode();

    INT16 = (IToken)input.LT(1);

    Match(input,INT,FOLLOW_INT_in_atom191); 

    INT16_tree = (CommonTree)adaptor.Create(INT16);

    adaptor.AddChild(root_0, INT16_tree);

}

                    break;

                case 2
:

                    //
Expr.g:32:9: ID

{

    root_0 = (CommonTree)adaptor.GetNilNode();

    ID17 = (IToken)input.LT(1);

    Match(input,ID,FOLLOW_ID_in_atom202); 

    ID17_tree = (CommonTree)adaptor.Create(ID17);

    adaptor.AddChild(root_0, ID17_tree);

}

                    break;

                case 3
:

                    //
Expr.g:33:9: '('! expr ')'!

{

    root_0 = (CommonTree)adaptor.GetNilNode();

    char_literal18 = (IToken)input.LT(1);

    Match(input,12,FOLLOW_12_in_atom212); 

    PushFollow(FOLLOW_expr_in_atom215);

    expr19 = expr();

    followingStackPointer_--;

    adaptor.AddChild(root_0, expr19.Tree);

    char_literal20 = (IToken)input.LT(1);

    Match(input,13,FOLLOW_13_in_atom217); 

}

                    break;

            }

        }

        catch (RecognitionException
re) 

        {

            ReportError(re);

            Recover(input,re);

        }

        finally 

        {

            retval.stop = input.LT(-1);

                retval.tree
= (CommonTree)adaptor.RulePostProcessing(root_0);

                adaptor.SetTokenBoundaries(retval.Tree,
retval.start, retval.stop);

        }

        return retval;

    }

The start and the end of the method is similar to the prog method, although this one declares a lot of variables that will be used later.

The core of the method starts in the first switch. Based on the next token an alternative is choosen. If it isn’t one of the expected tokens (INT, ID or ‘(‘) and error is thrown.

The second switch has the code to execute based on the selected alternative. The first two alternatives are atom : INT | ID, and what the code does is to create a “nil” node, match the token with the expected one, and add the token as a child of the “nil” node.

The last alternative, atom: '('! expr ')'!, create a “nil” node, matches the ‘(‘ token, calls to the expr method, adds the AST generated by the expression as a child of the “nil” node, and matches the ‘)’ token. In this alternative the matched tokens haven’t been added to the AST because the ! operator specifies to not add them.

The parse tree generated for the input
a=3
a+5

is:

The atom rule is called 3 times (for 3, for a and for 5).

The AST generation for the atom 3 is (before and after the finally keyword):

The “nil” node was optimized in the RulePostProcessing method.

The expr rule is called twice (for 3 and for a+5).

The optimized AST for the a+5 expression is:

The final AST generated is:

The images of the trees have been created using the StructsViz DebuggerVisualizers.>

To finish, lets see the code generated for the tree parser. The input to the tree parser based on the example AST is:

The code generated for the tree parser starts like this:

public class EvalTreeParser :
TreeParser 

{

    public static readonly string[]
tokenNames = new string[] 

    {

        "<invalid>", 

        "<EOR>", 

        "<DOWN>", 

        "<UP>", 

        "NEWLINE", 

        "ID", 

        "INT", 

        "WS", 

        "'='", 

        "'+'", 

        "'-'", 

        "'*'", 

        "'('", 

        "')'"

    };

    public const int INT
= 6;

    public const int EOF
= -1;

    public const int WS
= 7;

    public const int NEWLINE
= 4;

    public const int ID
= 5;

        public EvalTreeParser(ITreeNodeStream
input) 

            : base(input)

        {

            InitializeCyclicDFAs();

        }

    override public string[]
TokenNames

    {

        get { return tokenNames;
}

    }

    override public string GrammarFileName

    {

        get { return "Eval.g";
}

    }

    /** Map variable name to Integer object
holding value */

    public Hashtable memory = new Hashtable();

If you compare this code with the parser we studied before you can see that is identical to it but it doesn’t has the tree adaptor (because the tree parser does not generate an AST). If we compare the code generated for the rules, we’ll find out that it is very similar to the code generated for the methods studied earlier in the parser (but without the code for AST generation). For example, the code for the expr rule is:

    // $ANTLR start expr

    // Eval.g:24:1: expr returns [int value]
: ( ^( '+' a= expr b= expr ) | ^( '-' a= expr b= expr ) | ^( '*' a= expr b= expr )
| ID | integer= INT );

    public int expr() //
throws RecognitionException [1]

    {   

        int value =
0;

        CommonTree integer = null;

        CommonTree ID4 = null;

        int a = 0;

        int b = 0;

        try 

        {

            //
Eval.g:25:9: ( ^( '+' a= expr b= expr ) | ^( '-' a= expr b= expr ) | ^( '*' a= expr
b= expr ) | ID | integer= INT )

            int alt3
= 5;

            switch (
input.LA(1) ) 

            {

            case 9:

                alt3 =
1;

                break;

            case 10:

                alt3 =
2;

                break;

            case 11:

                alt3 =
3;

                break;

            case ID:

                alt3 =
4;

                break;

            case INT:

                alt3 =
5;

                break;

                default:

NoViableAltException nvae_d3s0 =

    new NoViableAltException("24:1:
expr returns [int value] : ( ^( '+' a= expr b= expr ) | ^( '-' a= expr b= expr ) |
^( '*' a= expr b= expr ) | ID | integer= INT );", 3, 0, input);

                    throw nvae_d3s0;

            }

            switch (alt3) 

            {

                case 1
:

                    //
Eval.g:25:9: ^( '+' a= expr b= expr )

{

    Match(input,9,FOLLOW_9_in_expr109); 

    Match(input, Token.DOWN, null); 

    PushFollow(FOLLOW_expr_in_expr113);

    a = expr();

    followingStackPointer_--;

    PushFollow(FOLLOW_expr_in_expr117);

    b = expr();

    followingStackPointer_--;

    Match(input, Token.UP, null); 

    value =  a+b; 

}

                    break;

                case 2
:

                    //
Eval.g:26:9: ^( '-' a= expr b= expr )

{

    Match(input,10,FOLLOW_10_in_expr132); 

    Match(input, Token.DOWN, null); 

    PushFollow(FOLLOW_expr_in_expr136);

    a = expr();

    followingStackPointer_--;

    PushFollow(FOLLOW_expr_in_expr140);

    b = expr();

    followingStackPointer_--;

    Match(input, Token.UP, null); 

    value =  a-b; 

}

                    break;

                case 3
:

                    //
Eval.g:27:9: ^( '*' a= expr b= expr )

{

    Match(input,11,FOLLOW_11_in_expr158); 

    Match(input, Token.DOWN, null); 

    PushFollow(FOLLOW_expr_in_expr162);

    a = expr();

    followingStackPointer_--;

    PushFollow(FOLLOW_expr_in_expr166);

    b = expr();

    followingStackPointer_--;

    Match(input, Token.UP, null); 

    value =  a*b; 

}

                    break;

                case 4
:

                    //
Eval.g:28:9: ID

{

    ID4 = (CommonTree)input.LT(1);

    Match(input,ID,FOLLOW_ID_in_expr180); 

                object obj
= memory[ID4.Text];

                if (obj
!= null){

value =  (int)obj;

                } else {

Console.WriteLine("undefined variable " + ID4.Text);

                }

}

                    break;

                case 5
:

                    //
Eval.g:37:9: integer= INT

{

    integer = (CommonTree)input.LT(1);

    Match(input,INT,FOLLOW_INT_in_expr203); 

    value =  Int32.Parse(integer.Text); /*
fix for 3.0b5 bug (will be fixed in next version so integer.Text works) */ 

}

                    break;

            }

        }

        catch (RecognitionException
re) 

        {

            ReportError(re);

            Recover(input,re);

        }

        finally 

        {

        }

        return value;

    }

The method starts declaring the variables used in the alternatives and the variable used to hold the return vale.

The first switch decides what alternative to select based on the next token of the input stream. Recall that the rule expr was:

expr returns [int value]

    :   ^('+' a=expr b=expr)  { $value = a+b; }

    |   ^('-' a=expr b=expr)  { $value = a-b; }   

    |   ^('*' a=expr b=expr)  { $value = a*b; }

    |   ID 

        {

            object obj = memory[$ID.text];

            if (obj != null){

                $value
= (int)obj;

            } else {

                Console.WriteLine("undefined
variable " + $ID.text);

            }

        }

    |   integer=INT       
           { $value = Int32.Parse($integer.text);
/* fix for 3.0b5 bug (will be fixed in next version so $INT.text works) */ }

    ;

The code associated to each alternative is inside the second switch. The first 3 alternatives have the same structure but differ in a token and in the operation to perform, so we’ll focus only on the first one. As what we want to match is a tree that has a ‘+’ token (token number 9) as the root, and two expressions as its childs, the code first has a Match to check that the token ‘+’ is present, then a Match to check that the ficticious DOWN token is present (so it is walking to the childs of the root). Then it calls two expr rules (saving the follow information in the stack as we explained earlier), and saving the return value in the variables a and b. Finally, the ficticious UP token is matched so it verifies that there are no more child nodes.

The alternatives 4 and 5 are straightforward as they only match a token and have the code inserted in the rule.

And that’s it. You can see that a tree parser is very very similar to a parser.

The code used to connect the lexer, the parser and the tree parser is:

// sets the input string

ANTLRStringStream strStream = new ANTLRStringStream(

    @"    a=3

        a+5

    ");

// creates the lexer

ExprLexer lexer = new ExprLexer(strStream);

// creates the parser with a stream of tokens that will
be extracted from the lexer to it

CommonTokenStream tokStream = new CommonTokenStream(lexer);

ExprParser parser = new ExprParser(tokStream);

// parse the input string and get the results

ExprParser.prog_return returnValue = parser.prog();

// creates the tree parser with a stream of tokens that
will be extracted from the AST

CommonTreeNodeStream treeNodeStream = new CommonTreeNodeStream((CommonTree)returnValue.Tree);

EvalTreeParser treeWalker = new EvalTreeParser(treeNodeStream);

// walk the AST executing any associated code

treeWalker.prog();

// get the AST and wrap it in our tree node class in order
to visualize it with StructsViz when debugging

// you can download an evaluation version of StructsViz
here: http://www.manuelabadia.com/products

AntlrDebugCommonTree AST = new AntlrDebugCommonTree((CommonTree)returnValue.Tree);

The parse tree used to evaluate the sample expression in the tree parser grammar is:

I hope this tutorial about ANTLR has been useful to clarify some gray areas and have a general view of the main classes involved.

To learn more about ANTLR refer to the upcoming book:

Download article source code (16.47 KB)

ANTLR C# Overview - Part 2

Your DisplayName here! — Tue, 02 Jan 2007 10:13:38 GMT

Click here for Part 1 of this overview
Click here for Part 3 of this overview

IMHO the more awkward thing in ANTLR is the tree implementation. A tree is implemented as a tree node and all the operations related to trees are moved to another class. Also, there can be “nil” nodes, that are fake nodes used as parent for childs (this is used to create flat lists).

In ANTLR a tree has to implement the ITree interface:

public interface ITree

{

    int CharPositionInLine { get;
}

    int ChildCount { get;
}

    int Line { get;
}

    bool Nil { get;
}

    string Text { get;
}

    int Type { get;
}

    void AddChild(ITree t);

    ITree DupNode();

    ITree DupTree();

    ITree GetChild(int i);

    string ToString();

    string ToStringTree();

}

In the ITree interface there are some properties that are also present in the IToken interface (Line, CharPositionInLine, Type and Text) in order to associate a position with the current tree for errors and because it is also needed for parsing.

The Nil property is used to check if this node is a “nil” node.

The property ChildCount and the method GetChild are used to navigate the tree.

The DupNode methods clones the current node and the DupTree method clones the whole tree.

In a normal implmentation of a tree node, the method AddChild doesn’t need more comments but in ANTLR the methods that operate on trees are not orthogonal and usually differ if one of the operands is a “nil” node. In this case, if the tree node passed to the AddChild is a “nil” node, all the children of that “nil” node are added as children of the tree. Otherwise works as expected.

The ITree interface is implemented by the abstract class BaseTree that implements the tree using a list of child nodes, and the node doesn’t have any payload.

The concrete classes that implement BaseTree in ANTLR are:
• CommonTree: that adds a token as the payload.
• ParseTree: that stores strings and tokens as the payload.

To operate on the tree you have to use a class that implements the ITreeAdaptor interface:

public interface ITreeAdaptor

{

    void AddChild(object t, IToken child);

    void AddChild(object t, object child);

    object BecomeRoot(IToken newRoot, object oldRoot);

    object BecomeRoot(object newRoot, object oldRoot);

    object Create(IToken payload);

    object Create(int tokenType, IToken fromToken);

    object Create(int tokenType, string text);

    object Create(int tokenType, IToken fromToken, string text);

    object DupNode(object treeNode);

    object DupTree(object tree);

    object GetChild(object t, int i);

    int GetChildCount(object t);

    object GetNilNode();

    string GetNodeText(object t);

    int GetNodeType(object t);

    int GetTokenStartIndex(object t);

    int GetTokenStopIndex(object t);

    int GetUniqueID(object node);

    object RulePostProcessing(object root);

    void SetNodeText(object t, string text);

    void SetNodeType(object t, int type);

    void SetTokenBoundaries(object t, IToken startToken, IToken stopToken);

}

The AddChild and Dup methods do the same as the ITree counterparts.

The Create methods are used to create a tree node from a token.

The method GetNilNode is used to obtain a “nil” node.

The GetChildCound and GetChild methods are used to traverse the tree.

The BecomeRoot method returns a tree where the newRoot is the root of the resulting tree and the oldRoot is a child of the resulting tree. There is special handling for “nil” nodes (see the ANTLR code for details).

The RulePostProcessing method is called after a rule has been processed in order to optimize the resulting tree. After this method, the SetTokenBoundaries is called in order to set the bounds in the input token stream of this tree (including all the children).

The other methods are for getting/setting the node type and text when doing tree parsing.

The abstract class BaseTreeAdaptor implements the ITreeAdaptor interface and adds an abstract method called createToken. The concrete class that is used in ANTLR is the CommonTreeAdaptor class, that inherits from BaseTreeAdaptor. The CommonTreeAdaptor class creates CommonTree and CommonToken objects.

When ANTLR generates a Parser that builds the AST, the generated class has a protected field called adaptor (and the associated property Adaptor) which is used in the rules to create the AST. Also a return type of each method created for each rule changes to a new generated class (with a name rulename_return) that inherits from the ParserRuleReturnScope:

public class ParserRuleReturnScope : RuleReturnScope

{

    public IToken start;

    public IToken stop;

}

public class RuleReturnScope

{

    public virtual object Start
{ get; }

    public virtual object Stop
{ get; }

    public virtual Antlr.StringTemplate.StringTemplate Template
{ get; }

    public virtual object Tree
{ get; }

}

The RuleReturnScope class is used to provide start and stop information (token or tree) as well as the AST or the template when output=AST or when output=template is used.

The generated class that inherits from ParserRuleReturnScope stores the resulting AST and any return value defined in the rule.

You may be wondering why to generate an AST and then create a Tree Parser for the generated AST to do more work if you can add attributes and logic to the rules in the parser to do what you want to do. The reason is that there are a lot of rules in the grammar that are just for precedence or to make the grammar cleaner and also there are some tokens (for example the brackets) that are not needed after parsing. The resulting AST has only the data need to perform our task without garbage. For example, consider a grammar for evaluating expressions with support for relational expressions and bit operators. The expression ((i >= 0) AND (i <= n)) OR ((index & 2) = 1) produces this parse tree:

The generated AST from that expression is:

So the AST is a lot easier (and clearer) to use.

I have used my StructsViz DebuggerVisualizer pack to generate those tree diagrams in the Visual Studio.NET 2005 debugger.

After studying the tree related classes and the Parser class it is time to start with Tree Parsers. The TreeParser class inherits from BaseRecognizer and will consume tree nodes from an ITree. The input of a tree parser will be a class implementing the ITreeNodeStream interface. This interface is an specialization of the IIntStream interface to operate on tree nodes:

public interface ITreeNodeStream : IIntStream

{

    bool HasUniqueNavigationNodes
{ set; }

    ITreeAdaptor TreeAdaptor { get;
}

    object TreeSource { get;
}

    object LT(int k);

    string ToString(object start, object stop);

}

As you can see, the interface can return any tree node with the LT method, and with the TreeSource and TreeAdaptor properties you can access to the tree providing the data and to the associated adaptor.

The ToString method prints the text of the specified nodes.

The HasUniqueNavigationNodes is used in debugging mode and specifies if the UP and DOWN nodes are reused or created each time they’re needed. The meaning of the UP and DOWN nodes will be explained later.

The CommonTreeNodeStream implements the ITreeNodeStream interface, and also the IEnumerable interface (so the nodes can be accessed sequentially using the IEnumerable related methods and properties, that is, Reset, MoveNext, Current). The class has 3 static tree nodes defined: the UP node, the DOWN node and the EOF node. To traverse the tree sequentially the class uses two stacks, the node stack and the index stack. The node stack is used to track the parent node when we’re walking down the tree. The index stack is used to know which child node we’re currently visiting. The tree is visited using a depth first traversal. When the first child of a node is visited, a ficticious DOWN node is added to the lookahead buffer and when the last child of a node is visited, a ficticious UP node is added to the lookahead buffer. After all nodes have been visited, the ficticious EOF node is always returned. When the nodes are accessed sequentially using the IEnumerable interface, the ficticious nodes are not returned. The ficticious nodes are returned only when the LT method of the ItreeNodeStream interface is called.

For completeness here are all the methods and properties of the CommonTreeNodeStream class:

public class CommonTreeNodeStream : ITreeNodeStream, IIntStream,
IEnumerator

{

    public CommonTreeNodeStream(ITree tree);

    public CommonTreeNodeStream(ITreeAdaptor adaptor, ITree tree);

    public virtual object Current
{ get; }

    public virtual void Reset();

    public virtual bool MoveNext();

    public virtual void Consume();

    public virtual int Index();

    public virtual int LA(int i);

    public virtual int Mark();

    public virtual void Release(int marker);

    public void Rewind();

    public virtual void Rewind(int marker);

    public virtual void Seek(int index);

    public virtual int Size();

    public bool HasUniqueNavigationNodes
{ get; set; }

    public ITreeAdaptor TreeAdaptor
{ get; }

    public virtual object TreeSource
{ get; }

    public virtual object LT(int k);

    public virtual string ToString(object start, object stop);

    protected int LookaheadSize
{ get; }

    protected internal virtual void AddLookahead(ITree node);

    protected internal virtual void AddNavigationNode(int ttype);

    protected internal virtual void fill(int k);

    protected internal virtual ITree handleRootNode();

    public override string ToString();

    public virtual string ToNodesOnlyString();

    protected internal virtual void ToStringWork(ITree p, ITree stop, StringBuilder buf);

    protected internal virtual ITree VisitChild(int child);

    protected internal virtual void WalkBackToMostRecentNodeWithUnvisitedChildren();

}

After the constructors, you can see the method and properties of the IEnumerable interface, followed by the methods and properties of the IIntStream interface, and then the methods of the ITreeNodeStream interface.

The other methods and properties are used to maintain a circular lookahead buffer of tree nodes and to handle the navigation taking the ficticious nodes into account.

Nothing better than a couple of images here. For the following AST:

The lookahead buffer with the ficticious tokens included looks like:

The TreeParser class inherits from BaseRecognizer and gets tree nodes from a class implementing the ITreeNodeStream interface:

public class TreeParser : BaseRecognizer

{

    public TreeParser(ITreeNodeStream input);

    public override IIntStream Input
{ get; }

    public virtual ITreeNodeStream TreeNodeStream
{ get; set; }

    protected internal override void Mismatch(IIntStream input, int ttype, BitSet follow);

    public override IList
ToTemplates(IList retvals);

}

As you can see, the TreeParser is a very simple class that has properties for the input stream and overrides 2 methods of the BaseRecognizer class.

When ANTLR creates a TreeParser, it generates a class that inherits from the TreeParser class. The generated class has a method for each rule in a similar way as the parsers.

Thanks to the smart idea behind ITreeNodeStream, a Parser and a TreeParser are very similar if you take a look at the generated code. The Parser consumes tokens from an ITokenStream in a linear way (one dimension) and the TreeParser consumes tokens in a hierarchical way (two dimensions), but serialized to one dimension thanks to the ficticious UP and DOWN tree nodes.

To complete this ANTLR overview, I’ll post an example of a lexer, a parser and a tree parser and the generated code in a few days.

Happy 2007!

Your DisplayName here! — Mon, 01 Jan 2007 23:36:54 GMT

Another year ends and a new one comes. Life goes as fast as usual and we’re keep on our way. It’s time to think about it… our actions, hopes, wishes, mistakes, etc.

I usually listen to a special song a few minutes after the start of the year. In the last few years I have been choosing "Aerosmith – Full Circle" because it has special connotations for me.

I wish you the best in the coming year.

ANTLR C# Overview - Part 1

Your DisplayName here! — Tue, 26 Dec 2006 15:10:19 GMT

Click here for Part 2 of this overview
Click here for Part 3 of this overview

There are some articles out there about ANTLR v3 that cover how to define grammars and tree parses but I haven’t seen any that gives a global vision about all the classes and interfaces involved, so I’ll try to fill that gap. I’m using the C# version of ANTLR 3.0b5 as it is what I use and it has better name conventions for interfaces and classes.

There’s an upcoming book about ANTLR by its autor that will be a very valuable material if you work with ANTLR:

ANTLR lets us create a lexer, a parser and a tree parser. Depending on what you are creating, the classes generated by ANTLR will inherit Lexer, Parser or the TreeParser class. Those 3 classes inherit from a common abstract class called BaseRecognizer where all the code for parsing is present.

The Lexer class is also an abstract class that extends BaseRecognizer and implements the ITokenSource interface.

The ITokenSource interface has only one method, NextToken, that is used to get all tokens from the input. For ANTLR a token is a class that implements the IToken interface:

public interface IToken

{

    int Channel { get; set;
}

    int CharPositionInLine { get; set;
}

    int Line { get; set;
}

    string Text { get; set;
}

    int TokenIndex { get; set;
}

    int Type { get; set;
}

}

The basic properties of a token are its type and its text. The Line and CharPositionInLine are used to know where the token was read from the input.

A parser will read tokens from a channel, so the Channel property is usually used to disntinguish from a “normal” token from a white space or other token used as separator that does not alter the input to be parsed.

All tokens read from the input are assigned an unique TokenIndex (starting from 0 and incremented each time a token is read).

The CommonToken class implements IToken and it is the class that is usually used to represent a token in ANTLR. It has two properties not present in the IToken interface, StartIndex and StopIndex, that are used to indicate where the token starts and ends in the input stream. So the Text property returns the data directly from the input stream unless the Text property has been explicitly set. The ToString method prints a token like this:

[@15,23:26=’else’,<10>,1:22]

Where 15 is the TokenIndex, 23:26 are the StartIndex and StopIndex respectively, else is the Text, 10 is the Type, and 1,22 are the Line and CharPositionInLine respectively.

Returning to the Lexer class… it reads the characters from a ICharStream, that is an interface that extends the IIntStream interface for reading characters and adding line and column information to it:

public interface IIntStream

{

    void Consume();

    int Index();

    int LA(int i);

    int Mark();

    void Release(int marker);

    void Rewind();

    void Rewind(int marker);

    void Seek(int index);

    int Size();

}

The IIntStream interface is a contract for a stream of integers with variable lookahead and marker points so the stream can save a return point with the Mark method and return to it using the Rewind method.

There are several classes implementing the ICharStream interface so the Lexer can get data from several sources:

• ANTLRStringStream: to provide data from a string.
• ANTLRFileStream: to provide data from a file.
• ANTLRReaderStream: to provide data from a TextReader.
• ANTLRInputStream: to provide data from a Stream.

So finally we’re ready to understand the Lexer class:

public abstract class Lexer : BaseRecognizer, ITokenSource

{

    public Lexer();

    public Lexer(ICharStream input);

    public virtual int CharIndex
{ get; }

    public virtual int CharPositionInLine
{ get; }

    public virtual ICharStream CharStream
{ set; }

    public override IIntStream Input
{ get; }

    public virtual int Line
{ get; }

    public virtual string Text
{ get; set; }

    public static void DisplayRecognitionError(string name, RecognitionException e);

    public virtual void Emit(IToken token);

    public virtual IToken Emit(int tokenType, int line, int charPosition, int channel, int start, int stop);

    public virtual void Match(int c);

    public virtual void Match(string s);

    public virtual void MatchAny();

    public virtual void MatchRange(int a, int b);

    public abstract void mTokens();

    public virtual IToken NextToken();

    public virtual void Recover(RecognitionException re);

    public override void ReportError(RecognitionException e);

    public void Skip();

}

The Lexer works using a ICharStream as its input and offers a bunch of properties to get information about the current character position of the underlying ICharStream.

The main operation accomplished by the Lexer class is to obtain tokens from the input stream when the NextToken method (of the implemented interface ITokenSource) is called.

When a Lexer is generated using ANTLR, a class that inherits Lexer is generated. That class will have a method called mXXX for each lexer rule where XXX is the rule name. Also a method called mTYYY (where YYY is an integer) will be generated for each token implicitly defined in a lexer rule like ‘>=’.

By default, each generated method will check if the expected characters are read from the input stream (using the Math, MathAny and MathRange methods) and then call the Emit method to generate the associated token, that is stored in a field called token.

When the NextToken method is called, the Lexer class the abstract method mTokens that is implemented in the class generated by ANTLR and what it does is to select one of the m* methods explained before to call based on the input (using a DFA for this). That method will set the token field, and if the token should not be skipped (to skip a token you have to call to the Skip method in the Lexer class) it returns it. If not it repeats the process until a token is returned or the end of the input is found (EOF).

The Parser class inherits from BaseRecognizer and reads tokens from an object that implements ITokenStream. ITokenStream is just a specialization of the IIntStream to work with ITokens instead of ints:

public interface ITokenStream : IIntStream

{

    IToken Get(int i);

    ITokenSource GetTokenSource();

    IToken LT(int k);

    string ToString(int start, int stop);

    string ToString(IToken start, IToken stop);

}

ITokenStream uses an object that implements ITokenSource (remember that the Lexer class implements ITokenSource) to obtain tokens. There are two classes implementing ITokenStream, CommonTokenStream and TokenRewriteString. The CommonTokenStream class buffers all the tokens and will return tokens in a specific channel. The TokenRewriteString class has additional functionality to insert, update and delete tokens.

The Parser class is very simple:

public class Parser : BaseRecognizer

{

    public Parser(ITokenStream input);

    public override IIntStream Input
{ get; }

    public virtual ITokenStream TokenStream
{ get; set; }

}

As only adds an additional property to return the ITokenStream that feeds the parser.

When a Parser is generated using ANTLR, a class that inherits from Parser is generated. For each parser rule, that class will have a method with the same name as the rule. The method signature will depend on the attributes used (if any) in the rule and if abstract syntax tree (AST) construction is enabled or not.

Tree parsers will be explained in another post as there is a lot of tree related theory to introduce.

Compiler tools for .NET

Your DisplayName here! — Thu, 09 Nov 2006 23:06:09 GMT

I have been playing lately with compiler generators and related stuff for something I’m working on. I had to re-read some parts of the dragon book (my memory is pretty bad) and I also found out that a new edition of the dragon book was released this year:

The best tool I have found is ANTLR. It is completely free, it can generate a lexer, a parser and a tree parser, so it can be used to generate all the needed stuff without having to use different tools. It supports C#, Java, C++ and Python. Also, it generates descendant recursive parsers so the code generated can be understood by a human (no more transition tables like yacc/bison). Even if predictive top down parsers can not handle all the context free grammars, this one supports pred-LL(k) grammars (LL(k) means Left to right Left most derivation with k tokens of lookahead, and the pred prefix means that it supports predicates to see if a rule has to be applied or not) with backtracking so it is really powerful.

The latest version (v3) is still in beta but it has some nice improvements over v2 so that’s the one I’m using. For v3 there isn’t much documentation so the learning curve is a bit high but it seems worth the effort. IMHO one of the bests things of ANTLR is that it has a great development IDE called ANTLRWorks that is amazing. Just look at this screenshots I took of some C# 2.0 grammar tests I did:

You have real time error checking, you can see a syntax diagram of the current rule, you can view the generated parse tree, debug the grammar, see rules dependencies, the DFA for the tokens, automatically remove left recursion from rules… awesome!

If you are wondering if ANTLR is good enough for you, think that JetBrains (the company that created ReSharper) uses it.

Enough talking, back to ANTLR…