ANTLR4

Parsing, Analysing, and Compiling with ANTLR4

What is ANTLR4?

“ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. It’s widely used to build languages, tools, and frameworks. From a grammar, ANTLR generates a parser that can build and walk parse trees.” — exact definition from Terence

ANTLR is like a tour that helps you explore a park (language). It gives you a map (grammar), a guide (parser), and a structured walking path (parse tree) to ensure you don’t get lost.

What can it do?

ANTLR can build compilers and interpreters, even create your own new programming language, convert one language to another, or parse complex text such as JSON or any text with a structured format + files. It can also be used for AI NLP, natural language processing due to how it can work with structured text.

ANTLR can also help when it comes to the security aspects, such as detecting SQL injection attacks from users, logs analysis for security logs, or if an API allows users to send structured queries; ANTLR can validate the input structure and patterns. It can even detect malware patterns in files, and misconfiguration in firewalls.

Core elements of ANTLR4

Grammar file

A grammar file defines the rules for how the input should be structured, so it includes the tokens (lexer rules) and the syntax (parser rules).

A simple grammar example for a calculator:

grammar Calc;

// Parser Rules
expr: expr ('+'|'-') expr   # AdditionOrSubtraction
    | INT                   # Number
    ;

prog: expr EOF;  // Ensures the entire input is parsed and ends properly

// Lexer Rules
INT: [0-9]+;       // Matches numbers
WS: [ \t\r\n]+ -> skip;  // Skips whitespace

Grammar Best Practises

1. Keep lexer and parser rules separate.
2. Use EOF to ensure full input is parsed.
3. Use hierarchical rules to handle operator precedence.
4. Avoid left recursions, don't let the rules call themselves first — this can lead to infinite recursion. e.g. expr: expr ‘+’ term | term. Use iteration, such as* expr: term (‘+’ term).**

Lexer

The lexer breaks the raw text into tokens, and each token is defined by the grammar, e.g., integers, booleans, or literals. Then, it passes these tokens into the parser.

Parser

The parser takes the tokens from the lexer and checks to see if the tokens follow the valid syntax from the defined parser rules in the grammar file.

It builds a parse tree while parsing the tokens and uses LL(*) algorithm as the parser reads the tokens it incrementally builds the parse tree. The AST is often used as the intermediate representation between the front-end and back-end, the AST removes unnecessary elements like parentheses and is used for further analysis also optimisation in the back-end.

Parse Tree for the simple grammar

There are two types of parsing: top-down parsing and bottom-up parsing.

Top-down parsing is a parsing technique where one first looks at the highest level of the parse tree and then works down the parse tree to the lowest node by using the rewriting of rules of a formal grammar.

Steps:

• Construct the top node of the tree and then the rest in pre-order. (depth-first)
• Pick a production and try to match the input; if you fail, backtrack.
• Essentially, we try to find a leftmost derivation for the input string (which we scan left to right).
• Some grammars are backtrack-free (predictive parsing)

Recursive descent is a top-down parsing technique that constructs the parse tree from the top, and the input is read from left to right. It uses procedures for every terminal and non-terminal entity.

Steps:

• Construct the root with the starting symbol of the grammar.
• Expand nodes using the grammar rules, in example, a current node A. Look at this node, and choose the matching production rule that matches this node. Add the child nodes for the symbols on the right-hand side of the rule.
• Match terminal symbols to the input. When a terminal like +, -, or INT is reached, check if it matches the input. If it matches, then move on to the next token.
• Continue these steps for non-terminals like expr or term in our Calc grammar. Keep expanding until the entire input is processed.
• Stop when it matches the parse tree.

Bottom-up parsing discovers and processes trees starting from the bottom left end, and then works its way upwards and rightwards.

Steps:

• Construct the tree for an input string, beginning at the leaves and working up towards the top (root).
• Bottom-up parsing, using a left-to-right scan of the input, tries to construct a rightmost derivation in reverse.
• Note: Handle a large class of grammars

Listeners and Visitors

Once the parse tree is generated by the parser, we need to traverse it and perform actions on the tree.

Listeners are event-driven parsing, and it automatically walks through the tree, and uses event listener approach; such as event listeners in Java. It calls methods like enterRule and exitRule when visiting the nodes automatically. Only downside to listeners is that they cannot return a value and have no control over the traversal; this is good or bad depending on your needs. Listeners are best for logging or event-based processing, e.g. debugging or syntax checking.

To make your own listener implementation you need to extend the BaseListener that is generated by the ANTLR4 recogniser.

Example code for a listener class in Java:

public class MyCalcListener extends CalcBaseListener {
    @Override
    public void enterExpr(CalcParser.ExprContext ctx) {
        System.out.println("Entering expression: " + ctx.getText());
    }

    @Override
    public void exitExpr(CalcParser.ExprContext ctx) {
        System.out.println("Exiting expression: " + ctx.getText()); 
    }
}

ctx.getText() returns the text of the current node in the parse tree.

enterExpr(CalcParser.ExprContext ctx) is called when entering an expression node.

exitExpr(CalcParser.ExprContext ctx) is called when entering an expression node.

Visitors

Visitors allow for manual tree traversal, you can visit and process specific parse tree nodes. This makes it a good choice for when evaluating expressions, code generation or transforming the parsed structures. Visitors also allow return values, so when you evaluate an expression; it means you can store the computed/result of the evaluation.

Example visitor code for the Calc grammar:

@Override
public Integer visitAdditionOrSubtraction(CalcParser.AdditionOrSubtractionContext ctx) {
    int left = visit(ctx.expr(0));  // Visit left operand (2)
    int right = visit(ctx.expr(1)); // Visit right operand (5)
    String operator = ctx.getChild(1).getText();  // Extract operator "+"

    if (operator.equals("+")) {
        return left + right;  // Returns 2 + 5
    } else {
        return left - right;
    }
}

visit(ctx.expr(0)) recursively visits the first child in the sub expression. The operator in this case is child 1.

Parse Tree for the simple grammar

Error Handling

ANTLR4 also provides a built-in error handling class, which can be extended to make a custom implementation of an error handler. This is crucial for compilers and interpreters. The error handler can generate syntax errors when invalid input is encountered, and you can override the original method to provide a more specific/custom output that could be very insightful for debugging. ANTLR also supports error recovery strategies to continue parsing or just to immediately fail on errors.

An example of a custom error handler for syntax errors in Java:

public class MyErrorListener extends BaseErrorListener {
    @Override
    public void syntaxError(Recognizer<?, ?> recognizer, Object offendingSymbol,
                            int line, int charPositionInLine, String msg, RecognitionException e) {
        System.err.println("Syntax Error at line " + line + ":" + charPositionInLine + " - " + msg);
    }
}

How to use ANTLR4 (IntelliJ way):

Luckily to make life easier, you can just install the ANTL4 community package on the IntelliJ marketplace.

1. Create a project in IntelliJ, SDK 21.
2. If ANTLR4 isn’t installed as an IntelliJ plugin; do it now by pressing CTRL + ALT + S, plugins marketplace and type ANTLR4. Reload.
3. In Project Structure > Project Settings > Libraries; click on the plus symbol at the top of the tab to add new project library, click on Java — find this antlr-4.13.2-complete.jar file then click on Apply on the bottom right.
4. Once it has been applied and added to the project. The imports will work from ANTLR.
5. Start making your grammar, make a new file name is anything but .g4 must be the ending. e.g. Sample.g4
6. Once grammar is made, then right click the grammar file in the project library and ‘Generate ANTLR recogniser’ — this will give the BaseVisitor and Listener classes allowing you to extend them and make your own implementation.

Front-end of a compiler:

Front-end is also known as the analysis phase, it processes the source code, checks the correctness and generates then the intermediate representation.

1. Lexical analysis (lexing) — converts source code into tokens.
2. Syntax analysis (parsing) — ensures the code follows the grammar rules.
3. Semantic Analysis — checks meaning, type checking, determining the static types of expressions, undeclared variables, multiple declarations, wrong arguments, or definite-assignment checks. The semantic analyser reorganises the Abstract Syntax Tree to handle structures that are inconvenient during parsing, using semantic information like type checking and scope resolution.
4. Intermediate representation generation — translates source code into an intermediate form.

The input is the Abstract Syntax Tree, produced by the parser representing the program structure. The output for the semantic analyser is then the annotated (annotations are links or keys to a symbol table) Abstract Syntax Tree which is enriched with scope and reference information. There is also a symbol table which is passed into the semantic analysis, this stores the important information about identifiers such as variables, functions, types, scope, etc. The semantic analyser reads and updates the symbol table to:

1. Resolve identifiers (where they’re declared).
2. Perform type checking to ensure that the operations use compatible types.
3. Check scope rules to verify variables and functions are accessed in the correct scopes.
4. Detect semantic errors such as undeclared variables or type mismatches.

The back-end of a compiler

1. Optimisation — improves efficiency, reduces memory usage, and speeds up execution.
2. Code generation — converts intermediate representation into machine code (assembly).
3. Register allocation — assigns variables to the CPU registers.
4. Machine code output — produces executable binary for the target architecture, e.g. .class, .exe, .out.

Key intermediate representation formats:

• Three-Address Code (TAC) — uses temporary variables
• Reverse polish notation (RPN) — operands before the operator like a stack. 23+ instead of 2+3.
• LLVM IR — most modern compilers