写在前面

这是作者在本学期学习编译原理的时候做的笔记，由于本人水平有限，对很多概念的理解比较浅显/(ㄒoㄒ)/，欢迎各位大佬多多评价，多多批评指正，希望与大家互相交流学习(●’◡’●)。

参考资料
[1] Alfred V. Aho,Monica S. Lam 《编译原理》
[2] 刘铭 《编译原理(第四版)》
[3] HUST编译原理课程组 PPT
[4] 哈尔滨工业大学 编译原理MOOC

最后更新时间

2022-11-1 10:00

2 文法和语言的基本知识

2.1 字母表和符号串

字母表：元素的非空有穷集合，如 ∑ = { a , b , c } \sum= \{ a,b,c\} ∑={a,b,c}。
字母表中需要至少包含一个元素。
符号：字母表中的元素。
符号串：符号的有穷序列，如a,b,ab,ba等。
不包含任何符号的符号串，称为空符号串，用$\epsilon$表示。

符号串的连接
设$x=abc,y=10a$，则$xy=abc10a,yx=10aabc$。
$\epsilon x=x\epsilon =x$。
集合的乘积
A B = { x y ∣ x ∈ A , y ∈ B } AB=\{ xy|x\in A,y\in B \} AB={xy∣x∈A,y∈B}。
如： A = { a , b } , B = { c , d } A=\{ a,b\},B=\{ c,d\} A={a,b},B={c,d}，则 A B = { a c , a d , b c , b d } AB=\{ ac,ad,bc,bd\} AB={ac,ad,bc,bd}。
{ ε } A = A { ε } = A \{ \varepsilon\}A=A\{ \varepsilon\}=A {ε}A=A{ε}=A。
符号串的幂运算
$x^0=\epsilon ,x^1=abc,x^2=abcabc,x^3=abcabcabc,...$
集合的幂运算
A 0 = { ε } , A 1 = A , A 2 = A A , . . . A^0=\{ \varepsilon\},A^1=A,A^2=AA,... A0={ε},A1=A,A2=AA,...
设 A = { a , b } , A 0 = { ε } , A 1 = { a , b } , A 2 = { a a , a b , b a , b b } , A 3 = { a a a , a a b , a b a , a b b , b a a , b a b , b b a , b b b } , . . . A=\{ a,b\},A^0=\{ \varepsilon\},A^1=\{ a,b\},A^2=\{ aa,ab,ba,bb\},A^3=\{ aaa,aab,aba,abb,baa,bab,bba,bbb\},... A={a,b},A0={ε},A1={a,b},A2={aa,ab,ba,bb},A3={aaa,aab,aba,abb,baa,bab,bba,bbb},...
集合的闭包与正闭包
正闭包：$A^{+}=A^1\cup A^2\cup ...\cup A^n...$
闭包：$A^{\ast }=A^0\cup A^1\cup A^2\cup ...\cup A^n...$
集合A的正闭包表示A上所有元素构成的所有符号串的集合。
集合A的闭包比集合A的正闭包多包含一个空符号串$\epsilon$。

2.2 文法的形式定义

规则
  规则也称为产生式，它是一个符号与另一个符号串的有序对$(A,\beta )$，通常写作：
$$A\to \beta (或A::=\beta )$$
其中，$A$是规则左部，它是一个符号；$\beta$是规则右部，他是一个符号串；$\to$和$::=$表示“定义为”或“生成”，意思是左部符号用右部的符号串定义或左部符号生成右部符号串。
  规则中出现的符号可分为两类，一类是终结符号，一般用大写字母表示；另一类是非终结符号，一般用小写字母表示。

文法
  文法是规则的有穷集合，通常表示成四元组$G=(V_N,V_R,P,S)$。其中，
  $V_N$是规则中非终结符号(nonterminal)的集合。
  $V_T$是规则中终结符号(terminal)的集合。$V_N\bigcap V_T=\varnothing$。通常用$V$表示$V_N\bigcup V_T$，称为文法$G$的字汇表。
  $P$是文法规则的集合。
  $S$是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。我们约定，第一条规则的左部是识别符号。

举例
  设字母表 ∑ = { a , b } \sum=\{ a,b\} ∑={a,b}，语言 L = { a b n a ∣ n ≥ 0 } L=\{ab^na|n\ge0 \} L={abna∣n≥0}，则定义语言的文法为 G = ( { A , B } , { a , b } , { A → a B a , B → B b ∣ ε } , A ) 。 G=(\{A,B \},\{ a,b\},\{A\rightarrow aBa,B\rightarrow Bb|\varepsilon \},A)。 G=({A,B},{a,b},{A→aBa,B→Bb∣ε},A)。

2.3 语言的形式定义

直接推导
  令$G$是一文法，我们从$xAy$直接推出$x\alpha y$，即$xAy\Rightarrow x\alpha y$，仅$A\to \alpha$是$G$的一个规则且$x,y\in (V_N\bigcup V_T{)}^{\ast }$。也就是说，从符号串$xAy$到$x\alpha y$仅使用一次规则。
  例如，设有文法 G [ S ] = ( { S } , { 0 , 1 } , P , S ) G[S]=(\{ S\},\{ 0,1\},P,S) G[S]=({S},{0,1},P,S)，其中$P$为$S\to 01|0S1$，有如下直接推导：
  $S\Rightarrow 01$，使用规则$S\to 01$，此时$x=\epsilon ,y=\epsilon$。
  $S\Rightarrow 0S1$，使用规则$S\to 0S1$，此时$x=\epsilon ,y=\epsilon$。
  $0S1\Rightarrow 0011$，使用规则$S\to 01$，此时$x=0,y=1$。
  $00S11\Rightarrow 000S111$，使用规则$S\to 0S1$，此时$x=00,y=11$。
  $000S111\Rightarrow 00001111$，使用规则$S\to 01$，此时$x=000,y=111$。
推导
  如果存在一个直接推导序列：${\alpha }_0\Rightarrow {\alpha }_1\Rightarrow ...\Rightarrow {\alpha }_n$，则称这个序列是一个从${\alpha }_0$至${\alpha }_n$的长度为n的推导，记为${\alpha }_0\stackrel{+}{\Rightarrow }{\alpha }_n$。表示从${\alpha }_0$出发，经一步或若干部或使用若干次规则可推导出${\alpha }_n$。
  例如，设有文法 G [ E ] = ( { E , T , F } , { i , + , ∗ , ( , ) } , P , E ) G[E]=(\{ E,T,F\},\{i,+,*,(,) \},P,E) G[E]=({E,T,F},{i,+,∗,(,)},P,E)，其中$P$为$E\to E+T|T,T\to T\ast F|F,F\to (E)|i$。
  对$i+i\ast i$有如下直接推到序列：$E\Rightarrow E+T\Rightarrow T+T\Rightarrow F+T\Rightarrow i+T\Rightarrow i+T\ast T\Rightarrow i+F\ast F\Rightarrow i+i\ast i$。

广义推导
  ${\alpha }_0\stackrel{\ast }{\Rightarrow }{\alpha }_n$表示从${\alpha }_0$出发，经0部或若干部，可推导出${\alpha }_n$。即${\alpha }_0\stackrel{\ast }{\Rightarrow }{\alpha }_n$意味着${\alpha }_0={\alpha }_n$或${\alpha }_0\stackrel{+}{\Rightarrow }{\alpha }_n$。

句型和句子
  设有文法$G[S]$，如果$S\stackrel{\ast }{\Rightarrow }x,x\in (V_N\bigcup V_T{)}^{\ast }$，则称符号串$x$为文法$G[S]$的句型。$S\stackrel{\ast }{\Rightarrow }x,x\in {V_T}^{\ast }$，则称$x$是文法$G[S]$的句子。

语言
  文法$G[S]$产生的所有句子的集合称为文法$G$所定义的语言，记为$L(G[S])$：
L ( G [ S ] ) = { x ∣ S ⇒ + x 且 x ∈ V T ∗ } L(G[S])=\{x|S\xRightarrow{+}x且x\in {V_T}^* \} L(G[S])={x∣S+ ​x且x∈VT​∗}
  由语言的定义可知，当文法给定时，语言也就确定。而且$L(G)$是${V_T}^{\ast }$的子集，即属于${V_T}^{\ast }$的符号串$x$不一定属于$L(G)$。

2.4 规范推导和规范规约

  同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中与所选择非终结符的次序有关。例如设有文法$G[N_1]$：
$$\begin{gathered} N_1\to N \\ N\to ND|N \\ D\to 0|1|2 \end{gathered}$$
  符号串$12$是该文法的一个句子，该句子可以由以下3个不同的推导序列推导出来：
(1) $N_1\Rightarrow N\Rightarrow ND\Rightarrow N2\Rightarrow D2\Rightarrow 12$
(2) $N_1\Rightarrow N\Rightarrow ND\Rightarrow DD\Rightarrow 1D\Rightarrow 12$
(3) $N_1\Rightarrow N\Rightarrow ND\Rightarrow DD\Rightarrow D2\Rightarrow 12$
  为了使句型或句子能够按一种特定的推导序列来产生，我们规定最右推导和最左推导。
  最左(最右)推导，是指对于一个推导序列中的每一步直接推导$\alpha \Rightarrow \beta$，都是对$\alpha$中的最左(最右)非终结符进行替换。如上面的例子，(1)是最右推导，(2)是最左推导，(3)既不是最右推导，也不是最左推导。其中最右推导又称为规范推导，用规范推导推导出的句型称为规范句型。
  规范推导的逆过程，称为最左归约，也称为规范归约。

2.5 短语、直接短语和句柄

短语
  令$G$是一个文法，$S$是一个文法的开始符号，假定$\alpha \beta \delta$是文法$G$的一个句型，如果有$S\stackrel{\ast }{\Rightarrow }\alpha A\delta$且$A\stackrel{+}{\Rightarrow }\beta$，则称$\beta$是相对于非终结符$A$的句型$\alpha \beta \delta$的短语。特别是，如果有$S\stackrel{\ast }{\Rightarrow }\alpha A\delta$且$A\Rightarrow \beta$，则称$\beta$是直接短语。

句柄
  一个句型的最左直接短语称为该句型的句柄。

举例
  设有文法 G [ S ] = ( { S , A , B } , { a , b } , P , S ) G[S]=(\{S,A,B \},\{a,b\},P,S) G[S]=({S,A,B},{a,b},P,S)，其中$P$为
$$\begin{gathered} S\to AB \\ A\to Aa|bB \\ B\to a|Sb \end{gathered}$$
求句型$baSb$的全部短语、直接短语和句柄。

  根据短语定义，可以从句型的推导过程中找出其全部短语、直接短语和句柄。对文法，首先建立该句型的推导过程：
$$\begin{gathered} S\Rightarrow AB\Rightarrow bBB\Rightarrow baB\Rightarrow baSb(最左推导) \\ S\Rightarrow AB\Rightarrow ASb\Rightarrow bBSb\Rightarrow baSb(最右推导) \end{gathered}$$
  从这两个推导过程中，有:
(1)$S\stackrel{\ast }{\Rightarrow }S,S\stackrel{+}{\Rightarrow }baSb$，句型本身是(相对于非终结符$S$)句型$baSb$的短语。
(2) $S\stackrel{\ast }{\Rightarrow }baB,B\Rightarrow Sb$，句型$baSb$中的子串$Sb$，是(相对于非终结符$B$)句型$baSb$的短语，且为直接短语。
(3)$S\stackrel{\ast }{\Rightarrow }bBSb,B\Rightarrow a$，句型$baSb$中的子串$a$，是(相对于非终结符$B$)句型$baSb$的短语，且为直接短语、句柄。
(4)$S\stackrel{\ast }{\Rightarrow }A,A\stackrel{+}{\Rightarrow }ba$，句型$baSb$中的子串$ba$，是(相对于非终结符$A$)句型$baSb$的短语。

2.6 语法树

语法树的生成
  推导构造语法树的过程为：以识别符号作为根结点，从它开始对每一步直接推导向下画一分支，分支结点的标记是直接推导中被替换的非终结符，按此方法逐步向下，画出每一步直接推导对应的分支，直到对该语法树再无分支可画出时，构造过程结束。
  语法树中从左到右的末端结点构成了由该语法树所表示的那个推导出的符号串。
$E\Rightarrow E-T\Rightarrow T-T\Rightarrow T\ast F-T\Rightarrow F\ast F-T\Rightarrow (E)\ast F-T\Rightarrow (E+T)\ast F-T\Rightarrow (T+T)\ast F-T\Rightarrow (T+F)\ast F-T\Rightarrow (T+i)\ast F-T\Rightarrow (T+i)\ast i\Rightarrow (T+i)\ast i-F$，根据该推导得到的语法树如下：

子树：语法树的子树是由某一非末端结点连同所有分支组成的部分。

简单子树：语法树的简单子树是指只有单层分支的子树。

**语法树和短语 **
  子树与短语的关系十分密切，根据子树的概念，句型的短语、直接短语、句柄的直接解释如下：

• 短语：子树的末端结点形成的符号串是相对于子树根的短语。如上图，$(T+i)$为句型的相对于$F$的短语。
• 直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。如上图，$T$为句型的相对于$F$的直接短语。
• 句柄：最左简单子树的末端结点形成的符号串是句柄。如上图，$T$为句柄。

文法的二义性
  如果一个文法存在某个句子对应两棵不同的语法树，则说明这个文法是二义性的。设有文法$G[E]$:$E\to E+E|E\ast E|(E)|i$，句子$i\ast i+i$有两个不同的最左推导，对应两棵不同的语法树，如下面所示：

  这种二义性情况是不允许的，因为当编译程序对它的结构进行语法分析时，就会产生两种甚至更多种不同的理解，必然会导致语义处理上的不确定性。

文法二义性的消除
  1.不改变文法中原有的语法规则，仅加进一些语法的非形式规定。如在上述文法中加入运算符优先顺序规则，即$\ast$优先于$+$，$+$、$\ast$服从左结合。这样文法仅有上面左侧的一种文法树。
  2.构造一个等价的无二义性文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。如对上述文法，将运算符的优先顺序和结合规则加到原有文法中，可以构造出无二义性文法$G^{{}^{\prime }}[E]$:$$\begin{gathered} E\to E+T|T \\ T\to T\ast F|F \\ F\to (E)|i \end{gathered}$$
  则句子$i\ast i+i$只有一种文法树：

2.7 文法和语言的分类

0型文法(无限制文法)
  若文法$G=(V_N,V_T,P,S)$中的每条规则$\alpha \to \beta$是这样一种结构：
  $\alpha \in (V_N\bigcup V_T{)}^{\ast }$且至少含一个非终结符，而$\beta \in (V_N\bigcup V_T{)}^{\ast }$，
则称$G$是0型文法。0型文法描述的语言是0型语言。由于0型文法没有加任何限制条件，故又称无限制性文法，相应的语言称无限制性语言。

1型文法
  若文法$G=(V_N,V_T,P,S)$中的每一条规则的形式为$\alpha A\beta \to \alpha u\beta$，其中$A\in V_N,\beta \in (V_N\bigcup V_T{)}^{\ast },u\in (V_T\bigcup V_N{)}^{+}$，则称$G$是1型文法，1型文法描述的语言是1型语言。
  由定义可知，利用规则将$A$替换成$u$时，必须考虑非终结符$A$只有在$\alpha$和$\beta$这样的一个上下文环境中才能把它替换为$u$，并且不允许替换成空串，故又称1型文法为上下文有关文法，相应的语言称为上下文有关语言。

2型文法
  若文法$G=(V_N,V_T,P,S)$中的每一条规则的形式为$A\to \beta$，其中$A\in V_N,\beta \in (V_N\bigcup V_T{)}^{\ast }$，则称$G$是2型文法，2型文法描述的语言是2型语言。
  有定义可知，利用规则将$A$替换成$\beta$时，与$A$的上下文无关，即无需考虑$A$在上下文中出现的情况，故又称2型文法为上下文无关文法，其产生的语言称为上下文无关语言。

3型文法
  若文法$G=(V_N,V_T,P,S)$中的每一条规则的形式为$A\to \alpha B$或$A\to \alpha$，其中$A.B\in V_N,\alpha \in {V_T}^{\ast }$，则称$G$为右线性文法。
  若文法$G=(V_N,V_T,P,S)$中的每一条规则的形式为$A\to B\alpha$或$A\to \alpha$，其中$A.B\in V_N,\alpha \in {V_T}^{\ast }$，则称$G$为左线性文法。
  右线性文法和左线性文法都称为3型文法或正规文法，3型文法描述的语言称为3型语言或正规语言。

  由上述4类文法的定义可知，从0型文法到3型文法，是逐渐增加对规则的限制条件而得到的，由它们所定义的语言类是依次缩小的，即有$L_3\subset L_2\subset L_1\subset L_0$。