编译原理（二）词法分析

词法分析

说明：以老师PPT为标准，借鉴部分教材内容，AlvinZH学习笔记。

语法分析基础

1. 词法分析程序的功能

词法分析：根据词法规则识别及组合单词，进行词法检查；
对数字常数完成数字字符串到（二进制）数值的转换；
删去空格、换行、制表等字符和注释。

2. 实现方案

词法分析单独做一遍。结构清晰，个遍功能单一，但是效率低。
词法分析作为单独的子程序，由语法分析程序调用。结构较复杂，效率高。

3. 单词种类及输出形式
单词种类：保留字、标识符、常数、分界符等。

输出形式：二元式，<单词类别，单词值>。按单词种类分类，也可以将保留字和界符采用一符一类。

正则文法和状态图

状态图：用于识别（接受）一定的字符串。包含一个初始状态（初态），至少一个终止状态（终态）。画法比较简单：

注意：

利用状态图分析识别字符串——自底向上。
状态图只能用于左线性文法（形如A→Bb）。这是明显和后面的DFA区别之处。

正则表达式

1.正则表达式运算符：|选择、·连接、*重复、()括号。优先级：括号优先，先*后·最后|。

2.正则表达式与3型文法等价。相互转换后续讲解。

确定的有穷自动机（DFA）

1. DFA五元式定义：(M = (S, ∑, δ, S0, Z))。其中 (S) 为有穷状态集，(∑) 为输入字母表，(δ) 为状态转换函数（S×∑ → S的映射），(S_0) 为初始状态，(Z) 为终止状态集。

2. 何为确定？表现在 (δ) 中的状态转换函数是单值函数。

3. DFA不可接受 (ε)，DFA M所接受的语言为：(L(M) = { α|δ(S0, α)= Sn, Sn∈Z })。

非确定的有穷自动机（NFA）

1. 若 (δ) 是一个多值函数，且输入允许为 (ε)，则有穷自动机是不确定的。即对于某个输入字符存在多个后继状态。

2. NFA五元式定义：(M' = (S, Σ∪{ε}, δ, S0, Z))。(δ) 为状态转换函数（S×∑∪{ε} → 2^{S的映射，2}S：S的幂集，即S的子集构成的集合）。

3. NFA M'所接受的语言为：(L(M') = { α|δ( S0,α) = S’ S’∩Z≠Φ })。

NFA的确定化——子集法

1. 已经证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的。这意味着，对于NFA M'，可以构造出DFA M，使得L(M)=L(M')。

2. 集合 (I) 的 (ε) 闭包。(I) 是NFA状态集S的一个子集，则ε-closure(I)为：

若s∈I，则s ∈ ε-closure(I)；
若s∈I，则从 s 出发经过任意条ε弧能够到达的任何状态都属于ε-closure(I)。

简单理解，ε-closure(I)就是由I中所有状态接收字符ε得到的状态集。

3. 集合 (I) 对应 (Ia)。(I) 是NFA状态集 (S) 的一个子集，a∈∑，则 (I_a = ε-closure(J))，其中 (J = ∪ δ(S, a)，S∈I)。

简单理解，分为两步，第一步找到 (I) 中所有状态接收字符 (a) 得到的状态集 (J)，再求 (ε-closure(J))。

4. 确定化方法，过程如下。建议结合教材例子，实际求解过程画表格更清晰。

①求初始状态：S0 = ε-closure(S0')；
②for 每个状态
    for 每个x∈∑
      计算新状态Ix；
注：过程②出现的新状态也在循环中，直到不出现新状态为止；

包含NFA M'原初态的状态集为DFA M的初态；包含NFA M'原终态的状态集为DFA M的终态。

5.简单例子

DFA的最小化——分割法

1. 状态s和状态t等价条件：

一致性条件：状态s和t必须同时为接受状态或不接受状态。
蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。

2. 最小化方法：分割法。思路：把DFA所有状态分割成不相关的子集，使得任意两个子集状态是可区分的，而同一子集中状态是等价的。具体操作如下：

①区分终态和非终态，为区号1,2；（一致性条件）
②每个原状态，对于每个输入，对应后继状态的区号，全部相同的视为等价（暂时）；（蔓延性条件）
③由于过程②划分出新的区间，对应的区号有所改变，重复过程②直至没有新区间出现。

正则文法、正则表达式、NFA（DFA）相互转换

1. 有穷自动机M => 正则文法G

①对转换函数f(A, t) = B，可写成一个产生式:A→tB，其中t∈Vt，A、B∈Vn
②对可接受状态Z，增加一个产生式：Z→ε
③有穷自动机的初态对应于文法的开始符号，有穷自动机的字母表 ∑ 为文法的终结符号集Vt。

【例】

注意： 不知你注意到了没有，有穷自动机M转换出来的文法规则都是右线性的，这就体现了有穷自动机自顶向下的特点，在语法分析LR分析法中会用到这一特性。

2. 正则文法G=>有穷自动机M
【算法】

① M的字母表 ∑ 与G的终结符号 Vt 相同
②为G中的每个非终结符Vn生成M的一个新状态，G的开始符号S作为M的开始状态S
③增加一个新状态Z，作为NFA的终态
④对G中产生式形如A→tB，其中t为终结符或ε，A和B为非终结符，构造M的一个转换函数f(A, t) = B
⑤对G中的形如A→t的产生式，构造M的一个转换函数f(A, t) = Z

【例】

3. 正则表达式 => 有穷自动机M
【算法】

【例】

4. 有穷自动机M => 正则表达式
【算法】

【例】

5. 正则文法转正则表达式
【算法】

代入规则：对于A→xB，B→y，转换为A→xy；
消除递归规则：对于A→xA|y，转换为A→x*y；
BNF规则：对于A→x，A→y，转换为A→x|y。

6. 正则表达式转正则文法
【算法】

对任何正则式r，选择一个非终结符S作为识别符号，并产生产生式 S→r；
若x、y是正则式，对形为A→xy的产生式，重写为A→xB和B→y，其中B为新的非终结符，B∈Vn。同样，对于 A→x*y，重写为A→xA，A→y；对于A→x|y，重写为 A→x，A→y。

【例】将S = a ( a | d )* 转换成相应的正则文法

解： 1) S→a(a|d)*

S→aA
A→(a|d)*
S→aA
A→(a|d)A
A→ε
S→aA
A→aA|dA
A→ε

LEX扩展知识点

1. 一个LEX源程序主要由三个部分组成：规则定义式、识别规则、用户子程序。各部分之间用%%隔开。实质是是一个有穷自动机。

规则定义式：形如D1→R1，其中D1为正则表达式名字（简名），R1为正则表达式。如digit →0|1|……|9。
识别规则：形如P1 {A1}，其中P1为词形，为在Σ∪{D1,D2,¨¨Dn}上的正则表达式；A1为语句序列，指出在识别出词形为Pi的单词以后，词法分析器所应作的动作。其基本动作是返回单词的类别编码和单词值。如digit(digit)* {RETURN(9,DTB }。

.2. 二义性处理原则：最长匹配原则；最优匹配原则。

引用说明

- 邵老师课堂PDF
- 《编译原理级编译程序构造》