第03章、文法和语言

1、1第三章第三章 文法和语言文法和语言本章目的本章目的 为语言的语法描述寻求工具为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）（严谨、简洁、易读）形式形式工具工具形式语言形式语言，抽象地定义为一个数学，抽象地定义为一个数学系统。系统。 “形式形式”是指这样的事实：语言的所有规则只以是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。什么符号串能出现的方式来陈述。 2本章知识点本章知识点( (内容内容) )引言和预备知识引言和预备知识文法和语言的形式定义文法和语言的形式定义文法的类型文法的类型上下

2、文无关文法及其语法树上下文无关文法及其语法树上下文无关文法的句型分析上下文无关文法的句型分析有关文法实用中的一些说明有关文法实用中的一些说明33.1 文法的直观概念和文法的直观概念和语言概述语言概述当我们表述一种语言时，无非是说明这种语言的当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是以自然语言为例，人们

3、无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明人们可以给出一些规则，用这些规则来说明(或者或者定义定义)句子的组成结构。句子的组成结构。4“我是大学生我是大学生”。是汉语的一个句子是汉语的一个句子句子句子 =主语主语谓语谓语主语主语 =代词代词名词名词代词代词 =我我你你他他名词名词 =王明王明大学生大学生工人工人英语英语谓语谓语 =动词动词直接宾语直接宾语动词动词 =是是学习学习直接宾语直接宾语 =代词代词名词名词 有了一组规则以后，有了一组规则以后， 不断地用不断地用 =的的右边代替右边代替左边左边，就可以导出句子。，就可以导出句子。5“我是大学生我是大学生”的构成符合上述规

4、则，而的构成符合上述规则，而“我大学生是我大学生是”不符合上述规则，我们说不符合上述规则，我们说它不是句子。它不是句子。这些规则成为我们判别句子结构合法与否这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。一种描述元语言称为文法。6语语 言言 概概 述述语言是由句子组成的集合，是由一组符号所构成的语言是由句子组成的集合，是由一组符号所构成的集合。集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉

5、语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 语法语法 Syntax语言研究的三个方面语言研究的三个方面 语义语义 Semantics 语用语用 Pragmatics7如果不考虑语义和语用，即只从语法这一侧面来看如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。形式语言抽象地定义为一个数学系统。“形式形式”是指这样的事实：语言的所有规则只以什是指这样的事实：语言的所有规则只以什么符号串能

6、出现的方式来陈述。么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其形式语言理论是对符号串集合的表示法、结构及其特性的研究。特性的研究。是程序设计语言语法分析研究的基础。是程序设计语言语法分析研究的基础。83.2 3.2 有关定义和记号的回顾有关定义和记号的回顾符号和符号串符号和符号串符号：符号：可以相互区别的记号（元素）。可以相互区别的记号（元素）。字母表字母表 ：符号（元素）的非空有穷集合（符号集）。符号（元素）的非空有穷集合（符号集）。符号串：符号串：由字母表由字母表 中的符号组成的任何有穷序列称为该字母中的符号组成的任何有穷序列称为该字母表上的符号串。表上的符号串

7、。1.空符号串空符号串(没有没有符号的符号串符号的符号串)是是 上的符号串上的符号串 2.若若x是是 上的符号串，上的符号串，a是是 的元素，则的元素，则xa是是 上的符号串上的符号串 3. y是是 上的符号串，当且仅当它可以由上的符号串，当且仅当它可以由1和和2导出。导出。 例如：例如： =a,b =a,b ,a,b,aa,ab,aabba ,a,b,aa,ab,aabba都都是是 上的符号串上的符号串9 符号串符号串s的头（前缀）：的头（前缀）：移走符号串移走符号串s尾部的零个或多于零尾部的零个或多于零个符号得到的符号串。个符号得到的符号串。 如：如： b是符号串是符号串banana的一个

8、前缀。的一个前缀。 符号串符号串s的尾（后缀）：的尾（后缀）：删去符号串删去符号串s头部的零个或多于零头部的零个或多于零个符号得到的符号串。个符号得到的符号串。 如如:nana是符号串是符号串banana的一个后缀。的一个后缀。 符号串符号串s的子串：的子串：从从s中删去一个前缀和一个后缀得到的符中删去一个前缀和一个后缀得到的符号串。号串。 如如:ana是符号串是符号串banana的一个子串。的一个子串。10 对于每个符号串对于每个符号串s， s和和两者两者都都是符号串是符号串s的前缀，后缀的前缀，后缀和子串。和子串。 符号串符号串s的真前缀，真后缀，真子串：的真前缀，真后缀，真子串：任何非空

9、符号串任何非空符号串 x,相应地，是相应地，是s的前缀，后缀或子串，并且的前缀，后缀或子串，并且 s x 符号串的运算符号串的运算 符号串的长度：符号串的长度：符号串中符号的个数符号串中符号的个数.符号串符号串s的长度记的长度记为为|s|。 的长度为的长度为0 连接：连接：符号串符号串x x、y y的连接的连接, ,是把是把y y的符号写在的符号写在x x的符号之的符号之后得到的符号串后得到的符号串xy xy 如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcd xy=abcd 有有a = a a = a 方幂：方幂：符号串自身连接符号串自身连接n n次得到的符号串次得到的符号串

10、 a an n 定义为定义为 aaaaaa naa n个个a a的连接的连接 a a1 1=a, a=a, a2 2=aa=aa则则a a0 0=11 符号串集合符号串集合：若集合若集合A中所有元素都是某字母表中所有元素都是某字母表 上的符号上的符号串，则称串，则称A为字母表为字母表 上的符号串集合。上的符号串集合。 两个符号串集合两个符号串集合A和和B的乘积的乘积 定义为定义为 AB = xy|xxy|x A A且且y y B B 若若 集合集合A= ab,cdeab,cde ，B = 0,10,1 则则 AB = ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 使用使

11、用 * 表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合。）组成的集合。* *称为称为的闭包的闭包。 上的上的除除外外的所有符号串组成的集合记为的所有符号串组成的集合记为 + 。 + +称为称为的正闭包的正闭包。12例：例：=a,b=a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab, .2*.32*13有关定义和记号有关定义和记号 语言语言是由句子组成的集合，是由一组符号所构成的集合。是由句子组成的集合，是

12、由一组符号所构成的集合。换言之，字母表换言之，字母表 上上的一个语言是的一个语言是 上的一些符号串的集合上的一些符号串的集合 (字母表字母表 上上的每个语言是的每个语言是 *的一个子集的一个子集)。 例如：例如：字母表字母表=a,b ,=a,b ,* *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, 集合集合ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n, , 或表示为或表示为w|ww|w* *且且w=aw=an nb bn n,n1,n1为为字母表字母表 上上的一个语言。的一个语言。 集合集合a,

13、aa,aaa,a,aa,aaa, 或或表示为表示为w|ww|w* *且且w=aw=an n,n1 ,n1 为为字字母表母表 上上的一个语言。的一个语言。 是一个语言。是一个语言。 即即 是一个语言。是一个语言。14语言语言上上的有关运算的有关运算 设设L是（是（ 上的）一个语言，上的）一个语言，M是（是（ 上的）一个语言，上的）一个语言， 语语言言L和和M的并，交，差，补的并，交，差，补是一个语言。是一个语言。 语言语言L和和M的并为的并为 L M，是一个语言是一个语言: w|w is in L or w|w is in L or is in M is in M 如：如： L1 =a,b, =

14、a,b,y,z My,z M1 1 =0,1,2 =0,1,28,9 8,9 L1 M1 1=a,b,=a,b, y,z y,z， 0,1,20,1,28,9 8,9 语言语言L和和M的连接的连接是一个语言，记是一个语言，记为为 LM LM=st |sst |sL且且 t tM 如：如： L1M1 =a1,b1, =a1,b1,y1,z0,z1,a2,b2y1,z0,z1,a2,b2a9a9z9 z9 有有L = = L=L。 L的的n次连接次连接Ln= LL.L 15 语言语言L的的 闭包闭包记记为为 L*， L*= L0 L1 L2 L0= Ln= L Ln-1= Ln-1 L，n 1 语

15、言语言L的正的正 闭包闭包记记为为 L+ L+= L1 L2 L3 . L*= L+ 如：如： L1 =a,b,=a,b,y,zy,z， M M1 1 =0,1,2=0,1,28,9 8,9 （L1 M1 1）=a,b,=a,b, y,z y,z，0,1,20,1,28,98,9 （L1 M1 1）* *=a,b,=a,b, y,z,0,1,2 y,z,0,1,28,9,8,9,aa,0a,xyz,6789st. L1（L1 M1 1）* *=所有字母打头的字母和数字符号串所有字母打头的字母和数字符号串 163.3 3.3 文法和语言的形式定义文法和语言的形式定义如果语言是如果语言是有穷有穷的

16、（只含有有穷多个句子），可以将句子的（只含有有穷多个句子），可以将句子逐一列出来表示逐一列出来表示如果语言是如果语言是无穷无穷的，找出语言的有穷表示。语言的有穷表的，找出语言的有穷表示。语言的有穷表示有两个途经：示有两个途经： 1. 1. 生成方式生成方式 （文法）（文法）：语言中的每个句子可以用严格语言中的每个句子可以用严格定义的规则来构造。定义的规则来构造。 2. 2. 识别方式识别方式（自动机）（自动机）：用一个过程，当输入的一任意用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答串属于语言时，该过程经有限次计算后就会停止并回答“是是”，若不属于，要么能停止并回答

17、，若不属于，要么能停止并回答“不是不是”，（要，（要么永远继续下去。）么永远继续下去。） 17文法即是用生成方式描述语言的：文法即是用生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义，进而在下面给出文法的定义，进而在文法的定义的基础上，文法的定义的基础上，给出给出推导的概念，句型、句子和语言的定义。推导的概念，句型、句子和语言的定义。18文法文法G定义为四元组定义为四元组(VN，VT，P，S )其中：其中：VN为非终结符号为非终结符号(或语法实体，或变量或语法实体，或变量)集；集；VT为终结符号集；为终结符号集；P为产

18、生式为产生式(也称规则也称规则)的集合；的集合； VN，VT和和P是是 非空有穷集。非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。一条产生式中作为左部出现。 VN和和VT不含公共的元素，即不含公共的元素，即VN VT = 用用V表示表示VN VT ，称为文法，称为文法G的字母表或字汇表。的字母表或字汇表。规则规则，也称重写规则、产生式或生成式，是形如，也称重写规则、产生式或生成式，是形如或或 =的的(，)有序对，其中有序对，其中是字母表是字母表V的正闭包的正闭包V+中的中的一个符号，且一个符号，且至

19、少包含一个非终结符至少包含一个非终结符;是是V*中的一个符号。中的一个符号。称为规则的左部，称为规则的左部，称作规则的右部。称作规则的右部。19例：例： 文法文法G=（VN，VT，P，S）VN = S VT = 0, 1 P= S0S1， S01 S为开始符号为开始符号20例：例： 文法文法G=（VN，VT，P，S）VN =标识符，字母，数字标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P= a, zz 0,0, , 99 S=21 1. G1. G：SaASaAb Aab Aab AaA AaAb A A 2. GS 2. GS： SaASaAb Aab AaA Aab AaA

20、b A A 3.3. GSGS：SaASaAb Aab |aA Aab |aAb | | 一般用写法一般用写法 3 322元符号元符号: = = | | 习惯表示习惯表示 大写字母：大写字母：非终结符非终结符 小写字母：小写字母：终结符终结符如：如： S AB A Ax | y B z231. 直接推导直接推导 是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=, v=,w=, 其中其中VV* *,V,V* * 则称则称v v直接推导直接推导到到w,w,也称也称w w是是v v的直接推导，的直接推导，记作记作 v v w w 也称也称w w直接归约直接归约到到v

21、v例：例：GSGS： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S124 + *2. 推导推导: 若存在若存在v w0 w1 . wn=w,(n0) 则记为则记为v = w，称，称v推导出推导出w，或，或w归约到归约到v 若有若有v = w，或，或v=w， 则记为则记为v = w+*25例：例：GSGS： S0S1， S01 S 0S1 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S = 00001111 S = S 00S11 =

22、00S11+*261. 句型句型 有文法有文法G，若，若S = x，则称，则称x是文法是文法G的句型。的句型。 即：即：从开始符号推导出的任意符号串。从开始符号推导出的任意符号串。2. 句子句子 有文法有文法G，若，若S = x，且，且xVVT T* *，则称，则称x是文法是文法G的的句子。句子。即：即：从开始符号推导出的终结符号串。从开始符号推导出的终结符号串。例：例：G G： S0S1， S01 S 0S1 00S11 000S111 00001111 S 01 G的的句型句型有：有：S，0S1，00S11，000S111，00001111，01 G的的句子句子有：有：00001111,

23、01*27例：例：GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式28由文法由文法G生成的生成的语言语言记为记为L(G)，它是文法，它是文法G的一切句子的集合的一切句子的集合: L(G)=x|S = x，其中，其中S为文法的开始符为文法的开始符号，且号，且x VVT T* * 例：例：GS： S0S1， S01 L(G)=0n1n|n1*29文法的等价文法的等价若若L（G1）=L（G2），则

24、称文法），则称文法G1和和G2是等价的。是等价的。如文法如文法G G1AA：A0R A0R 与与 G G2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1303.4 3.4 文法的类型文法的类型 通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky(乔姆斯基）将文法分为四种类型：乔姆斯基）将文法分为四种类型：0型文法（短语文法）型文法（短语文法）：对任一产生式：对任一产生式，都，都有有(V(VN NVVT T) )+ +，且至少含有一个非终结符，且至少含有一个非终结符， (V(VN NVVT T) )* *1 1型文法（上下文有关文法）型文法（

25、上下文有关文法）：对任一产生式对任一产生式，都有，都有|， 仅仅仅仅 SS除外除外 31文法的类型文法的类型( (续续) )2 2型文法（上下文无关文法）型文法（上下文无关文法）：对任一对任一产生式产生式，都有，都有VVN N ， (V(VN NVVT T) )* *3 3型文法（正规文法）型文法（正规文法）：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其，其中中AVAVN N ，BVBVN N ，aVaVT T32文法的类型举例文法的类型举例例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS： SCDSCDAbAaAbAa CaCA CaCABaB

26、ABaBA CbCB CbCBBbAbBbAbADaDADaD Ca CaBDbDBDbD Da DaAaDaAaDa33文法的类型举例文法的类型举例例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|134文法的类型举例文法的类型举例GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d例：例：3 3型文法（正规文法）型文法（正规文法）35四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系2型文法型文法1

27、型文法型文法0型文法型文法3型文法型文法36文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG ）产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法型文法或上下文无关文法（ CFG ）产生的语言产生的语言称为称为2型语言型语言或上下文无关或上下文无关语言（语言（ CF L ） 3 3型文法或正则（正规）文法型文法或正则（正规）文法（ RG ）产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（正规）语言（语言（ RL ）四种文法之间

28、的关系四种文法之间的关系 是将产生式做进一步限制而是将产生式做进一步限制而定义的。定义的。 37根据形式语言理论根据形式语言理论, ,文法和自动机（识文法和自动机（识别系统）间有这样的关系别系统）间有这样的关系 0型文法型文法（短语结构文法）的能力相当于（短语结构文法）的能力相当于图灵机图灵机，可以表征任何递归可枚举集，而且任何可以表征任何递归可枚举集，而且任何0型语言都型语言都是递归可枚举的是递归可枚举的 1型文法型文法（上下文有关文法）：产生式的形式为（上下文有关文法）：产生式的形式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上的上下文中时，才允许下文

29、中时，才允许取代取代A A。其识别系统是。其识别系统是线性界线性界限自动机限自动机。38 带带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁头磁头 任何能用任何能用图灵机图灵机描述的计算都能机械实现，描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵任何能在现代计算机上实现的计算都能用图灵机描述机描述39 2型文法型文法（上下文无关文法（上下文无关文法CFG）：产生式的形式）：产生式的形式为为AA，取代取代A A时与时与A A的上下文无关。其识别的上下文无关。其识别系统是不确定的系统是不确定的下推自动机下推自动机。 3型文法型文法（

30、正规文法（正规文法RG）：产生的语言是有）：产生的语言是有穷自穷自动机动机（FA）所接受的集合）所接受的集合403.5 3.5 上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的上下文无关文法有足够的能力描述程序设计语言的语法结构语法结构语法树语法树-句型推导句型推导的的直观表示直观表示41GE： EE+T|T TT*F|F F(E)|iEE+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*i EE+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*iEE+T T+T T+T*F F+T*F F

31、+F*F i+F*F i+F*i i+i*i42规范推导规范推导 规范句型规范句型最左（最右）推导：最左（最右）推导：在推导的任何一步在推导的任何一步，其，其中中、是句型，都是对是句型，都是对中的最左（右）非终中的最左（右）非终结符进行替换结符进行替换最右推导被称为最右推导被称为规范推导规范推导。由规范推导所得的句型称为由规范推导所得的句型称为规范句型规范句型43 设设G=( VN,VT,P,S)为一为一CFG，若一棵树满足下列，若一棵树满足下列4个条件，个条件，则此树称作则此树称作G的语法树的语法树(推导树推导树)(派生树）：派生树）：1. 每个结点都有一个标记，此标记是每个结点都有一个标记

32、，此标记是V的一个符号的一个符号2. 根的标记是根的标记是S3. 若一结点若一结点n至少有一个它自己除外的子孙，并且有标记至少有一个它自己除外的子孙，并且有标记A，则肯定则肯定AVVN N4. 如果结点如果结点n有标记有标记A,其直接子孙结点从左到右的次序是其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中的一个产生式中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行谓之语法树的结果：从左到右读出叶子的标记而构成的行谓之 44语法树语法树-句型推导句型推导的的直观表示直观表示给定文法给定文法G=(VN

33、,VT,P,S)，对于，对于G的任何句型都能构的任何句型都能构造与之关联的语法树造与之关联的语法树(推导树推导树)定理：定理：G为上下文无关文法，为上下文无关文法，对于对于，有，有S = ，当且仅当，当且仅当文法文法G有以有以为结果的一棵语法树为结果的一棵语法树(推导树推导树)*45构造语法树构造语法树GE： EE+T|T TT*F|F F(E)|iEE+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*i E EE + T E + T T E E + T T F46E EE+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*i (最左推导最左推导)

34、E EE+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i (最右推导最右推导)E EE+T T+T T+T*F F+T*F F+F*F i+F*F i+F*i i+i*i E E E + T E + T T T T T * * F F F F i F F i i i i i 看不出句型中的符号被替代看不出句型中的符号被替代的顺序的顺序47上下文无关文法的语法树的用处上下文无关文法的语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a

35、 b a句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点叶子结点：树中：树中没有子孙的结点没有子孙的结点。从左到右从左到右读出推导树的读出推导树的叶子标记叶子标记连接成的连接成的文文法符号法符号串串，为，为GS的的句型句型。也把该推导树称。也把该推导树称为该为该句型句型的的语法树语法树。48上下文无关文法的语法树上下文无关文法的语法树z推导过程中推导过程中施用施用产生式产生式的的顺序顺序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaS

36、aASaSbASaSbAaaabAaaabbaa49一棵语法树表示了一个句型的种种可能的一棵语法树表示了一个句型的种种可能的( (但但未必是所有的未必是所有的) )不同推导过程，包括最左不同推导过程，包括最左( (最右最右) )推导。推导。但是，一个句型是否只对应唯一的一棵语法但是，一个句型是否只对应唯一的一棵语法树呢树呢? ?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左( (最右最右) )推推导呢导呢? ?50例：例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i

37、 i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+i51 若一个文法存在某个句子对应两棵不同的语法树，则称这若一个文法存在某个句子对应两棵不同的语法树，则称这个个文法是二义文法是二义的的或者，若一个文法存在某个句子有两个不同的最左（右）或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个推导，则称这个文法是二义文法是二义的的 判定任给的一个上下文无

38、关文法是否二义，或它是否产生判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件，如：规定运解的，但可以为无二义性寻找一组充分条件，如：规定运算符的优先顺序和结合规则。算符的优先顺序和结合规则。 52文法的二义性和语言的二义性是两个不同的概念。因为可能文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法有两个不同的文法G G和和GG，其中，其中G G是二义的，但是却有是二义的，但是却有L(G)=L(G)L(G)=L(G)，也就是说，这两个文法所

39、产生的语言是相，也就是说，这两个文法所产生的语言是相同的。同的。二义文法改造为无二义文法二义文法改造为无二义文法GE: E i GEGE: E i GE：E T|E+TE T|E+T E E+E T F|T E E+E T F|T* *F F E E E E* *E F E F （E E）|i|i E (E) E (E) 规定优先顺序和结合律规定优先顺序和结合律z 如果产生上下文无关语言的每一个文法都是二义的，则说如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望

40、对它的每个语句的分希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。析是唯一的。533.6 3.6 句型的分析句型的分析一、有关概念一、有关概念1.句型分析句型分析 句型分析就是识别一个符号串是否为某文法的句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。句型，是某个推导的构造过程。2.分析程序分析程序 在语言的编译实现中，把完成句型分析的程序在语言的编译实现中，把完成句型分析的程序称为称为分析程序分析程序或或识别程序识别程序。分析算法又称。分析算法又称识别算法识别算法。3.从左到右的分析算法从左到右的分析算法 从左到右的分析算法从左到右的分析算法，即总是从左，即

41、总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。而依次识别右边的一个符号，直到分析结束。54二、句型的分析算法分类二、句型的分析算法分类 分析算法可分为分析算法可分为2类：类：1.自顶向下自顶向下(自上而下自上而下)分析法：分析法： 从文法的开始符号出发，反复使用文法的产从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的生式，寻找与输入符号串匹配的推导推导。2.自底向上自底向上(自下而上自下而上)分析法：分析法： 从输入符号串开始，逐步进行从输入符号串开始，逐步进行归约归约，

42、直至归约，直至归约到文法的开始符号。到文法的开始符号。55两种方法反映了两种语法树的构造过程两种方法反映了两种语法树的构造过程自顶向下方法自顶向下方法 是从文法符号开始，将它做为语是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串；结果正好是输入符号串；自底向上方法自底向上方法 则是从输入符号串开始，以它做则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树。为语法树的结果，自底向上地构造语法树。56自顶向下的语法分析自顶向下的语法分析- -例例例：文法例：文法G：S cAd A ab A a识别输入串识

43、别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabd57自底向上的语法分析自底向上的语法分析- -例例例：文法例：文法G： S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导： cAd cabd S cAd58(1)S cAd (2) A ab (3)A a 识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子1. 1. 自顶向下的语法分析自顶向下的语法分析若若S c

44、Ad 后选择后选择(3)扩展扩展A， S cAd cad ， 那将会？那将会？ w的第二个符号可以与叶子结点的第二个符号可以与叶子结点a得以匹配，但第得以匹配，但第三个符号却不能与下一叶子结点三个符号却不能与下一叶子结点d匹配匹配？宣告分析失败（其意味着，识别程序不能为串？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即构造语法树，即cad不是句子）不是句子）-显然是错误的结论。显然是错误的结论。导致失败的原因是在分析中对导致失败的原因是在分析中对A的选择不是正确的。的选择不是正确的。 S c A d a59对串对串cabd的分析中，如果不是的分析中，如果不是选择选择ab用产生式用

45、产生式(2),而是选而是选择择a用产生式用产生式(3)将将a归约到了归约到了A，那么最终就达不到归约，那么最终就达不到归约到到S的结果，因而也无从知的结果，因而也无从知道道cabd是一个句子。是一个句子。c a b d c A b d a(1)S cAd (2) A ab (3)A a 识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子2. 2. 自底向上的语法分析自底向上的语法分析60三、句型分析的有关问题三、句型分析的有关问题1. 在自顶向下的分析方法中在自顶向下的分析方法中如何如何选择选择使用使用哪个哪个产生产生式进行推导式进行推导？假定要被代换的最左非终结符号是假定要

46、被代换的最左非终结符号是B，且有，且有n条规则：条规则：BA1|A2|An，那么如何确定用哪个右，那么如何确定用哪个右部去替代部去替代B？2.在自底向上的分析方法中在自底向上的分析方法中如何如何识别可归约的串识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选选择一个择一个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串，该子串称为称为“可归约串可归约串”61四、四、刻画刻画“可归约串可归约串”文法文法GS1. 句型的短语句型的短语 S = A且且 A = ，则称则称是是句型句型相相对于非终结符对于非终结符A的的短语。短语。2. 句

47、型的直接短语句型的直接短语(或简单短语或简单短语) 若有若有A ，则称则称是句型是句型相对于非终相对于非终结符结符A 的的直接短语。直接短语。3. 句型的句柄句型的句柄 一个句型的一个句型的最左直接短语最左直接短语称为称为该句型该句型的的句柄。句柄。*+62例例i i* *i+ii+i例例 ：i i* *i+i i+i 的短语、直接短语和句柄的短语、直接短语和句柄 E E + T T FT * F i3 短语短语：i1* * i2+ + i3， i1* * i2 ，F i2 i1 ， i2 ， i3 。 i1 直接短语直接短语： i1 ， i2 ， i3 。句柄句柄： i1 GEGE：EE+T

48、|TEE+T|T TT TT* *F|FF|F F(E)|i F(E)|i句型：句型：i i* *i+ii+i633.7 3.7 文法实用中的一些说明文法实用中的一些说明- -化简文法化简文法一、文法中不含有害规则和多余规则一、文法中不含有害规则和多余规则1. 有害规则：有害规则：形如形如PP的产生式。会引起文法的二义性。的产生式。会引起文法的二义性。2. 多余规则：多余规则：指文法中任何句子的推导都不会用到的规则。指文法中任何句子的推导都不会用到的规则。文法中不含有文法中不含有不可到达不可到达和和不可终止不可终止的非终结符。的非终结符。 3. 不可到达：不可到达：文法中某些非终结符不在任何规

49、则的右部出文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。现，该非终结符称为不可到达。4. 不可终止不可终止: 文法中某些非终结符，由它不能推出终结符文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。号串，该非终结符称为不可终止。64二、不含多余非终结符的条件二、不含多余非终结符的条件 对于文法对于文法GS，为了保证任一非终结符，为了保证任一非终结符A在句在句子推导中出现，必须满足如下两个条件：子推导中出现，必须满足如下两个条件： 1. A必须在某句型中出现必须在某句型中出现 即有即有S = A，其中，其中，属于属于V V* * 2. 必须能够从必须能够从A

50、推出终结符号串推出终结符号串t来来 即即A = t，其中，其中tVT*65三、三、化简文法化简文法例例例：例：GS ： 1) SBe 2) BCe D为不可到达为不可到达 3) BAf C为不可终止为不可终止 4) AAe 5) Ae 6) CCf 7) Df 产生式产生式 2），），6），），7）为）为多余规则，多余规则，应去应去掉。掉。66四、四、上下文无关文法中的上下文无关文法中的规则规则z具有形式具有形式A的规则称为的规则称为规则规则，其中，其中AVNz某些著作和讲义中限制这种规则的出现。因某些著作和讲义中限制这种规则的出现。因为为规则会使有关文法的一些讨论和证明变规则会使有关文法的一些讨论和证明变得复杂得复杂z两种定义的唯一差别是两种定义的唯一差别是句子在不在语言中。句子在不在语言中。1. 什么是什