编译原理复习笔记-词法分析

词法分析的几个问题

术语

• 模式(pattern)：产生和识别元素的规则
• 记号(token)： 按照某个模式(或规则)识别出的元素(一组)。记号的区分:记号=记号的类别+记号的属性
• 单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值

作用

• 滤掉源程序无用成分
• 处理与平台有关输入
• 根据模式识别记号，并交给语法分析器
• 调用符号表管理器或出错处理器，进行相关处理 。

工作方式

• 单独扫描，产生记号流供语法分析器使用。
• 作为语法分析器的子程序，并行工作。

模式的形式化描述

语言L是有限字母表∑上有限长度字符串的集合。（注意：字符表有限，字符串长度有限）

令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:

1. ε是正规式，它表示集合L(ε)={ε}
2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a}
3. 若正规式r和s分别表示集合L(r)和L(s)，则

• r|s是正规式，表示集合L(r)∪L(s)，
• rs是正规式，表示集合L(r)L(s)，
• r*是正规式，表示集合(L(r))*，
• (r)是正规式，表示的集合仍然是L(r)

可用正规式描述的语言称为正规语言或正规集。

运算性质

1. 三种运算(并，连接，闭包)具有左结合性
2. 优先级：闭包>连接>或。
3. 不同正规式可表示同一个正规集，即正规式与正规集是多对一。
4. 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P = Q。
5. 等价性判断：根据定义或代数性质。

• r | s = s | r
• ( r s ) t = r ( s t )
• r | ( s | t ) = ( r | s ) | t
• ε r = r, r ε = r
• r ( s | t ) = r s | r t
• r* = ( r+ | ε )
• ( s | t ) r = s r | t r
• r** = r*

简化正规式的几个技巧

• 正闭包：r+ = r r* = r* r，r* = r+ | ε
• 可缺省：r?=r|ε
• 仅由|运算构成的正规式，则可改写为[r]，其中包括枚举或分段。
• [r]是一个字符组形式的正规式，则[^r]是表示∑ - L(r)的正规式。

记号的识别——有限自动机

模式的描述使用正规式，记号的识别使用有限自动机。

有限自动机：M =（S，∑，move，s0，F），其中

1. S是有限个状态（state）的集合；
2. ∑是有限个输入字符（包括ε）的集合；
3. move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
4. s0是唯一的初态（也称开始状态）；
5. F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。

有限自动机的几点说明

• 最长识别原则：如<=的识别。
• 不确定性：在当前状态下对同一字符有多于一个的下一状态转移。 （反复试探，指数增长，大量回溯）

DFA：NFA的特例，具有确定性。

1. 没有状态具有 ε 状态转移
2. 对每个状态 s 和每个字符 a ，最多有一个下一状态。

有限自动机之间的等价性： 若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。

正规式与有限自动机从两个侧面表示正规集。正规式是描述，自动机是识别。因此，当它们表示相同集合时，均存在等价的问题。

从正规式到词法分析器

步骤： 描述（正规式描述模式）-构造NFA（一对一构造）-确定化（等价的DFA）-最小化（最少的状态数）-构造词法分析器

从正规式到NFA：Thompson算法

先用语法树右分解正规式，再自下而上构造NFA。

1. 对ε，构造NFA N(ε) 接受{ε}：直接构造
2. 对∑上的每个字符a，构造NFA N(a) 接受{a}：直接构造
3. 若N(p)和N(q)是正规式p和q的NFA，则

1. 对正规式p|q，构造NFA N(p|q)：接受L(p)∪L(q):把初态和终态取出合并，且增加初态和终态两条ε的路径
2. 对正规式pq，构造NFA N(pq) 接受L(p)L(q):把N(p)的终态和N(q)初态合并
3. 对正规式p*，构造NFA N(p*) 接受L(p*)：增加从初态到终态的ε路径，且在N(p)内部有从最后指向最前的ε路径
4. 对于正规式(p)，使用p本身的NFA，不再构造。

确定化：从NFA到DFA

• 并行 用状态集取代状态，将不确定的下一状态确定化。 状态集：ε闭包（路径上是ε相连的状态）+ smove(S,a)
• 子集法 将路径确定化并记录下来，得到等价的DFA。

方法：将并行法每一个状态集编号，得到编号之间的转换关系。

最小化DFA

若从s和t来分析序列w均可得到相同的结果，则s,t是不可区分的，即可合并的。最小化就是反向利用可区分。一开始，仅有非终态和各终态是可区分的，经过划分，把可区分的状态分离，直到不可分离，最后不可区分的状态合并成一个状态。
算法：

1. 初始划分：分为终态和非终态。
2. 反复分裂划分组：若某个集合某个元素可以指向已经被划分出来的元素，则将该元素划分出来，直到不可再分裂。
3. 选取代表，修改状态转移。
4. 消除死状态和不可达状态。

DFA构造词法分析器

1. 表驱动型的词法分析器:速度慢，程序与模式无关，规模大，可用工具生成
2. 直接编码的词法分析器：速度快，程序与模式有关，规模较小，需要手工编写