词法分析
词法分析
词法分析(Lexical Analysis)是编译器的第一步,它把源代码这串"字符流"切成一颗颗有意义的"词",再贴上类别标签交给语法分析。这个过程既要过滤掉空格、注释、换行,又要识别出关键字、标识符、数字、运算符等词法单元。
通俗理解:词法分析就像英语课上把一句话切分成单词。字符流
int a=3+b;在人看来是"一句话",但机器只看到 12 个字符,词法分析器要把它切成inta=3+b;七个词,并告诉后续阶段每个词的身份。
词法单元、词素、模式
这三个概念常被混用,其实分得很清楚:
- 词法单元(Token):分类后的抽象结果,通常是一个二元组
<类别, 属性值>,例如<ID, 指向符号表>、<NUM, 3>。它是词法分析交给语法分析的最终产物。 - 词素(Lexeme):源代码中真实出现的字符序列,是"这一次匹配上"的具体字符串。
- 模式(Pattern):一条描述"什么样的字符序列算作某类词法单元"的规则,通常用正则表达式表达。
以 int a = 3 + b; 为例:
| 词素 | 匹配的模式 | 词法单元 |
|---|---|---|
int | 保留关键字 int | <KW_INT> |
a | 字母开头的标识符 | <ID, "a"> |
= | 单个等号 | <ASSIGN> |
3 | 一串数字 | <NUM, 3> |
+ | 加号 | <PLUS> |
b | 字母开头的标识符 | <ID, "b"> |
; | 分号 | <SEMI> |
同一个模式可以匹配无数个词素,但每个词素只会生成一个词法单元。
正则表达式
词法层面的语言"规则"用正则表达式来描述就够了。它有四种基本运算:
- 字母(Symbol):单个字符本身,如
a、0、+。 - 连接(Concatenation):两个正则式相接,如
ab表示先a后b。 - 并(Union / Alternation):
a | b表示a或b。 - 闭包(Kleene Closure):
a*表示a出现 0 次或多次;a+是 1 次或多次的简写。
用它写常见词类:
letter -> [A-Za-z_]
digit -> [0-9]
id -> letter (letter | digit)*
int -> digit+
if -> i f
while -> w h i l e
关键字本质也是一个具体的字符串,可以看作特殊的标识符。
有限自动机:NFA 与 DFA
正则表达式是"规则的写法",而识别一个字符串是否匹配规则,用有限自动机(Finite Automaton)。它由状态、转移、起始态和接受态组成。
- NFA(Nondeterministic Finite Automaton):同一个输入可以有多个转移方向,还允许 ε(空串)转移。像下棋时同时试所有走法。
- DFA(Deterministic Finite Automaton):任一状态遇到任一输入,最多一条确定的转移。执行时不用回溯,速度快。
以标识符 letter (letter | digit)* 为例,DFA 结构可以描述成:
起始态 s0 --letter--> s1 (接受态)
s1 --letter--> s1
s1 --digit--> s1
s0 是起点,读到一个字母就走到 s1;s1 是接受态,只要后面继续读到字母或数字就自己跳回自己;一旦读到别的字符(如空格、=),就停下来把 s0 到当前位置的字符判为一个标识符词素。
从正则式到最小 DFA
工程上不会手画 DFA,而是让工具走一条流水线:
- 正则式 → NFA(Thompson 构造):对基本符号、连接、并、闭包各定义一小块 NFA 片段,再按语法组合。例如
a|b构造成 "起始态 -ε-> a 分支,-ε-> b 分支,两分支汇合到终态"。 - NFA → DFA(子集构造 / Subset Construction):把 NFA 中"可能同时处于的状态集合"看作 DFA 的一个状态,逐步展开。ε 闭包用来把所有能靠 ε 到达的状态合并。
- DFA 最小化:合并等价状态(对任何输入行为都一致的状态),得到状态数最少的 DFA。
以 (a|b)*abb 为例,Thompson 构造给出 11 个状态的 NFA,子集构造得到 5 个 DFA 状态,最小化后仍是 5 个,说明它已经是最小的。识别时只需按字符沿转移走,命中接受态即成功。
手写一个词法分析器
下面用 Python 写一段识别整数和标识符的极简词法分析器,重点展示最长匹配原则——即使 int1 前三个字符像关键字 int,也要一直读到 int1 整个词素结束再判断。
KEYWORDS = {"int", "if", "while", "return"}
def tokenize(src: str):
i, n = 0, len(src)
tokens = []
while i < n:
c = src[i]
if c.isspace():
i += 1
continue
# 整数:尽量多地吃数字
if c.isdigit():
j = i
while j < n and src[j].isdigit():
j += 1
tokens.append(("NUM", int(src[i:j])))
i = j
continue
# 标识符或关键字:字母开头,后续字母数字下划线
if c.isalpha() or c == "_":
j = i
while j < n and (src[j].isalnum() or src[j] == "_"):
j += 1
lexeme = src[i:j]
kind = "KW" if lexeme in KEYWORDS else "ID"
tokens.append((kind, lexeme))
i = j
continue
# 单字符符号
tokens.append(("SYM", c))
i += 1
return tokens
print(tokenize("int a = 30 + int1;"))
# [('KW','int'), ('ID','a'), ('SYM','='),
# ('NUM',30), ('SYM','+'), ('ID','int1'), ('SYM',';')]
注意 int1 没有被切成 int 加 1——while 循环会一 直吃到不再是字母数字为止,之后再拿完整词素去和关键字表比对。这就是最长匹配。
lex / flex 工具
工业界一般不手写状态机,而是让 lex/flex 从正则规则里生成 C 代码。一个 .l 文件通常长这样:
%{
#include <stdio.h>
%}
digit [0-9]
letter [A-Za-z_]
id {letter}({letter}|{digit})*
%%
"int" { return KW_INT; }
"if" { return KW_IF; }
{id} { yylval.s = strdup(yytext); return ID; }
{digit}+ { yylval.n = atoi(yytext); return NUM; }
[ \t\n]+ { /* 跳过空白 */ }
. { return yytext[0]; }
%%
三段结构:定义段(宏和头文件)、规则段("正则 → 动作"对)、辅助函数段。flex 会把这份文件编译成一个高效的 DFA。规则从上到下匹配,相同长度时先出现的优先,所以要把关键字放在标识符规则之前。
注意事项
关键字与标识符。语言的关键字(if、while、int)在词法层面完全长得像标识符。常见做法是先按标识符规则匹配整个词素,然后查一张关键字表:命中就返回对应关键字 token,否则返回 ID。这样只写一条正则规则就能覆盖两类词。
最长匹配和优先级。当多条规则可能匹配同一段前缀时,取匹配最长的那一条;长度相同时按规则表中的先后顺序取胜。这两条规则共同保证 >= 不会被切成 > 和 =,inttype 不会被误认为关键字 int。
错误恢复。遇到不认识的字符不能整个编译中止,通常做法是"报告位置、跳过一个字符、继续扫描",也可以跳到下一个空白或分号做同步。良好的错误恢复能让编译器一次报多个错,而不是每次只报第一个。
前瞻(Lookahead)。有些词法规则光看当前字符判不出来,比如 Fortran 里 DO 5 I=1,25 是循环、DO5I=1.25 是赋值——差别在于逗号还是句点。这类情况需要向前多看几字符,flex 提供 r1/r2 语法表达"匹配 r1 但前提是后面跟着 r2",实现有限前瞻。
词法分析虽然是编译器最"表层"的一步,却直接决定了后续所有阶段拿到什么样的输入。把它做扎实,语法分析才能干净利落地展开。