2021-09-16 《编译原理》学习笔记：第2周

第三章 词法分析 3.1 简介 3.1.1 编译器的阶段 3.1.2 词法分析器的任务

​ 举例：

​ 这些被返回的单词叫做记号：

• IF等：是关键字，对应源程序 if
• IDENT：表示是标识符集合，把 x 等放到后面；IDENT 即分类 / 词类， x 可叫做词素，即单词对应的实际文本

3.1.3 单词 / 记号 / token

​ 分为 5 类：

• 关键字，保留字，如 if、while 等
• 标识符，如变量名等
• 常数，如 23、4.5 等
• 运算符，如+、*等
• 界符，如逗号、分号等

3.1.4 信息的二元式表示

​ 二元式表示：（单词种别，单词自身的值）

（1）记号的表示方式

1. 枚举类型： kind

​ 是对词法分析器能识别的记号的分类；对语言来说数目有限，不同语言不同

2. lexeme： 识别出的单词的值

enum kind { IF, LPAREN, ID, INTLIT, ... };
struct token {
    enum kind k;
    char *lexeme;
};

if  (x > 5) ⟹ token {k = IF, lexeme = 0} token {k = LPAREN, lexeme = 0} token {k = ID, lexeme = ’x’} … \text{if \ (x > 5)}\quad\Longrightarrow\quad \begin{array}{l} \text{token \{k = IF, lexeme = 0\}}\\ \text{token \{k = LPAREN, lexeme = 0\}}\\ \text{token \{k = ID, lexeme = 'x'\}}\\ \dots \end{array} if  (x > 5)⟹token {k = IF, lexeme = 0}token {k = LPAREN, lexeme = 0}token {k = ID, lexeme = ’x’}…​

（2）标识符

​ 需要记载标识符的类别、层次以及其他属性。这些属性放在符号表中，使用指向该标识符所在符号表位置的指针：

3.2 手工构造法 3.2.1 词法分析器的实现方法

（1）手工编码实现

• 相对复杂、且容易出错

• 但是目前非常流行的实现方法

  – GCC，LLVM，…

• 比生成的词法分析器更快速，因为有优化

（2）词法分析器的生成器

​ 程序员只需要写一些词法规则的说明等，利用工具生成。

• 可快速原型、代码量较少
• 但较难控制细节

3.2.2 转移图

（1）转移图的介绍

​ 识别关键字 new 的代码片段：

c = nextChar();
if (c == 'n')
{
    c = nextChar();
    if (c == 'e')
    {
        c = nextChar();
        if (c == 'w')
            report success;
        else
            ...
    }
    else
        ...
}
else
    ...

• 转移图： 相当于一个有穷自动机 FA，用来表示该代码片段，表示一个识别器。

• S0： 初始状态

• S3： 接受状态，用双圈表示

  当输入为 new 时，识别器才会到达 S3。

（2）6 种关系运算符的转移图

、=、> （识别失败时，注意将该字符回退就，进行其他的操作） 3.2.3 标识符的转移图 3.2.4 识别关键字（if） 3.3 正则表达式

​ 转移图 / 有穷自动机可以详细精确地定义语言，但不够直观。

​ 因此可以使用正则表达式（Regular Expression）来描述该语言，称为正则语言。

R E ⟺ 等价 F A RE\quad \stackrel{\text{等价}}{\Longleftrightarrow}\quad FA RE⟺等价​FA

3.3.1 自动生成工具

​ 自动生成工具接受声明规范，仅仅需要输入识别单词的规则就可以，也就是要识别的目标。使得程序员不用写大量的代码，仅仅需要写一个规范就可以了，可以帮助程序员减少工作量。

3.3.2 定义

​ 对于给定的字符集 Σ = { c 1 ,   c 2 ,   … ,   c n } \Sigma=\{c_{1},\ c_{2},\ \dots,\ c_{n}\} Σ={c1​, c2​, …, cn​}

• 空串 ε \varepsilon ε 是正则表达式，表示仅含空串的集合

• 对于任意 c ∈ Σ c\in\Sigma c∈Σ， c c c 是正则表达式，表示仅包含 c c c 的集合

• 下列组合中也是正则表达式：

  • 选择： M   ∣   N = { M ,   N } M\ |\ N=\{M,\ N\} M ∣ N={M, N}
  • 连接： M N = { m n   ∣   m ∈ M ,   n ∈ N } MN=\{mn\ |\ m\in M,\ n\in N\} MN={mn ∣ m∈M, n∈N}
  • 闭包： M ∗ = { ε ,   M , M M ,   M M M ,   …   } M^{*}=\{\varepsilon,\ M, MM,\ MMM,\ \dots\} M∗={ε, M,MM, MMM, …}

  优先级：括号 < 闭包 < 连接 < 选择 < 左结合

  例如：

1. 正则表达式 a   ∣   b a\ |\ b a ∣ b 表示语言 { a ,   b } \{a,\ b\} {a, b}
2. ( a   ∣   b ) ( a   ∣   b ) (a\ |\ b)(a\ |\ b) (a ∣ b)(a ∣ b) 表示语言 { a a ,   a b ,   b a ,   b b } \{aa,\ ab,\ ba,\ bb\} {aa, ab, ba, bb}
3. a ∗ a^{*} a∗ 表示由零个或多个 a a a 组成的串的集合，即 { ε ,   a ,   a a ,   …   } \{\varepsilon,\ a,\ aa,\ \dots\} {ε, a, aa, …}
4. ( a ∣ b ) ∗ (a|b)^* (a∣b)∗ 表示由零个或多个 a a a 或 b b b 的实例构成的串的集合，即由 a a a 和 b b b 构成的所有串的集合 { ε ,   a ,   b ,   a a ,   a b ,   b a ,   b b ,   a a a ,   …   } \{\varepsilon,\ a,\ b,\ aa,\ ab,\ ba,\ bb,\ aaa,\ \dots\} {ε, a, b, aa, ab, ba, bb, aaa, …}
5. a   ∣   a ∗ b a\ |\ a^{*}b a ∣ a∗b 表示语言 { a ,   b ,   a b ,   a a b ,   a a a b ,   …   } \{a,\ b,\ ab,\ aab,\ aaab,\ \dots\} {a, b, ab, aab, aaab, …}，串 a a a 和以 b b b 结尾的零个或多个 a a a 组成的串的集合

3.3.3 正则表达式的代数定律 3.3.4 举例

1. C 语言的标识符： ( a ∣ b ∣ c ∣ . . . ∣ z ∣ A ∣ B ∣ C . . . ∣ Z ∣ _ ) ( a ∣ b ∣ c ∣ . . . ∣ z ∣ A ∣ B ∣ C ∣ . . . ∣ Z ∣ 0 ∣ . . ∣ 9 ∣ _ ) ∗ (a|b|c|...|z|A|B|C...|Z|\_)(a|b|c|...|z|A|B|C|...|Z|0|..|9|\_)^{*} (a∣b∣c∣...∣z∣A∣B∣C...∣Z∣_)(a∣b∣c∣...∣z∣A∣B∣C∣...∣Z∣0∣..∣9∣_)∗

2. 无符号整数： 0 ∣ ( 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9 ) ( 0 ∣ 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9 ) ∗ 0 | (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^{*} 0∣(1∣2∣3∣4∣5∣6∣7∣8∣9)(0∣1∣2∣3∣4∣5∣6∣7∣8∣9)∗

3. 无符号浮点数： ( 0 ∣ 1 ∣ … ∣ 9 ) ( 0 ∣ 1 ∣ … ∣ 9 ) ∗ ( . ( 0 ∣ 1 ∣ … ∣ 9 ) ( 0 ∣ 1 ∣ … ∣ 9 ) ∗ ∣ ε ) ( E ( + ∣ − ∣ ε ) ( 0 ∣ 1 ∣ … ∣ 9 ) ( 0 ∣ 1 ∣ … ∣ 9 ) ∗ ∣ ε ) (0|1|…|9) (0|1|…|9)^* (.(0|1|…|9) (0|1|…|9)^*|\varepsilon) (E(+|-|\varepsilon)(0|1|…|9) (0|1|…|9)^*|\varepsilon) (0∣1∣…∣9)(0∣1∣…∣9)∗(.(0∣1∣…∣9)(0∣1∣…∣9)∗∣ε)(E(+∣−∣ε)(0∣1∣…∣9)(0∣1∣…∣9)∗∣ε)

3.3.5 正则表达式与正规文法

• 对任意一个正规文法，存在一个定义同一个语言的正则表达式

• 对每个正则表达式，存在一个生成同一个语言的正规文法

• 可相互转换

3.3.6 正则表达式的扩展

• ＋：一个或多个实例，e+ == 一个或多个 e

• ？：零个或一个实例，e? == 零个或一个 e

• 字符类

  • [abc] == a|b|c
  • 连续：第一个和最后一个符号，中间连词符：[a - c] == a|b|c

• 转义

  • 如：使用 \* 表示 *

3.4 有限状态自动机 3.4.1 有限状态自动机（FA）

​ 一个确定的有穷自动机 M 是一个五元组： M = ( Σ ,   S ,   q 0 ,   F ,   δ ) M=(\Sigma,\ S,\ q_{0},\ F,\ \delta) M=(Σ, S, q0​, F, δ)

• Σ： 输入符号表。是一个有穷字母表，其中每个元素称为一个输入符号
• S： 有限状态集。其中的每个元素称为一个状态
• q0： 唯一的初态。q0 ∈ \in ∈ S
• F： 一个终态集。包含一个或多个元素，也称可接受状态或结束状态，用双层圆圈表示。F ⊆ \sube ⊆ S
• δ ： 转移函数，是 S × Σ → K 上的映像，表示状态的切换

3.4.2 NFA 和 DFA

• 非确定的有限状态自动机（NFA）： 状态转移函数是不确定的

  对任意的字符，最多有一个状态可以转移： δ : S × Σ → S \delta:S\times\Sigma\rightarrow S δ:S×Σ→S NFA 可以不消耗字符，接受空串转换状态：

• 确定的有限状态自动机（DFA）： 每次接受字符走到的状态是确定的

  对任意的字符，有多于一个状态可以转移： δ : S × ( Σ ∪ ε ) → ℘ ( S ) \delta:S\times(\Sigma\cup\varepsilon)\rightarrow \wp(S) δ:S×(Σ∪ε)→℘(S) 其中， ℘ \wp ℘ 表示幂集。

​ 二者之间的联系：

1. NFA 和 DFA 在表达力上是等价的。
2. 任何 DFA 是某个 NFA 的一个特例，任何 NFA 可以通过一个 DFA 模拟。

N F A D F A 初 始 状 态 不 唯 一 唯 一 弧 上 的 标 记 字 ( 单 字 符 、 ε ) 字 符 转 换 关 系 非 确 定 确 定 \begin{array}{c} \hline & NFA & DFA \\ \hline 初始状态 & 不唯一 & 唯一\\ 弧上的标记 & 字(单字符、\varepsilon) & 字符\\ 转换关系 & 非确定 & 确定\\ \hline \end{array} 初始状态弧上的标记转换关系​NFA不唯一字(单字符、ε)非确定​DFA唯一字符确定​​

3.5 正则表达式到 NFA 3.5.1 Thompson 算法

（1）递归构造

1. e → ε e\rightarrow\varepsilon e→ε

2. e → c e\rightarrow c e→c

3. e → e 1     e 2 e\rightarrow e_1\ \ \ e_2 e→e1​   e2​

4. e → e 1   ∣   e 2 e\rightarrow e_1\ |\ e_2 e→e1​ ∣ e2​

5. e → e 1 ∗ e\rightarrow e_1^* e→e1∗​

（2）示例： a ( b   ∣   c ) ∗ a(b\ |\ c)^{*} a(b ∣ c)∗

1. 分别构建对应于 a 、 b a、b a、b 和 c c c 的 NFA

2. 为括号中的表达式 b   ∣   c b\ |\ c b ∣ c 构建 NFA

3. 为闭包 ( b ∣ c ) ∗ (b|c)^* (b∣c)∗ 构建 NFA

4. 将对应于 a a a 和 ( b   ∣   c ) ∗ (b\ |\ c)^* (b ∣ c)∗ 的 NFA 连接起来

由 Thompson 算法构造出来的任何一个 NFA，均只可能包括唯一的起始状态和唯一的接受状态。 3.5.2 另一种方法

（1）三种基本操作

1. r = r 1 r 2 r=r_{1}r_{2} r=r1​r2​

2. r = r 1   ∣   r 2 r=r_{1}\ |\ r_{2} r=r1​ ∣ r2​

3. r = ( r 1 ) ∗ r=(r_{1})^{*} r=(r1​)∗

（2）组合操作

3.6 NFA 转换到 DFA 3.6.1 算法思想

（1）原理

​ DFA 的构造过程可以看做是对 NFA 动作过程的模拟。

• 子集 I 的 ε \varepsilon ε 闭包： ε − c l o s u r e ( I ) = I ∪ { S ′   ∣   从 某 个 S ∈ I 出 发 经 过 任 意 条 ε 弧 能 到 达 S ′ } \varepsilon-closure(I)=I\cup\{S'\ |\ 从某个 S\in I 出发经过任意条 \varepsilon 弧能到达 S'\} ε−closure(I)=I∪{S′ ∣ 从某个S∈I出发经过任意条ε弧能到达S′}

• 弧 a 的 ε \varepsilon ε 闭包： I a = ε − c l o s u r e ( J ) I_{a}=\varepsilon-closure(J) Ia​=ε−closure(J) 其中 J 为 I 中的某个状态出发经过一条弧而到达的状态集合。

​ 例如上图中，令 I 为初始点，即 I = { 1 } I=\{1\} I={1}，则：

ε − c l o s u r e ( I ) = { 1 ,   2 } J = { 5 ,   4 ,   3 } I a = ε − c l o s u r e ( { 5 ,   4 ,   3 } ) = { 5 ,   4 ,   3 ,   6 ,   2 ,   7 ,   8 } \varepsilon-closure(I)=\{1,\ 2\}\\ J=\{5,\ 4,\ 3\}\\ \begin{aligned} I_{a}&=\varepsilon-closure(\{5,\ 4,\ 3\})\\ &=\{5,\ 4,\ 3,\ 6,\ 2,\ 7,\ 8\}\\ \end{aligned} ε−closure(I)={1, 2}J={5, 4, 3}Ia​​=ε−closure({5, 4, 3})={5, 4, 3, 6, 2, 7, 8}​

​ 即表示：从初始点 1 出发，经过 a 所能够到达的所有状态。

（2）算法步骤

​ 不失一般性，我们设字母表只包含两个元素：a 和 b。构造一张状态集的转换表： I I a I b ε − C l o s u r e ( { X } ) { …   } { …   } { …   } { …   } { …   } { …   } { …   } { …   } \begin{array}{c|c|c} I & I_{a} & I_{b}\\ \hline \varepsilon-Closure(\{X\}) & \{\dots\} & \{\dots\}\\ \{\dots\} & \{\dots\} & \{\dots\}\\ \{\dots\} & \{\dots\} & \{\dots\} \end{array} Iε−Closure({X}){…}{…}​Ia​{…}{…}{…}​Ib​{…}{…}{…}​​

1. 首先，第 1 行第 1 列置为 ε − c l o s u r e ( { X } ) \varepsilon-closure(\{X\}) ε−closure({X})，并求出其 Ia，Ib
2. 检查 Ia、Ib，看它们是否在第 1 列出现过，未曾出现的写在第 1 列的下面，继续求出其 Ia’，Ib’
3. 重复上述过程，直到所有第 2、3 列子集全部出现在第 1 列为止

（3）举例

I I a I b ε − C l o s u r e ( { X ,   1 ,   2 } ) { 1 ,   5 ,   2 } { 1 ,   6 ,   2 } { 1 ,   5 ,   2 } { 1 ,   3 ,   5 ,   2 ,   4 ,   Y } { 1 ,   6 ,   2 } { 1 ,   6 ,   2 } { 1 ,   5 ,   2 } { 1 ,   3 ,   6 ,   2 ,   4 ,   Y } { 1 ,   3 ,   5 ,   2 ,   4 ,   Y } { 1 ,   3 ,   5 ,   2 ,   4 ,   Y } { 1 ,   6 ,   2 ,   4 ,   Y } { 1 ,   3 ,   6 ,   2 ,   4 ,   Y } { 1 ,   5 ,   2 ,   4 ,   Y } { 1 ,   3 ,   6 ,   2 ,   4 ,   Y } { 1 ,   6 ,   2 ,   4 ,   Y } { 1 ,   5 ,   2 ,   4 ,   Y } { 1 ,   3 ,   6 ,   2 ,   4 ,   Y } { 1 ,   5 ,   2 ,   4 ,   Y } { 1 ,   3 ,   5 ,   2 ,   4 ,   Y } { 1 ,   6 ,   2 ,   4 ,   Y } \begin{array}{c|c|c} I & I_{a} & I_{b}\\ \hline \varepsilon-Closure(\{X,\ 1,\ 2\}) & \{1,\ 5,\ 2\} & \{1,\ 6,\ 2\}\\ \{1,\ 5,\ 2\} & \{1,\ 3,\ 5,\ 2,\ 4,\ Y\} & \{1,\ 6,\ 2\}\\ \{1,\ 6,\ 2\} & \{1,\ 5,\ 2\} & \{1,\ 3,\ 6,\ 2,\ 4,\ Y\}\\ \{1,\ 3,\ 5,\ 2,\ 4,\ Y\} & \{1,\ 3,\ 5,\ 2,\ 4,\ Y\} & \{1,\ 6,\ 2,\ 4,\ Y\}\\ \{1,\ 3,\ 6,\ 2,\ 4,\ Y\} & \{1,\ 5,\ 2,\ 4,\ Y\} & \{1,\ 3,\ 6,\ 2,\ 4,\ Y\}\\ \{1,\ 6,\ 2,\ 4,\ Y\} & \{1,\ 5,\ 2,\ 4,\ Y\} & \{1,\ 3,\ 6,\ 2,\ 4,\ Y\}\\ \{1,\ 5,\ 2,\ 4,\ Y\} & \{1,\ 3,\ 5,\ 2,\ 4,\ Y\} & \{1,\ 6,\ 2,\ 4,\ Y\}\\ \end{array} Iε−Closure({X, 1, 2}){1, 5, 2}{1, 6, 2}{1, 3, 5, 2, 4, Y}{1, 3, 6, 2, 4, Y}{1, 6, 2, 4, Y}{1, 5, 2, 4, Y}​Ia​{1, 5, 2}{1, 3, 5, 2, 4, Y}{1, 5, 2}{1, 3, 5, 2, 4, Y}{1, 5, 2, 4, Y}{1, 5, 2, 4, Y}{1, 3, 5, 2, 4, Y}​Ib​{1, 6, 2}{1, 6, 2}{1, 3, 6, 2, 4, Y}{1, 6, 2, 4, Y}{1, 3, 6, 2, 4, Y}{1, 3, 6, 2, 4, Y}{1, 6, 2, 4, Y}​​

1. 把表看成状态转换矩阵，子集视为状态，那么该表唯一刻画了一个确定的有限自动机 M。

   • 初态是 ε − c l o s u r e ( { X } ) \varepsilon-closure(\{X\}) ε−closure({X})
   • 终态是含有原终态 Y 的子集

2. 于是，NFA 与 DFA 等价

3. 将每个子集（状态）进行编号，那么就可以得到新的状态转换图 D： I a b 0 1 2 1 3 2 2 1 4 3 3 5 4 6 4 5 6 4 6 3 5 \begin{array}{c|c|c} I & a & b\\ \hline 0 & 1 & 2\\ 1 & 3 & 2\\ 2 & 1 & 4\\ 3 & 3 & 5\\ 4 & 6 & 4\\ 5 & 6 & 4\\ 6 & 3 & 5 \end{array} I0123456​a1313663​b2245445​​

3.6.2 子集构造算法

I0 = eps_closure(n0);
I = {I0};                                 // I：计算得到的 DFA 的所有状态
workList = I0;                            // workList：实现为队列
while (workList != [])
{
    remove i from workList;
    foreach (char c)                      // c：每个字符，如 ASCII 码，则遍历 256 次
    {
        t = e-closure (delta(i, c));      // i 中每个状态接受 c 后的状态
        D[i, c] = t;                      // 记录 DFA 中的状态转换，即填表
        if (t not in I)
            add t to I and workList;
    }
}