1. Overall Responsibilities of the Compiler Front End
The compiler needs to convert human-written source code into a structured representation that subsequent stages can process. In this process, lexical analysis and syntax analysis handle recognition tasks at different levels.
- Lexical Analysis: Recognize character sequences and divide them into tokens, the lexical units that carry independent meaning.
- Syntax Analysis: According to the grammar rules defined by the language, determine whether the token sequence conforms to the grammar and build a syntax tree.
- Semantic Analysis: Check whether the syntactic structure has valid semantics, for example, whether variables are declared, whether types match, and whether function call arguments are correct.
The overall process is as follows:
flowchart TB
A["Source Code"]
B["Lexical Analysis (Lexer)"]
C["Token Sequence"]
D["Syntax Analysis (Parser)"]
E["Abstract Syntax Tree AST"]
F["Semantic Analysis"]
G["Intermediate Representation IR"]
A --> B
B --> C
C --> D
D --> E
E --> F
F --> G
style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
Note that lexical analysis and syntax analysis are conceptual divisions of responsibility; this does not mean that every compiler must implement them as completely separate modules. Some parsers process the character stream directly, or combine lexical analysis and syntax analysis.
2. Lexical Analysis
2.1 What Is Lexical Analysis
Lexical analysis is the first major stage of the compiler front end.
It reads the character stream in the source code and, according to the lexical rules defined by the programming language, divides consecutive characters into individual tokens.
For example:
int count = 10 + 20;
The lexer does not directly understand the complete computational meaning of this code; instead, it identifies the lexical units within it:
| Source Code Fragment | Token Type | Description |
|---|---|---|
int |
KEYWORD | Keyword |
count |
IDENTIFIER | Identifier |
= |
ASSIGN | Assignment operator |
10 |
INTEGER_LITERAL | Integer literal |
+ |
PLUS | Addition operator |
20 |
INTEGER_LITERAL | Integer literal |
; |
SEMICOLON | Semicolon |
The core tasks of lexical analysis are:
- Identify keywords, identifiers, literals, and operators.
- Identify delimiters and punctuation.
- Handle non-essential characters such as spaces, line breaks, and comments.
- Record the token's type, content, and source code position.
- Detect character sequences that cannot match lexical rules.
2.2 Composition of a Token
A token is the basic unit output by lexical analysis.
A token usually contains the following information:
| Attribute | Meaning | Example |
|---|---|---|
| Type | Token type | IDENTIFIER |
| Lexeme | Original text in the source code | count |
| Literal | Parsed literal value | 123 |
| Position | Source code position | Line 1, column 5 |
Among these, Type and Lexeme are the most essential pieces of information.
For example:
int count = 123;
The identifier count can be represented as:
Type: IDENTIFIER
Lexeme: count
The integer 123 can be represented as:
Type: INTEGER_LITERAL
Lexeme: 123
Literal: 123
Not all tokens need to have a Literal. For identifiers and operators, it is usually enough to record the type and the lexeme; for literals such as numbers and strings, the parsed value may need to be stored as well.
2.3 Common Token Types
Token classification differs across programming languages, but the following categories are usually included:
| Token Type | Example | Description |
|---|---|---|
| Keyword | if, while, return |
Keywords reserved by the language |
| Identifier | name, calculate |
Names of variables, functions, types, etc. |
| Integer literal | 10, 0xFF |
Integer constant |
| Floating-point literal | 3.14, 1e-5 |
Floating-point constant |
| String literal | "hello" |
String constant |
| Operator | +, ==, && |
Operators |
| Delimiter | (, ), {, } |
Structural boundaries |
| Comment | // comment |
Usually not emitted as an ordinary token |
| Whitespace | Spaces, line breaks | Usually ignored or handled as a special token |
Note that comments and whitespace are not necessarily discarded outright.
For example, code formatters, syntax highlighters, macro systems, and compilers that need to preserve source structure may retain comments, whitespace, or line-break information.
2.4 Lexical Rules and Regular Expressions
Lexical analysis typically defines valid tokens through a set of lexical rules.
Many common lexical rules can be described using regular expressions.
For example:
| Token | Example Regular Expression | Meaning |
|---|---|---|
| Identifier | [a-zA-Z_][a-zA-Z0-9_]* |
Starts with a letter or underscore |
| Integer | [0-9]+ |
One or more digits |
| Whitespace | [ \t\r\n]+ |
Spaces, tabs, and line breaks |
| Addition operator | \+ |
Plus sign |
| Assignment operator | = |
Equals sign |
Taking the identifier rule as an example:
[a-zA-Z_][a-zA-Z0-9_]*
It means:
- The first character must be an English letter or an underscore.
- Subsequent characters may be English letters, digits, or underscores.
- The number of characters may be one or more.
Therefore:
name
_user
count123
all satisfy this rule, whereas:
123name
does not satisfy the identifier rule.
This is only a simplified example. The identifier rules of real languages may support Unicode characters and are subject to the character categories and normalization rules in the language specification.
2.5 Distinguishing Keywords from Identifiers
Keywords and identifiers usually have similar character forms but belong to different semantic categories.
For example:
int if_count = 10;
where:
intis a keyword.if_countis an identifier.
A lexer usually adopts one of the following strategies:
Strategy 1: Recognize keywords independently
Define dedicated rules for keywords within the lexical rules.
Strategy 2: Recognize identifiers first, then look them up in the keyword table
First recognize the complete lexeme according to the identifier rule, then look it up in the keyword table to determine whether it is a keyword or an ordinary identifier.
The second approach is very common in practical lexers.
The key point is: a keyword usually cannot be recognized as a keyword merely because it contains some keyword fragment.
For example, if_count should not be split into if and _count.
2.6 The Maximal Munch Principle
When several lexical rules can all match the current input, the lexer usually prefers the rule that matches the longest character sequence.
This is called the maximal munch principle.
For example:
a >= b
For > and >=, both can match starting from the current position, but maximal munch will prefer to recognize >=.
Another example:
count123
The lexer should recognize the entire character sequence as a single identifier first, rather than splitting it into count and 123.
The longest-match principle can eliminate a great deal of lexical ambiguity, but it does not solve all grammatical problems. Different languages may also handle conflicts through keyword precedence, special lexical rules, and context rules.
3. How the Lexer Works
3.1 From Character Stream to Token Stream
A lexer typically reads source code from left to right.
It must maintain the current read position and identify the next Token according to the lexical rules.
The basic process is as follows:
flowchart TB
A["Read source code characters"]
B["Skip or handle whitespace and comments"]
C["Match lexical rules"]
D{"Is there a valid match?"}
E["Apply the longest-match rule"]
F["Generate Token"]
G["Record Token position"]
H["Continue reading"]
I["Report lexical error"]
J["End"]
A --> B
B --> C
C --> D
D -->|"Yes"| E
E --> F
F --> G
G --> H
H --> A
D -->|"No"| I
I --> J
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style I fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style J fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
In practice, a lexer usually does not run a full regular expression match for every Token. Mature lexers tend to convert lexical rules into finite automata so that they can recognize character sequences efficiently.
3.2 Finite Automaton
A finite automaton is a mathematical model used to recognize specific character patterns, and it is also an important theoretical foundation of lexical analysis.
A finite automaton mainly consists of the following parts:
- A set of states: the different states in the recognition process.
- A set of input characters: the range of characters the automaton can read.
- A state transition function: defines how to switch states after reading a character.
- An initial state: the starting point of the recognition process.
- Accepting states: indicating that the current character sequence conforms to some lexical rule.
For example, to recognize a simple decimal integer:
[0-9]+
It can be represented by a simple automaton:
flowchart LR
A(["Start"])
B["Read digit"]
C(["Accepting state"])
A --> B
B -->|"digit"| B
B --> C
style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
This model expresses the following: after reading at least one digit, the current integer lexeme can be accepted; if more digits are read, the automaton stays in the digit state.
In a formal automaton, the accepting state and the end of reading are two different concepts. The automaton may enter an accepting state at some position but still need to keep reading in order to determine whether a longer valid match exists.
3.3 DFA and NFA
Finite automata fall into two main categories:
| Type | Full name | Characteristics |
|---|---|---|
| DFA | Deterministic Finite Automaton | Given a state and an input character, the state transition is unique |
| NFA | Nondeterministic Finite Automaton | A single state and input character may correspond to multiple transitions, and empty transitions may also exist |
A lexer can usually convert regular expressions into an NFA and then further into a DFA.
The common conversion process:
flowchart TB
A["Regular expression"]
B["Construct NFA"]
C["NFA state set"]
D["Subset construction"]
E["DFA"]
F["Optimize DFA"]
G["Generate lexer"]
A --> B
B --> C
C --> D
D --> E
E --> F
F --> G
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style C fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
Where:
- NFA is easier to construct from a regular expression.
- At runtime, a DFA can directly determine the next state based on the current state and input character.
- A DFA can usually be optimized by methods such as state merging.
Note that a DFA may suffer from state explosion because its state set is too large. In practice, lexers choose different automaton structures based on performance and implementation complexity, and do not necessarily use a complete, minimized DFA.
4. Syntax Analysis
4.1 What Is Syntax Analysis
Syntax analysis is the second major phase of the compiler front end.
It receives the token sequence generated by the lexer and, according to the grammar rules defined by the programming language, identifies the structural relationships between tokens.
For example:
int result = a + b * c;
Lexical analysis can identify:
INT
IDENTIFIER(result)
ASSIGN
IDENTIFIER(a)
PLUS
IDENTIFIER(b)
MULTIPLY
IDENTIFIER(c)
SEMICOLON
However, merely obtaining the token sequence is not enough to determine the nesting relationships of the expression.
Syntax analysis needs to further identify:
- This is a variable declaration statement.
resultis the declared variable.- The right-hand side is an addition expression.
- The right operand of the addition expression is a multiplication expression.
Therefore, the core task of syntax analysis is to build a hierarchical structure among tokens.
4.2 Grammar Rules and Context-Free Grammars
Programming languages usually use formal grammars to describe their syntactic structure.
A common one in compilers is the context-free grammar (CFG).
A context-free grammar usually consists of four parts:
Where:
- V: the set of nonterminals, representing syntactic structures.
- \Sigma: the set of terminals, usually corresponding to tokens.
- P: the set of production rules.
- S: the start symbol, representing the entry point of syntax analysis.
For example, define a simple arithmetic expression grammar:
Expr -> Expr + Term
Expr -> Term
Term -> Term * Factor
Term -> Factor
Factor -> NUMBER
Factor -> ( Expr )
Where:
Exprrepresents an expression.Termrepresents a term.Factorrepresents a factor.NUMBERrepresents a numeric token.+,*,(, and)are terminals.
This set of rules expresses the structural relationship that multiplication has higher precedence than addition.
Note that the above grammar is in left-recursive form. It is suitable for some bottom-up parsing algorithms, but cannot be used directly with an ordinary recursive descent parser. A recursive descent parser usually needs to eliminate left recursion first, or adopt another parsing strategy.
4.3 Parse Tree
According to the grammar rules, a parser can build a parse tree, also called a concrete syntax tree (CST).
For example:
a + b * c
According to the expression grammar above, the following structure can be formed:
```mermaid flowchart TB A["Expr"] B["Expr"] C["+"] D["Term"] E["Term"] F["*"] G["Factor"] H["Factor"] I["Factor"] J["a"] K["b"] L["c"] A --> B A --> C A --> D B --> E E --> G G --> J D --> H D --> F D --> I H --> K I --> L style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976 style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155 style C fill:#FFF5DE,stroke:#E8D29A,color:#334155 style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155 style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155 style F fill:#FFF5DE,stroke:#E8D29A,color:#334155 style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style H fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style I fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style J fill:#E8EDF2,stroke:#B8C3CE,color:#334155 style K fill:#E8EDF2,stroke:#B8C3CE,color:#334155 style L fill:#E8EDF2,stroke:#B8C3CE,color:#334155 linkStyle default stroke:#A3B8AC,stroke-width:1.5px ```From the tree structure, we can see that:
- The root node represents the entire expression.
- Addition is the top-level operation of the expression.
- Multiplication belongs to the subexpression on the right side of the addition.
b * cis organized as a complete multiplicative structure.
This is how operator precedence is reflected in the syntax tree.
4.4 Concrete Syntax Tree and Abstract Syntax Tree
The concrete syntax tree (CST) and the abstract syntax tree (AST) are two concepts that are easily confused.
Concrete Syntax Tree (CST)
It retains more syntactic detail and can usually reflect the expansion process of grammar productions.
Abstract Syntax Tree (AST)
It retains the core structure useful for program semantic analysis and subsequent compilation, omitting some purely syntactic detail.
For example:
a + b * c
Its AST can be simplified to:
+
/ \
a *
/ \
b c
The AST does not need to retain all parentheses, semicolons, and intermediate grammar nodes.
A CST focuses more on how the source code conforms to the grammar, while an AST focuses more on what structure the program expresses.
| Comparison Dimension | CST | AST |
|---|---|---|
| Full Name | Concrete Syntax Tree | Abstract Syntax Tree |
| Structure | Closer to the complete grammar | Closer to the program structure |
| Syntactic Detail | Usually retains more | Usually omits redundant detail |
| Parentheses and Delimiters | Usually retained | Usually not retained as independent nodes |
| Main Use | Syntax reconstruction, formatting, editor tools | Semantic analysis, optimization, code generation |
Not all compilers build both a CST and an AST. Some compilers build the AST directly during parsing.
V. Core Issues in Syntax Analysis
5.1 Operator Precedence
Operator precedence determines the order in which different operators in an expression are combined.
For example:
a + b * c
If multiplication has higher precedence than addition, the expression is equivalent to:
a + (b * c)
and not to:
(a + b) * c
The parser needs to organize expressions correctly through grammar structure, operator precedence tables, or precedence rules in the parsing algorithm.
5.2 Operator Associativity
Associativity determines how operators of the same precedence are organized.
For example:
a - b - c
Subtraction is usually left-associative, so the expression is equivalent to:
(a - b) - c
and not to:
a - (b - c)
The assignment operator is usually right-associative:
a = b = c
Its structure is usually equivalent to:
a = (b = c)
Precedence and associativity together determine the syntactic structure of an expression.
5.3 Left Recursion and Right Recursion
The direction of recursion in a grammar affects how the parser is implemented.
For example:
Left recursion:
Expr -> Expr + Term
Expr -> Term
Right recursion:
Expr -> Term + Expr
Expr -> Term
Both forms can express a sequence of additions, but they place different requirements on the parser.
A recursive descent parser starts by calling the function corresponding to a nonterminal. If it is implemented directly according to a left-recursive grammar:
parseExpr():
parseExpr()
match("+")
parseTerm()
the function will keep calling itself, resulting in infinite recursion.
Therefore, recursive descent parsers usually need to eliminate left recursion.
For example, converting the left-recursive expression:
Expr -> Expr + Term
Expr -> Term
into:
Expr -> Term ExprTail
ExprTail -> + Term ExprTail
ExprTail -> ε
Here, ε represents the empty string.
This form allows the recursive descent parser to consume input tokens step by step.
5.4 Grammar Ambiguity
If a token sequence can generate multiple different parse trees under the same grammar, then the grammar is ambiguous.
For example:
Expr -> Expr + Expr
Expr -> Expr * Expr
Expr -> NUMBER
For:
a + b * c
two different interpretations are possible:
(a + b) * c
or:
a + (b * c)
If the grammar does not explicitly specify precedence and associativity, the structure of the expression cannot be uniquely determined.
Common solutions include:
- Redesign the grammar so that precedence is reflected in the hierarchy of productions.
- Configure operator precedence and associativity for the parser.
- Use a parsing strategy suited to handling ambiguous expressions.