跳到主要内容

词法分析

词法分析​

词法分析(Lexical Analysis)是编译器的第一步,它把源代码这串"字符流"切成一颗颗有意义的"词",再贴上类别标签交给语法分析。这个过程既要过滤掉空格、注释、换行,又要识别出关键字、标识符、数字、运算符等词法单元。

通俗理解:词法分析就像英语课上把一句话切分成单词。字符流 int a=3+b; 在人看来是"一句话",但机器只看到 12 个字符,词法分析器要把它切成 int a = 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,而是让工具走一条流水线:

  1. 正则式 → NFA(Thompson 构造):对基本符号、连接、并、闭包各定义一小块 NFA 片段,再按语法组合。例如 a|b 构造成 "起始态 -ε-> a 分支,-ε-> b 分支,两分支汇合到终态"。
  2. NFA → DFA(子集构造 / Subset Construction):把 NFA 中"可能同时处于的状态集合"看作 DFA 的一个状态,逐步展开。ε 闭包用来把所有能靠 ε 到达的状态合并。
  3. 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",实现有限前瞻。

词法分析虽然是编译器最"表层"的一步,却直接决定了后续所有阶段拿到什么样的输入。把它做扎实,语法分析才能干净利落地展开。