1
编译原理第二章 文法和语言上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 2月
2
本章目的自然语言是人与人交流思想的工具，程序语言是人和计算机之间传达信息的工具。为了描述程序语言，
本章将引进有关形式语言的基本概念。文法是程序语言的生成系统，自动机是程序语言的识别系统，用文法来精确定义一个语言，然后根据这个文法构造识别这个语言的自动机，因此文法对程序语言和编译程序的构造来说意义重大。随着计算机的发展，形式语言学发展很快。 N.Chomsky将文法分成四类，程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，语义则要借助于上下文有关文法来描述。因此我们的注意力是针对这几类文法，特别是上下文无关文法。
3
第二章 文法和语言
§ 2.1 基本概念一,语言
1,字母表定义 2.1 符号的非空有穷集合称为字母表，通常用 ∑表示。字母表中每个元素称为一个符号或一个字符。
不同语言的字母表可能是不同的，例如二进制数这个语言的字母表 ∑={0,1}。程序语言中的标识符，它的字母表
∑={a,b,..,z,0,1,..,9}。通常程序语言的字母表是 ASCⅡ 字符集。
2,字符串定义 2.2 由字母表 ∑中的字符所组成的有穷序列，称为字母表上的符号串，或字符串，字。
[例 2.1]如,字母表 ∑={0,1},则 0,1,00,01,10,11,000,001,010,… 都是
∑上的字符串，如则 a,b,,ab,ba,bb,aaa… 分别是 ∑上的字符串。
4
空串：不包含任何字符的字符串，用 ε表示，它是 ∑上的一个特殊的字符串。对任一字母表 ∑，都有 ε是 ∑上的字符串。
字符串的长度：是指字符串 x中的字符的个数，用 |x|表示。
如 x=abc，则 |x| =3。特别地有 | ε | =0.
字符串的联结：设 x,y是 ∑上的字符串，则它们的联结 xy是将 y的符号相继连接在 x的符号后所得到的新的字符串，
如,x=aba,y=bba,则 xy=ababba.
联结是字符串上的一种运算，满足结合律，但不满足交换律。但 εx=xε=x则另当别论。
5
3.子串
字符串的前缀和后缀：设 z=xy则 x是 z的前缀,y是 z的后缀,
特别当 y≠ε时 x是 z的真前缀,当 x≠ε时,y是 z的真后缀,
[例 2.2]设 x=abc,则 ε,a,ab,abc都是 x的前缀，其 ε,a,ab为真前缀，而 abc,bc,c,ε都是 x的后缀，其中 bc,c,ε为真后缀。
定义 2.3 一个非空字符串 x删去它的前缀和后缀后所得的字符串为 x的子串，如果删去的前缀和后缀不同时为 ε，则该子串为真子串。
[例 2.3]设 x=abc，其子串为 abc,ab,bc,a,c,b,ε真子串为 ab,
bc,a,c,b,ε请注意 ac不是子串，它只是字符串 abc的一个子序列。
6
4.语言定义 2.4,
给出字母表?，则?上任一字符串集合，称为?上的一个语言，记为 L，该语言的每一个字符串，便是语言 L的一个语句或句子。
[例 2.4]设?={a,b,c},则 L={a,aa,ab,aaa,aab,aba,abb,…} 为?上的一个语言，如果 a表示字母,b表示数字,c看作其他符号,
则 L通常是程序语言中的标识符集。其中每个标识符便是标识符集的一个句子。
由有限个字符串组成的集合为一有穷语言，反之为无穷语言。
7
对于字母表?，用?*表示?上所有字符串的集合。
如?={a,b}，则?*={?,a,b,aa,ab,bb,ba,…} 。
显然?上的任一语言 L，都有 L*
对于?，令?+=?*-{?}，它是?上不含空串的字符串集合。
对于?*的子集 L,M,(它们都?上的语言 )，可以定义下列四种语言之间的运算。
定义 2.5,语言 L和 M的连接,LM={xy | x∈ L and y∈ M}。
基于同一律,{?}L=L {?}=L，除此而外，通常 LM≠ML，即连接不满足交换律，但满足结合律，即 (LM)N=L(MN)。
通常记 L2=LL,并约定 Lo={?}。
8
定义 2.6,
语言 L和 M的合并,L∪ M={x | x∈ L or | x∈ M}。
如同集合间的合并运算那样，它满足结合律，交换律。
定义 2.7,
语言 L的闭包,L*= Lo∪ L1∪ L2∪ L3∪ …L?。
定义 2.8,
语言 L的正闭包 L+= L1∪ L2∪ L3∪ …L?。
如果?把看成是字母表?上长度为 1的字符串集合，它当然也是字母表?上的一个语言，则是语言的自身连接，它也是上的一个语言，特别令?o= {?},：
则,
*=? o∪? 1∪? 2∪? 3∪ …
+=? 1∪? 2∪? 3∪ …
9
[例 2.5]设字母集合 L={a,b,c,…z},数字集合
D={0,1,…9},则
L∪D 是字母数字集
LD是一个字母后跟一个数字的字符串集。
L*是由字母组成的字符串（包括）集合。
L(L∪ D) *是由字母开头的字母数字串的集合。
D+是长度大于等于 1的数字串的集合。
10
二、文法
1.文法的定义定义 2.9 文法 G是一个四元组,G=(Vt,Vn,S,P),其中：
Vt为终结符号集，这是个非空有限集；
Vn为非终结符号集，它也是个非空有限集；
S为一文法开始符，是一特殊的非终结符，
P是产生式的非空有限集，其中每个产生式 (或称规则 )是一序偶,通常写作,α → β
或 α::=β
读成 α是 β或 α定义 β为。 α是产生式左部,β为产生式右部。
α,β都是由终结符和非终结符组成的符号串，只是 α
∈ (Vt∪Vn)+ 且至少有一个非终结符，而 β∈ (Vt∪ Vn)*。
11
终结符号是指语言不可再分的基本符号，通常是一个语言的字母表。
非终结符号，也称为语法变量，它代表语法实体，或语法范畴，它不像终结符号代表了语法的最小元素，是一种个体记号，它是一个类，一个集合，一个非终结符代表了一定的语法概念。
例如，在程序语言中，可以把变量、常数,+,×,
(,)等看成是终结符，而表达式是这些终结符满足一定规则的符号串的集合，如 i*(i+i),i+i+i等，符号串中可包含非终结符号。
12
文法开始符号是非终结符，代表语法实体中我们最感兴趣的语法实体，即语言的目标，而其他语法实体只是构造语言目标时的中间变量。
如表达式文法的语言的目标是表达式，程序语言的目标通常为程序。
产生式就是构造某个语法实体时，应满足的规则，所以产生式也称为产生规则或规则，与一个语法实体相关的规则可能不止一个。
例如有 P→ α 1
P→ α2
…….
P→ αn
这里,P∈Vn,αi∈ (Vt∪Vn)*,i=1,2,?,n,为简便，有相同左部的产生式可写成,P→ α1 | α2 | … | αn
其中每个 αi称为 P的一个候选式，直竖,|”读为
“或”，它与,→,一样是用来描述文法的元语言符号。
13
[例 2.6]
标识符是字母开始的字母数字串，
如果,
用 L表示 <字母 >,D表示 <数字 >,T表示 <字母或数字 >，
则有,
L→a | b | … |z
D→0 | 1 | … |9
T→L |D
如果,
用 S表示 <字母数字串 >，
则,<字母或数字 >是一 <字母数字串 >； <字母数字串 >后跟一个 <字母或数字 >，也是 <字母数字串 >，
所以有,S→T |ST
其中产生式 S→T |ST 是一种左递归形式，由它可产生一串 T。因此作为 <标识符 >的非终结符 I，它或为单个字母，
或为字母后跟字母数字串，故有,I→L |LS
14
因此相应的文法,
G=({a,b,…,z,0,1,…,9},{I,S,T,L,D},I,P)
I→L |LS
S→T |ST
P,T→L |D
L→a | b | … |z
D→0 | 1 | … |9
15
[例 2.7] 程序语言中的只含 +,× 运算的表达式，如果用 i表示变量或常数，在程序语言定义中用 BNF表示法来描叙上述表达式：
<表达式 >::=<表达式 >+<项 >
<表达式 >::=<项 >
<项 >::=<项 >*<因子 >
<项 >::=<因子 >
<因子 >::=(<表达式 >)
<因子 >::=i
如果用 E代表 <表达式 >,T代表 <项 >,F代表 <因子 >，
将,:=改为 →,产生式左部相同的合并，且将此表达式文法记为 G2，则,
G2=({i,+,*,(,)},{E,T,F},E,P)
E→E+T | T
P,T→T*F | F
F→(E) | i
16
例 2.6描述了标识符的词法规则，例 2.7描述了表达式的语法规则，产生这种差别的原因在于例 2.6的终结符集是输入字符集，它是构成单词的最基本元素，例 2.7的终结符集则是经词法分析识别后的单词集，如变量 i,运算符 +,*，界符
（，）。它们被视为语法分析中最基本的元素。
我们约定：
用大写字母 A,P,S,E等表示非终结符。
用小写字母 i,t,x,y等表示终结符。
而希腊字母 α β δ γ 等表示文法符号串 (V=Vt∪ Vn)*，
有 α∈ V*等。
17
2.上下文无关文法如果,文法中的所有产生式均为,
P→ α形式，
其中 P∈ Vn,α∈ V*,并且文法开始符 S至少在某个产生式左部出现一次，则文法 G是一上下文无关文法。
[例 2.8]程序语言中只含 +,*运算的表达式也可以用文法 G1
来定义,
G2=({i,+,*,(,)},{E,T,F},E,P)
其中：
P,E→E+E | E*E|(E) | i
即变量是最简单的表达式，如果 E1,E2为表达式，则
E1*E2,E1+E2,(E1)也是表达式。
18
3.文法产生的语言
（ 1） 直接推出：
定义 2.10设文法 G=(Vt,Vn,S,P),α,β ∈ (Vt∪ Vn)*,如果有 A→? ∈ P,则称 α Aβ可直接推出 α? β，
即,α Aβ=> α?β
其中,=>”表示直接推出,是应用产生规则进行推导的记号,
而,→,是产生式中的定义记号,两者是不同的,直接推导是对文法符号串中的某个非终结符 A,用相应的产生式的右部来替换这个左部非终结,而得到 α?β。
α Aβ可直接推出 α?β,则也可说 α?β是 α Aβ 直接推导,与推导方向相反,我们称 α?β可直接归约到 α Aβ。
19
（ 2） 如果 α 1可直接推出 α 2,α 2可直接推出 α 3,…,
α n-1可直接推出 α n,即存在一个自 α 1至 α n的直接推导序列则我们称 α 1可推出 α n,记为,
+
α 1=> α n,它表示从 α 1出发,经过一步或若干步,可推导出 α n。 这个推导序列的长度为 n-1。
如果记 o *
α 1=> α 1,则 α 1=>α n
表示自出发经过 0步或若干步可推导出 α n。
20
（ 3） 句型和句子：
定义 2.11 设文法 G=(Vt,Vn,S,P),α ∈ (Vt∪ Vn)*。
如有 *
S=>α,α ∈ (Vt∪ Vn)*,则称 α 是文法 G的一个句型,
如 α ∈ Vt*则称是文法 G的一个句子,也即只含终结符的句型是一个句子 。
由定义可见,S是文法的一个句型,但不可能是句子 。 例 2.9
推出的 i+i*i是文法的一个句子,当然也是一个句型,而 E+E，
E+E*E,E+E*i,E+i*i则都是句型 。
（ 4） 文法产生的语言：
定义 2.12 文法 G=(Vt,Vn,S,P)所产生的句子的全体,称为由文法 G产生的语言,记为 L(G),即有：
+
L(G)={α |S=> α,α ∈ Vt*}
（ 5） 文法的等价：对文法 G1,G2,如果有 L(G1)=L(G2)，
则称文法 G1和 G2是等价的 。
例 2.7中的文法与例 2.8中的文法描述了相同的语言,故它们是等价的 。
21
三,归约与句柄
1.规范推导例 2.9中 (2.1)式给出了文法的一个句子 i+i*i的一个推导序列,
在这个推导序列中每一步推导都是对句型中的最右非终结符用相应产生式右部进行替换,这样的推导称为最右推导 。
如果将最右替换改为最左替换,则为最左推导 。 同一句子
i+i*i的最左推导为,E=>E+E=>i+E=>i+E*E=>i+i*E=>i+i*i
im im im im im
还有其他形式的推导 。 但我们只考虑最左推导和最右推导,
特别我们将最右推导称为规范推导,用 =>来表示 。
R
(2.1)就是句子 i+i*i的规范推导,与规范推导的方向相反,便是规范归约的过程 。
22
2.短语定义 2.13设 α β?是文法 G的一个句型,如果有：
* +
即,S=>α A?并且 A=>β
则称 β是句型 α β?的关于非终结符 A的一个短语,或称 β是
α β?的一个短语,特别当 A-> β ∈ P时,β为句型 α β?的一个直接短语,或简单短语 。
3.句柄定义 2.14一个句型的最左直接短语称为该句型的句柄 。
一个句型的直接短语可能不止一个,但最左直接短语则是唯一的,将句型中的句柄用产生式左部代替得到新句型,
这便是一次规范归约,它恰与规范推导相反 。
4.素短语定义 2.15 含有终结符的短语,如果它不存在也具有这种性质的真子串,则该短语为素短语 。
23
§ 2.2 分析树与二义性一、分析树可以用一棵树来表示一个句型的推导，对文法
⑴每个结点用一个文法符号来标记；
⑵根结点用文法开始符 S标记；
⑶内部结点以非终结符 A标记，它的所有子结点从左到右标记为：
x1,x2,…,xn,
则 A->x1x2…xn ∈ P ；
⑷如果有结点标记为 ε，则它必是叶结点，且它是它的父结点的唯一子结点。
24
一个句型相应的分析树是这样构造的：以文法开始符 S作为根结点；随着推导的逐步展开，对句型中某个非终结符 A用相应产生式的右部替换时，为标记 A的结点生成其子结点依次为的子树，直至推导结束。
25
二、子树在一棵分析树中，一个内部结点 A连同它的所有后裔组成了一棵子树，称这棵子树为 A-树，因此一棵分析树有多少个内部结点，就有多少棵子树。分析树本身是 S-树，它是一棵平凡子树。
子树与短语直接短语句柄素短语的对应关系：
每棵子树对应的符号串 (当然是句型的子串 )是这个句型相对于子树结点的一个短语；
如果这棵子树是二代子树，则这短语为直接短语；
最左的二代子树便是句柄；
如果子树对应的符号串含终结符，且在该子树中不再包含有终结符的子树，则是素短语。
显然从分析树出发找短语、句柄、素短语要直观得多
26
子树与短语直接短语句柄素短语的对应关系,
每棵子树对应的符号串 (当然是句型的子串 )是这个句型相对于子树结点的一个短语；
如果这棵子树是二代子树，则这短语为直接短语；
最左的二代子树便是句柄；
如果子树对应的符号串含终结符，且在该子树中不再包含有终结符的子树，则是素短语。
显然从分析树出发找短语、句柄、素短语要直观得多
27
三、二义性定义 2.16 文法 G的一个句子如果能找到两种不同的规范推导或二棵不同的分析树，则称这个句子是二义性的，
一个文法包含二义性的句子则这个文法是二义性的，
否则该文法是无二义性的。
一个文法是二义的，并不是说文法描述的的语言也是二义的，这也说明，对一个二义文法，如果能找到一个非二义文法，那么二义文法的二义性是可以消除的。
如果找不到，则二义文法描述的语言为先天二义的。
我们总是希望一个文法是无二义性的，使句子的分析可以唯一确定的方式进行。但文法的二义性是不可判定的，也即不存在一种算法，可在有限步内判定一个文法是否为二义的。
28
§ 2.3 形式语言分类
1956年，语言家 Noam Chomsky首先建立了形式语言的描述，定义了四类文法及相应的形式语言，并将它们与相应的识别系统相联系，推动了计算机科学的发展，对程序语言的设计，编译方法，计算复杂性等方面有重大影响。
Chomsky将文法分成 0型,1型,2型,3型四种类型。
29
定义 2.17
文法 G的每一个产生式均为下列形式：
α→β
其中,α∈ V*VnV*,即至少含一个非终结符，
β ∈ V*,
则文法 G称为 0型文法或短语文法。
0型文法相应的语言为 0型语言，或称递归可枚举集，它的识别系统是图灵（ Turing）机。
30
定义 2.18
文法 G的每一个产生式均为下列形式：
α→β 且 | α |? | β |
则文法 G为 1型文法，或上下文有关文法，也称上下文敏感文法。
1型文法相应的语言称为 1型语言或上下文有关语言，
它的识别系统是线性有界自动机。
下述的定义 2.18'与定义 2.18等价。
定义 2.18‘ 文法 G的每一个产生式均为下列形式：
αA?→αβ?其中 α,?∈ V*,A ∈ Vn,β ∈ V + 。
显然它满足定义 2.18的长度限制，但它更明确地表达了上下文有关的特性，即 A必须在的上下文环境中才能被替换。
31
定义 2.19 文法 G的每一个产生式均为下列形式：
A→α 其中 α∈ V*,A ∈ Vn
则称文法 G为 2型文法或上下文无关文法。
显然用 α去替换 A时，与 A的上下文无关。
2型文法相应的语言称为 2型语言或上下文无关语言。它的识别系统是下推自动机。
32
定义 2.20 文法 G的每个产生式均为下列形式：
A→α 或 A→α B
其中 α∈ Vt*,A,B∈ Vn,则文法 G称为 3型文法或正规文法、右线性文法。 3型文法相应的语言为 3型语言或正规语言，它的识别系统为有限自动机。
当然 3型文法呈左线性形式,A→α 或 A→ Bα也是一样的。
33
习 题,
2.1(a),(b)
2.2
2.3
2.5
2.6
编译原理第二章 文法和语言上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 2月
2
本章目的自然语言是人与人交流思想的工具，程序语言是人和计算机之间传达信息的工具。为了描述程序语言，
本章将引进有关形式语言的基本概念。文法是程序语言的生成系统，自动机是程序语言的识别系统，用文法来精确定义一个语言，然后根据这个文法构造识别这个语言的自动机，因此文法对程序语言和编译程序的构造来说意义重大。随着计算机的发展，形式语言学发展很快。 N.Chomsky将文法分成四类，程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，语义则要借助于上下文有关文法来描述。因此我们的注意力是针对这几类文法，特别是上下文无关文法。
3
第二章 文法和语言
§ 2.1 基本概念一,语言
1,字母表定义 2.1 符号的非空有穷集合称为字母表，通常用 ∑表示。字母表中每个元素称为一个符号或一个字符。
不同语言的字母表可能是不同的，例如二进制数这个语言的字母表 ∑={0,1}。程序语言中的标识符，它的字母表
∑={a,b,..,z,0,1,..,9}。通常程序语言的字母表是 ASCⅡ 字符集。
2,字符串定义 2.2 由字母表 ∑中的字符所组成的有穷序列，称为字母表上的符号串，或字符串，字。
[例 2.1]如,字母表 ∑={0,1},则 0,1,00,01,10,11,000,001,010,… 都是
∑上的字符串，如则 a,b,,ab,ba,bb,aaa… 分别是 ∑上的字符串。
4
空串：不包含任何字符的字符串，用 ε表示，它是 ∑上的一个特殊的字符串。对任一字母表 ∑，都有 ε是 ∑上的字符串。
字符串的长度：是指字符串 x中的字符的个数，用 |x|表示。
如 x=abc，则 |x| =3。特别地有 | ε | =0.
字符串的联结：设 x,y是 ∑上的字符串，则它们的联结 xy是将 y的符号相继连接在 x的符号后所得到的新的字符串，
如,x=aba,y=bba,则 xy=ababba.
联结是字符串上的一种运算，满足结合律，但不满足交换律。但 εx=xε=x则另当别论。
5
3.子串
字符串的前缀和后缀：设 z=xy则 x是 z的前缀,y是 z的后缀,
特别当 y≠ε时 x是 z的真前缀,当 x≠ε时,y是 z的真后缀,
[例 2.2]设 x=abc,则 ε,a,ab,abc都是 x的前缀，其 ε,a,ab为真前缀，而 abc,bc,c,ε都是 x的后缀，其中 bc,c,ε为真后缀。
定义 2.3 一个非空字符串 x删去它的前缀和后缀后所得的字符串为 x的子串，如果删去的前缀和后缀不同时为 ε，则该子串为真子串。
[例 2.3]设 x=abc，其子串为 abc,ab,bc,a,c,b,ε真子串为 ab,
bc,a,c,b,ε请注意 ac不是子串，它只是字符串 abc的一个子序列。
6
4.语言定义 2.4,
给出字母表?，则?上任一字符串集合，称为?上的一个语言，记为 L，该语言的每一个字符串，便是语言 L的一个语句或句子。
[例 2.4]设?={a,b,c},则 L={a,aa,ab,aaa,aab,aba,abb,…} 为?上的一个语言，如果 a表示字母,b表示数字,c看作其他符号,
则 L通常是程序语言中的标识符集。其中每个标识符便是标识符集的一个句子。
由有限个字符串组成的集合为一有穷语言，反之为无穷语言。
7
对于字母表?，用?*表示?上所有字符串的集合。
如?={a,b}，则?*={?,a,b,aa,ab,bb,ba,…} 。
显然?上的任一语言 L，都有 L*
对于?，令?+=?*-{?}，它是?上不含空串的字符串集合。
对于?*的子集 L,M,(它们都?上的语言 )，可以定义下列四种语言之间的运算。
定义 2.5,语言 L和 M的连接,LM={xy | x∈ L and y∈ M}。
基于同一律,{?}L=L {?}=L，除此而外，通常 LM≠ML，即连接不满足交换律，但满足结合律，即 (LM)N=L(MN)。
通常记 L2=LL,并约定 Lo={?}。
8
定义 2.6,
语言 L和 M的合并,L∪ M={x | x∈ L or | x∈ M}。
如同集合间的合并运算那样，它满足结合律，交换律。
定义 2.7,
语言 L的闭包,L*= Lo∪ L1∪ L2∪ L3∪ …L?。
定义 2.8,
语言 L的正闭包 L+= L1∪ L2∪ L3∪ …L?。
如果?把看成是字母表?上长度为 1的字符串集合，它当然也是字母表?上的一个语言，则是语言的自身连接，它也是上的一个语言，特别令?o= {?},：
则,
*=? o∪? 1∪? 2∪? 3∪ …
+=? 1∪? 2∪? 3∪ …
9
[例 2.5]设字母集合 L={a,b,c,…z},数字集合
D={0,1,…9},则
L∪D 是字母数字集
LD是一个字母后跟一个数字的字符串集。
L*是由字母组成的字符串（包括）集合。
L(L∪ D) *是由字母开头的字母数字串的集合。
D+是长度大于等于 1的数字串的集合。
10
二、文法
1.文法的定义定义 2.9 文法 G是一个四元组,G=(Vt,Vn,S,P),其中：
Vt为终结符号集，这是个非空有限集；
Vn为非终结符号集，它也是个非空有限集；
S为一文法开始符，是一特殊的非终结符，
P是产生式的非空有限集，其中每个产生式 (或称规则 )是一序偶,通常写作,α → β
或 α::=β
读成 α是 β或 α定义 β为。 α是产生式左部,β为产生式右部。
α,β都是由终结符和非终结符组成的符号串，只是 α
∈ (Vt∪Vn)+ 且至少有一个非终结符，而 β∈ (Vt∪ Vn)*。
11
终结符号是指语言不可再分的基本符号，通常是一个语言的字母表。
非终结符号，也称为语法变量，它代表语法实体，或语法范畴，它不像终结符号代表了语法的最小元素，是一种个体记号，它是一个类，一个集合，一个非终结符代表了一定的语法概念。
例如，在程序语言中，可以把变量、常数,+,×,
(,)等看成是终结符，而表达式是这些终结符满足一定规则的符号串的集合，如 i*(i+i),i+i+i等，符号串中可包含非终结符号。
12
文法开始符号是非终结符，代表语法实体中我们最感兴趣的语法实体，即语言的目标，而其他语法实体只是构造语言目标时的中间变量。
如表达式文法的语言的目标是表达式，程序语言的目标通常为程序。
产生式就是构造某个语法实体时，应满足的规则，所以产生式也称为产生规则或规则，与一个语法实体相关的规则可能不止一个。
例如有 P→ α 1
P→ α2
…….
P→ αn
这里,P∈Vn,αi∈ (Vt∪Vn)*,i=1,2,?,n,为简便，有相同左部的产生式可写成,P→ α1 | α2 | … | αn
其中每个 αi称为 P的一个候选式，直竖,|”读为
“或”，它与,→,一样是用来描述文法的元语言符号。
13
[例 2.6]
标识符是字母开始的字母数字串，
如果,
用 L表示 <字母 >,D表示 <数字 >,T表示 <字母或数字 >，
则有,
L→a | b | … |z
D→0 | 1 | … |9
T→L |D
如果,
用 S表示 <字母数字串 >，
则,<字母或数字 >是一 <字母数字串 >； <字母数字串 >后跟一个 <字母或数字 >，也是 <字母数字串 >，
所以有,S→T |ST
其中产生式 S→T |ST 是一种左递归形式，由它可产生一串 T。因此作为 <标识符 >的非终结符 I，它或为单个字母，
或为字母后跟字母数字串，故有,I→L |LS
14
因此相应的文法,
G=({a,b,…,z,0,1,…,9},{I,S,T,L,D},I,P)
I→L |LS
S→T |ST
P,T→L |D
L→a | b | … |z
D→0 | 1 | … |9
15
[例 2.7] 程序语言中的只含 +,× 运算的表达式，如果用 i表示变量或常数，在程序语言定义中用 BNF表示法来描叙上述表达式：
<表达式 >::=<表达式 >+<项 >
<表达式 >::=<项 >
<项 >::=<项 >*<因子 >
<项 >::=<因子 >
<因子 >::=(<表达式 >)
<因子 >::=i
如果用 E代表 <表达式 >,T代表 <项 >,F代表 <因子 >，
将,:=改为 →,产生式左部相同的合并，且将此表达式文法记为 G2，则,
G2=({i,+,*,(,)},{E,T,F},E,P)
E→E+T | T
P,T→T*F | F
F→(E) | i
16
例 2.6描述了标识符的词法规则，例 2.7描述了表达式的语法规则，产生这种差别的原因在于例 2.6的终结符集是输入字符集，它是构成单词的最基本元素，例 2.7的终结符集则是经词法分析识别后的单词集，如变量 i,运算符 +,*，界符
（，）。它们被视为语法分析中最基本的元素。
我们约定：
用大写字母 A,P,S,E等表示非终结符。
用小写字母 i,t,x,y等表示终结符。
而希腊字母 α β δ γ 等表示文法符号串 (V=Vt∪ Vn)*，
有 α∈ V*等。
17
2.上下文无关文法如果,文法中的所有产生式均为,
P→ α形式，
其中 P∈ Vn,α∈ V*,并且文法开始符 S至少在某个产生式左部出现一次，则文法 G是一上下文无关文法。
[例 2.8]程序语言中只含 +,*运算的表达式也可以用文法 G1
来定义,
G2=({i,+,*,(,)},{E,T,F},E,P)
其中：
P,E→E+E | E*E|(E) | i
即变量是最简单的表达式，如果 E1,E2为表达式，则
E1*E2,E1+E2,(E1)也是表达式。
18
3.文法产生的语言
（ 1） 直接推出：
定义 2.10设文法 G=(Vt,Vn,S,P),α,β ∈ (Vt∪ Vn)*,如果有 A→? ∈ P,则称 α Aβ可直接推出 α? β，
即,α Aβ=> α?β
其中,=>”表示直接推出,是应用产生规则进行推导的记号,
而,→,是产生式中的定义记号,两者是不同的,直接推导是对文法符号串中的某个非终结符 A,用相应的产生式的右部来替换这个左部非终结,而得到 α?β。
α Aβ可直接推出 α?β,则也可说 α?β是 α Aβ 直接推导,与推导方向相反,我们称 α?β可直接归约到 α Aβ。
19
（ 2） 如果 α 1可直接推出 α 2,α 2可直接推出 α 3,…,
α n-1可直接推出 α n,即存在一个自 α 1至 α n的直接推导序列则我们称 α 1可推出 α n,记为,
+
α 1=> α n,它表示从 α 1出发,经过一步或若干步,可推导出 α n。 这个推导序列的长度为 n-1。
如果记 o *
α 1=> α 1,则 α 1=>α n
表示自出发经过 0步或若干步可推导出 α n。
20
（ 3） 句型和句子：
定义 2.11 设文法 G=(Vt,Vn,S,P),α ∈ (Vt∪ Vn)*。
如有 *
S=>α,α ∈ (Vt∪ Vn)*,则称 α 是文法 G的一个句型,
如 α ∈ Vt*则称是文法 G的一个句子,也即只含终结符的句型是一个句子 。
由定义可见,S是文法的一个句型,但不可能是句子 。 例 2.9
推出的 i+i*i是文法的一个句子,当然也是一个句型,而 E+E，
E+E*E,E+E*i,E+i*i则都是句型 。
（ 4） 文法产生的语言：
定义 2.12 文法 G=(Vt,Vn,S,P)所产生的句子的全体,称为由文法 G产生的语言,记为 L(G),即有：
+
L(G)={α |S=> α,α ∈ Vt*}
（ 5） 文法的等价：对文法 G1,G2,如果有 L(G1)=L(G2)，
则称文法 G1和 G2是等价的 。
例 2.7中的文法与例 2.8中的文法描述了相同的语言,故它们是等价的 。
21
三,归约与句柄
1.规范推导例 2.9中 (2.1)式给出了文法的一个句子 i+i*i的一个推导序列,
在这个推导序列中每一步推导都是对句型中的最右非终结符用相应产生式右部进行替换,这样的推导称为最右推导 。
如果将最右替换改为最左替换,则为最左推导 。 同一句子
i+i*i的最左推导为,E=>E+E=>i+E=>i+E*E=>i+i*E=>i+i*i
im im im im im
还有其他形式的推导 。 但我们只考虑最左推导和最右推导,
特别我们将最右推导称为规范推导,用 =>来表示 。
R
(2.1)就是句子 i+i*i的规范推导,与规范推导的方向相反,便是规范归约的过程 。
22
2.短语定义 2.13设 α β?是文法 G的一个句型,如果有：
* +
即,S=>α A?并且 A=>β
则称 β是句型 α β?的关于非终结符 A的一个短语,或称 β是
α β?的一个短语,特别当 A-> β ∈ P时,β为句型 α β?的一个直接短语,或简单短语 。
3.句柄定义 2.14一个句型的最左直接短语称为该句型的句柄 。
一个句型的直接短语可能不止一个,但最左直接短语则是唯一的,将句型中的句柄用产生式左部代替得到新句型,
这便是一次规范归约,它恰与规范推导相反 。
4.素短语定义 2.15 含有终结符的短语,如果它不存在也具有这种性质的真子串,则该短语为素短语 。
23
§ 2.2 分析树与二义性一、分析树可以用一棵树来表示一个句型的推导，对文法
⑴每个结点用一个文法符号来标记；
⑵根结点用文法开始符 S标记；
⑶内部结点以非终结符 A标记，它的所有子结点从左到右标记为：
x1,x2,…,xn,
则 A->x1x2…xn ∈ P ；
⑷如果有结点标记为 ε，则它必是叶结点，且它是它的父结点的唯一子结点。
24
一个句型相应的分析树是这样构造的：以文法开始符 S作为根结点；随着推导的逐步展开，对句型中某个非终结符 A用相应产生式的右部替换时，为标记 A的结点生成其子结点依次为的子树，直至推导结束。
25
二、子树在一棵分析树中，一个内部结点 A连同它的所有后裔组成了一棵子树，称这棵子树为 A-树，因此一棵分析树有多少个内部结点，就有多少棵子树。分析树本身是 S-树，它是一棵平凡子树。
子树与短语直接短语句柄素短语的对应关系：
每棵子树对应的符号串 (当然是句型的子串 )是这个句型相对于子树结点的一个短语；
如果这棵子树是二代子树，则这短语为直接短语；
最左的二代子树便是句柄；
如果子树对应的符号串含终结符，且在该子树中不再包含有终结符的子树，则是素短语。
显然从分析树出发找短语、句柄、素短语要直观得多
26
子树与短语直接短语句柄素短语的对应关系,
每棵子树对应的符号串 (当然是句型的子串 )是这个句型相对于子树结点的一个短语；
如果这棵子树是二代子树，则这短语为直接短语；
最左的二代子树便是句柄；
如果子树对应的符号串含终结符，且在该子树中不再包含有终结符的子树，则是素短语。
显然从分析树出发找短语、句柄、素短语要直观得多
27
三、二义性定义 2.16 文法 G的一个句子如果能找到两种不同的规范推导或二棵不同的分析树，则称这个句子是二义性的，
一个文法包含二义性的句子则这个文法是二义性的，
否则该文法是无二义性的。
一个文法是二义的，并不是说文法描述的的语言也是二义的，这也说明，对一个二义文法，如果能找到一个非二义文法，那么二义文法的二义性是可以消除的。
如果找不到，则二义文法描述的语言为先天二义的。
我们总是希望一个文法是无二义性的，使句子的分析可以唯一确定的方式进行。但文法的二义性是不可判定的，也即不存在一种算法，可在有限步内判定一个文法是否为二义的。
28
§ 2.3 形式语言分类
1956年，语言家 Noam Chomsky首先建立了形式语言的描述，定义了四类文法及相应的形式语言，并将它们与相应的识别系统相联系，推动了计算机科学的发展，对程序语言的设计，编译方法，计算复杂性等方面有重大影响。
Chomsky将文法分成 0型,1型,2型,3型四种类型。
29
定义 2.17
文法 G的每一个产生式均为下列形式：
α→β
其中,α∈ V*VnV*,即至少含一个非终结符，
β ∈ V*,
则文法 G称为 0型文法或短语文法。
0型文法相应的语言为 0型语言，或称递归可枚举集，它的识别系统是图灵（ Turing）机。
30
定义 2.18
文法 G的每一个产生式均为下列形式：
α→β 且 | α |? | β |
则文法 G为 1型文法，或上下文有关文法，也称上下文敏感文法。
1型文法相应的语言称为 1型语言或上下文有关语言，
它的识别系统是线性有界自动机。
下述的定义 2.18'与定义 2.18等价。
定义 2.18‘ 文法 G的每一个产生式均为下列形式：
αA?→αβ?其中 α,?∈ V*,A ∈ Vn,β ∈ V + 。
显然它满足定义 2.18的长度限制，但它更明确地表达了上下文有关的特性，即 A必须在的上下文环境中才能被替换。
31
定义 2.19 文法 G的每一个产生式均为下列形式：
A→α 其中 α∈ V*,A ∈ Vn
则称文法 G为 2型文法或上下文无关文法。
显然用 α去替换 A时，与 A的上下文无关。
2型文法相应的语言称为 2型语言或上下文无关语言。它的识别系统是下推自动机。
32
定义 2.20 文法 G的每个产生式均为下列形式：
A→α 或 A→α B
其中 α∈ Vt*,A,B∈ Vn,则文法 G称为 3型文法或正规文法、右线性文法。 3型文法相应的语言为 3型语言或正规语言，它的识别系统为有限自动机。
当然 3型文法呈左线性形式,A→α 或 A→ Bα也是一样的。
33
习 题,
2.1(a),(b)
2.2
2.3
2.5
2.6
