Week 4 - Parser 1

In the previous chapter, we introduced the main components of a compiler's front end and explored lexical analysis. Next, we will turn to the parser. Before diving into the details, let us establish what a parser does: it takes the token stream produced by the lexer and applies a set of grammar rules to organize those tokens into a parse tree for further analysis. If the input cannot be parsed according to those rules, the program contains a syntax error.

What is a parser?

A Parser takes a token stream from a Lexer and turns it into a tree.

This tree is called a parse tree, and the rules used to build it form the grammar.

Recap: Context-Free Grammar (CFG)

We use a context-free grammar (CFG) to describe syntax rules. In the context of formal languages and compiler design, a grammar specifies the syntax of a language.

Like regular expressions, which we covered in the previous chapter, CFGs provide a formal way to describe a language. Regular expressions describe lexical rules: what individual tokens look like. CFGs describe syntax rules at a higher level: how those tokens fit together to form a structurally valid program. ANTLR uses context-free grammars to describe syntax.

Why are CFGs more expressive than regular expressions?

CFGs can describe structures that regular expressions cannot, including recursive and nested structures. A classic example is balanced parentheses: ().

Languages described by CFGs, known as context-free languages, are generally recognized using a pushdown automaton. Unlike the finite automaton used to recognize regular languages, a pushdown automaton has a stack, allowing it to handle recursive and nested structures.

A finite automaton can be viewed as a special case of a pushdown automaton. If you are interested, see Wikipedia - Automata theory.

Two essential components of a CFG are terminals and nonterminals.

Simply put, terminals are the tokens handed to the parser by the lexer. They are the basic units of the grammar and cannot be broken down any further within it. Nonterminals represent structures that the parser recognizes by combining tokens from the input stream. The rules for forming these structures are called productions. A production describes how terminals and nonterminals can form a nonterminal. Viewed in the other direction, it tells us which sequence of terminals and nonterminals a nonterminal can produce—hence the name "production."

Recap: Productions

In the lectures, we write a production as head -> body.

The head must be a nonterminal, while the body contains zero or more terminals or nonterminals.

Defining a CFG in ANTLR

Let us start with a simple ANTLR grammar:

grammar Calc1;

expr    : expr ADD expr
        | expr SUB expr
        | factor
        ;

factor  : INT
        ;

INT : [0-9]+ ;
ADD : '+' ;
SUB : '-' ;

WS  : [ \t\r\n]+ -> skip ; 

In ANTLR terminology, terminals are usually called tokens, and nonterminals are defined by rules.

Both definitions follow the same basic format: a name, a colon, the rule body, and a final semicolon. A token or rule definition can contain multiple alternatives.

ANTLR distinguishes lexer rules from parser rules by the first letter of their names: lexer rule names must begin with an uppercase letter, while parser rule names must begin with a lowercase letter. Lexer and parser rules can be mixed within the grammar; neither group has to come first.

The Calc1 grammar above contains:

• Four terminal definitions whose names begin with an uppercase letter.
• Two nonterminals whose names begin with a lowercase letter.
• Four productions, expressed as alternatives within the parser rules.

Parser Rule

Here is a basic parser rule:

factor : INT ;

The general format is ruleName : Alternatives ;.

A nonterminal can have multiple productions. Separate the alternatives with | and end the rule with ;:

expr    : expr ADD expr
        | expr SUB expr
        | factor
        ;

Rule Elements

Each alternative can contain token references (starting with an uppercase letter), rule references (starting with a lowercase letter), or string literals such as 'literal'.

We can use string literals directly in a parser rule. ANTLR automatically creates and references a corresponding lexer rule, which you can see in the generated .tokens file.

For example, instead of defining ADD: '+', we can write the literal '+' directly in the parser rule:

expr    : expr '+' expr
        | expr '-' expr
        ;

Subrules

An alternative can itself contain a block of alternatives, called a subrule. You can think of a subrule as an anonymous rule defined in place.

Subrules have four forms, with syntax much like regular expressions:

1. (x | y | z): Match one of the alternatives exactly once.
2. (x | y | z)?: Match one of the alternatives once, or not at all.
3. (x | y | z)*: Match the block zero or more times, choosing an alternative each time.
4. (x | y | z)+: Match the block one or more times, choosing an alternative each time.

Subrule Example: (...)* for Zero or More Repetitions

Consider this rule:

expr: NUMBER ('+' NUMBER)*;

Here, ('+' NUMBER)* is a subrule. It means that the sequence '+' NUMBER can appear zero or more times.

---

✅ Matching Inputs

• 7

  • Zero repetitions of ('+' NUMBER).

• 7 + 2

  • One repetition.

• 7 + 2 + 5

  • Two repetitions.

• 7 + 2 + 5 + 8

  • Three repetitions.

---

❌ Non-Matching Inputs

• + 2

  • The rule must begin with a NUMBER.

• 7 +

  • A NUMBER is missing after the +.

Using an ANTLR Parser

How do we use the parser generated by ANTLR? Let us revisit these lines from the example in Week 1 - Intro:

    // Give ANTLR the string we want to parse
    CharStream input = CharStreams.fromString("1 + 2");
    // Create the lexer
    Calc1Lexer lexer = new Calc1Lexer(input);
    // Create the token stream
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    // Create the parser
    Calc1Parser parser = new Calc1Parser(tokens);
    // Start parsing at the 'expr' rule
    ParseTree tree = parser.expr();
    // Print the tree
    System.out.println(tree.toStringTree(parser));

When we create the Calc1Parser, we pass it the CommonTokenStream produced in the previous step. Calling parser.expr() then asks the parser to build a parse tree rooted at expr from that token stream.

ANTLR generates a method for every parser rule, using the rule's name as the method name. Calling one of these methods starts parsing from that rule, which becomes the root of the resulting tree.

Start Rules and EOF

The rule we choose when we first invoke the parser is called the start rule. In ParseTree tree = parser.expr(), the start rule is expr, which is also the nonterminal at the root of the tree we want to build. Keep in mind that a start rule does not necessarily consume every token in the stream: it consumes only the tokens needed to build that parse tree.

This is why running the program above can produce the error line 1:5 no viable alternative at input '<EOF>': after the parser consumes the input tokens, it encounters the special token <EOF>, which marks the end of the stream. If it cannot find a valid alternative at that point, it reports this error.

Usually, we want the parser to process an entire source file. To do so, we can define a higher-level start rule that explicitly includes the end-of-file token:

root: expr EOF;

expr : ... 

Then use ParseTree tree = parser.root(); in Java to parse the entire token stream.

Quickly Inspecting a Parse Tree

By now, this command should look familiar:

make

We have been using it to generate lexers and parsers since the earlier labs.

There is no ANTLR magic built into make itself, though. It simply runs the commands defined in the Makefile at the project root.

What Does make Actually Do?

In the Makefile we have been using, this is the command that generates the ANTLR code:

Makefile

java -jar $(ANTLR_JAR) \
    -visitor \
    -o $(OUTPUT_DIR)/$(basename $<) \
    -package generated.$(basename $<) \
    $<

We have already specified the location of ANTLR:

ANTLR_JAR := libs/antlr-4.13.2-complete.jar

For a grammar named Calc1.g4, the Makefile rule therefore runs a command like this:

java -jar libs/antlr-4.13.2-complete.jar \
    -visitor \
    -o src/main/java/generated/Calc1 \
    -package generated.Calc1 \
    Calc1.g4

Think of make as a handy command runner

It finds our .g4 files and invokes:

antlr-4.13.2-complete.jar

to generate the corresponding Java lexer, parser, and visitor.

ANTLR is doing the actual code generation.

---

We Have Already Printed a Parse Tree

In Week 1 - Intro, we used this line to inspect the parse tree produced by the parser:

System.out.println(tree.toStringTree(parser));

Here, tree is the ParseTree obtained by parsing from a particular parser rule. The call:

tree.toStringTree(parser)

converts that tree into a parenthesized representation that is easy to display in a terminal.

For example, given this input:

1 + 2

we might get output like this:

(expr (expr 1) + (expr 2))

Recall that producing this tree required us to set up the entire parsing pipeline ourselves:

Input
  ↓
CharStream
  ↓
Lexer
  ↓
Token Stream
  ↓
Parser
  ↓
ParseTree
  ↓
toStringTree(...)

In other words, we manually created the lexer, token stream, and parser in Main.java, then printed the resulting parse tree.

The antlr-4.13.2-complete.jar file also includes a ready-made testing tool:

org.antlr.v4.gui.TestRig

It provides a quick way to carry out much the same process.

There is nothing mysterious about TestRig

Previously, we created the lexer, token stream, and parser ourselves in Main.java, then called:

tree.toStringTree(parser)

TestRig packages that testing workflow into a tool we can run directly.

If we just want to see how a grammar parses a piece of input, there is no need to edit Main.java every time.

---

Using -tree to Inspect a Parse Tree

Suppose we have a grammar file named:

Calc1.g4

with generated Java classes in the package:

generated.Calc1

and we want to start parsing from this rule:

expr
    : ...
    ;

First, run the usual command:

make

and make sure the generated Java source files have been compiled.

Then run:

echo '1 + 2 * 3' | \
java -cp "bin:libs/antlr-4.13.2-complete.jar" \
    org.antlr.v4.gui.TestRig \
    generated.Calc1.Calc1 \
    expr \
    -tree

ANTLR will print the parse tree directly in the terminal. For example:

(expr (expr 1) + (expr 2) * (expr 3))

The exact structure depends on your grammar.

Although this representation does not look like a tree drawn on paper, the parentheses show how the nodes are nested.

For example, we can take:

(expr (expr 1) + (expr (expr 2) * (expr 3)))

and expand it over multiple lines:

(expr
    (expr 1)
    +
    (expr
        (expr 2)
        *
        (expr 3)
    )
)

This makes the parent-child relationships easier to see.

---

What Does This Command Mean?

The command may look long, but there are only a few parts to focus on:

Argument	Meaning
bin:libs/antlr-4.13.2-complete.jar	Where the Java runtime looks for compiled .class files and ANTLR classes
org.antlr.v4.gui.TestRig	The grammar testing tool bundled with ANTLR
generated.Calc1.Calc1	The grammar to use
expr	The parser rule to start from
-tree	Print the parse tree in the terminal

The parts you will change most often are:

generated.Calc1.Calc1
expr

For example, if your grammar is:

grammar SPL;

its generated Java package is:

generated.SPL

and its entry rule is:

compUnit
    : ...
    ;

then you can use:

echo '...' | \
java -cp "bin:libs/antlr-4.13.2-complete.jar" \
    org.antlr.v4.gui.TestRig \
    generated.SPL.SPL \
    compUnit \
    -tree

Look at the tree when debugging your parser

When you are unsure whether your grammar behaves as intended, -tree is a useful debugging tool.

It is especially helpful for checking:

• Whether a piece of input was parsed correctly.
• What structure a particular parser rule matched.
• Whether operator precedence and associativity work as expected.
• Why an expression was parsed differently from what you had in mind.
• How a grammar change affects the parse tree.

Looking at the tree ANTLR actually produces can be much more helpful than repeatedly trying to work it out from the .g4 file alone.

---

Viewing a Graphical Parse Tree

TestRig also provides the option:

-gui

which displays the parse tree graphically.

For example:

echo '1 + 2 * 3' | \
java -cp "bin:libs/antlr-4.13.2-complete.jar" \
    org.antlr.v4.gui.TestRig \
    generated.Calc1.Calc1 \
    expr \
    -gui

If a graphical display is available and configured correctly, ANTLR opens a window showing the tree.

However, we usually develop on a virtual machine through SSH or VS Code Remote-SSH.

In that setup, ANTLR runs on the remote virtual machine. The remote terminal may not have access to a graphical display by default, so -gui may not be able to open a window directly.

Explore this further if you are interested

It is possible to display GUI applications from a remote Linux environment.

If you would like to learn more, look into:

• X11 forwarding.
• The DISPLAY environment variable.
• How remote Linux applications display their windows on a local computer.

These topics are outside the course requirements, and you do not need them to complete the projects.

For everyday parser debugging in this course, using:

-tree

is sufficient.

---

First, you need a tree to inspect

Both -tree and -gui display a parse tree, so you need a parser before you can use them for this purpose.

If your .g4 file begins with:

lexer grammar ExampleLexer;

then you currently have only a lexer. It produces a token stream, not a parse tree.

Without a parser, there is no parse tree to display.

Exercise

Extend the Calc1 grammar introduced above to support multiplication, division, and parentheses in addition to addition and subtraction. Then write a small program to test it with the following input:

(1 + 2 * 2 / 3)