Mastering Compiler Front‑End: Lexical, Syntax & Semantic Analysis with Antlr

1. Introduction

The concept of “code visualization” has been introduced earlier; this article focuses on the compiler front‑end knowledge required for building such visualizations and points to further reading for deeper study.

2. Compiler

The discussion concentrates on the front‑end of a compiler, while back‑end code generation and target‑machine specifics are rarely visualized.

2.1 Compiler Workflow

2.2 Compiler Front‑End

2.2.1 Lexical Analysis (Scanning)

Lexical analysis, also called scanning, reads the character stream of a source program and groups characters into meaningful lexemes such as keywords, identifiers, constants, operators, and delimiters. For each lexeme the lexer produces a token of the form <type, attribute>.

The core logic of the lexer is based on finite automata, including nondeterministic finite automata (NFA) and deterministic finite automata (DFA).

2.2.1.2 Practice

Use Antlr to perform lexical analysis on a Java source file. The Java8Lexer.g4 file defines token rules, and a simple HelloWorld program is analyzed.

# Lexical rules (excerpt)
ABSTRACT : 'abstract';
ASSERT   : 'assert';
BOOLEAN  : 'boolean';
BREAK    : 'break';
BYTE     : 'byte';
... 
StringLiteral : '"' StringCharacters? '"';
fragment StringCharacters : StringCharacter+;
fragment StringCharacter : ~["\\
] | EscapeSequence;

public class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello, World");
    }
}

# Compile lexer
antlr Java8Lexer.g4
# Compile generated Java files (ensure Antlr JAR is in CLASSPATH)
javac Java8Lexer.java
# Run lexer and view tokens
grun Java8Lexer tokens -tokens ./examples/helloworld.java

2.2.2 Syntax Analysis (Parsing)

Parsing, also called syntactic analysis, takes the token stream and builds an abstract syntax tree (AST) according to a context‑free grammar (CFG). A CFG consists of non‑terminals, terminals, production rules, and a start symbol.

Parsing strategies include top‑down approaches (recursive‑descent, LL) and bottom‑up approaches (LR), each with different strengths and complexities.

2.2.2.2 Practice

Use Antlr with PlayScript.g4 (which imports CommonLexer.g4) to generate a parser and visualize the AST.

grammar PlayScript;
import CommonLexer; // import lexical definitions

@header { package antlrtest; }

expression : assignmentExpression
           | expression ',' assignmentExpression ;

assignmentExpression : additiveExpression
                     | Identifier assignmentOperator additiveExpression ;

assignmentOperator : '=' | '*=' | '/=' | '%=' | '+=' | '-=' ;

additiveExpression : multiplicativeExpression
                    | additiveExpression '+' multiplicativeExpression
                    | additiveExpression '-' multiplicativeExpression ;

multiplicativeExpression : primaryExpression
                        | multiplicativeExpression '*' primaryExpression
                        | multiplicativeExpression '/' primaryExpression
                        | multiplicativeExpression '%' primaryExpression ;

# Compile grammar
antlr PlayScript.g4
# Compile generated Java files (ensure Antlr JAR is in CLASSPATH)
javac *.java
# Run parser with GUI to view AST
grun antlrtest.PlayScript expression -gui

2.2.3 Semantic Analysis

Semantic analysis checks that the program conforms to language rules, performing type checking, variable binding, control‑flow verification, uniqueness, and access‑control checks. It uses symbol tables and various compiler components such as Symbol, Scope, Type, Attr, Check, Resolve, Flow, LambdaToMethod, TransTypes, and Lower.