词法分析

1. 词法分析程序

扫描源程序文件中的字符流，识别出构成语言的单词/记号（token），验证单词的合法性，最后讲识别出的 token 发送给语法分析程序

1. 提升编译程序的模块化和可维护性：使每个模块专注于自己的任务，便于理解、测试和调试
2. 提高编译程序的效率：采用高效专用的词法分析器可以快速扫描和识别单词，从而整体上加速编译过程
3. 增强编译程序的可移植性：独立的词法分析模块可以更容易地适应不同平台的字符编码和输入格式

Token 用一个二元组 (Type, Lexeme) 表示

Type	Lexeme	定义
关键字/保留字	本身	是由语言设计者预先定义的、在语言中具有特殊意义的词汇，如 if、while、begin、end 等
标识符	指向标识符在符号表的入口的指针	用于表示变量、函数等用户自定义的名称，通常由语言设计者规定了构造标准，如只能由字母、数字和下划线构成
常数	具体数值	程序中的固定值，如整数、浮点数、字符、字符串等
运算符	本身	用于表达运算、赋值、逻辑判断等操作，如 +、-、*、/
界符	本身	各种分隔符和括号，如分号、逗号、括号、花括号等
空白符	忽略	空格、制表符、换行符

对于程序段 if i=5 then x=y 扫描后得到

单词	类型	属性值
if	关键字	‘if’
i	标识符	指向 i 在符号表入口的指针
=	运算符	‘=’
5	常量	‘5’
then	关键字	‘then’
x	标识符	指向 x 在符号表入口的指针
=	运算符	‘=’
y	标识符	指向 y 在符号表入口的指针

2. PL/0

2.1 单词种别

1. 关键字类
   • beginsym / endsym：表示 begin / end，用于定义程序或过程的块结构
   • ifsym / thensym：表示 if / then，用于条件语句
   • whilesym / dosym：表示 while / do，用于循环结构
   • callsym：表示 call，调用过程
   • constsym：表示 const，声明常量
   • varsym：表示 var，声明变量
   • procsym：表示 procedure，声明过程
   • oddsym：表示 odd，在布尔表达式中用来判断是否为奇数
   • writesym / readsym：表示 write / read，执行输入输出操作
2. 运算符和关系运算符
   • plus / minus / times / slash / percent：对应 + - * / %
   • eql / neq / lss / leq / gtr / geq：对应 = <> < <= > >=
   • becomes：对应 :=，表示赋值运算
3. 界符
   • lparen / rparen：左括号 ( 和右括号 )
   • comma：逗号 ,
   • semicolon：分号 ;
   • period：点号 .
4. 标识符与常量
   • identifier：标识符，用于用户自定义名称
   • number：数字常量
5. 特殊或占位符
   • nul：无效符号

2.2 全局变量

一般来说，词法分析程序具有以下数据机构，用于记录当前 token：

• enum symbol sym：传递单词种别
• char id[]：传递标识符的名称
• int num：传递无符号整数的值

识别出标识符 position 后，则令 sym=identifier，id="position"
识别出无符号整数 60 后，则令 sym=number，num=60

2.3 主要流程

1. 获取源代码字符流中的下一个字符
2. 识别并过滤掉空白：跳过空格、制表符、换行符等非实际语义的空白字符
3. 识别关键字或标识符：如果当前字符是字母，则将它以及后续的字母和数字存入缓冲区，直到遇到字母/数字字符为止，构成一个完整的字符串
4. 识别数字：如果当前字符是数字，则持续读入连续的数字字符，直到遇到非数字字符为止，将得到的字符串转移为整数
5. 识别运算符或界符：如果是多字符组合，需要读取下一个字符以判断是否匹配，否则只识别单字符符号
6. 如果当前字符不符合上述五个大类中的任何一种，则认为它是未知或非法的单词，进行错误处理或报告
7. 根据识别的单词，设置全局变量 sym、id 和 num

3. 单词的形式化描述工具

3.1 正规文法

正规文法：要求文法$G = (V_N,V_T,S,P)$ 中的规则满足右线性形式：$A \to a$ 或$A \to aB$，其中 A 和 B 是非终结符，a是终结符

3.2 正规式 / 正则表达式

正规式（Regular Expression）是描述正规集的工具，用于构造复杂的字符串模式

• 连接：$ab$ 表示字符 a 后紧跟 b
• 并集：$a|b$ 表示字符 a 或 b
• 闭包：$a^*$ 表示零个或多个字符 a
• 正闭包：$a^+$ 表示一个或多个字符 a

代数规律

• 并集的交换律：$r | s = s | r$
• 并集的可结合律：$r | (s | t) = (r | s) | t$
• 并集的抽取律：$r | r = r$
• 并集的吸收率：$R | S = S$ 当且仅当$R \subseteq S$
• 连接的可结合律：$(rs)t = r(st)$
• 连接的恒等律：$\varepsilon r = r, r\varepsilon = r$
• 并集和连接的分配律：$r(s | t) = rs | rt, (s | t)r = sr | tr$
• 闭包的幂等律：$(r^*)^* = r^*, r^*r^* = r^*$
• 闭包的递归律：$r^* = \varepsilon | rr^*$

C 语言标识符：(_|letter)(_|letter|digit)
十进制数字：0|([1-9][0-9]*)
2的倍数的二进制表示：(0|1)*0

等价正规式：

• $b(ab)* = (ba)^*b$
• $(a|b)* = (a^*b^*)^*$

3.3 正规文法和正规式的转移

3.3.1 将正规式转移成正规文法

1. 选择一个非终结符 S 生成正规式产生式：$S \to r$
2. 对连接正规式产生式：$A \to xy$ 重写成$A \to xB, B \to y$
3. 对并集正规式产生式：$A \to x | y$ 重写成$A \to x, A \to y$
4. 对闭包正规式产生式：$A \to x^*y$ 重写成$A \to xB, A \to y, B \to xB, B \to y$（注意这里的 y 可以是$\varepsilon$）
5. 不断利用 2-4 的规则做变换，直到每个产生式都符合正规文法的形式

3.3.2 将正规文法转移为正规式

1. $A \to xB, B \to y$ 变为$A = xy$
2. $A \to xA|y$ 变为$A = x^*y$
3. $A \to x, A \to y$ 变为$A = x|y$

4. 有穷自动机

4.1 有穷自动机

有穷自动机（Finite Automaton, FA）是一种数学模型程序，用于描述和识别有限集合的字符串，从而判断是否接受或拒绝字符串，通常定义为一个五元组$M = (Q, \Sigma, f, S, Z)$

• K：有穷状态集
• $\Sigma$：有穷符号集 / 输入字母表
• $f: K \times \Sigma \to K / 2^K$：状态转移函数
• S：初始状态
• Z：终止状态集 / 接受状态集

在有限自动机中，“终止/接受状态”只是一个状态的标签，表示如果输入在这个状态结束，则字符串被认为是可接受的，但并不意味着无法继续转移

状态图表示

• 状态：用圆圈表示
• 初始状态：由一个箭头指向
• 接受状态：用双圆圈标记
• 转移：若存在$f(k_i, a) = k_j$ 则有从状态节点$k_i$ 到 状态节点$k_j$ 标记为$a$ 的弧

矩阵表示：行表示状态，列表示输入符号，k 行 a 列为 f(k,a) 的值，在终态行的右端标以 1，否则标以 0

FA 表示的语言就是 FA 接受的全部字符串的集合，记为 L(M)：对于符号串$t = t_1t_2 \ldots t_n$，若存在$f(S, t) = P,f(X, t_it_j) = f(f(X, t_i), t_j)$，其中 S 是初始状态，P 是终止状态，则称 t 可被 FA 所接受

对于上述自动机有$f(S, baab) = f(f(S, b), aab) = f(V, aab) = f(f(V, a), ab) = f(U, ab) = f(f(U, a), b) = f(Q, b) = Q$，且 Q 是终态，因此符号串 baab 可以被 DFA M 接受

4.2 DFA 和 NFA

区别	确定性有限自动机（Deterministic）	非确定性有穷自动机（Nondeterministic）
多态转移	每个状态对于每个符号只有一个状态转移	每个状态对于每个符号可以有多个状态转移
空串转移	不存在	可以有
接受情况	只有唯一的路径，不到达终止状态则表示不可接受	可能有多条路径，只要有一条路径到达终止状态则可以被接受

5. 转换流程

5.1 RE -> NFA：Thompson 构造算法

Thompson 构造算法

• 对于正规式$\varepsilon$，构造$x \xrightarrow{\varepsilon} y$
• 对于正规式$a$，构造$x \xrightarrow{a} y$
• 对于正规式$r=s|t$，构造$x \xrightarrow{\varepsilon} N(s) \xrightarrow{\varepsilon} y$ 和$x \xrightarrow{\varepsilon} N(t) \xrightarrow{\varepsilon} y$
• 对于正规式$r=st$，则将$N(s)$ 的终态和$N(t)$ 的初态相结合
• 对于正规式$r=s^*$，构造$x \xrightarrow{\varepsilon} N(s) \xrightarrow{\varepsilon} y$ 和$x \xrightarrow{\varepsilon} y$ 以及$N(s) \xrightarrow{\varepsilon} N(s)$（从终态指向初态）

对于正规式$r=(a|b)^*abb$

1. 令$r_1=a$，则可以构造$2 \xrightarrow{a} 3$
2. 令$r_2=b$，则可以构造$4 \xrightarrow{b} 5$

3. 令$r_3=a|b$，则可以构造$1 \xrightarrow{\varepsilon} 2 \xrightarrow{a} 3 \xrightarrow{\varepsilon} 6$ 和$1 \xrightarrow{\varepsilon} 4 \xrightarrow{b} 5 \xrightarrow{\varepsilon} 6$

4. 令$r_4=r_3^*$，则可以构造$0 \xrightarrow{\varepsilon} 1$、$6 \xrightarrow{\varepsilon} 7$、$0 \xrightarrow{\varepsilon} 7$ 以及$6 \xrightarrow{\varepsilon} 1$

5. 令$r_5=a, r_6=b, r_7=b, r_8=r_5r_6, r_9=r_8r_7$，则可以构造$7 \xrightarrow{a} 8 \xrightarrow{a} 9 \xrightarrow{b} 10$

6. 令$r_{10} = r_4r_9$，则可以构造出最终的有穷自动机

5.2 NFA -> DFA：子集构造算法

ε-closure(I) 是 I 中任何状态 S 经过任意条 ε 弧能到达的状态集合

move(I, a) 是 I 中任何状态经过一条 a 弧能到达的状态集合

子集构造算法

1. 计算 NFA 初始状态的 ε-closure(S) 作为 DFA 的初始状态集合
2. 如果 DFA 中存在没有被标记的状态 T，对每个输入符号 a，找到 move(T, a)
3. 计算 U = ε-closure(move(T, a))
4. 如果 U 没有出现在 DFA 中，则将 U 作为未标记的子集加入 DFA 中
5. 重复 2-4，直到没有新的状态集合被发现为止

1. NFA 的初始状态为 0，则$T_0 = \varepsilon\text{-closure}(0) = \{0, 1, 2, 4, 7\}$
2. 标记$T_0$：
   1. $move(T_0, a) = \{3, 8\}$，则$T_1 = \varepsilon\text{-closure}(\{3, 8\}) = \{1, 2, 3, 4, 6, 7, 8\}$
   2. $move(T_0, b) = \{5\}$，则$T_2 = \varepsilon\text{-closure}(5) = \{1, 2, 4, 5, 6, 7\}$
3. 标记$T_1$：
   1. $move(T_1, a) = \{3, 8\}$，则$\varepsilon\text{-closure}(\{3, 8\}) = \{1, 2, 3, 4, 6, 7, 8\} = T_1$，已经存在
   2. $move(T_1, b) = \{5, 9\}$，则$T_3 = \varepsilon\text{-closure}(5) = \{1, 2, 4, 5, 6, 7, 9\}$
4. 标记$T_2$：
   1. $move(T_2, a) = \{3, 8\}$，则$\varepsilon\text{-closure}(\{3, 8\}) = \{1, 2, 3, 4, 6, 7, 8\} = T_1$，已经存在
   2. $move(T_2, b) = \{5\}$，则$\varepsilon\text{-closure}(5) = \{1, 2, 4, 5, 6, 7, 9\} = T_2$，已经存在
5. 标记$T_3$：
   1. $move(T_3, a) = \{3, 8\}$，则$\varepsilon\text{-closure}(\{3, 8\}) = \{1, 2, 3, 4, 6, 7, 8\} = T_1$，已经存在
   2. $move(T_3, b) = \{5, 10\}$，则$T_4 = \varepsilon\text{-closure}(\{5, 10\}) = \{1, 2, 4, 5, 6, 7, 10\} = T_4$
6. 标记$T_4$：
   1. $move(T_4, a) = \{3, 8\}$，则$\varepsilon\text{-closure}(\{3, 8\}) = \{1, 2, 3, 4, 6, 7, 8\} = T_1$，已经存在
   2. $move(T_4, b) = \{5\}$，则$\varepsilon\text{-closure}(5) = \{1, 2, 4, 5, 6, 7, 9\} = T_2$，已经存在

算法终止，得到 5 个子集：
$T_0 = \{0, 1, 2, 4, 7\} = 0$
$T_1 = \{1, 2, 3, 4, 6, 7, 8\} = 1$
$T_2 = \{1, 2, 4, 5, 6, 7\} = 2$
$T_3 = \{1, 2, 4, 5, 6, 7, 9\} = 3$
$T_4 = \{1, 2, 4, 5, 6, 7, 10\} = 4$

那么由 NFA 构造的 DFA 如下

1. 状态集$K = \{0, 1, 2, 3, 4\}$
2. 符号集$\Sigma = \{a, b\}$
3. 起始状态$S = 0$
4. 终止状态集$Z = \{4\}$
5. 状态转移函数
   $f(0, a) = 1$
   $f(0, b) = 2$
   $f(1, a) = 1$
   $f(1, b) = 3$
   $f(2, a) = 1$
   $f(2, b) = 2$
   $f(3, a) = 1$
   $f(3, b) = 4$
   $f(4, a) = 1$
   $f(4, b) = 2$

对于不含$\epsilon$ 的 NFA，可以利用状态转移矩阵变成 DFA

1. 从初始态开始，得到每个输入符号下到达的状态
2. 如果产生了新状态，就增加一行，继续得到该状态下每个输入符号能到达的状态
3. 以此类推，直到没有新的状态产生

	0	1
A	A	BC
BC	AC	BC
AC	AC	BC

5.3 DFA 化简：分割子集法

无用状态

• 不可到达态：从初始状态出发，经过任何输入符号串都无法到达的状态
• 不可接受态：从当前状态出发，经过任何输入符号串都无法到达终态

从 a 到 b，消除了不可到达态 s4；从 b 到 c，消除了不可到达态 s6 和 s8

等价状态

• 一致性条件：状态 s 和 t 必须同时为可接受状态或不可接受状态
• 蔓延性条件：对于所有输入符号，状态 s 和 t 必须转移到等价状态

分割子集法

1. 将状态集合分为两个子集，一个由接受态组成，一个由不可接受态组成：{1,2,3,4} 和 {5,6,7}
2. 对每个子集，若其内部状态对于某个输入符号的转移结果落在不同子集，则将原子集分割
   1. {1,2,3,4} 中的 1 和 2 经过 a 转移到 6 和 7，3 和 4 经过 a 转移到 1 和 4，因此分割成 {1,2} 和 {3,4}
   2. {3,4} 中的 3 经过 a 转移到 1，4 经过 a 转移到 4，因此分割成 {3} 和 {4}
   3. {5,6,7} 中的 5 经过 b 转移到 3，6 和 7 经过 b 转移到 1 和 2，因此分割成 {5} 和 {6,7}
3. 可以发现此时无法分割，则用剩下子集组成新的状态：令 1 代表 {1,2}，令 6 代表 {6,7}

可以利用转移矩阵逐步区分

5.4 DFA -> Table-Drive Code

int state_index(char c) {
   if (c == 'S') return 0;
   if (c == 'T') return 1;
   if (c == 'U') return 2;
}

int symbol_index(char c) {
   if (c == '0') return 0;
   if (c == '1') return 1;
   return -1;
}

start_state = 'S';
end_state = ['U'];
char Table[3][2] = {
   {'T', 'U'},
   {'T', 'U'},
   {'T', 'x'}
};

bool DFA(const char *str) {
   char state = start_state;
   int str_len = strlen(str);
   for (int i = 0; i < str_len; i++) {
      int symIdx = symbol_index(str[i]);
      int stateIdx = state_index(state);
      if (symIdx == -1) {
         printf("非法字符: %c\n", str[i]);
         return false;
      }
      current_state = Table[stateIdx][symIdx];
      if (state == 'x')
         return false;
   }

   for (int i = 0; i < 2; i++)
      if (state == end_state[i])
         return true;
   return false;
}

6. 有穷自动机的其他转换

6.1 有穷自动机 -> 正规式

1. 首先加上两个节点 x 和 y，其中 x 用 ε 弧连接到所有起始节点，所有终态节点用 ε 弧连接到 y，因此新的自动机只有唯一的起始节点 x 和唯一的终态节点 y
2. 利用如下消去规则
   1. 如果有$1 \xrightarrow{a} 2 \xrightarrow{b} 3$，则变成$1 \xrightarrow{ab} 3$
   2. 如果有$1 \xrightarrow{a} 2$ 和 $ 1 \xrightarrow{b} 2$，则变成$1 \xrightarrow{a|b} 2$
   3. 如果有$1 \xrightarrow{a} 2 \xrightarrow{c} 3$ 和$2 \xrightarrow{b} 2$，则变成$1 \xrightarrow{ab^*c} 3$
3. 化简到最后只有$x \xrightarrow{\ldots} y$ 的弧，上面的标记就是等价的正规式

对于如下有穷自动机

1. 对于$0 \xrightarrow{a} 3 \xrightarrow{a} 4$ 变为$0 \xrightarrow{aa} 4$
2. 对于$0 \xrightarrow{b} 1 \xrightarrow{b} 2$ 变为$0 \xrightarrow{bb} 2$
3. 对于$0 \xrightarrow{a} 0$ 和$0 \xrightarrow{b} 0$，变为$0 \xrightarrow{a|b} 0$
4. 对于$4 \xrightarrow{a} 4$ 和$4 \xrightarrow{b} 4$，变为$4 \xrightarrow{a|b} 4$
5. 对于$2 \xrightarrow{a} 2$ 和$2 \xrightarrow{b} 2$，变为$2 \xrightarrow{a|b} 2$

6. 对于$0 \xrightarrow{aa} 4 \xrightarrow{\varepsilon} y$ 和$4 \xrightarrow{a|b} 4$，变为$0 \xrightarrow{aa(a|b)^*\varepsilon} y$
7. 对于$0 \xrightarrow{bb} 2 \xrightarrow{\varepsilon} y$ 和$2 \xrightarrow{a|b} 2$，变为$0 \xrightarrow{bb(a|b)^*\varepsilon} y$
8. 对于$0 \xrightarrow{aa(a|b)^*\varepsilon} y$ 和$0 \xrightarrow{bb(a|b)^*\varepsilon} y$，变为$0 \xrightarrow{(aa(a|b)^*)|(bb(a|b)^*)} y$，化简得到$0 \xrightarrow{(aa|bb)(a|b)^*} y$

9. 对于$x \xrightarrow{\varepsilon} 0 \xrightarrow{(aa|bb)(a|b)^*} y$ 和$0 \xrightarrow{a|b} 0$，变为$x \xrightarrow{\varepsilon(a|b)^*(aa|bb)(a|b)^*} y$
10. 因此最后得到正规式为：$x \xrightarrow{(a|b)^*(aa|bb)(a|b)^*} y$

6.2 正规文法 -> 有穷自动机

• 增加一个新状态 Z 作为 M 的终止状态
• 对于 G 中每个形如$A \to tB$ 的产生式，构造$A \xrightarrow{t} B$
• 对于 G 中每个形如$A \to t$ 的产生式，构造$A \xrightarrow{t} Z$

6.3 有穷自动机 -> 正规文法

• 对于 M 中每个形如$A \xrightarrow{t} B$，构造产生式$A \to tB$
• 对于 M 中每个可接受状态 Z，构造产生式$Z \to \varepsilon$

7. lex

7.1 概述

自动构造工具：是一类利用形式化描述如正规表达式自动生成程序的工具，也就是说，用户只需要用正规表达式描述单词模式，自动构造工具就可以自动生成用于词法分析的代码

lex：读入用户编写的一个 lex.l 的描述文件，生成一个名为 lex.yy.c 的 C 源程序文件，其中包含函数 yylex()，用于读取源程序的字符流，并返回下一个 Token

7.2 正则表达式

正规表达式	匹配表达式	例子	注意
x	匹配字面量字符x	a匹配a，b匹配b	区分大小写
.	匹配除换行符之外的任意单个字符	. 可匹配 x、3、# 等	换行符是\n
[字符列表]	匹配列表中任一字符	[xyz] 匹配 x 或 y 或 z	可用 - 表示范围，如 [1-4] 匹配 1,2,3,4
[^字符列表]	匹配不在列表中的任一字符	[^A-Z] 匹配除了大写字母之外的字符	[^] 匹配任何字符（除换行符外）
“字符串”	匹配完全相同的字符串	“if” 匹配单词 if	字符串内的 " 和 \ 需转义
\转义字符	正规表达式中的特殊字符需要在前面加上斜杠	\* 表示 *，\ 表示 \，\"表示 "
\数字	匹配八进制数对应的ASCII字符	\101 匹配字符 A
\x数字	匹配十六进制数对应的ASCII字符	\x41 匹配字符 A
r*	匹配 r 的闭包	a* 可匹配空串、a、aa、aaa 等	包括空串
r+	匹配 r 的正闭包	a+ 可匹配 a、aa、aaa 等	不包括空串
r?	匹配 r 零次或一次	a? 匹配空串或 a
r{n}	匹配 r 恰好出现 n 次	a{3} 匹配 aaa	n 必须非负
r{m,n}	匹配 r 至少 m 次，至多 n 次	a{2,4} 匹配 aa、aaa 或 aaaa	m 必须小于等于 n
r{m,}	匹配 r 至少 m 次	a{2,} 匹配 aa、aaa、aaaa 等
®	改变优先级，优先匹配 r	捕获子串 (ab)+ 匹配 ab、abab 等
rs	匹配的连接	ab 匹配字符串 ab	顺序不能颠倒
r|s	匹配 r 或 s	a|b 匹配 a 或 b
r/s	匹配后面是 s 的 r	a/b 匹配 a	不匹配 s，回退扫描
^r	匹配以 r 开头的行	^abc 仅匹配行首的 abc
r$	匹配以 r 结尾的行	xyz$ 匹配以 xyz 结尾的行
<c>r	匹配在特定条件下的 r	<COMMENT>r 表示在 COMMENT 状态下才能匹配 r	用于区分不同上下文状态，INITIAL 是 Lex 默认的起始条件
{宏}	匹配宏定义所代表的正规表达式		宏需要事先定义

常用的正则表达式

• 单个数字：#D [0-9]
• 单个字母：L [a-zA-Z]
• 标识符：{L}({L}|{D})*
• 数值字面量：[+-]?(0|[1-9][0-9]*) -> 可选的正负号 + 0 或非 0 开头的数字
• 字符串字面量：\"(\\.|[^\\"\n])*\" -> 双引号 + 转义字符或非反斜杠/非双引号/非换行符的闭包 + 双引号
• 空白间隔：[ \t]+ -> 空格和制表符的闭包
• C 注释：\/\/[^\n]*\n -> 两个斜杠 + 非换行符的闭包 + 换行符

7.3 全局变量

• yytext：指向当前 token 的指针
• yyleng：当前 token 的长度
• yylineno：当前 token 所在的行号
• yyin：输入文件指针
• yyout：输出文件指针

7.4 描述文件

lex 描述文件：描述各种单词的模式，并为每种模式指定对应的 C 语言动作代码，每个部分之间用 %% 分割

1. 定义部分：设定词法分析器的全局环境和基础配置

   • C 部分：包含在 %{ … %} 中
     • 头文件：如 #include <stdio.h>
     • 全局变量声明：如 int num_lines=0;
     • C 中的宏定义：如 #define ADDCOL() Column += yyleng;
   • lex 部分
     • lex 中的宏定义：如 D [0-9]
     • 选项：如 %option noyywrap 表示不自动调用 yywrap()
     • 起始条件声明：如 %x COMMENT

2. 规则部分：定义了词法分析器如何从输入中识别各类单词，同时应该作出什么反应，格式通常为 正则表达式 {动作代码}

   • 正则表达式：如 "if" 或 [ \t\n]
   • 动作代码：如 { return IF; } 或 { return ~YYEOF; }

3. 辅助代码部分/用户子程序部分：实现了词法分析器的运行入口及相关功能，可以配合后续语法分析器使用

   • 主函数：用于启动词法分析，如int main() { yylex(); return 0; }
   • 自定义 lex 函数：如 yywrap() 或 yyerror()
   • 自定义辅助函数：通常用于打印调试信息

~YYEOF 是一个特殊的返回值，用来表明匹配到了无效字符，从而让词法分析器忽略当前匹配，继续扫描下一个 token

lex 的正规表达式匹配原则

1. 最长匹配：如果有多个正规表达式都能匹配当前输入的一部分，则 Lex 会选择匹配字符数最多的那个规则
2. 顺序匹配：如果存在两个或多个规则匹配同样长度的字符串，则 Lex 会选择在描述文件中先出现的规则

%{
#include <stdio.h>
int num_lines = 0;
int num_chars = 0;
int num_numbers = 0;
#define DIGIT [0-9]
%option noyywrap
%x COMMENT
%}
%%
\n                {++num_lines; ++num_chars;}
{DIGIT}           {++num_numbers; ++num_chars;}
.                 {++num_chars;}
"\\\*"            {BEGIN(COMMENT);}
<COMMENT>"\*\\"   {BEGIN(INITIAL);}
%%
void Print(void) {
   printf("Lines: %d, Characters: %d, Numbers: %d\n", num_lines, num_chars, num_numbers);
}
int main(void) {
   yylex();
   Print();
   return 0;
}
void yyerror(const char *s) {
   fprintf(stderr, "Error: %s\n", s);
}

DIGIT 规则必须在 . 规则之上，否则将永远不会匹配到 DIGIT，num_numbers 永远不会更新

7.5 使用案例

1. 编写 lex 描述文件命名为 mylexer.l
2. $ lex mylexer.l：生成 lex C 源程序文件 lex.yy.c
3. $ gcc lex.yy.c -ll -o mylexer：链接 lex 库，生成可执行文件 mylexer
4. ./mylexer < input.txt：传递输入文件，执行可执行文件

lex 描述文件

%{
#include <stdio.h>
#include <stdlib.h>
int num_lines = 1;
int num_chars = 0;
int num_numbers = 0;
%}
%option noyywrap
%%
\n             { ++num_lines; ++num_chars; }
[ \t]+         { num_chars += yyleng; }
[0-9]+         { ++num_numbers; printf("Number: %s\n", yytext); num_chars += yyleng; }
[a-zA-Z]+      { printf("Word: %s\n", yytext); num_chars += yyleng; }
.              { ++num_chars; }
%%
int main(void) {
    yylex();
    printf("\nLines: %d, Characters: %d, Numbers: %d\n", num_lines, num_chars, num_numbers);
    return 0;
}

输入文本

Hello world！
Here is dasi aged 21
1 + 2 = 3

输出结果

Word: Hello
Word: world
Word: Here
Word: is
Word: dasi
Word: aged
Number: 21
Number: 1
Number: 2
Number: 3

Lines: 3, Characters: 45, Numbers: 4