编译原理第三章文法和语言.ppt

1、第三章文法和语言,2,学习本章的目的,为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）。 构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。 形式工具-形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。,3,【学习目标】,本章目的是为语言的语法描述寻求工具 掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一-文法。 熟练使用文法定义程序设计语言的单词和语法成分 对形式语言的理论有一个初步基础,4,【学习指南】, 什么

2、是文法，什么是它定义的语言？ 在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？ 什么是语法分析？语法分析方法的分类。,【难重点】,关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。形式是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。,5,知识体系,推导/归约,凑规则,6,教学内容,字母表与符号串 文法与语言的关系 文法的概念 文法与语言的形式定义 文法构造与文法简化 由语言构造文法的例子 文法的简化 语法树与文法的二义性,7,语言,语言是由句子组成的集合，是由一组记号所构成的集合。 汉

3、语-所有符合汉语语法的句子的全体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体 研究语言 ： 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系,8,研究程序设计语言： 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面： 语法 Syntax 语义 Semantics 语用 Pragmatics 语法 - 表示构成语言句子的各个记号之间的组合规律。 语义 - 表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 -表示在各个记号所出现的行为中，它们的来源、使用和影响。,9,如果不考虑语义和

4、语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。 形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,形式语言,10,一、字母表 字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如: 1.机器语言：由符号“0”和“1”组成的字母表， =0，1 2.ASCII字符集； 3.汉语的字母表中包括汉字、数字及标点符号 4. C语言字母表为： =AZ， az， 09， +， -， *， /， ，:， ， ; ， ， (， )， ，

5、， ， ,3.1 符号和符号串,11,二、符号串 1.符号 一个抽象实体，我们不再形式地定义它(就象几何中的”点”一样)。例如字母是符号，数字也是符号。 2.符号串 由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串，也称作“字”或“句子”。 (1)不包含任何符号的符号串，称为空符号串简称空串，记为 。 (2) 若=a，b 则a,b,ab,ba,abb,baa.是上的符号串。 在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。,12,设z是符号串 长度:是该符号串中的符号的数目。例如|aab|=3，|=0。 前缀(头):删去z尾部的若干个(包括0

6、个)符号所得的。 表示: z=x 后缀(尾):删去z头部的若干个(包括0个)符号所得的。 表示: z=x 真前缀(固有头)x，真后缀(固有尾)x :xz 子串: 从z中删去一个前缀和一个后缀 逆转（用z表示）：将z中的符号按相反次序写出而得到的符号串。,3术语,13,例：符号串z=banana 长度：banana=6 前缀：,b,ba,ban,bana,banan,banana 真前缀: ,b,ba,ban,bana,banan 后缀：banana,anana,nana,ana,na,a, 真后缀: anana,nana,ana,na,a, 子串: banana,anana,banan,ana

7、n, 逆转（用z表示）：ananab,14,1.连接：设x和y是符号串，它们的连接 xy是把y的符号写在x的符号之后得到的符号串。例如：x=ba,y=nana,xy=banana x=x=x 2.方幂：符号串x自身连接n次得到的。 x0= ; x1=x; x2=xx; ;xn=xn-1x=xxn-1; 例如： x=ba, x1= ba, x2=baba, x3=bababa, xn=(ba)n,三.符号串的运算,15,定义:集合中的一切元素都是某字母表上的符号串 设A和B是两个符号串集合，A=ab,bc,B=ac,cb则 1. 乘积(连接)：AB=xy|xA and yB 例：AB=abac,

8、abcb,bcac,bccb 2. 合并：AB = x|xA or xB 例：AB = ab,bc,ac,cb 3. 空集: 注意：A=A=A 4. 方幂：符号串集合的自身乘积。 A0=，A1A，A2AA，. AnAn-1AAAn-1 例：A=a,b则： A0=，A1=A=a,b，A2=AA=aa,ab,ba,bb A3A2A=AA2=aaa,aab,aba,abb,四. 符号串集合(语言）的运算,16,5. 集合A的Kleene闭包(星闭包)，记作A*，字母表A的各次方幂之并。其含义是由A上符号组成的所有串的集合（包括空串) A*Ai(i=0) =A0A1A2A3 A=a,b A*,a,b,

9、aa,ab,ba,bb, aaa,aab,aba,abb, 6集合A的正闭包，记作A+，其含义是由字母表A上的符号组成的所有串(不包括空串)的集合。 A+Ai(i =1) =A1A2A3A4 A=a,b A+a,b,aa,ab,ba,bb, aaa,aab,aba,abb, A* A0 A+ A+=AA*A*A,17,语言是由句子组成的集合，是由一组符号所构成的集合。换言之，字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。 例如：字母表=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或表示为w|w*且

10、w=anbn,n1 字母表上的一个语言。 集合a,aa,aaa, 或表示为w|w*且w=an,n1 字母表上的一个语言。 是一个语言。 即 是一个语言。,18,给出语言上的有关运算,设 L是（上的）一个语言 M是（上的）一个语言 语言L和M的并，交，差，补是一个语言。 语言L和M的并为 LM: LM=w|wL 或 wM 如： L1=a,b,y,z M1=1,28,9 L1M1=a,b, y,z，1,28,9 语言L和M的连接为LM：LM=st|sL且tM 如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L = L=L。 L的n次连接Ln= L L.L 如： L12 =aa,ab

11、,az,ba,bz,za,zz,19,语言L的闭包记为 L*， L*= L0L1L2.Ln L0= ， Ln= L Ln-1= Ln-1 L,n1 语言L的正闭包记为 L+， L+= L1L2L3 .Ln L+= L L*= L*L L*= L+ 如： L1 =a,b,y,z M1 =1,28,9 （L1M1）=a,b, y,z，1,28,9 （L1M1）*=a,b,y,z,1,2,8,9, aa,1a,xyz,6789st. L1（L1M1）*=所有字母打头的字母和数字符号串,20,例如：L=AZ,az D=09 1LD是由所有一个字母后跟一个数字组成的符号串所构成的集合。 2LD=AZ,a

12、z ,09 3. L4是所有由四个字母构成的符号串的集合。 4L（LD)* 是所有由字母打头的字母和数字组成的符号串所构成的集合。 5D+是由所有长度大于等于1的数字串所构成的集合。,如何来描述一种语言？ (1)枚举法 例:1,11,111,1111 (2)自然语言 (3)省略表示法 例:1,11,111, (4)描述法 例:1i|i0,21,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示； 如果语言是无穷的，则需要找出语言的有穷表示。语言的有穷表示有两种途经： 生成方式（文 法）：语言中的每个句子可以用严格定义的规则来构造。 识别方式（自动机）：是使用自动机的行为描述语言。

13、它的行为相当于一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”；若不属于，要么能停止并回答“不是”，要么永远继续下去。,22,文法即是生成方式描述语言的： 语言中的每个句子可以用严格定义的规则来构造。下面给出文法的定义，进而在文法定义的基础上，给出推导的概念，句型、句子和语言的定义。,23,3.2 文法和语言的形式定义,文法的直观概念和语言概述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以

14、给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用BNF来表示这种句子的构成规则：,24,语法规则：“句子由主语后跟随谓语组成”表示为：句子 主语 谓语,句子主语 谓语 主语代词 主语名词 代词我 代词你 代词他 名词王明 名词大学生 名词工人 名词英语 谓语 动词 直接宾语 动词 是 动词学习 直接宾语 代词 名词,一、引子,25,有了一组规则以后，按照如下方式用它们导出句子：开始去找左端的带有的规则并把它由右端的符号串代替，这个动作表示成： 句子 主语谓语， 然后在得到的串中,选取或,再用相应规则的右端代替之

15、。比如,选取了,并采用规则, 那么得到:,重复做下去。,句子 主语 谓语 代词 谓语 我 谓语 我 动词 直接宾语 我 是 直接宾语 我 是 名词 我 是 大学生,句子根据规则推导出来,26,分析：我是大学生,谓语,主语,代词,动词,直接宾语,句子,大学生,我,是,名词,27,句子 + 我是大学生 英语是工人 大学生是英语 其中，符合语法且合符语义的句子仅是： 我是大学生。 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述

16、元语言称为文法。,句子既要符合语法又要符合语义,28,每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看： 其一,是该句子的创立者所想要表示的意义; 另一,是接收者所检验到的意义。 这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,29,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称为形式语言。形式语言可以抽象地定义为一个数学系统。 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的

17、表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。,30,1 文法是一个数学系统 文法是描述语言的语法结构的形式规则(语法规则)。 由下列基本成份来刻画：一组基本符号，一组形成规则，一组公理，一组推理规则。 有关文法术语的概念： 非终结符用来代表语法范畴（语法单位）； 终结符语言中不可再分的字符串； 开始符号一个特殊的非终结符号，它表示方法所定义的是什么样的语法范畴； 产生式(规则)用来定义符号串之间关系的一组规则(语法规则)；,二、文法和语言的定义,31,VN是一个非空有穷非终结符号集合； VT是一个非空有穷终结符号集合； VTVN；字汇表(词汇表)V= VTVN SVN ，称为

18、开始符号或识别符号； 至少要在一条产生式中作为左部出现。 P是一个产生式(规则)的非空有穷集合， 每个产生式的形式是(或:=)，其中V+，V*。开始符号S至少必须在某个产生式的左部出现一次 。 1，2 缩写形式：1|2,文法是四元组G=（VN ,VT ,P, S ），其中：,32,句子的语法有四部分：终结符号集，非终结符号集，语法规则，开始符号,上例中： 终结符号集 VT=我,你,他,王明,大学生,工人,英语,是,学习 非终结符号集 VN= 句子，主语，谓语，代词，名词，动词，直接宾语 语法规则集 P=句子 主语谓语， 开始符号 S=句子,33,文法的优点 文法给出了精确的，易于理解的语法说明

19、 自动产生高效的语法分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改,34,G=(，a,+,*,(,)， P, ) P： * （)a 即：EE+TT TT*FF F(E)a,例3.2 算术表达式的文法G:,35,习惯上只将产生式写出，并有如下约定：,第一条产生式的左部是开始符号; 用括起的是非终结符，否则为终结符。 大写字母表示非终结符，小写字母表示终结符; G可写成GS，其中S是开始符号,36,例：文法G=（VN，VT，P，S） VN = S , VT = a, b P= SaSb, Sab S为开始符号,可写成： G：SaSb Sab,或写成： GS：SaSb Sa

20、b,37,为定义文法所产生的语言，我们还需要引入推导的概念。 推导与归约 产生式定义了V*中的各个符号之间的关系。 推导是从开始符号开始，通过产生式的右部取代左部的过程，最终能产生一个语言的句子。 归约是从给定源语言的句子开始，通过产生式的左部取代右部的过程，最终到达开始符号。,2. 直接推导和推导的定义,38,推导的分类,39,定义3.2 直接推导 “” 令G=(VN ,VT,P,S）， 若P, 且,(VTVN)*, 则称(应用规则)直接推出, 记作： 或者说：直接推导出 直接归约到,例：G：S0S1，S01 直接推导： 0S10011 （v=0S1，w=0011，使用规则S01，=0，=1

21、） S0S1 （v=S，w=0S1，使用规则S0S1，=，=） 0S100S11 （v=0S1，w=00S11，使用规则S0S1，=0，=1）,40,定义3.3 推导： + 如果存在一个直接推导序列： v=w0w1w2 wn（n1） 表示成 v+ wn (v推导出w，或w归约到v) 定义3.4 广义推导： * v=w或者v+wn ,表示成 v* wn 最左推导：A (A)，VT* 最右推导：A (A)，VT*,例：G： S0S1，S01 0S1 00S11 000S111 00001111 即 0S1 + 00001111 也记作 0S1 * 00001111,41,T+T,F+T,a+T*F

22、,E+T,E,a+F*F,a+a*F,a+a*a,例：EE+TT TT*FF F(E)a 写出对符号串w=a+a*a的最左、最右推导过程。,E+T*F,E+T*a,E+F*a,E+a*a,E+T,E,T+a*a,F+a*a,a+a*a,最左推导,最右推导,EE+TT+TF+T a+Ta+T*F a+F*Fa+a*F a+a*a,EE+TE+T*FE+T*a E+F*aE+a*a T+a*aF+a*aa+a*a,可以记作：E +a+a*a,a+T,42,定义3.5 句型：设文法G=(VN,VT,P,S)。如果符号串x是从识别符号推导出来的，即S *x，则称x是文法GS的句型。 句子：x仅由终结符

23、号组成（即S*x，且xVT*），则称x是GS的句子。 简记：仅含终结符号的句型是一个句子。 定义3.6 语言 L(G）：是由文法G产生的所有句子组成 的集合：L(G) x |S +x且 xVT*,3、语言的定义,43,例：考虑一个文法G(0,1,S,S，P）其中P：S0S1 01,S0S1 00S11 03S13 0n-1S1n-1 0n1n,S0S1 0011 句型S,0S1,0011 句子0011,S01 句型S,01 句子01,使用第二个产生式一次得到,L(GS)=0n1n|n1,使用第一个产生式n-1次，再使用第二个产生式一次得到,使用第一个产生式n-1次，再使用第二个产生式一次得到,

24、44,定义3.7,若L（G1）=L（G2），则称文法G1和G2等价。,GS: S0S1 S01 S01 S0S1 0011 S0S1 00S11 0n1n L(GS)=0n1n|n1,GA: A0R A01 RA1 A01 A0R0A1 0011 A0R0A1 00R100A11 0n1n L(GA)=0n1n|n1,L(GS)=L(GA) GS和GA等价,45,递归产生式与递归文法 递归：同一操作或同一组操作的连续重复。 递归产生式：产生式的左部和右部出现了相同非终结符。如： 左递归产生式 UU 右递归产生式 UU 自嵌入产生式 UU 递归文法： 直接递归：文法中有递归产生式。 间接递归：经

25、过若干步推导，出现递归。 例: UVx VUy|z UVxUyx,46,递归文法的用处：用于定义无限语言(递归语言) 总结：语言无限，一定存在递归。 语言有限，一定不存在递归。 例1：GS: SaB|bB Ba|b,SaB aa,SaB ab,SbB ba,SbB bb,L(GS)=aa,ab,ba,bb,47,例:G: | 0|1|2|3|9,DN S 1位数 0|1|9,DN NS SS 0S|1S|9S 2位数,DN NS NSS SSS 0SS|9SS 3位数,等等 L(GD)=V+ V=0,1,，9,48,例：GS：SaA|a AaS Sa SaA aaS aaa SaA aaS a

26、aaA aaaaS aaaaa,说明： 本例是较简单的文法的例子，比较容易理解文法能产生什么，一般来说，确定文法将产生什么可能是困难的。,L(GS)=a2n+1|n0,49,已知文法，写出相应的语言描述应满足： 该文法所推导的任何句子都包含在语言的描述中； 所描述的语言不包含任何该文法不包含的句子，即：文法推导不出来的句子。 换句话说，文法推导不出非已知的句子。,50,3.3 文法的类型,自从乔姆斯基(Chomsky)于1956年建立形式语言的描述以来，形式语言的理论发展很快。这种理论对计算机科学有着深刻的影响，特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。 乔姆斯基把

27、文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。,51,0型（短语） 产生式形式 , (VNVT)+且至少含有一个非终结符，而(VNVT)* 1型（上下文有关） 产生式形式：均满足|；仅S例外，但S不得出现在任何产生式的右部。 2型（上下文无关） 产生式形式： ，VN，(VTVN)* 3型（正规文法） (右线性) AaB 或 A a (左线性) ABa 或 A a 其中：A,BVN ,aVT,52,例：2型（上下文无关） 文法GS： SAB ABS|0 BSA|1,例：3型（正规） GS：S0A|1B|0 A0A|1B|0S B1B|1|0,53,四种文

28、法之间的逐级“包含”关系,0型文法强于1型文法 1型文法强于2型文法 2型文法强于3型文法,54,文法和语言,0型文法产生的语言称为0型语言 1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL） 3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL） 四种文法之间的关系是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,形式语言小结：,计算机语言的描述需借助

29、形式语言 如：用2型文法描述高级语言的语法规则 文法的用途 以有限的规则和符号，说明无穷的句子 成为语言设计和实现的依据 文法特征（0,1,2,3型) 反映语言结构的复杂性、决定分析方法,56,1.语法树的定义 表示一个句型推导的图表称为语法树，它描述的句子的结构。 设G=(VN,VT,P,S),G的一棵语法树满足如下条件： 每一个结点有一个标记，此标记是VTVN中的符号。 根的标记是S。 若某结点是内部结点且有标记A，则A必在VN中。 若编号为n的结点有标记A,结点n1,n2,nk是点n的从左到右的儿子,并分别有标记A1,A2,Ak,则AA1A2Ak必须是P中的产生式。 语法树的结果： 从左

30、到右读出叶子的标记而构成的行。,3.4 上下文无关文法及其语法树,57,A,a,S,2,3,4,例： G=(S,A,a,b,P,S） 其中 P： SaASa ASbASSba G的一棵推导树如下图：,S,1,b,S,A,5,6,7,a,8,a,9,b,a,10,11,语法树是描述上下文无关文法句型推导 的直观方法,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。 也把该推导树称为该句型的语法树。 句子：aabbaa,58,语法树句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)。 定理： G为上

31、下文无关文法，对于，有S*,当且仅当 文法G有以为结果的一棵语法树(推导树)。,59,根据推导序列，对每步推导画相应分支 P： SaASa ASbASSba 符号串：aabbaa的推导过程和语法树如下：,S,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,2.如何画出语法树,aAa,aSbAa,aSbbaa,aabbaa,aAS,S,S,从语法树中看不出句型中的符号被替代的顺序,可见，对符号串aabbaa至少存在两种推导。推导过程不同，语法树的生长过程不同，但最终的语法树完全相同。,60,a,b,a,a,b,a,S,A,S,A,S,S,b,a,b,a,S,A,S,A,a,b,P

32、: SaASa A SbA SS ba,注意：语法树的顺序性,61,语法树是推导的图形表示。 1. 一个句型推导或分析用一棵树结构图示 出来，它反映了一个句子的语法结构。 2. 对于一个句子的多种推导(若文法是无二义性的)，采用各种推导过程，画出的语法树是一样的。语法树并未描述推导过程。 3. 在书中，用画语法树的过程解释语法分析过程，用语法树图解语法结构。,关于语法树的几点说明,62,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,aAa,aSbAa,aSbbaa,aabbaa,aAS,S,63,语法树中除了叶结点以外的任意一个结点连同它的所有的子孙结点构成一棵子树。例如：,

33、3. 子树,简单子树：只含有单层分枝的子树称为简单子树。,64,用子树解释短语，直接短语，句柄: 句型由树的末端符从左至右连成的串是该文法的一个句型。 短语子树的末端符自左至右连成的串，相对于子树而言称之为短语。 直接短语简单子树的末端符自左至右连成的串，相对于子树而言称之为直接短语。 句柄最左的简单子树的末端符自左至右连成的串。,65,例如：对表达式文法GE和句子a1+a2*a3,挑选出推导过程中产生的句型中的短语，直接短语，句柄。 方法：画出该句型或句子的语法树即可求得。,句子a1+a2*a3中： 短语：a1,a2,a3,a2*a3， a1+a2*a3 直接短语：a1,a2,a3 句柄：a

34、1,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,66,如果一文法的某个句子存在两棵语法树，那么该句子是二义性的。如果一文法包含二义性的句子，则这个文法是二义性的；否则，该文法是无二义性的。 若一个文法中存在某个句子，它有两个不同的最左或最右推导（两棵语法树），则这个文法是二义的。 对于一个程序语言来说，常常希望它的文法是无二义的。 考虑表达式下面的文法 GE,其产生式如下： EE+EE*E(E)a 对于句子a+a*a, 有如下两个最左推导：,4.文法的二义性(歧义性)的定义,67,EE+Ea+E a+E*Ea+a*E a+a*a,E E*EE+E*E a+E*Ea+a*E a+a

35、*a,E,E,最左推导,例,1.,2.,68,B bB|Bb|b 构造符号串bb的语法树,B,B,b,B,b,B,69,二义性的几点说明： 1. 一般来说，程序语言存在无二义性文法 例：简单算术表达式的文法 二义性文法 EE+E|E-E|E*E|E/E|(E)|a 非二义性文法 EE+T|E-T|T TT*F|T/F|F F(E)|a,改造方法：使文法含有更多的信息,70,2. 在能驾驭的情况下，使用二义性文法。 3. 文法二义性问题是不可判定的，也就是不存在一种算法，能在有限步内确切地判定一个文法是否为二义性文法。 4. 存在先天二义性语言。例如： aibicji,j1aibjcji,j1

36、存在一个二义性的句子akbkck。,71,补充：语言文法（不是一一对应的） 在某些情况下，人们以某种形式给出有关语言的描述，如何为此语言构造一个文法使得它生成的语言正好满足这个预言的描述呢？,Za|aZ,n 0 Z|aZ 或Z|Za,Za|Za,例1：L=an|n1 VT=a 分析：n=1, L=a n=2, L=aa ; 任意个a。 方法：从上到下找 Z最少一个a： Za 在Z上添加若干a: ZaZ 或 ZZa,72,例2：L=a2nb|n1 VT=a,b 分析：n=1, L=aab n=2, L=aaaab L：偶数个a后跟一个b 方法：从上到下找 两部分： ZAb A:偶数个a，即a2n

37、 A最少两个a: Aaa AaAa,ZAb Aaa|aAa,ZAb Aaa|Aaa,ZAb Aaa|aaA,或 AaaA,或 AAaa,73,例3：L=anbn|n1 VT=a,b 分析：n=1, L=ab n=2, L=aabb n=3, L=aaabbb L：a,b个数相同的符号串 方法：从上到下找 Z最少是ab Zab Z前后分别加一个a,b ZaZb,Zab|aZb,74,L(GZ)=aibj|i,j1 方法1： Z AB A aA|a 或 A Aa|a B bB|b 或 B Bb|b,ZAB AaA|a BbB|b,ZAB AAa|a BBb|b,方法2: ZaZ ZaB； B仅由b

38、组成 Bb|bB 或 Bb|Bb,方法3： ZZb ZAb； A仅由a组成 Aa|aA 或 Aa|Aa,ZaB|aZ Bb|bB,ZaB|aZ Bb|Bb,ZAb|Zb Aa|aA,ZAb|Zb Aa|Aa,75,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。 根据语法分析方法的特点，可以将其分成两大类，一是自顶向下的分析方法，一是自底向上的分析方法，名称来源与建

39、立语法树的方法有关。 自顶向下的分析 自底向上的分析,3.5 句型的分析,76,自顶向下的分析,基本思路: 从文法的识别符号开始，建立一个推导序列，使其推得的终结符号串恰好是所给的符号串。若目标能实现，则所给符号串获得识别，其结构符合文法。反之，则不符合文法。,77,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,例如，对表达式文法GE EE+T|E-T|T TT*F|T/F|F F(E)|a 符号串a1+a2*a3,判断该符号串是否为文法的句子。,可自顶向下建立该符号串的语法树，即该符号串为文法的句子。,78,自底向上分析,基本思路 从待分析的符号串本身入手，尝试将它归约为识别符号

40、，即对符号串一步一步进行归缘直至识别符号，若能成功，则符号串被识别为句子，否则，不是。,79,+,a1,*,a2,a3,例如，对表达式文法GE EE+T|E-T|T TT*F|T/F|F F(E)|a 符号串a1+a2*a3,判断该符号串是否为文法的句子。,可自底向上建立该符号串的语法树，即该符号串为文法的句子。,80,用上下文有关文法描述程序语言不仅相当困难，将使语法定义变得烦杂，难懂，而且一般不能构造有效的分析程序，因此，通常用上下文无关文法描述，而把与上下文有关的限制包含在非形式描述的全局语法与语义中。 把描述词法的正规文法从描述语法的上 下文无关文法中分离出来。在分离出正则文法后的上下文无关文法中，这些单词符号是属于终结符号VT中的符号。,为什么不用上下文有关文法描述程序语言,在程序语言中，与词法有关的产生式属于正规文法；与局部语法有关的产生式属于上下文无关文法；而与全局语法和语义有关的部分往往要用