编译原理笔记 03 - 词法分析

正则表达式

• 正则表达式 (Regular Expression，RE) 是一种用来描述正则语言的更紧凑的表示方法。
  • 【例】语言 L={a} { a , b } ( { ε } ∪ ( { . , _ } { a , b } { a , b } ) )
  • 用正则表达式 r 可表示为：
  • r = a (a | b) ( ε | (.| _) (a | b) (a | b) )
  • 句子含义是：以 a 开头，连接一个任意长度的 ab 串，接下来连接一个空串，此时表示句子结束。除此之外，还可以连接一个.和_，接下来连接一个长度大于等于 1 的 ab 串。
  • 注意：{}*表示克林闭包

• 正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r 定义 (表示) 一个语言，记为 L(r)。这个语言也是根据 r 的子表达式所表示的语言递归定义的。

  正则表达式的定义

• ε 是一个 RE，L(ε) = {ε}

  • 空串是一个正则表达式，它表示的语言只包含一个空串
• 如果 a∈∑，则 a 是一个 RE，L(a) = {a}
  • 字母表中的任何一个符号，都是一个正则表达式，它表示的语言只包含它本身
• 假设 r 和 s 都是 RE，表示的语言分别是 L(r) 和 L(s)，则
  • r|s 是一个 RE，L(r|s) = L(r)∪L(s)
  • rs 是一个 RE，L(rs) = L(r) L(s)
  • r 是一个 RE，L(r)= (L(r))*
  • (r) 是一个 RE，L( (r) ) = L(r)
• 运算的优先级：*(克林闭包)、连接、|(或运算)

【例】令Σ = {a，b}，即符号表中包含两个元素 a 和 b，由正则表达式的定义可知：a 是一个正则表达式，b 也是一个正则表达式，因此：

• L(a|b) = L(a)∪L(b) ={a}∪{b} = {a, b}
  • 由于 a 和 b 都是 RE，所以 a | b 还是一个正则表达式
• L((a|b)(a|b)) = L(a|b) L(a|b)={a, b}{a, b}= { aa, ab, ba, bb }
  • 由于 a|b 是 RE，所以 a|b 连接 a|b 还是一个 RE
• L(a) = (L(a)) = {a} *= { ε, a, aa, aaa, . . . }
  • a 的克林闭包表示将任意个 a 连接起来
• L((a|b) ) = (L(a|b)) = {a, b} *= { ε, a, b, aa, ab, ba, bb, aaa, . . .}
  • a|b 的克林闭包表示任意长度的 ab 串
• L(a|a*b) = { a, b, ab, aab, aaab, . . .}
  • a 或上 a 的克林闭包 b，表示一个 a 或者是若干个 a 后面连接一个 b

【例】用 RE 描述 C 语言中的无符号整数

• 十进制整数的 RE：(1|…|9)(0|…|9)*|0
  • 表示第一个符号是 1-9 之间的一个数，接下来连接若干个 0-9 之间的数字。除此之外，还可以是数字 0。
• 八进制整数的 RE：0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*
  • 表示第一个符号是数字 0，第二个符号是若 1-7 之间的一个数字，接下来连接若干个 0-7 之间的数字。
• 十六进制整数的 RE：0x(0|1|…|9|a|…| f |A|…|F)(0|…|9|a|…| f |A|…|F )*
  • 表示第一个符号是 0，第二个符号是 x，第三个符合是 1-F 之间的一个符号，接下来连接若干个 0-F 之间的符号。

可以用 RE 定义的语言叫做正则语言或正则集合

RE 的代数定律

正则文法与正则表达式等价

• 对任何正则文法 G，存在定义同一语言的正则表达式 r

• 对任何正则表达式 r，存在生成同一语言的正则文法 G

  正则定义

  为了方便起见，我们可以给某些正则表达式命名，然后像使用字母表中的符号一样使用这些名字构造正则表达式。这是正则定义提出的背景。
  正则定义是具有如下形式的定义序列

• d1→r1

• d2→r2
• …
• dn→rn

r 是正则表达式，d 是给正则表达式起的名字。
其中：

• 每个 di 都是一个新符号，它们都不在字母表 Σ中，而且各不相同
• 每个 ri 是字母表 Σ∪{d1 ,d2 , … ,di-1} 上的正则表达式
  • 每个 RE 只能说字母表中的符号或者是给正则表达式起的名字

综上，正则定义就是给一些 RE 命名，并在之后的 RE 中像使用字母表中的符号一样使用这些名字。
【例】C 语言中标识符的正则定义

• digit → 0|1|2|…|9
• letter → A|B|…|Z|a|b|…|z|
• id → letter (letter|digit) *
• 前两句箭头右部是 RE，左部是给 RE 起的名字，最后一句是用起的名字定义 id，也就是标识符。表示字母打头的字母数字串。

【例】（整型或浮点型）无符号数的正则定义

• digit → 0|1|2|…|9
• digits → digit digit*
  • 表示长度大于等于 1 的数字串
• optionalFraction → .digits|ε
  • 表示可选的小数部分，因为是可以为空串
• optionalExponent → (E(+|-|ε)digits ) | ε
  • 表示可选的指数部分，因为是可以为空串

• number → digits optionalFraction optionalExponent

  有穷自动机

• 有穷自动机 (Finite Automata，FA) 由两位神经物理学家 MeCuloch 和 Pitts 于 1948 年首先提出，是对一类处理系统建立的数学模型

• 这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）
• 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

【例】电梯控制装置

• 输入：顾客的乘梯需求（所要到达的层号）
• 状态：电梯所处的层数 + 运动方向

• 电梯控制装置并不需要记住先前全部的服务要求，只需要知道电梯当前所处的状态以及还没有满足的所有服务请求

  FA 模型

  

• 输入带 (input tape)：用来存放输入符号串

• 读头 (head)：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动

• 有穷控制器 (finite control)：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一状态

  FA 的表示

• 转换图（Transition Graph）

  • 结点：FA 的状态
    • 初始状态（开始状态）：只有一个，由 start 箭头指向
    • 终止状态（接收状态）：可以有多个，用双圈表示
  • 带标记的有向边：如果对于输入 a，存在一个从状态 p 到状态 q 的转换，就在 p、q 之间画一条有向边，并标记上 a。即状态 p 时遇到输入 a，则转换状态到 q。

【例】有穷自动机的转换图

FA 定义 (接收) 的语言

• 给定输入串 x，如果存在一个对应于串 x 的从初始状态到某个终止状态的转换序列，则称串 x 被该 FA 接收

【例】对上例中的有穷自动机，输入 abbaabb
首先，在初始状态 0 遇到第一个输入 a，保持状态 0，接下来遇到两个 b 以后，依然保持状态 0，在接下来又遇到一个 a，还保持状态 0，遇到第二个 a，进入状态 1，接下来，遇到输入 b，进入状态 2，再遇到第二个 b，进入终止状态 3。可见上例中的有穷自动机可以接受串 abbaabb。

• 由一个有穷自动机 M 接收的所有串构成的集合称为是该 FA 定义 (或接收) 的语言，记为 L(M)

【例】对于上例中的有穷自动机，它的语言

• L(M) = 所有以 abb 结尾的字母表 {a, b} 上的串的集合

  最长子串匹配原则

  最长子串匹配原则 (Longest String Matching Principle) 是指：当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配。
  【例】下图中自动机
  

• 终态 1 表示匹配到<

• 终态 2 表示匹配到<=
• 当输入串为<=时，它的前缀与终态 1 和 2 都匹配上了，此时，根据最长子串匹配原则，我们选择终态 2 进行匹配。

由上例可见，在到达某个终态之后，只要输入带上还有符号，FA 就继续前进，以便寻找尽可能长的匹配。

有穷自动机的分类

• 确定的 FA (Deterministic finite automata, DFA)

• 非确定的 FA (Nondeterministic finite automata, NFA)

  确定的有穷自动机 (DFA)

  M = (S，Σ ，δ，s0，F)M=(S，Σ，δ，s_0，_F)

• S：有穷状态集

• Σ：输入字母表，即输入符号集合。假设ε不是 Σ中的元素
• δ：将 S×Σ映射到 S 的转换函数。 ∀s∈S, a∈Σ, δ(s,a) 表示从状态 s 出发，沿着标记为 a 的边所能到达的状态。
• s0：开始状态 (或初始状态)，s0∈ S
• F：接收状态 (或终止状态) 集合，F⊆ S

【例】一个 DFA

• S：状态集合。包含状态 0、状态 1、状态 2、状态 3
• Σ：输入字母表，即输入符号集合。包含字母符号 a、b
• δ：转换函数。用转换表表示。状态 0 遇到输入 a 时，转换到状态 1，遇到输入 b 时，转换到状态 0，……

• 可以看出，转换表与转换图等价，都可以表示有穷自动机

  非确定的有穷自动机 (NFA)

  与 DFA 的区别是：

• δ：将 S×Σ映射到 2S 的转换函数。∀s∈S, a∈Σ, δ(s,a) 表示从状态 s 出发，沿着标记为 a 的边所能到达的状态集合。即从状态 s 出发，沿着标记为 a 的边所能到达的状态不唯一。

【例】一个 NFA

• 当初始状态 0 遇到符号 a，它所能到达的状态集合包括状态 0 和状态 1 两个元素。

  DFA 和 NFA 的等价性

• 对任何非确定的有穷自动机 NFA ，存在定义同一语言的确定的有穷自动机 DFA

• 对任何确定的有穷自动机 DFA ，存在定义同一语言的非确定的有穷自动机 NFA

【例】DFA 和 NFA 的等价性

• 上图的 DFA 和 NFA 都表示以 abb 结尾的串，表示同一个 RE
• 从表现形式上看，NFA 比 DFA 更加直观

• 从计算机实现上，DFA 比 NFA 更易实现

  带有空边的 NFA

• 有向边上可以标记空串的 NFA，叫做带有 “ε- 边” 的 NFA

【例】带有 “ε- 边” 的 NFA

• 状态 A 和状态 B 之间的有向边标记为 ε ，表示状态 A 不需要任何输入就可以直接进入状态 B

  带有和不带有空边的 NFA 的等价性

  【例】带有和不带有空边的 NFA 的等价性
  

  DFA 的算法实现

• 输入：以文件结束符 eof 结尾的字符串 x。DFA 的开始状态 s0，接收状态集 F，转换函数 move。

• 输出：如果 DFA 接收 x，则回答 “yes”，否则回答 “no”。
• 方法：将下述算法应用于输入串 x。 | 1 2 3 4 5 6 7 8 | s = s0; // s表示当前状态 c = nextChar(); // c表示当前输入符号 while (c! = eof){ s = move (s,c); c = nextChar (); } if (s在F中) return”yes”; else return “no”; | | —- | —- |

Copy

• 函数nextChar( )返回输入串x的下一个符号

• 函数move(s, c)表示从状态s出发，沿着标记为c的边所能到达的状态

  从 RE 到 DFA 的转换

  正则表达式是一个符号序列的形式，能够很直观的描述单词的构成。但是在构造词法分析器时，我们真正实现或模拟的是 DFA。因此，这就要求从正则表达式到有穷自动机的转换。
  

• 直接从 RE 构造 DFA 比较困难，但我们可以先把 RE 转换为等价的 NFA，再将 NFA 转换为等价的 DFA。

  从 RE 到 NFA 的转换

• ε 对应的 NFA：从初始状态到终止状态不需要任何输入，也就是说它接受一个空串

• 符号 a 对应的 NFA

• r = r1r2 对应的 NFA

• r = r1|r2 对应的 NFA

• r = (r1) * 对应的 NFA

【例】r=(a|b)*abb 对应的 NFA

从 NFA 到 DFA 的转换

【例 1】从 NFA 到 DFA 的转换

• 由 NFA 写出转换表，由转换表画出 DFA
• A,B 是一个状态合集，表示 A 或 B 状态

【例 2】从带有空边的 NFA 到 DFA 的转换

• 由 NFA 写出转换表，由转换表画出 DFA
• 由于在初始状态 A 不需要任何输入就能进入状态 B，所以状态 B 也是一个初始状态，同理，C 也是初始状态。由于初始状态 C 在 NFA 也是一个终止状态，所以 DFA 中的初始状态集 A,B,C 也被标记为终止状态；
• 初始状态 A 在遇到 0 时进入状态的合集仍是 A,B,C；
• 初始状态 A 在遇到 1 时进入状态的合集是 B,C，所以增加节点 B,C，由于状态 C 在 NFA 中是一个终止状态，所以 DFA 中的状态 B,C 也标记为终止状态；
• 初始状态 A 在遇到 2 时进入状态的合集是 C，所以增加节点 C，由于状态 C 在 NFA 中是一个终止状态，所以 DFA 中的状态 C 也标记为终止状态。
• 初始状态 B 在遇到 0 时不进行状态转换；
• 初始状态 B 在遇到 1 时进入状态的合集仍是 B,C；
• 初始状态 B 在遇到 2 时进入状态的合集是 C，
• 初始状态 C 在遇到 0 时不进行状态转换；
• 初始状态 C 在遇到 1 时不进行状态转换；

• 初始状态 C 在遇到 2 时进入状态的合集仍是 C；

  NFA 到 DFA 的算法实现

  由于与 NFA 等价的 DFA 中的每一个状态都是一个 NFA 状态集合的子集。因此，从 NFA 到 DFA 的转换方法也叫子集构造法。
  
  子集构造法中空闭包的算法实现
  

  识别单词的 DFA

  识别标识符的 DFA

  

• letter连接letter|digit

• 克林闭包、连接、或的 DFA 画法可见本文的 “从 RE 到 NFA 的转换” 部分

  识别无符号数的 DFA

  

• 由 RE 转换为 NFA：

• 无符号数的 RE 由三部分构成：digits、optionalFraction、optionalExponent
• 第一部分是长度大于等于 1 的数字串
• 第二部分是可选的小数部分，它的 RE 由两个子表达式或运算得到
• 第三部分是可选的指数部分，它的 RE 由两个子表达式或运算得到

由于这个 NFA 中含有空边，所以我们需要将该 NFA 转换为等价的 DFA。

• NFA 的初始状态也是 DFA 的初始状态 0
• 状态 0 在遇到 d 时，既可以进入到状态 1 也可以沿着空边进入状态 3 还可以沿着空边进入状态 6。即状态 0 在遇到 d 时，可以进入状态 1，3，6。因此，我们在 DFA 中构造一个新的状态，该状态是由状态 1，3，6 构成的状态集合。
• 状态 1，3，6 中状态 1 遇到 d 时，可以进入状态 1，3，6
• 状态 1，3，6 中状态 1 遇到.时，进入状态 2
• 状态 1，3，6 中状态 3 遇到 E 时，可以进入状态 4，5
• 状态 2 遇到 d，可以进入状态 3，6
• 状态 3，6 中状态 3 遇到 d 时，可以进入状态 3，6
• 状态 3，6 中状态 3 遇到 E 时，可以进入状态 4，5
• 状态 4，5 中状态 4 遇到+或-时，进入状态 5
• 状态 4，5 中状态 5 遇到 d 时，进入状态 6
• 状态 5 中遇到 d 时，进入状态 6
• 状态 6 中遇到 d 时，仍进入状态 6

检验该 DFA 能否识别无符号数：

• 从初始状态 0 遇到 d 进入状态 136，该状态可以接受若干数字，若之后不再遇到其他符号，则该 DFA 成功接受一个整数。
• 若之后遇到.，则需要继续接受小数部分，进入状态 2，遇到 d 进入状态 36，该状态可以接受若干数字，若之后不再遇到其他符号，则该 DFA 成功接受一个小数。
• 若之后遇到E，则需要继续接受指数部分，进入状态 45。
• 也可以直接在整数部分接受 E，连接一个指数部分。

• 综上，该 DFA 能识别无符号数

  识别各进制无符号整数的 DFA

  

• 左边从上至下分别是十、八、十六进制的 DFA

• 右上角是整合了十、八、十六进制 DFA 的 DFA
• 从初始状态遇到 1-9 中的一个数字，进入状态 1，继续接受若干个 0-9 中数字构成的数字串，最终识别到十进制整数，识别完成后以 token 形式表示该单词，种别码是 DEC，value 是属性值。
• 从初始状态遇到 0，可以进入状态 2，3，5，因此构造一个新的状态 235，如果在该状态之后，输入串不再有其他符号，则这时输入的 0 被识别为一个十进制的整数 0，种别码是 DEC，属性值是 0。
• 状态 235 遇到数字 1-7 中的一个数字，进入状态 4，继续接受若干个 0-7 中数字构成的数字串，最终识别到八进制数，识别完成后以 token 形式表示该单词，种别码是 OCT，value 是属性值。

• 状态 235 遇到数字 x 中的一个数字，进入状态 6，状态 6 遇到 1-f 中的数字，进入状态 7，继续接受若干个 0-f 中数字构成的数字串，最终识别到十六进制数，识别完成后以 token 形式表示该单词，种别码是 HEX，value 是属性值。

  识别多行注释的 DFA

  

• 初始状态 0 识别到/，进入状态 1，表示当前串以/结尾；

• 若之后遇到，进入状态 2，表示当前串以/结尾；
• 若之后遇到任何符号，都保持在状态 2，表示注释内容；
• 若之后遇到，进入状态 3，表示注释结束的那个；
• 若之后再遇到，则一直保持在状态 3，表示当前串以结尾；
• 若之后再遇到/，则进入状态 4，此时则可以成功接收到一个注释。

• 若在状态 3 遇到到除*和/的其他符号，则退回状态 2，说明注释内容还没结束。

  识别单词的 DFA

• 将上面的 DFA 都整合起来，则可以得到词法分析中识别单词的 DFA。

• 将识别出的单词转换成统一的机内表示—— 词法单元 (token) 形式。

• 该 DFA 可识别出关键字、标识符、数字 (常量)、运算符、界符
• 该 DFA 从初始状态开始，从左至右，逐个扫描输入串中的每个单词，每当识别出一个单词，就把它表示成 token 形式，然后退回到初始状态，继续识别下一个单词。
• 该 DFA 图中没有提到识别关键字。事实上，关键字是由字母组成的，我们可以由识别标识符的 DFA 来识别关键字。

• 每当识别出一个标识符，就查一下关键字表，如果该字符串在关键字表中，那么就把该字符串识别为关键字，反之，把该字符串识别为一个普通的标识符。

  词法分析器的错误处理

• 词法分析阶段可检测错误的类型

  • 单词拼写错误
    • 【例】int i = 0x3G; float j =1.05e;
  • 非法字符
    • 【例】 ~@
• 词法错误检测的实现原理
  • 如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序。
    • 即当前状态不可以遇到当前输入符
• 错误处理程序的处理步骤
  • 查找已扫描字符串中最后一个对应于某终态的字符
    • 如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词
    • 如果没找到，则确定出错，采用错误恢复策略
• 错误恢复策略
  • 最简单的错误恢复策略：“恐慌模式 (panic mode)” 恢复
    • 从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止