前言

目前以手中这本清华大学出版社出版的编译原理(第3版，张素琴等编著)作为复习总结，因为考试都是大题，一部分概念会被忽略。所有内容都需要通过举例和推导来帮助加深理解，优先为过几天的考试服务。该文实现了教材中那些特别复杂的推导符号，并且这几天会加紧持续更新。

第2章 文法和语言

符号和符号串

空符号串用\(\varepsilon\)表示，长度为0

若 \(\Sigma=\{0,1\}\) ，则 \(\Sigma^*=\{\varepsilon,0,1,00,11,000,001,...\}\)，称 \(\Sigma^*\) 为集合 \(\Sigma\) 的闭包；\(\Sigma^+=\{0,1,00,11,000,001,...\}\)，称\(\Sigma^+\)为集合\(\Sigma^+\)的正闭包。

文法和语言的形式定义

规则或产生式或生成式，表示为 \(\alpha\rightarrow\beta\) 或 \(\alpha::=\beta\)

文法 \(G\) 定义为四元组 \((V_N, V_T, P, S)\)
\(V_N\)为非终结符集合
\(V_T\)为终结符集合
\(P\)为规则集
\(S\)为识别符或开始符

例如：
\(G[S]:S\rightarrow0S1\)
\(S\rightarrow01\)

直接推导用 \(\Rightarrow\)，如 \(0S1\Rightarrow 00S11\)
长度为\(n(n\geq1)\)的推导用 \(\stackrel{+}{\Rightarrow}\)，如\(S\stackrel{+}{\Rightarrow} 000S111\)
长度为\(n(n\geq0)\)的推导用 \(\stackrel{*}{\Rightarrow}\)，如\(S\stackrel{*}{\Rightarrow} 000S111 \stackrel{*}{\Rightarrow} 000S111\)

句型：对\(S\stackrel{*}{\Rightarrow}x\)，称x是文法G[S]的句型。x可以包含非终结符
句子：若上述x仅由终结符构成，则x是文法G[S]的句子
短语：若\(S\stackrel{*}{\Rightarrow}\alpha A\delta\) 且\(A\stackrel{+}{\Rightarrow}\beta\)，则称 \(\beta\) 为句型 \(\alpha A\delta\) 相对于非终结符\(A\)的短语
直接短语：特别的，若\(A\Rightarrow \beta\)，则称 \(\beta\) 为句型 \(\alpha A\delta\) 相对于规则\(A\rightarrow \beta\)的直接短语
句柄：规范句型的直接短语

文法描述的语言 是 该文法一切句子的集合，如：
\(L(G[S])=\{0^n1^n|n\geq1\}\)

文法类型

文法类型	每个产生式\(\alpha\rightarrow\beta\)的特点
0型文法	\(\alpha\in(V_N\cup V_T)^*\)且至少含一个非终结符，且\(\beta\in(V_N\cup V_T)^*\)
1型 或 上下文有关文法	在0型文法的基础上，还满足\(\mid\beta\mid\geq\mid\alpha\mid\)，仅\(S\rightarrow\varepsilon\)除外
2型 或 上下文无关文法	\(\alpha\)是一个非终结符，\(\beta\in(V_N\cup V_T)^*\)
3型 或 正规文法	满足\(A\rightarrow aB\)或\(A\rightarrow B\)的形式，即\(\beta\)中只有1个非终结符，以及0或1个终结符

最左推导：在推导\(\alpha\Rightarrow\beta\)中，对\(\alpha\)中最左非终结符进行替换
最右推导：又称作规范推导，所推导得到的句型称为右句型，或规范句型

二义性：一个文法存在某个句子对应两棵不同的语法树

语法树

已知文法\(G[S]:\)
\(S\rightarrow aAS\)
\(A\rightarrow SbA\)
\(S\rightarrow a\)
\(A\rightarrow ba\)

文法G的句型aabbaa的一颗推导树为：

文法限制

有害规则：如\(U\rightarrow U\)，只会引发二义性
多余规则：非终结符D不在任何规则的右部出现，即不可到达的

这一章的可能考点

1. 已知文法求语言
2. 已知语言求文法
3. 列出句型的短语、直接短语、句柄
4. 语法树、最左推导、规范推导

第3章 词法分析

正规式

正规式	含义
\(a\)	仅a
\(a\mid b\)	该字符可以为a或b
\(ab\)	字符a后面紧跟b
\(a^*\)	n(n>=0)个连续的a
\((a\mid b)b\)	ab或bb

正规文法与正规式的等价性

正规式转化为正规文法

对\(A\rightarrow x^*y\)型正规产生式，重写为：
\(A\rightarrow xB\)
\(A\rightarrow y\)
\(B\rightarrow xB\)
\(B\rightarrow y\)

对\(A\rightarrow x\mid y\)型正规产生式，重写为：
\(A\rightarrow x\)
\(A\rightarrow y\)

正规文法转化为正规式

	文法产生式	正规式
规则1	\(A\rightarrow xB\) 和 \(B\rightarrow y\)	\(A=xy\)
规则2	\(A\rightarrow xA\mid y\)	\(A=x^*y\)
规则3	\(A\rightarrow x\) 和 \(A\rightarrow y\)	\(A=x\mid y\)

有穷自动机

确定的有穷自动机(DFA)

确定的有穷自动机\(M\)是一个五元组：\(M=(K,\Sigma,f,S,Z)\)
\(K\)是一个有穷状态集
\(\Sigma\)是一个输入符号表
\(f\)是状态转换函数，例如\(f(k_i,a)=k_j (k_i,k_j\in K)\)
\(S\in K\)，是唯一的一个初态
\(Z\subseteq K\)，是一个终态集

DFA的确定性表现在转换函数 \(f:K\times\Sigma\rightarrow K\) 是一个单值函数

例如： DFA \(M=(\{S,U,V\}, \{a,b\}, f, S, \{V\})\)
\(f(S,a)=U\)
\(f(S,b)=V\)
\(f(U,b)=V\)
\(f(V,a)=U\)

现验证\(bab\)是否为\(M\)所接受，因为：
\(f(S, bab)=f(f(S,b), ab)=f(V,ab)=f(f(V,a),b)=f(U,b)=V\)，而\(V\)属于终态，故\(bab\)可为\(M\)接受。

不确定的有穷自动机(NFA)

不确定的有穷自动机\(M\)是一个五元组：\(M=(K,\Sigma,f,S,Z)\)
\(K\)是一个有穷状态集
\(\Sigma\)是一个输入符号表
\(f\)是\(K\times\Sigma^*\rightarrow 2^K\)的多值映像，即允许函数值有多种结果
\(S\in K\)，是非空初态集
\(Z\subseteq K\)，是一个终态集

NFA可以使用空转移，但DFA不可以。例如：\(f(0, \varepsilon)=\{0,3\}\)

NFA转换为等价DFA

状态集合\(I\)的\(\varepsilon-\)闭包，表示为\(\varepsilon-closure(I)\)，是状态集\(I\)中的任何状态\(S\)经过任意条\(\varepsilon\)弧能到达的状态的集合。显然，状态集合\(I\)的任何状态\(S\)都属于\(\varepsilon-closure(I)\)

状态集合\(I\)的\(a\)弧转换，表示为\(move(I,a)\)，定义为状态集合J，其中J是所有那些可以从\(I\)中某一状态经过一条\(a\)弧而到达的状态全体

子集法

初始状态集	\(\varepsilon-closure(I)\)	a	b
\(\{0\}\)	\(\{0,1,2,4,7\}\)
\(T_0=\{0,1,2,4,7\}\)		\(\{3,8\}\)	\(\{5\}\)
\(\{3,8\}\)	\(\{1,2,3,4,6,7,8\}\)
\(\{5\}\)	\(\{1,2,4,5,6,7\}\)
\(T_1=\{1,2,3,4,6,7,8\}\)		\(\{3,8\}\)	\(\{5,9\}\)
\(T_2=\{1,2,4,5,6,7\}\)		\(\{3,8\}\)	\(\{5\}\)
\(\{5,9\}\)	\(\{1,2,4,5,6,7,9\}\)
\(T_3=\{1,2,4,5,6,7,9\}\)		\(\{3,8\}\)	\(\{5,10\}\)
\(\{5,10\}\)	\(\{1,2,4,5,6,7,10\}\)
\(T_4=\{1,2,4,5,6,7,10\}\)		\(\{3,8\}\)	\(\{5\}\)

重命名状态集	a	b
\(T_0\)	\(T_1\)	\(T_2\)
\(T_1\)	\(T_1\)	\(T_3\)
\(T_2\)	\(T_1\)	\(T_2\)
\(T_3\)	\(T_1\)	\(T_4\)
\(T_4\)	\(T_1\)	\(T_2\)

DFA的最小化

1. 将\(P\)划分为终态集与非终态集，得\(P'=\{N,T\}\)
2. 递归地分割\(P'\)中的子集，使得被分割的子集中的所有状态都能够根据不同的输入符号转换到被分割的目标子集中的所有状态
3. 直到不可再被分割后，将\(P'\)中的每个子集合并为一个状态。含原初态的状态为初态，而含原终态的状态为终态。

\(P=\{1,2,3,4,5,6,7\}\)被划分为\(P_0=\{\{1,2,3,4\},\{5,6,7\}\}\)

在非终态集中，在1和2构成集合时，通过a可以到达终态集，通过b可以到达3。而3,4通过b到达的是终态集，显然有区别，故划分为\(P_1=\{\{1,2\},\{3,4\},\{5,6,7\}\}\)

在6和7构成集合时，通过a可以到达4，通过b可以到达集合{1,2}，而5通过a到达的是7，显然有区别，故划分为\(P_2=\{\{1,2\},\{3,4\},\{5\},\{6,7\}\}\)

由于3通过a到达集合{1,2}，而4通过a到达4，有明显区分，故划分为\(P_3=\{\{1,2\},\{3\},\{4\},\{5\},\{6,7\}\}\)

最后不能再划分了，因此令1代表{1,2}，消去2，令6代表{6,7}，消去7.最终得到的为最小化的DFA \(M'\)

正规式和有穷自动机的等价性

略

正规文法和有穷自动机的等价性

略

这一章的可能考点

1. 根据文法构造DFA，或给定NFA转DFA
2. DFA的最小化
3. 正规文法、正规式、有穷自动机之间的转换

第4章 自顶向下的语法分析方法

确定的自顶向下分析思想

开始符号集或首符号集：设\(G=(V_T,V_N,P,S)\)是上下文无关文法。
\(FIRST(\alpha)=\{a \mid\alpha \stackrel{*}{\Rightarrow} a\beta, a\in V_T, \alpha,\beta\in V^*\}\)

若\(\alpha \stackrel{*}{\Rightarrow} \varepsilon\)，则规定\(\varepsilon \in FIRST(\alpha)\)，称\(\varepsilon \in FIRST(\alpha)\)为\(\alpha\)的开始符号集或首符号集

简单来说，就是查看该句型推导出的所有句子的首字母集合。

例如文法\(G[S]:\)
\(S\rightarrow Ap\)
\(S\rightarrow Bq\)
\(A\rightarrow aA\)
\(A\rightarrow \varepsilon\)
\(B\rightarrow Bb\)
\(B\rightarrow b\)

那么\(FIRST(S)=\{a,b,p\}\)，\(FIRST(A)=\{a,\varepsilon\}\)，\(FIRST(B)=\{b\}\)

FOLLOW集：设\(G=(V_T,V_N,P,S)\)是上下文无关文法，\(A\in V_N\)，S是开始符号
\(FOLLOW(A)=\{a\mid S\stackrel{*}{\Rightarrow}\mu A\beta且a\in V_T,a\in FIRST(\beta), \mu\in {V_T}^*, \beta\in V^+\)
若\(S \stackrel{*}{\Rightarrow}\mu A\beta\)，且\(\beta \stackrel{*}{\Rightarrow}\varepsilon\)，则 \(\# \in FOLLOW(A)\)

简单来说，就是查看该句型在被推导前后面跟随的所有可能的第一个字母的集合。需要将出现在推导式左边的非终结符往

例如之前的文法\(G[S]\)，\(FOLLOW(S)=\{\#\}\)，\(FOLLOW(A)=\{p\}\)，\(FOLLOW(B)=\{b,q\}\)

选择符号集：一个产生式的选择符号集SELECT。给定上下文无关文法的产生式\(A\rightarrow \alpha, A\in V_N, \alpha\in V^*\)，若\(a\stackrel{*}{\nRightarrow}\varepsilon\)，则\(SELECT(A\rightarrow\alpha)=FIRST(\alpha)\)

而如果\(a\stackrel{*}{\Rightarrow}\varepsilon\)，则\(SELECT(A\rightarrow\alpha)=(FIRST(\alpha)-\{\epsilon\})\cup FOLLOW(A)\)。

求出选择符号集，是为了找到哪些符号应该使用该推导。那么，如果\(A\rightarrow \alpha\)不能推出空串，显然 从该推导得到的所有句子的首字母构成的集合 来反向看出 哪些字母应该使用该推导。而如果\(A\rightarrow \alpha\)能推出空串，则还要考虑该非终结符的后跟字符。

一个上下文无关文法是LL(1)文法的充要条件，是对每个非终结符A的两个不同产生式，\(A\rightarrow\alpha, A\rightarrow\beta\)，满足
\[SELECT(A\rightarrow\alpha)\cap SELECT(A\rightarrow\beta)=\emptyset\]

例如文法\(G[S]:\)
\(S\rightarrow aA\)
\(S\rightarrow d\)
\(A\rightarrow bAS\)
\(A\rightarrow \varepsilon\)

有：
\(SELECT(S\rightarrow aA)=\{a\}\)
\(SELECT(S\rightarrow d)=\{d\}\)
\(SELECT(A\rightarrow bAS)=\{b\}\)
\(SELECT(A\rightarrow \varepsilon)=\{a,d,\#\}\)

所以：
\(SELECT(S\rightarrow aA)\cap SELECT(S\rightarrow d)=\{a\}\cap\{d\}=\emptyset\)
\(SELECT(A\rightarrow bAS)\cap SELECT(A\rightarrow \varepsilon)=\{b\}\cap\{a,d,\#\}=\emptyset\)

LL(1)文法的判别

LL(1)的含义：第1个L 表明 从左向右扫描输入串，第2个L 表明 分析过程中将使用最左推导，1表明只需向右看一个符号就知道该选择哪个产生式推导。

1. 找出能推出\(\varepsilon\)的非终结符
2. 计算FIRST集
3. 计算FOLLOR集
4. 计算SELECT集
5. 进行判断

某些非LL(1)文法到LL(1)文法的等价变换

LL(1)文法的充分条件为不含左公共因子

提取左公共因子

例如\(A\rightarrow \alpha\beta\mid \alpha\gamma\)，可以写成：
\(A\rightarrow \alpha B\)
\(B\rightarrow \beta\)
\(B\rightarrow \gamma\)

一般情况如\(A\rightarrow \alpha_1\alpha_2...\alpha_n(\beta_1\mid\beta_2\mid...\mid\beta_n)\)，可以写成：
\(A\rightarrow\alpha_1 A_1\)
\(A_1\rightarrow\alpha_2 A_2\)
\(...\)
\(A_{n-1}\rightarrow\alpha_n B\)

\(B\rightarrow\beta_1\)
\(B\rightarrow\beta_2\)
\(...\)
\(B\rightarrow\beta_n\)

此外，还需要检查文法是否含有隐式的左公共因子，如：
\((1)A\rightarrow ad\)
\((2)A\rightarrow Bc\)
\((3)B\rightarrow aA\)

将(3)带入(2)，可暴露出左公共因子：
\((1)A\rightarrow ad\)
\((2)A\rightarrow aAc\)
\((3)B\rightarrow aA\)

可以看到此时(3)为多余规则，可以删去，最后整理得到：
\((1)A\rightarrow aB\)
\((2)B\rightarrow Ac\)
\((2)B\rightarrow d\)

改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法

若还有空产生式，则还需要用LL(1)文法的判别方式进行判断

消除左递归

对于包含直接左递归的文法，如\(G[S]:A\rightarrow Ab,A\rightarrow c, A\rightarrow d\)

可以直接改写成右递归：\(A\rightarrow cA', A\rightarrow dA', A'\rightarrow bA',A'\rightarrow b\)

一般情况下，如\(A\rightarrow A(\beta_1\mid\beta_2\mid...\mid\beta_n), A\rightarrow \alpha_1\mid\alpha_2\mid...\mid\alpha_n\)，分为了包含左递归和不含左递归的两部分，可以变形为：
\(A\rightarrow \alpha_1 A'\)
\(A\rightarrow \alpha_2 A'\)
\(...\)
\(A\rightarrow \alpha_n A'\)

\(A'\rightarrow \beta_1 A'\)
\(A'\rightarrow \beta_2 A'\)
\(...\)
\(A'\rightarrow \beta_n A'\)

对于包含间接左递归的文法，如\(G[S]:\)
\((1)A\rightarrow aB\)
\((2)A\rightarrow Bb\)
\((3)B\rightarrow Ac\)
\((4)B\rightarrow d\)

可以考虑把(1)和(2)带入(3)：
\((1)B\rightarrow aBc\)
\((2)B\rightarrow Bbc\)
\((3)B\rightarrow d\)

不会引起左递归的式子为(1)和(3)，故可以写成：
\((1)B\rightarrow aBcB'\)
\((2)B\rightarrow dB'\)
\((3)B'\rightarrow bcB'\)
\((4)B'\rightarrow \varepsilon\)

消除一切左递归

LL(1)文法的实现

程序实现

1. 求出文法G[S]各个产生式的SELECT集合
2. 然后根据集合内的符号来选择所属产生式

写程序时，用getsym来读入下一个符号，如果有不合法的符号，应当有错误处理。

如文法\(L(G[S]): A\rightarrow aBd \mid b, B\rightarrow\varepsilon\mid c\)

\(SELECT(A\rightarrow aBd)=\{a\}\)
\(SELECT(A\rightarrow b)=\{b\}\)
\(SELECT(B\rightarrow \varepsilon)=\{d\}\)
\(SELECT(B\rightarrow c)=\{c\}\)

void PraseA()
{
    if (sym == 'a')
    {
        getsym();
        PraseB();
        if (sym == 'd')
            getsym();
    }
    else if (sym == 'b')
    {
        getsym();
    }
    else
    {
        error();
    }
}

void PraseB()
{
    if (sym == 'c')
    {
        getsym();
    }
    else if (sym == 'd')
    {
    }
    else
    {
        error();
    }
}

预测分析表

求出所有规则的SELECT集后，根据集合填入预测分析表。如上面的文法：

	a	b	c	d	#
A	\(\rightarrow aBd\)	\(\rightarrow b\)
B			\(\rightarrow c\)	\(\rightarrow \varepsilon\)

对\(acd\)分析过程如下：

步骤	分析栈	剩余输入串	推导所用产生式或匹配
1	#A	acd#	A→aBd
2	#dBa	acd#	a匹配
3	#dB	cd#	B→c
4	#dc	cd#	c匹配
5	#d	d#	d匹配
6	#	#	接受

这一章的可能考点

1. 判别文法是否为LL(1)
2. 已知LL(1)文法，构造预测分析表
3. 给定LL(1)文法和输入串，写出分析过程表

第5章 自底向上的移进-归约分析

自底向上的移进-规约分析要求对输入符号串自左向右扫描，按句柄进行归约。
移进：将输入串的下一个字符移入符号栈
归约：符号栈中的顶部几个符号如果能匹配某条推导式的右边，则用该推导式的左边替换

自底向上的移进-归约法是每次对最左边的内容进行归约，它的逆过程为自顶向下的规范(最右)推导。

设文法 \(G[S]\) 为
\(S\rightarrow aAcBe\)
\(A\rightarrow b\)
\(A\rightarrow Ab\)
\(B\rightarrow d\)

对输入串\(abbcde\)使用自顶向下的最右推导：
\[S\Rightarrow aAcBe \Rightarrow aAcde \Rightarrow aAbcde \Rightarrow abbcde\]

对应的，我们可以得到它的逆过程，即规约过程。

步骤	符号栈	输入符号串	动作
(1)	#	abbcde#	移进
(2)	#a	bbcde#	移进
(3)	#ab	bcde#	归约\((A\rightarrow b)\)
(4)	#aA	bcde#	移进
(5)	#aAb	cde#	归约\((A\rightarrow Ab)\)
(6)	#aA	cde#	移进
(7)	#aAc	de#	移进
(8)	#aAcd	e#	归约\((B\rightarrow d)\)
(9)	#aAcB	e#	移进
(10)	#aAcBe	#	归约\((S\rightarrow aAcBe)\)
(11)	#S	#	接受(acc)

第6章 LR分析

LR(K)分析使用自底向上分析法，从左到右扫描符号，只需要根据分析栈中的符号栈和向右顺序查看输入串的K(K>=0)个符号来确定分析器接下来是移进还是规约，因而也能唯一地确定句柄。

LR分析器

总控程序负责LR分析过程

分析栈分为状态栈和文法符号栈。它们均是后进先出。

分析表分为动作(ACTION)表和状态转换(GOTO)表两个部分。

SP为栈指针，指向状态栈和文法符号栈，即状态栈和符号栈元素数目始终保持一致。

状态转换表内容按关系\(GOTO[S_i, X]=S_j\)确定，即当栈顶状态为\(S_i\)遇到栈顶符号\(X\)时应当转向状态\(S_j\)

动作表按\(ACTION[S_i,a]\)确定了栈顶状态为\(S_i\)时遇到输入符号\(a\)应执行的动作。