编译原理笔记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的代数定律

定律	描述
r \| s = s \| r	\| 是可以交换的
r \| ( s \| t ) = ( r \| s ) \| t	\| 是可结合的
r ( s t ) = ( r s ) t	连接是可结合的
r ( s \| t ) = r s \| r t ; ( s \| t ) r = s r \| t r	连接对 \| 是可分配的
εr=rε=r	ε 是连接的单位元
r* = ( r \| s )*	克林闭包中一定包含 ε
r ** = r *	克林闭包具有幂等性

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

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

正则定义

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

正则定义是具有如下形式的定义序列

d₁→r₁
d₂→r₂
…
d_n→r_n

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

其中：

每个 d_i 都是一个新符号，它们都不在字母表 Σ中，而且各不相同
每个 r_i 是字母表 Σ∪{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 )$$

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×Σ映射到2^S的转换函数。∀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";

函数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)”恢复
  - 从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止