Back to series
· 10 min read

Lexical Analysis and Syntax Analysis


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:

  1. Identify keywords, identifiers, literals, and operators.
  2. Identify delimiters and punctuation.
  3. Handle non-essential characters such as spaces, line breaks, and comments.
  4. Record the token's type, content, and source code position.
  5. 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:

  1. The first character must be an English letter or an underscore.
  2. Subsequent characters may be English letters, digits, or underscores.
  3. 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:

  • int is a keyword.
  • if_count is 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.
  • result is 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:

G = (V, \Sigma, P, S)

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:

  • Expr represents an expression.
  • Term represents a term.
  • Factor represents a factor.
  • NUMBER represents 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 * c is 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.