编译原理词法分析

一、正规文法和正规式

1、文法与自动机的关系

0型文法（短语结构文法）：其能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的。
1型文法（上下文有关文法CSG）：产生式的形式为 $α_1Aα_2\toα_1βα_2$ ，即只有 $A$ 出现在 $α_1$ 和 $α_2$ 的上下文中时，才允许 $β$ 取代 $A$ 。其识别系统是线性有界自动机。
2型文法（上下文无关文法CFG）：产生式的形式为 $A\toβ$ ， $β$ 取代 $A$ 时与 $A$ 的上下文无关。其识别系统是不确定的下推自动机。
3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合。

2、正规文法与正规式

单词符号结构的描述方法：
- 正规文法（3型文法）
- 正规式（正则表达式）

正规表达式（正则表达式）(regular expression)
是说明单词模式(pattern)的一种重要的表示法(记号)，是定义正规集的数学工具。

在编译中，用以描述单词符号。

定义（正规式和它所表示的正规集）：

设字母表为 ∑，辅助字母表 ∑'={ Φ ，ε ，| ，• ，*，( ，) }

Φ 和 ε 都是 ∑ 上的正规式，它们所表示的正规集分别为 {ε} 和 {} ；
任何 a∈∑，a 是 ∑ 上的一个正规式，它所表示的正规集为 {a} ；
假定e₁ 和 e₂ 都是 ∑ 上的正规式，它们所表示的正规集分别为 L(e₁) 和 L(e₂) ，那么，(e₁) , e₁| e₂, e₁•e₂, e^* 也都是正规式,它们所表示的正规集分别为
L(e₁) , L(e₁)∪L(e₂), L(e₁)L(e₂) 和 (L(e₁))^* 。
仅由有限次使用上述三步骤而定义的表达式才是 ∑ 上的正规式，仅由这些正规式所表示的集合才是 ∑ 上的正规集。

正规式中的符号
- “ $|$ ” 读为“或”（也有使用“ $+$ ”代替“ $|$ ” 的）；
- “ $•$ ” 读为 “连接 ”；
- “ $*$ ”读为“闭包”（即任意有限次的自重复连接。

在不致混淆时，括号可省去，但规定算符的优先顺序为“ * ”、“ • ”、“ | ” 。连接符“ • ”一般可省略不写。“ * ”、“ • ”和“ | ”都是左结合的。

3、正规式等价

若两个正规式 $e_1$ 和 $e_2$ 所表示的正规集相同,则说 $e_1$ 和 $e_2$ 等价,写作 $e_1 = e_2$

例如： $e_1= (a|b)， e_2 = b|a$

又如：

${e_1= b(ab)^* , e_2 = (ba)^*b}$

$e_1= (a|b)^*, e2=(a^*|b^*)^*$

正规式等价变换规则：

设r,s,t为正规式，正规式服从的代数规律有：
1. “或”服从交换律： $r|s=s|r$
2. “或”的可结合律： $r|(s|t)=(r|s)|t$
3. “连接”的可结合律： $(rs)t=r(st)$
4. 分配律： $r(s|t)=rs|rt$ ， $(s|t)r=sr|tr$
5. 零一律(ε是“连接”的恒等元素)： $εr=r$ ， $rε=r$
6. “或”的抽取律: $r|r=r$ ， $r^*=ε|r|rr|\dots$

4、正规式到正规文法

5、正规文法到正规式

对 $G=(V_N,V_T,P,S)$ ,存在一个 $\sum =V_T$ 上的正规式 $r : L(r)=L(G)$

$A→xB, B→y ≈ A=xy$
$A→xA|y ≈ A=x→y$
$A→x|y ≈ A=x→y$

二、自动机

有穷自动机：

有穷自动机(有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具

有穷自动机分为两类：

确定的有穷自动机(Deterministic Finite Automata) ：DFA
不确定的有穷自动机(Nondeterministic Finite Automata) ：NFA

1、DFA : 确定的有穷自动机

DFA定义：

一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z），其中:

K 是一个有穷集，它的每个元素称为一个状态；
Σ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
f 是转换函数，是在 K×Σ→K 上的映射，即，如 f（ki，a）=kj ，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态 kj ，我们把 kj 称作 ki 的一个后继状态；
S∈K是唯一的一个初态；
Z⊂K是一个终态集，终态也称可接受状态或结束状态。

∑^*上的符号串 t 在DFA M上运行：

一个输入符号串t，（将它表示成 Tt₁的形式，其中T∈∑，t₁∈ ∑^*）在DFA M=（K，Σ，f，S，Z）上运行的定义为：
f（Q， Tt₁）=f（f（Q，T），t₁），其中Q∈K 扩充转换函数 f 为 K×Σ^*→ K上的映射，且： f（k_i，ε）= k_i

∑^*上的符号串 t 被 DFA M接受：

M=（K，Σ，f，S，Z）
若t∈ ∑^*，f（S，t）=P，其中S为M的开始状态，P ∈ Z，Z为终态集，则称t为DFA M所接受（识别）。

DFA M所能接受的符号串的全体记为L(M)

对于任何两个有穷自动机M和M′，如果L(M)=L(M′)，则称M与M′是等价的

结论：
∑ 上一个符号串集 V⊂∑^* 是正规的，当且仅当存在一个 ∑ 上的确定有穷自动机M，使得 V=L(M)

DFA的确定性表现在转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态
从状态转换图来看，若字母表Σ含有n个输入字符，那么任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记

2、NFA : 不确定的有穷自动机

定义：
NFA M=(K，∑，f，S，Z)，其中:

K为状态的有穷非空集
∑为有穷输入字母表
f为 K×∑* 到 K 的子集（2^K）的一种映射
S⊆K 是初始状态集
Z⊆K 为终止状态集

f为 K×∑* 到 K 的子集（2^K）的一种映射

对任何一个具有 ε 转移的不确定的有穷自动机NFA N，一定存在一个不具有 ε转移的不确定的有穷自动机NFA Ｍ，使得L(M)=L(N)

∑^*上的符号串 t 在NFA M上运行:

一个输入符号串t，（我们将它表示成Tt₁的形式，其中T∈∑，t₁∈ ∑*）在NFA M上运行的定义为：
f（Q，Tt₁）=f（f（Q，T），t₁）其中Q∈K

∑^*上的符号串t被NFA M接受：

若t ∈ ∑*，f(S₀，t)=P，其中S₀ ∈S，P ∈ Z，则称
t为NFA M所接受（识别）
也可以这样理解：
对于 Σ^*中的任何一个串 t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为 ε的弧)等于 t ，则称 t 可为NFA M所识别(读出或接受)。
若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路，其上所有弧的标记均为 ε，那么空字可为 M 所接受。

NFA M所能接受的符号串的全体记为L(M)

结论：
∑ 上一个符号串集V ⊂ ∑ ^* 是正规的，当且仅当存在一个 ∑ 上的不确定的有穷自动机M，使得 V=L(M)

DFA是NFA的特例。对每个NFA N一定
存在一个DFA Ｍ, 使得 L(M)=L(N)；
对每个NFA N存在着与之等价的DFA M
有一种算法,可以将NFA转换成接受同样语言的DFA.这种算法称为子集法
与某一NFA等价的DFA不唯一

从NFA的矩阵表示中可以看出，表项通常是一状态的集合，

而在DFA的矩阵表示中，表项是一个状态，

NFA到相应的DFA的构造的基本思路是：
- DFA的每一个状态对应NFA的一组状态

DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态

3、NFA确定化算法

NFA N = (K, ∑, f, K₀, K_t) , 按如下方法构造一个DFA M=(S, ∑, d, S₀, S_t), 使得L(M)=L(N)：

M 的状态集 S 由K的一些子集组成。用 [S₁ S₂... S_j] 表示 S 的元素，其中S₁ ，S₂... S_j 是K的状态。并且约定，状态S₁ ，S₂... S_j 是按某种规则排列的，即对于子集 {S₁, S₂}={ S₂, S₁} 来说，S的状态就是[S₁S₂]
M和N的输入字母表是相同的，即为 ∑
转换函数是这样定义的：
$d([S_1S_2...S_j], a) = [R_1R_2...R_t]$ ，其中
${R_1, R_2, ... , R_t}= ε-closure(move({S_1,S_2,…,S_j},a))$
$S_0=ε-closure(K_0)$为 M 的开始状态；
S_t={[S_i S_k ... S_e] ，其中[S_i S_k ... S_e]∈S 且 {S_i, S_k, … , S_e}∩ K_t ≠ Φ}

4、构造NFA N状态K的子集的算法

假定所构造的子集族为C，即C= (T₁, T₂,,... T_I),其中T₁, T₂,,... T_I为状态K的子集。

开始，令e-closure(K0)为C中唯一成员，并且它是未被标记的。

while （C中存在尚未被标记的子集T）do {                                   
标记T；
for 每个输入字母a   do    {
    U:= ε-closure(move(T,a))；
     if  U不在C中  then
     将U作为未标记的子集加在C中 
}                              
}