一、编译器前端的整体职责
编译器需要将人类编写的源代码转换为后续阶段能够处理的结构化表示。在这一过程中,词法分析和语法分析承担不同层次的识别任务。
- 词法分析(Lexical Analysis):识别字符序列,将其划分为具有独立意义的词法单元 Token。
- 语法分析(Syntax Analysis):根据语言定义的语法规则,判断 Token 序列是否符合语法,并构建语法树。
- 语义分析(Semantic Analysis):检查语法结构是否具有合法的语义,例如变量是否声明、类型是否匹配、函数调用参数是否正确。
整体流程如下:
flowchart TB
A["源代码 Source Code"]
B["词法分析 Lexer"]
C["Token 序列"]
D["语法分析 Parser"]
E["抽象语法树 AST"]
F["语义分析"]
G["中间表示 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
需要注意,词法分析和语法分析是概念上的职责划分,并不意味着所有编译器都必须将它们实现为完全独立的模块。某些解析器会直接处理字符流,或者将词法分析与语法分析结合起来。
二、词法分析(Lexical Analysis)
2.1 什么是词法分析
词法分析是编译器前端的第一个主要阶段。
它读取源代码中的字符流,按照编程语言定义的词法规则,将连续字符划分为一个个 Token。
例如:
int count = 10 + 20;
词法分析器不会直接理解这段代码的完整计算含义,而是识别其中的词法单元:
| 源代码片段 | Token 类型 | 说明 |
|---|---|---|
int |
KEYWORD | 关键字 |
count |
IDENTIFIER | 标识符 |
= |
ASSIGN | 赋值运算符 |
10 |
INTEGER_LITERAL | 整数字面量 |
+ |
PLUS | 加法运算符 |
20 |
INTEGER_LITERAL | 整数字面量 |
; |
SEMICOLON | 分号 |
词法分析的核心任务是:
- 识别关键字、标识符、字面量和运算符。
- 识别分隔符和标点符号。
- 处理空格、换行、注释等非必要字符。
- 记录 Token 的类型、内容和源代码位置。
- 发现无法匹配词法规则的字符序列。
2.2 Token 的组成
Token 是词法分析输出的基本单位。
一个 Token 通常包含以下信息:
| 属性 | 含义 | 示例 |
|---|---|---|
| Type | Token 类型 | IDENTIFIER |
| Lexeme | 源代码中的原始文本 | count |
| Literal | 解析后的字面量值 | 123 |
| Position | 源代码位置 | 第 1 行,第 5 列 |
其中,Type 和 Lexeme 是最核心的信息。
例如:
int count = 123;
标识符 count 可以表示为:
Type: IDENTIFIER
Lexeme: count
整数 123 可以表示为:
Type: INTEGER_LITERAL
Lexeme: 123
Literal: 123
Literal 并非所有 Token 都需要具备。对于标识符和运算符,通常只需要记录类型与词素;对于数字、字符串等字面量,可能需要额外保存解析后的值。
2.3 常见 Token 类型
不同编程语言的 Token 分类存在差异,但通常包含以下类别:
| Token 类型 | 示例 | 说明 |
|---|---|---|
| 关键字 | if、while、return |
语言保留的关键字 |
| 标识符 | name、calculate |
变量、函数、类型名称等 |
| 整数字面量 | 10、0xFF |
整数常量 |
| 浮点数字面量 | 3.14、1e-5 |
浮点常量 |
| 字符串字面量 | "hello" |
字符串常量 |
| 运算符 | +、==、&& |
运算操作符 |
| 分隔符 | (、)、{、} |
结构边界 |
| 注释 | // comment |
通常不作为普通 Token 输出 |
| 空白字符 | 空格、换行 | 通常被忽略或作为特殊 Token 处理 |
需要注意,注释和空白字符不一定会被直接丢弃。
例如,代码格式化工具、语法高亮工具、宏系统以及需要保留源码结构的编译器,可能会保留注释、空白或换行信息。
2.4 词法规则与正则表达式
词法分析通常通过一组词法规则定义合法的 Token。
许多常见词法规则可以使用正则表达式描述。
例如:
| Token | 示例正则表达式 | 含义 |
|---|---|---|
| 标识符 | [a-zA-Z_][a-zA-Z0-9_]* |
字母或下划线开头 |
| 整数 | [0-9]+ |
一个或多个数字 |
| 空白字符 | [ \t\r\n]+ |
空格、制表符和换行 |
| 加法运算符 | \+ |
加号 |
| 赋值运算符 | = |
等号 |
以标识符规则为例:
[a-zA-Z_][a-zA-Z0-9_]*
它表示:
- 第一个字符必须是英文字母或下划线。
- 后续字符可以是英文字母、数字或下划线。
- 字符数量可以是一个或多个。
因此:
name
_user
count123
都符合这个规则,而:
123name
不符合该标识符规则。
这只是简化示例。实际语言的标识符规则可能支持 Unicode 字符,并且会受到语言规范中字符类别和规范化规则的约束。
2.5 关键字与标识符的区分
关键字和标识符通常具有相似的字符形式,但语义类别不同。
例如:
int if_count = 10;
其中:
int是关键字。if_count是标识符。
词法分析器通常采用以下策略之一:
策略一:独立识别关键字
在词法规则中为关键字定义专门规则。
策略二:先识别标识符,再查关键字表
先按照标识符规则识别完整词素,再查询关键字表,确定它究竟是关键字还是普通标识符。
第二种方式在实际词法分析器中非常常见。
关键点是:关键字通常不能仅仅因为包含某个关键字片段就被识别为关键字。
例如,if_count 不应该被拆分成 if 和 _count。
2.6 最长匹配原则(Maximal Munch)
当多个词法规则都可以匹配当前输入时,词法分析器通常优先选择能够匹配最长字符序列的规则。
这称为最长匹配原则。
例如:
a >= b
对于 > 和 >=,两者都可能从当前位置开始匹配,但最长匹配会优先识别 >=。
再例如:
count123
词法分析器应当优先将整个字符序列识别为一个标识符,而不是拆分成 count 和 123。
最长匹配原则可以避免大量词法歧义,但它并不能解决所有语法问题。不同语言还可能通过关键字优先级、特殊词法规则和上下文规则处理冲突。
三、词法分析器的工作原理
3.1 字符流到 Token 流
词法分析器通常按照从左到右的顺序读取源代码。
它需要维护当前读取位置,并根据词法规则识别下一个 Token。
基本过程如下:
flowchart TB
A["读取源代码字符"]
B["跳过或处理空白与注释"]
C["匹配词法规则"]
D{"是否存在合法匹配"}
E["应用最长匹配规则"]
F["生成 Token"]
G["记录 Token 位置"]
H["继续读取"]
I["报告词法错误"]
J["结束"]
A --> B
B --> C
C --> D
D -->|"是"| E
E --> F
F --> G
G --> H
H --> A
D -->|"否"| 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
实际实现中,词法分析器通常不会为每个 Token 都执行完整的正则表达式匹配。成熟的词法分析器往往会将词法规则转换为有限自动机,以高效识别字符序列。
3.2 有限自动机(Finite Automaton)
有限自动机是一种用于识别特定字符模式的数学模型,也是词法分析的重要理论基础。
有限自动机主要由以下部分组成:
- 状态集合:表示识别过程中的不同状态。
- 输入字符集合:自动机能够读取的字符范围。
- 状态转移函数:定义读取字符后如何切换状态。
- 初始状态:识别过程的起点。
- 接受状态:表示当前字符序列符合某种词法规则。
例如,识别简单十进制整数:
[0-9]+
可以用一个简单的自动机表示:
flowchart LR
A(["开始"])
B["读取数字"]
C(["接受状态"])
A --> B
B -->|"数字"| 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
这个模型表达的是:至少读取一个数字后,就可以接受当前整数词素;如果继续读取数字,则仍然保持在数字状态。
在正式的自动机中,接受状态与读取结束是两个不同概念。自动机可能在某个位置进入接受状态,但仍需要继续读取,以判断是否存在更长的合法匹配。
3.3 DFA 与 NFA
有限自动机主要分为两类:
| 类型 | 全称 | 特点 |
|---|---|---|
| DFA | Deterministic Finite Automaton | 给定状态和输入字符,状态转移唯一 |
| NFA | Nondeterministic Finite Automaton | 一个状态和输入字符可能对应多个转移,也可能存在空转移 |
词法分析器通常可以将正则表达式转换为 NFA,再进一步转换为 DFA。
常见转换过程:
flowchart TB
A["正则表达式"]
B["构造 NFA"]
C["NFA 状态集合"]
D["子集构造法"]
E["DFA"]
F["优化 DFA"]
G["生成词法分析器"]
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
其中:
- NFA 更容易从正则表达式构造。
- DFA 在运行时可以根据当前状态和输入字符直接确定下一状态。
- DFA 通常可以通过状态合并等方法进行优化。
需要注意,DFA 可能因为状态集合过大而产生状态膨胀。实际词法分析器会根据性能和实现复杂度选择不同的自动机结构,并不一定采用完整、最小化的 DFA。
四、语法分析(Syntax Analysis)
4.1 什么是语法分析
语法分析是编译器前端的第二个主要阶段。
它接收词法分析器生成的 Token 序列,根据编程语言定义的语法规则,识别 Token 之间的结构关系。
例如:
int result = a + b * c;
词法分析可以识别出:
INT
IDENTIFIER(result)
ASSIGN
IDENTIFIER(a)
PLUS
IDENTIFIER(b)
MULTIPLY
IDENTIFIER(c)
SEMICOLON
但是,仅仅得到 Token 序列,还无法确定表达式的嵌套关系。
语法分析需要进一步识别:
- 这是一个变量声明语句。
result是声明的变量。- 右侧是一个加法表达式。
- 加法表达式的右操作数是一个乘法表达式。
因此,语法分析的核心工作是建立 Token 之间的层次结构。
4.2 语法规则与上下文无关文法
编程语言通常使用形式文法描述其语法结构。
编译器中常见的是上下文无关文法(Context-Free Grammar,CFG)。
上下文无关文法通常由四个部分组成:
其中:
- V:非终结符集合,表示语法结构。
- \Sigma:终结符集合,通常对应 Token。
- P:产生式规则集合。
- S:开始符号,表示语法分析的入口。
例如,定义简单的算术表达式文法:
Expr -> Expr + Term
Expr -> Term
Term -> Term * Factor
Term -> Factor
Factor -> NUMBER
Factor -> ( Expr )
其中:
Expr表示表达式。Term表示项。Factor表示因子。NUMBER表示数字 Token。+、*、(、)是终结符。
这组规则表达了乘法优先级高于加法的结构关系。
需要注意,以上文法是左递归形式,适合某些自底向上的解析算法,但不能直接用于普通的递归下降解析器。递归下降解析器通常需要先消除左递归,或者采用其他解析策略。
4.3 语法分析树(Parse Tree)
语法分析器根据文法规则,可以构建语法分析树,也称为具体语法树(Concrete Syntax Tree,CST)。
例如:
a + b * c
根据前面的表达式文法,可以形成如下结构:
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
从树结构可以看出:
- 根节点表示整个表达式。
- 加法是表达式的顶层运算。
- 乘法属于加法右侧的子表达式。
b * c被组织为一个完整的乘法结构。
这就是运算符优先级在语法树中的体现。
4.4 具体语法树与抽象语法树
具体语法树(CST)和抽象语法树(AST)是两个容易混淆的概念。
具体语法树(CST)
保留更多语法细节,通常能够反映文法产生式的展开过程。
抽象语法树(AST)
保留对程序语义分析和后续编译有用的核心结构,省略部分纯语法细节。
例如:
a + b * c
其 AST 可以简化为:
+
/ \
a *
/ \
b c
AST 不需要保留所有括号、分号以及中间文法节点。
CST 更关注源代码如何符合文法,AST 更关注程序表达了什么结构。
| 对比维度 | CST | AST |
|---|---|---|
| 全称 | Concrete Syntax Tree | Abstract Syntax Tree |
| 结构 | 更接近完整文法 | 更接近程序结构 |
| 语法细节 | 通常保留较多 | 通常省略冗余细节 |
| 括号和分隔符 | 通常保留 | 通常不作为独立节点保留 |
| 主要用途 | 语法还原、格式化、编辑器工具 | 语义分析、优化、代码生成 |
并不是所有编译器都会同时构建 CST 和 AST。有些编译器直接在解析过程中构建 AST。
五、语法分析的核心问题
5.1 运算符优先级
运算符优先级决定表达式中不同运算符的结合顺序。
例如:
a + b * c
如果乘法优先级高于加法,则表达式等价于:
a + (b * c)
而不是:
(a + b) * c
语法分析器需要通过文法结构、运算符优先级表或解析算法中的优先级规则,正确组织表达式。
5.2 运算符结合性
结合性决定相同优先级的运算符如何组织。
例如:
a - b - c
减法通常是左结合的,因此表达式等价于:
(a - b) - c
而不是:
a - (b - c)
赋值运算符通常是右结合的:
a = b = c
其结构通常等价于:
a = (b = c)
优先级与结合性共同决定表达式的语法结构。
5.3 左递归与右递归
文法中的递归方向会影响解析器的实现方式。
例如:
左递归:
Expr -> Expr + Term
Expr -> Term
右递归:
Expr -> Term + Expr
Expr -> Term
两种形式都可以表达连续加法,但它们对解析器的要求不同。
递归下降解析器从非终结符对应的函数开始调用。如果直接按照左递归文法实现:
parseExpr():
parseExpr()
match("+")
parseTerm()
函数会不断调用自身,导致无限递归。
因此,递归下降解析器通常需要消除左递归。
例如,将左递归表达式:
Expr -> Expr + Term
Expr -> Term
转换为:
Expr -> Term ExprTail
ExprTail -> + Term ExprTail
ExprTail -> ε
其中,ε 表示空串。
这种形式可以让递归下降解析器逐步消费输入 Token。
5.4 文法二义性
如果一个 Token 序列能够根据同一套文法生成多棵不同的语法树,那么该文法就是二义文法。
例如:
Expr -> Expr + Expr
Expr -> Expr * Expr
Expr -> NUMBER
对于:
a + b * c
可能产生两种不同的解释:
(a + b) * c
或者:
a + (b * c)
如果文法没有明确规定优先级和结合性,就无法唯一确定表达式结构。
解决方式通常包括:
- 重新设计文法,使优先级体现在产生式层次中。
- 为解析器配置运算符优先级和结合性。
- 使用适合处理二义表达式的解析策略。