学习地址：

• 国防科技大学编译原理 MOOC 课程

词法分析

词法分析器

任务

词法分析的任务：

从左到右逐个字符地对源程序进行扫描，产生一个单词符号序列

执行词法分析任务的叫做词法分析器（Lexical Analyzer）

功能

词法分析器的功能：

输入源程序、输出单词符号

单词符号种类：

• 基本字，或关键字：

• 标识符：用来表示各种用户定义的名字

• 常数

• 运算符：+、-、*、/

• 分界符：,、;…

词法分析器的输出：

• 输出的单词符号的表示形式 → 单词种别、单词自身的值

与语法分析

体现了 分解 和 权衡 两种计算思维。

结构

1. 预处理子程序：剔除无用的空白、跳格等编辑性字符。放入扫描缓冲区。

2. 扫描器通过 起点指示器 和 搜索指示器 两个指针对扫描缓冲区进行扫描。

   • NOTE：解决标识符过长问题 → 将缓冲区分为两个半区，互补使用。半区的缓冲区长度就是程序允许的标识符的最大长度。

单词符号的识别

1. 超前搜索

   现代语言一般加入几点限制，来避免超前搜索：

   1. 所有基本字都是保留字，用户不能用它们作为自己的标识符。

   2. 基本字作为特殊的标识符来处理，使用保留字表。

   3. 如果基本字、标识符和常数（或标号）之间没有确定的运算符或界符作为间隔，则必须使用一个空白作为间隔。

2. 状态转换图。用于识别（或接受）一定的字符串：若存在一条从初态到某一终态的道路，且这条道路上的所有弧上的表机腹连接成的字等于 $$\alpha$$，则称 $$\alpha$$ 被该状态转换图所识别（接受）。

   将状态转换图一般化：

   • 变量 curState 用于保存现有状态

   • 用二维数组表示状态图：stateTrans[state][ch]

设计

1. 设计程序设计语言的单词规范
2. 设计程序语言对应的状态转换图
3. 根据状态转换图，并根据三种分析模式，编程实现代码
   • 该过程十分有规律，那么是否有自动生成词法分析器的方法呢

自动生成词法分析器

基础理论：正规表达式和有限自动机理论。

概念

基本概念：

• 字母表：一个有穷字符集，记作 $$\Sigma$$

• 字符串：$$\Sigma$$ 中的字符构成的有穷序列，或称 字

• 空字：不包含任何字符的序列，记作 $$\epsilon$$

• $$\Sigma^{*}$$ 表示 $$\Sigma$$ 上所有字的集合，包含空字 $$\epsilon$$

• 子集的连接（积）：$$UV = {\alpha\beta | \alpha \in U & \beta \in V}\ where\ U,V \subseteq \Sigma^{*}$$

• V 的闭包：$${\displaystyle V^{*} = \cup^{+\infin}_{i=0} V_i }$$

• V 的正规闭包：$$V^{+} = VV^{*}$$

正规式和正规集：

• 关系：

  • 正规集可以用正规集表示
  • 正规式是表示正规集的一种方法
  • 一个字集合是正规式 $$\Leftrightarrow$$ 他能用正规式表示

• 递归定义：

  1. $$\epsilon$$ 和 $$\varnothing$$ 都是 $$\Sigma$$ 上的正规式，他们所表示的正规集是 $${\epsilon}$$ 和 $$\varnothing$$。
  2. 任何 $$a \in \Sigma$$，$$a$$ 是 $$\Sigma$$ 上的正规式，他表示的正规集为 $${a}$$
  3. 假定 $$e_1$$ 和 $$e_2$$ 都是 $$\Sigma$$ 上的正规式，他们所表示的正规集为 $$L(e_1)$$ 和 $$L(e_2)$$，则：
     1. $$(e_1 | e_2)$$ 为正规式，他们所表示的正规集为 $$L(e_1) \cup L(e_2)$$
     2. $$(e_1 \cdot e_2)$$ 为正规式，他们所表示的正规集为 $$L(e_1)L(e_2)$$
     3. $$(e_1)^{}$$ 为正规式，他所表示的正规集为 $$(L(e_1))^{}$$
  4. Define：仅有有限次使用上述三步骤而定义的表达式才是 $$\Sigma$$ 上的正规式，仅由这些正规式表示的字集才是 $$\Sigma$$ 上的正规集。

• 等价：若两个正规式所表示的正规集相同，则这两个正规式等价。

确定有限自动机 DFA

对状态转换图进行形式化定义，就得到了确定有限自动机的概念：

• 确定有限自动机 $$M$$ 可以表示为一个五元组，$$M = (S, \Sigma, f, S_0, F)$$ ，其中：

  1. $$S$$ ：有穷状态集；
  2. $$\Sigma$$：输入字母表（有穷）；
  3. $$f$$ ：状态转换函数，为 $$S \times \Sigma \rightarrow S$$ 的单值部分映射；
  4. $$S_0$$：是唯一的一个初态，$$S_0 \in S$$
  5. $$F$$：终态集（可空）

• 如果对于 $$\Sigma^{*}$$ 中的任何字 $$\alpha$$，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等与 $$\alpha$$，则称 $$\alpha$$ 为 DFA M 所识别（接受）。DFA M 所识别的字的全体记位 $$L(M)$$

非确定有限自动机 NFA

NFA 与 DFA 有着相似的定义，不同点在于上面的第 3、4 点。转换函数的终态不确定，体现了非确定的含义。

• 确定非有限自动机 $$M$$ 可以表示为一个五元组，$$M = (S, \Sigma, f, S_0, F)$$ ，其中：

  1. $$S$$ ：有穷状态集；
  2. $$\Sigma$$：输入字母表（有穷）；
  3. $$f$$ ：状态转换函数，为 $$S \times \Sigma^{*} \rightarrow 2^{S}$$ 的单值部分映射；
  4. $$S_0$$：是一个非空初态集，$$S_0 \subseteq S$$
  5. $$F$$：终态集（可空）

• 对于 $$\Sigma^{*}$$ 中的任何字 $$\alpha$$，若存在一条从初态到某一终态的道路，且这条道路上所有弧上的标记字连接成的字等于 $$\alpha$$（忽略那些标记为 $$\epsilon$$ 的弧），则称 $$\alpha$$ 为 NFA M 所接受。NFA M 所识别的字的全体记为 $$L(M)$$

NFA vs. DFA

区别

从状态图看他们的区别：

• NFA 可以有多个初态。

• 弧上的标记可以是 $$\Sigma^{*}$$ 中的一个字（甚至可以是一个正规式），而不一定是单个字符。

• 同一个字可能出现在同状态射出的多条弧上。

• DFA 是 NFA 的特例。

等价

对于任何两个有限自动机 M 和 M’，如果 $$L(M) = L(M’)$$，则称 M 与 M’ 等价。

自动机理论中的结论：

• 自动机理论中的一个重要结论：判断两个自动机等价性的算法是存在的。
• DFA 与 NFA 识别能力是相同的

根据定义我们知道，DFA 是特殊的 NFA，所以我们只需要一个将 NFA 确定化的算法。

NFA 确定化：假定 NFA $$M = (S, \Sigma, f, S_0, F)$$，我们对 M 的状态转换图进行如下改造：

• 等价变换 1：引进新的初始结点 X 和终态结点 Y，$$X, Y \notin S$$，从 X 到 $$S_0$$ 中任意状态结点连一条 $$\epsilon$$ 箭弧，从 F 中任意状态结点引一条 $$\epsilon$$ 箭弧到 Y → 解决初始状态唯一性问题。

• 等价变换 2：对 M 的状态转换图进一步施加替换，其中 k 是新引入的状态 → 简化了图上的标记。

• 等价变换 3：算法，子集法 → 解决 $$\epsilon$$ 弧和转换关系：

  • 概念 $$\epsilon$$-闭包（$$\epsilon-closure(I)$$）：设 I 是 S 的一个子集，定义 I 的 $$\epsilon$$-闭包为：

    • 若 $$s \in I$$，则 $$s \in \epsilon-closure(I)$$；
    • 若 $$s \in I$$，从 s 出发经过任意条 $$\epsilon$$ 弧能够达到的任何状态 $$s’$$ 都属于 $$\epsilon-closure(I)$$

  • 定义 $$I_a = \epsilon-closure(J)\ where\ a \in \Sigma, J 为 I中的状态经过一条 a 弧到达的状态集合$$

  • 算法，子集法：不失一般性，设字母表只包含两个 a 和 b，我们构造一张计算状态集的转换表：

    1. 首先，置第 1 列为 $$\epsilon-closure({X})$$，并求出这一列的 $$I_a$$ 和 $$I_b$$

    2. 然后检查这两个 $$I_a$$ 和 $$I_b$$，看他们是否在表的第一列中出现，把未曾出现的填入后面的空行的第 1 列上，求出每行第 2，3 列上的集合。

    3. 重复上述过程，直到所有第 2，3 的子集均出现在第一列为止。

    4. 该转换表唯一刻画了一个 DFA M，其中初态是 $$\epsilon-closure(X)$$，终态是含有原终态 Y 的子集。

DFA 的化简

概念：

• DFA 的化简（最小化）：对于给定的 DFA M，寻找一个状态数比 M 少的 DFA M’，使得 $$L(M) = L(M’)$$。
• 状态的等价性：假设 s 和 t 为 M 的两个状态，如果从状态 s 出发能读出某个字 $$\alpha$$ 而停止于终态，那么同样，从 t 出发也能读出 $$\alpha$$ 而停止于终态，反之亦然，则称状态 s 和 t 等价。
• 状态可区别：如果两个状态不等价，则称他们是可区别的。

DFA 化简：

• 基本思想：把 M 的状态集划分成一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集内的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。

• 化简算法：

  1. 首先把 S 划分为终态和非终态两个子集，形成基本划分 $$\Pi$$

  2. 假定到某一时刻，$$\Pi$$ 含有 m 个子集，记作：$$\Pi = {I^{(1)}, I^{(2)}, …, I^{(m)}}$$，检查 $$\Pi$$ 中的每个子集是否可以进一步划分：

     1. 对某个 $$I^{i}$$，若存在一个输入字符 a 使得 $$I_a^{(i)}$$ 不会包含在现行的 $$\Pi$$ 的某个子集 $$I^{(j)}$$ 中，则应该至少把 $$I^{(i)}$$ 分为两个部分。

        若 $$s_1, s_2 \in I^{(i)}, a \in \Sigma$$，且 $$f(s_1, a) = t_1, f(s_2, a)=t_2$$ ，$$t_1, t_2$$ 属于不同子集，则将 $$I^{(i)}$$ 分成两个部分：

        • $$I^{(i1)} = {s | s \in I^{(i)} 且 s 经 a 弧到达 t，且 t 与 t_1 属于现行 \Pi 中的同一子集}$$
        • $$I^{(i2)} = I^{i} - I^{(i1)}$$

     2. 一般地，对某个 a 和 $$I^{(i)}$$，若 $$I^{(i)}$$ 落入现行 $$\Pi$$ 中的 N 个不同子集，则应该把 $$I^{i}$$ 划分成 N 个不相交的组，使得每个组 $$J$$ 的 $$J_a$$ 都落入 $$\Pi$$ 的同一子集。

  3. 重复步骤 2，直到 $$\Pi$$ 所含的子集数目不再增长。

  4. 对于上述最后划分 $$\Pi$$ 中的每个子集，我们选取每个子集中的一个状态代表其他状态，则可以得到化简之后的 NFA M‘。

正规式和有限自动机的等价性

一个正规式 r 与一个有限自动机 M 等价 $$\Leftrightarrow$$ $$L(r) = L(M)$$

定理：对于 $$\Sigma$$ 上任一 NFA M，都存在一个 $$\Sigma$$ 上的正规式 r，使得 $$L(r) = L(M)$$。证明算法如下：

• 假定 NFA $$M = <S, \Sigma, \delta, S_0, F>$$，我们对 M 的状态图进行如下改造：

  1. 在 M 的状态图上加入两个状态 X 和 Y， 从 X 用 $$\epsilon$$ 弧连接到 M 的所有初态结点，从 M 的所有终态结点用 $$\epsilon$$ 弧连接到 Y，从而形成一个新的 NFA，记作 M’，他只有一个初态 X 和一个终态 Y，显然 $$L(M) = L(M’)$$

  2. 将 $${\displaystyle (i) \xrightarrow{r_1} (j) \xrightarrow{r_2} (k)}$$ 替换为 $${\displaystyle (i) \xrightarrow{r_1 \cdot r_2} (k)}$$

  3. 将 替换为 $$(i) \xrightarrow{r_1 | r_2} (j)$$

  4. 将 替换为 $$(i) \xrightarrow{r_1 \cdot r_2* \cdot r_3} (k)$$

  5. 重复上述 2-4 规则，直至图中只剩下两个结点一条弧。最后 X 到 Y 上的弧标记的正规式即为自动机所对应的正规式 r。

定理：对于任何一个正规式 r，都存在一个 NFA M，使得 $$L(M) = L(r)$$，并且 M 只有一个初态和一个终态，而且没有从终态出发的箭弧。对运算符数目 k 进行数学归纳法证明，证明如下：

• 若 r 具有 0 个运算符，则 $$r = \epsilon$$ 或 $$r = \varnothing$$ 或 $$r = a\ where\ a \in \Sigma$$。很显然容易构造这样满足要求的 NFA。

• 假设对于运算符数目少于 $$k(k \ge 1)$$ 的正规式成立，当 r 中含有 k 个运算符时，r 有三种情况，显然都成立。

• PostScript：上述证明实际上也是将正规表达式构造成 NFA 的算法。

词法分析自动生成 LEX

编译流程大致如下：

简单使用

LEX 官方手册如下：http://dinosaur.compilertools.net/lex/index.html。以下介绍简单规范：

• LEX 编写主要分为 AUXILIARY DEFINITION （辅助定义）和 RECOGNITION RULES （识别规则）两个部分

  1. 辅助定义：以文法形式给常用正规式进行命名，比如：digit->1|2|3|4|5|6|7|8|9|0

  2. 识别规则：都由两部分组成，一个正规式和一小段程序代码。

工作流程

LEX 工作过程：

• 对于每一个识别规则 $$P_i$$ 构造一个响应的非确定有限自动机 $$M_i$$；
• 通过一个 $$\epsilon$$ 弧将这些自动机连接成一个新的 NFA；
• 把 NFA 确定化、最小化，生成该 DFA 的状态转换表和控制执行程序。