Child pages
  • Five minute introduction to ANTLR 3
Skip to end of metadata
Go to start of metadata

Five minute introduction to ANTLR 3

What is ANTLR 3?

ANTLR - ANother Tool for Language Recognition - is a tool that is used in the construction of formal language software tools (or just language tools) such as translators, compilers, recognizers and, static/dynamic program analyzers. Developers use ANTLR to reduce the time and effort needed to build and maintain language processing tools. In common terminology, ANTLR is a compiler generator or compiler compiler (in the tradition of tools such as Lex/Flex and Yacc/Bison) and it is used to generate the source code for language recognizers, analyzers and translators from language specifications. ANTLR takes as its input a grammar - a precise description of a language augmented with semantic actions - and generates source code files and other auxiliary files. The target language of the generated source code (e.g. Java, C/C++, C#, Python, Ruby) is specified in the grammar.

Software developers and language tool implementors can use ANTLR to implement Domain-Specific Languages, to generate parts of language compilers and translators, or even to help them build tools that parse complex XML.

As stated above, ANTLR 3 generates the source code for various tools that can be used to recognize, analyze and transform input data relative to a language that is defined in a specified grammar file. The basic types of language processing tools that ANTLR can generates are Lexers (a.k.a scanners, tokenizers), Parsers and, TreeParsers (a.k.a tree walkers, c.f. visitors).

What exactly does ANTLR 3 do?

ANTLR reads a language description file called a grammar and generates a number of source code files and other auxiliary files. Most uses of ANTLR generates at least one (and quite often both) of these tools:

  • A Lexer: This reads an input character or byte stream (i.e. characters, binary data, etc.), divides it into tokens using patterns you specify, and generates a token stream as output. It can also flag some tokens such as whitespace and comments as hidden using a protocol that ANTLR parsers automatically understand and respect.
  • A Parser: This reads a token stream (normally generated by a lexer), and matches phrases in your language via the rules (patterns) you specify, and typically performs some semantic action for each phrase (or sub-phrase) matched. Each match could invoke a custom action, write some text via StringTemplate, or generate an Abstract Syntax Tree for additional processing.

ANTLR's Abstract Syntax Tree (AST) processing is especially powerful. If you also specify a tree grammar, ANTLR will generate a Tree Parser for you that can contain custom actions or StringTemplate output statements. The next version of ANTLR (3.1) will support rewrite rules that can be used to express tree transformations.

Most language tools will:

  1. Use a Lexer and Parser in series to check the word-level and phrase-level structure of the input and if no fatal errors are encountered, create an intermediate tree representation such as an Abstract Syntax Tree (AST),
  2. Optionally modify (i.e tranform or rewrite) the intermediate tree representation (e.g. to perform optimizations) using one or more Tree Parsers, and
  3. Produce the final output using a Tree Parser to process the final tree representation. This might be to generate source code or other textual representation from the tree (perhaps using StringTemplate) or, performing some other custom actions driven by the final tree representation.

Simpler language tools may omit the intermediate tree and build the actions or output stage directly into the parser. The calculator shown below uses only a Lexer and a Parser.

ANTLR, Then and Now

ANTLR 3 is the latest version of a language processing toolkit that was originally released as PCCTS in the mid-1990s. As was the case then, this release of the ANTLR toolkit advances the state of the art with its new LL(star) parsing engine. ANTLR provides a framework for the generation of recognizers, compilers, and translators from grammatical descriptions. ANTLR grammatical descriptions can optionally include action code written in what is termed the target language (i.e. the implementation language of the source code artifacts generated by ANTLR).

When it was released, PCCTS supported C as its only target language, but through consulting with NeXT Computer, PCCTS gained C++ support after 1994. PCCTS's immediate successor was ANTLR 2 and it supported Java, C# and Python as target languages in addition to C++.

Target languages

ANTLR 3 already supports Java, C#, Objective C, C, Python and Ruby as target languages. Support for additional target languages including C++, Perl6 and Oberon (yes, Oberon) is either expected or already in progress. This is all due in part to the fact that it is much easier to add support for a target language (or customize the code generated by an existing target) in ANTLR 3.

Why should I use ANTLR 3?

Because it can save you time and resources by automating significant portions of the effort involved in building language processing tools. It is well established that generative tools such as compiler compilers have a major, positive impact on developer productivity. In addition, many of ANTLR v3's new features including an improved analysis engine, its significantly enhanced parsing strength via LL(star) parsing with arbitrary lookahead, its vastly improved tree construction rewrite rules and the availability of the simply fantastic AntlrWorks IDE offers productivity benefits over other comparable generative language processing toolkits.

How do I use ANTLR 3?

1. Get ANTLR 3

Download and install ANTLR 3 from the ANTLR website.

2. Run ANTLR 3 on a simple grammar

2.1 Create a simple grammar

Java

grammar SimpleCalc;

tokens {
	PLUS 	= '+' ;
	MINUS	= '-' ;
	MULT	= '*' ;
	DIV	= '/' ;
}

@members {
    public static void main(String[] args) throws Exception {
        SimpleCalcLexer lex = new SimpleCalcLexer(new ANTLRFileStream(args[0]));
       	CommonTokenStream tokens = new CommonTokenStream(lex);

        SimpleCalcParser parser = new SimpleCalcParser(tokens);

        try {
            parser.expr();
        } catch (RecognitionException e)  {
            e.printStackTrace();
        }
    }
}

/*------------------------------------------------------------------
 * PARSER RULES
 *------------------------------------------------------------------*/

expr	: term ( ( PLUS | MINUS )  term )* ;

term	: factor ( ( MULT | DIV ) factor )* ;

factor	: NUMBER ;


/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

NUMBER	: (DIGIT)+ ;

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ 	{ $channel = HIDDEN; } ;

fragment DIGIT	: '0'..'9' ;

C#

Note: language=CSharp2 with ANTLR 3.1; ANTLR 3.0.1 uses the older CSharp target

grammar SimpleCalc;

options {
    language=CSharp2;
}

tokens {
	PLUS 	= '+' ;
	MINUS	= '-' ;
	MULT	= '*' ;
	DIV	= '/' ;
}

@members {
    public static void Main(string[] args) {
        SimpleCalcLexer lex = new SimpleCalcLexer(new ANTLRFileStream(args[0]));
       	CommonTokenStream tokens = new CommonTokenStream(lex);

        SimpleCalcParser parser = new SimpleCalcParser(tokens);

        try {
            parser.expr();
        } catch (RecognitionException e)  {
            Console.Error.WriteLine(e.StackTrace);
        }
    }
}

/*------------------------------------------------------------------
 * PARSER RULES
 *------------------------------------------------------------------*/

expr	: term ( ( PLUS | MINUS )  term )* ;

term	: factor ( ( MULT | DIV ) factor )* ;

factor	: NUMBER ;


/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

NUMBER	: (DIGIT)+ ;

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ 	{ $channel = Hidden; } ;

fragment DIGIT	: '0'..'9' ;

Objective-C


To be written. Volunteers?

grammar SimpleCalc;

options
{
    language=ObjC;
}

OR : '||' ;

C

grammar SimpleCalc;

options
{
    language=C;
}

tokens
{
	PLUS 	= '+' ;
	MINUS	= '-' ;
	MULT	= '*' ;
	DIV	= '/' ;
}

@members
{

 #include "SimpleCalcLexer.h"

 int main(int argc, char * argv[])
 {

    pANTLR3_INPUT_STREAM           input;
    pSimpleCalcLexer               lex;
    pANTLR3_COMMON_TOKEN_STREAM    tokens;
    pSimpleCalcParser              parser;

    input  = antlr3AsciiFileStreamNew          ((pANTLR3_UINT8)argv[1]);
    lex    = SimpleCalcLexerNew                (input);
    tokens = antlr3CommonTokenStreamSourceNew  (ANTLR3_SIZE_HINT, TOKENSOURCE(lex));
    parser = SimpleCalcParserNew               (tokens);

    parser  ->expr(parser);

    // Must manually clean up
    //
    parser ->free(parser);
    tokens ->free(tokens);
    lex    ->free(lex);
    input  ->close(input);

    return 0;
 }

}

/*------------------------------------------------------------------
 * PARSER RULES
 *------------------------------------------------------------------*/

expr	: term   ( ( PLUS | MINUS )  term   )*
        ;

term	: factor ( ( MULT | DIV   )  factor )*
        ;

factor	: NUMBER
        ;


/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

NUMBER	    : (DIGIT)+
            ;

WHITESPACE  : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+
              {
                 $channel = HIDDEN;
              }
            ;

fragment
DIGIT	    : '0'..'9'
            ;

Python

grammar SimpleCalc;

options {
	language = Python;
}

tokens {
	PLUS 	= '+' ;
	MINUS	= '-' ;
	MULT	= '*' ;
	DIV	= '/' ;
}

@header {
import sys
import traceback

from SimpleCalcLexer import SimpleCalcLexer
}

@main {
def main(argv, otherArg=None):
  char_stream = ANTLRFileStream(sys.argv[1])
  lexer = SimpleCalcLexer(char_stream)
  tokens = CommonTokenStream(lexer)
  parser = SimpleCalcParser(tokens);

  try:
        parser.expr()
  except RecognitionException:
	traceback.print_stack()
}

/*------------------------------------------------------------------
 * PARSER RULES
 *------------------------------------------------------------------*/

expr	: term ( ( PLUS | MINUS )  term )* ;

term	: factor ( ( MULT | DIV ) factor )* ;

factor	: NUMBER ;


/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

NUMBER	: (DIGIT)+ ;

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ 	{ $channel = HIDDEN; } ;

fragment DIGIT	: '0'..'9' ;

2.2 Run ANTLR 3 on the simple grammar

java org.antlr.Tool SimpleCalc.g

ANTLR will generate source files for the lexer and parser (e.g. SimpleCalcLexer.java and SimpleCalcParser.java). Copy these into the appropriate places for your development environment and compile them.

2.3 Revisit the simple grammar and learn basic ANTLR 3 syntax

Let's break this example down and develop the simple calculator from the beginning. This can help you learn ANTLR by example.

Before you start

You can learn best by following along, experimenting, and looking at the generated source code. If so, you'll need:

  • A simple text editor,
  • An installed copy of ANTLR 3.1, or
  • An installed copy of ANTLR Works (free, highly recommended, and contains its own copy of ANTLR)


Define a trivial grammar

Any language processing system has at least two components:

  1. A lexer that takes a stream of characters and divides the stream into tokens according to pre-set rules, and
  2. A parser that reads the tokens and interprets them according to its rules.

Let's start by defining the rules for a simple arithmetic expression: 100+23:

Trivial calculator
grammar SimpleCalc;

add	: NUMBER PLUS NUMBER;

NUMBER	: ('0'..'9')+ ;

PLUS 	: '+';

This example contains two lexer rules - NUMBER and PLUS - and the parser rule add. Lexer rules always start with an uppercase letter, while parser rules start with lowercase letters.

  • NUMBER defines a token (named "NUMBER") that contains any character between 0 and 9, inclusive, repeated one or more times. .. creates a character range, while + means "one or more times". (This suffix should look familiar if you know regular expressions.)
  • PLUS defines a token with a single character: +.
  • add defines a parser rule that says "expect a NUMBER token, a PLUS token, and a NUMBER token in that order." Any other tokens, or tokens in a different order, will trigger an error message.
Flesh out the calculator

Let's first allow more complex expressions such as 1 or 1+2 or 1+2+3+4 This starts with a single number, then can add a plus sign and a number (possibly more than once):

repeated addition
add: NUMBER (PLUS NUMBER)*

The * symbol means "zero or more times".

If you want to implement both addition and subtraction, you can make a small adjustment:

Addition and subtraction
add: NUMBER ((PLUS | MINUS) NUMBER)*

MINUS : '-';

As you may have guessed, | means "or" as in "PLUS or MINUS".

If you want to parse complete arithmetic expressions such as 1+2*3, there's a standard recursive way to do it:

Recursive expression definition
expr	: term ( ( PLUS | MINUS )  term )* ;
term	: factor ( ( MULT | DIV ) factor )* ;
factor	: NUMBER ;

MULT : '*';
DIV  : '/';

To evaluate an expression, always start with expr.

Handle white space

Our grammar is intolerant of white space: it will give warnings about spaces, tabs, returns, etc. Let's tell the Lexer that it's safe to discard any white space it finds.

First, we have to define white space:

  • A space is ' '
  • A tab is written '\t'
  • A newline (line feed) is written '\n'
  • A carriage return is written '\r'
  • A Form Feed has a decimal value of 12 and a hexidecimal value of $0C. ANTLR uses Unicode, so we define this as 4 hex digits: '\u000C'

Put these together with an "or", allow one or more to occur together, and you have

Defining whitespace
WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+;

However, if we write the expression 3 + 4*5, the lexer will generate NUMBER WHITESPACE PLUS WHITESPACE NUMBER MULT NUMBER and this will cause the parser to complain about the unknown WHITESPACE tokens. We need a way to hide them from the parser.

ANTLR maintains two channels of communication between the lexer and the parser - a default channel and a hidden channel. The parser listens to only one channel at a time (usually the default one), so you can "hide" a token by assigning it to the hidden channel.

There can be more than two channels and the parser can listen to them individually or get the text from all the channels merged together. This is useful when you are writing a text-processing tool that needs to pass through the whitespace and comments to the output while letting the parser ignore those elements.

You hide the token by setting the token's $channel flag to the constant HIDDEN. This requires adding a little code to the lexer, which you do by adding curly brackets:

Defining whitespace
WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ { $channel = HIDDEN; };

If you're following along at the keyboard, try generating the Lexer and Parser code now and search the Lexer for channel = HIDDEN

ANTLR generates Java code by default. You'll learn how to change that in just a minute.

Tidy up the code

You can use a few techniques to make your grammar more readable:

  1. Add comments including single-line // and multi-line /* ... */
  2. Gather your simple token definitions (single characters, single words, etc.) into a tokens section at the top of the file.
  3. Consider defining sub-parts of tokens with fragment rules. A fragment will never generate a token by itself but can be used as part of the rule defining another token.

Here's a tidied-up copy:

Tidier grammar
grammar SimpleCalc;

tokens {
	PLUS 	= '+' ;
	MINUS	= '-' ;
	MULT	= '*' ;
	DIV	= '/' ;
}

/*------------------------------------------------------------------
 * PARSER RULES
 *------------------------------------------------------------------*/

expr	: term ( ( PLUS | MINUS )  term )* ;

term	: factor ( ( MULT | DIV ) factor )* ;

factor	: NUMBER ;

/*------------------------------------------------------------------
 * LEXER RULES
 *------------------------------------------------------------------*/

NUMBER	: (DIGIT)+ ;

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+ 	{ $channel = HIDDEN; } ;

fragment DIGIT	: '0'..'9' ;
Turn this into a stand-alone program

If you try to run this parser, nothing happens.

You need to add some code to make this work as a stand-alone tool, and you may want to add some variables at the top of the parser. All of this happens in a {{ @header { ... } }} block at the top of the file:

Main entry point for Java
@members {
    public static void main(String[] args) throws Exception {
        SimpleCalcLexer lex = new SimpleCalcLexer(new ANTLRFileStream(args[0]));
       	CommonTokenStream tokens = new CommonTokenStream(lex);

        SimpleCalcParser parser = new SimpleCalcParser(tokens);

        try {
            parser.expr();
        } catch (RecognitionException e)  {
            e.printStackTrace();
        }
    }
}

This shows the usual pattern: take an input stream, feed it to the generated Lexer, get a token stream from the lexer, feed that to the parser, and then call one of the methods on the parser. (Each parser rule adds a corresponding method to the parser.)

Don't like Java? You can use ANTLR to generate code for Java, C, C++, C#, Objective-C, Python, Ruby, and other languages (see Code Generation Targets) as well as add your own generator. Use an options block to switch languages:

Typical options block
grammar SimpleCalc;

options {
    language=CSharp2;
}

Your five minutes are up!

You've just seen:

  • How to write lexer rules
  • How to write basic parser rules
  • How to direct tokens away from the parser (to ignore them)
  • How to insert executable code into a parser.

Some points to consider:

  • You can insert custom actions anywhere.
  • Most of your custom code winds up in the last stage of the parsing process. Here it was in the Parser; if you used an AST, it would be in the tree parser.

What next?

This covers the majority of the things you need to know to develop a grammar. You may want to work through another of the tutorials:

You could also:

Special constructs (reference)

Construct

Description

Example

(...)*

Kleene closure - matches zero or more occurrences

LETTER DIGIT* - match a LETTER followed by zero or more occurrences of DIGIT

(...)+

Positive Kleene closure - matches one or more occurrences

('0'..'9')+ - match one or more occurrences of a numerical digit
LETTER (LETTER|DIGIT)+ - match a LETTER followed one or more occurrences of either LETTER or DIGIT

fragment

fragment in front of a lexer rule instructs ANTLR that the rule is only used as part of another lexer rule (i.e. it only builds a fragment of a recognized token)

fragment {{ DIGIT : '0'..'9' ;

NUMBER : (DIGIT)+ ('.' (DIGIT)+ )? ;}}

11 Comments

  1. Unknown User (adv12)

    tried to make a minor edit to this doc but the wiki software seems to munge it in the process.  Seems like clicking "edit" removes some escape sequences....

  2. Unknown User (electricdipole)

    If you are trying the C version and you get:

    ------- 

    Error while generating the grammar:

    (10): internal error: group CDbg line 33: template outputFile has no region called imports

    ------- 

    And from the console:

    ------- 

    [13:42:06] error(10):  internal error: group CDbg line 33: template outputFile has no region called imports

    [13:42:06] error(10):  internal error: group CDbg line 78: template genericParser has no region called superClassName

    [13:42:06] error(10):  internal error: group CDbg line 160: template dfaState has no region called noViableAltException

    [13:42:06] error(10):  internal error: group CDbg line 162: template dfaStateSwitch has no region called noViableAltException

    [13:42:06] error(10):  internal error: org.antlr.tool.Message.toString(Message.java:124): Assertion failed! Message ID 10 created but is not present in errorMsgIDs or warningMsgIDs.

    ------- 

    Then you should click on "Generate"->"Generate Code" or Ctrl-Shift-G

     Hopefully this is useful to someone.

  3. Unknown User (electricdipole)

    If you try the C# example and get the error message:

    --------

    Cannot generate the grammar because:
    error(10): internal error: no such group file CSharp2.stg

    --------

    This means ANTLRWorks can't find a string template group file for CSharp2***.  So there are three options:
    1. Create a CSharp2.stg and find a way to get ANTLRWorks to "see" that - I unzipped the java archive (zip file) and created a CSharp2 folder at a sibling level to the existing CSharp folder and added a CSharp2.stg to that directory - this is basically just faking CSharp2 support
    2. Get ANTLR version 3.1.x - not sure how that integrates with ANTLRWorks - in other words haven't tried that
    3. change the grammar to just CSharp (instead of CSharp2)

  4. Unknown User (artem kulyabin)

    I'm using antlr-3.0.1, C runtime, when the assembly error "undefined reference to` TOKENSOURCE `"

  5. Unknown User (artem kulyabin)

    "tokens = antlr3CommonTokenStreamSourceNew  (ANTLR3_SIZE_HINT, lex->pLexer->tokSource);" - it works.

  6. Unknown User (hkastenberg@gmail.com)

    When using the listed code excerpt to turn the grammar into a stand-alone program, I encounter compilation errors in the generated Java sources.

    Instead of instantiating class SimpleCalc, this should be class SimpleCalcParser like in the first code code excerpt, right?

  7. Ooops. yep. fixed in code. thanks.

  8. Unknown User (isthan)

    This is a great tutorial but  I seem to have issues when I take the advice of collecting the tokens into the block as depicted in the guide.  I get errors in the ANTLRWorks console and the tool tip says "Undefined reference."  

  9. Unknown User (amorphis187@hotmail.com)

    Hello I have just started with antlr I have downloaded antlrWorks-1.4.3. Also antr-3.4-complete-no-antlr-v2.jar and set the classpath. 

    I opened antlrWorks and just copied C grammar then it generated code for me. So I included the 4 files. I have created

    a main where I have just copied the @member main. First I got include problems then I added #include "SimpleCalcParser.h".

    But now I have another problem

    'antlr3AsciiFileStreamNew': identifier not found

    Thank you for attention.

  10. Unknown User (snaka.gml@gmail.com)

    I used antlr 3.4 and C runtime on Mac OS X.

    I faced following error:

    Undefined symbols for architecture x86_64:
      "_antlr3AsciiFileStreamNew", referenced from:
          _main in ccjpU2ed.o
    ld: symbol(s) not found for architecture x86_64
    

    So I fixed grammar file

    input  = antlr3AsciiFileStreamNew          ((pANTLR3_UINT8)argv[1]);
    

    to

    input  = antlr3FileStreamNew              ((pANTLR3_UINT8)argv[1], ANTLR3_ENC_8BIT);
    

    Now it works.

  11. Unknown User (mjakubicek)

    I can't resist complaining about this, as it also illustrates the generally bad shape of the C runtime library. Why was this change not performed in a backward-compatible way? It would have been so easy to keep the old interface – antlr3AsciiFileStreamNew would just call antlr3FileStreamNew with ANTLR3_ENC_8BIT as you show. The same goes for antlr3StringStreamNew. Now everybody has to produce lots of code bloat to check for the runtime version (that is btw. not exported anywhere...unless you want to include antlr3config.h that will override your own defines [edit: right, this is done anyway]) and maintain backward compatibility with antlr 3.2. A big (sad).