编译原理

Cpt 2 文法和语言

基本概念

形式语言是字母表上的符号按一定的规则组成的所有符号串集合；其中的每个符号串称为一个句子。

字母表∑是非空有穷集合，其元素称为符号。

符号串是由字母表∑中的符号组成的有穷序列称为 (字母表∑上的)符号串。特别地，不含任何符号的有穷序列称为空串，记为ε。

单词和源程序都是符号串

规则以某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成规则。

设a,b为两个符号串，则有以下运算:

连接：a.b = ab \\ 或：a|b = a或者b \\ 方幂：a^n = aa … a = aa^{n-1} = a^{n-1}a \\ 零幂：a^0 = ε \\ 正闭包：a^+ = a^1|a^2|…|a^n|… \\ 星闭包：a^* = a^0|a^1|a^2|…|a^n|…

设 A 和 B 为两个符号串集合，则有以下运算：

乘积： AB = { xy | x∈A 且 y∈B} \\ 和： A∪B = A+B = { x | x∈A 或 x∈B} \\ 方幂：A^n = AA…A = AA^{n-1} = A^{n-1}A \\ 零幂：A^0 = { ε }; \\ 正闭包：A^+ = A^1∪A^2∪…∪A^n∪… \\ 星闭包：A^* = A^0∪A^1∪A^2∪…∪A^n∪…

若 A 为任一字母表，则 A* 就是该字母表上的所有符号串的集合

文法G定义为一个四元组(V_N，V-T，P，S) \\ 记为 G ＝(VN，VT，P，S)。其中 \\ V_N是非空有穷集合，称为非终结符集，其元素称为非终结符； \\ V_T是有穷集合，称为终结符集，其元素称为终结符； \\ P是非空有穷集合，称为规则集，其元素是字母表V_N∪V_T上的规则， \\ V_N∪V_T称为文法的字母表 V，且V_N ∩ V_T＝ \emptyset； \\ S ∈ V_N ，称为开始符。 \\\\ 设文法 G ＝(V_N，V_T，P，S), 对于 β ∈ V^* = (V_N∪V_T)^* \\ 推导是从规则的左部变为右部，规约是从规则的右部变为左部 \\ 如果 S\xRightarrow{*}β ，则称 β 是文法 G 的句型 \\ 如果 β 是 G 的句型，且 β ∈ (V_T)^*，则称 β 是 G 的句子 \\\\ 文法G能够产生的所有句子的集合称为 G 的语言，记为 L(G) \\ L(G) = \{β︱S\xRightarrow{*}β，β ∈ {V_T}^*\}

文法类型

0型文法：规则左侧至少含有一个非终结符

1型文法：左侧符号串长度不大于右侧符号串长度（除了空规则），并使0型文法，又称上下文相关文法

2型文法：左侧都只有一个非终结符，且是1型文法

3型文法：如果任意 α→β∈ P，α∈ V_N ，且β只能是Ba或a（除空规则之外），则称文法G属于左线性3型文法,如果任意 α→β∈ P，α∈ V_N ，且β只能是aB或a（除空规则之外），则称文法G属于右线性3型文法。左线性3型文法和右线性3型文法，统称3型文法，也称为正规文法。

推导和二义性

如果在推导的每一步总是选择当前句型的最左（最右）边非终结符进行推导，则称这种推导过程为最左（最右）推导。最右推导，也叫规范推导。由规范推导所得的句型，叫做规范句型。规范推导的逆过程，叫做规范归约。如果一个文法存在某个句子对应至少两颗不同的语法树，则说这个文法是二义的，相当于说存在两种推导过程推出了同一个结果。

文法的二义性，并不等同于语言的二义性，尽管两者之间可能存在非必然的联系。因为二义性文法G，可能存在与之等价的无二义性的文法G′，即L(G)＝L(G′）。 如果一个语言不存在无二义性的文法，则称该语言是先天二义性的。文法的二义性判定问题是递归不可解的。即不存在这个判定问题的算法。

自下而上分析法：从输入符号串α开始，逐步进行“归约”，直至归约出文法的开始符号 S，则输入串α是文法G定义的语言的句子。否则不是

短语、简单短语和句柄

某个非终结符 A 在推导过程中推导出来的终结符串，那么这一串就叫做句型 xαy 关于 A 的短语

简单短语：某非终结符一步直接推出的一段串

句柄：最左简单短语

Cpt 3 词法分析

状态转换图

状态转换图是一张有限方向图，结点代表状态，用圆圈表示，状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态，终态用双圈表示。

正规式与正规集

正规表达式（简称正规式）也可以表示正规集合(语言），一个符号串集合是正规集当且仅当它能用正规式表示，正规文法所描述的是 VTV_T 上的正规集。正规式和正规文法是描述正规集合（即正规语言）的不同方式。

对给定的字母表\Sigma \\ \epsilon和\emptyset都是\Sigma上的正规式，它们所表示的正规集为\{\epsilon\}和\emptyset，即L(\epsilon)＝ \{\epsilon\}， L(\emptyset)＝\emptyset; \\ 任何a\in \Sigma ，a是\Sigma上的正规式，它所表示的正规集为L(a)=\{a\} ; \\ 假定e1和e2都是\Sigma上的正规式，它们所表示的正规集为L(e1)和L(e2)，则 \\ (e1|e2)为正规式，它所表示的正规集为L(e1|e2)=L(e1)\cup L(e2) \\ (e1.e2)为正规式，它所表示的正规集为L(e1.e2)=L(e1)L(e2) \\ (e1)^*为正规式，它所表示的正规集为L((e1)^*)=(L(e1))^*

正规式和正规文法的转换

如果正规式r和文法G，有L(r)＝L(G)则称正规式r和文法G是等价的。从形如产生式 S→r 开始，按下表规则进行转换， 直到全部形如产生式， 符合正规文法之规则形式为止，可得到P和 VNV_N 。 反之则进行逆运算。

DFA和NFA

不确定的有穷自动机(NFA)：边上的标号没有限制，一个符号可出现在离开同一个状态的多条边上，ε可以做标号

确定的有穷自动机(DFA)：对于每个状态以及每个符号，有且只有一条边

两种自动机都识别正则语言，对于每个可以用正则表达式描述的语言，均可用某个NFA或DFA来识别；反之亦然。

DFA:M是一个五元式 M=(K, \Sigma, f, S, Z),其中： \\ K: 有穷状态集 \\ \Sigma : 输入字母表(有穷) \\ f: 状态转换函数，为K \times \Sigma \rightarrow K的单值部分映射，f(k_i，a)=k_j表示： \\ 当现行状态为k_i，输入字符为a时，将状态转换到下一状态k_j，k_j称为k_i的一个后继状态 \\ S\in K是唯一的一个初态 \\ Z\subseteq K: 终态集(可空)，也称可接受状态集或结束状态集 \\\\ NFA:M是一个五元式M=(K, \Sigma, f, S, Z),其中： \\ K: 有穷状态集 \\ \Sigma: 输入字母表(有穷) \\ f: 状态转换函数，为K\times \Sigma \cup \{ε\}\rightarrow2^K的部分映射，其中2^K表示K的幂集 \\ S \subset K是非空的初态（也可以为非空集合） \\ Z \subset K: 终态集 \\\\ f可以扩充为f': K\times \Sigma ^* \rightarrow K映射，并以f替代f'使用。设a \in \Sigma, β \in \Sigma ^*，q\in K \\ L(M)＝\{α|α\in \Sigma ^*, f’(S, α)\in Z \}

NFA转DFA

基本思想：构造得到的DFA的每个状态和NFA的状态子集对应，DFA读入a1, a2, …, an后到达的状态对应于从NFA开始状态出发沿着a1, a2, …, an可能到达的状态集合，在算法中“并行地模拟”NFA在遇到一个给定输入串时可能执行的所有动作。

ϵ−closure(s)\epsilon-closure(s) ：从NFA状态s开始，只通过e转换能到达的NFA状态集合

ϵ−closure(T)\epsilon-closure(T) ：从T中某个状态s开始，只通过e转换能到达的NFA状态集合

move(T,a)move(T, a) ：从T中某个状态s出发，通过一个标号为a的转换能到达的NFA状态集合，即 M(T,a)M(T,a)

设 NFA:M＝(K,\Sigma,f,S,Z)则与之等价的DFA:M'＝(K',\Sigma ',f',S',Z')，其中: \\ ⑴ K'＝ρ(K)(ρ(K) = 2^K) \\ ⑵ \Sigma '＝ \Sigma \\ ⑶ f'(q,a)＝\varepsilon _\text{closure(M(q,a))} \\ ⑷ S'＝\varepsilon _\text{closure(S)} \\ ⑸ Z'＝\{q︱q\subset K', q \cap Z ≠ \emptyset\} \\\\ 具体计算步骤可以是： \\ ① 置K'为空集； \\ ② 计算M'的开始状态S'＝\varepsilon _\text{closure(M(q,a))}， S'作为K'新增状态； \\ ③ 对于K'每一新增状态q，计算出每个a \in \Sigma的转换状态p， \\ 即f'(q,a) ＝p＝\varepsilon _\text{closure(M(q,a))}。如果p \notin K'，则p作为K'新增状态； \\ ④ 重复③，直到K'不再出现新增状态为止； \\ ⑤ 计算接受状态集Z'＝\{q︱q \in K',q \cap Z ≠ \emptyset\}

设字母表只包含两个 a 和b，构造一张表。首先，置第1行第1列为 ϵclosure(s0)\epsilon_\text{closure}({s_0}) 求出这一列的 T_a，T_b ；然后，检查这两个 T_a，T_b ，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合。重复上述过程，直到所有第2，3列子集全部出现在第一列为止。

初态是 ϵclosure(X)\epsilon_{closure}(X) ，终态是含有原终态Y的子集

DFA最小化

计算 DFA M的等价状态，然后将等价状态合并，得到最小化的DFA M’，使用分割法：

  1. 状态集K划分为两个状态子集{Z，K-Z}，记为P={Z，K-Z}；

  2. 如果 ∃I∈P ∃a∈Σ ∃J∈P [M(I,a)⊈J]即状态子集 I∈P 中至少存在两个 p 和 q，使得 f(p,a)∈J′ 和 f(q,a)∈J′′且 J′≠J′′ (J′,J′′∈P)则将 I 分割成 I′ 和 I′′，即 I′={r∣∀r∈I [f(r,a)∈J′]}, I′′=I−I′重置划分 P: P←(P−{I})∪{I′,I′′}. \text{如果 }\exists I\in\mathcal{P}\ \exists a\in\Sigma\ \exists J\in\mathcal{P}\ [M(I,a)\nsubseteq J] \\ \text{即状态子集 }I\in\mathcal{P}\text{ 中至少存在两个 }p\text{ 和 }q\text{，使得 }f(p,a)\in J' \text{ 和 } f(q,a)\in J'' \\ \text{且 }J'\neq J''\ (J',J''\in\mathcal{P}) \\ \text{则将 }I\text{ 分割成 }I'\text{ 和 }I''\text{，即 }I'=\{r\mid \forall r\in I\ [f(r,a)\in J']\},\ I''=I-I' \\ \text{重置划分 }\mathcal{P}:\ \mathcal{P}\leftarrow(\mathcal{P}-\{I\})\cup\{I',I''\}.

  3. 置重复2，直到满足 ∀I∈P, ∀a∈Σ, ∃J∈P 使得 [M(I,a)⊆J]\forall I\in\mathcal{P},\ \forall a\in\Sigma,\ \exists J\in\mathcal{P}\ \text{使得}\ [M(I,a)\subseteq J] 条件为止；

  4. 在M基础上，对于划分P的同一个状态子集中的全部状态及其相应的转换函数合并，最后所得即为最小化的M’。

NFA转化为正规式

首先，在M的转换图上加进两个状态X和Y，从X用e弧连接到M的所有初态结点，从M的所有终态结点用e弧连接到Y，从而形成一个新的NFA，记为M’，它只有一个初态X和一个终态Y，从正规式到NFA的转化则反过来变化就好了。