编译原理—文法和语言.pptx-淘文阁

资源描述

《编译原理—文法和语言.pptx》由会员分享，可在线阅读，更多相关《编译原理—文法和语言.pptx（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、语言概述语言概述语言是由句子组成的集合，或说是由一组符号串所构成的集合。语言是由句子组成的集合，或说是由一组符号串所构成的集合。汉语汉语所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言所有该语言的程序的全体所有该语言的程序的全体每个句子构成的规律每个句子构成的规律研究语言研究语言每个句子的含义每个句子的含义每个句子和使用者的关系每个句子和使用者的关系研究程序设计语言研究程序设计语言每个程序构成的规律每个程序构成的规律每个程序的含义每个程序的含义每个程序和使用者的关系每个程序和使用者的关系

2、语言研究的三个方面语言研究的三个方面语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics第1页/共61页语法语法表示构成语言句子的各个记号之间的组合规律。表示构成语言句子的各个记号之间的组合规律。语义语义表示各个记号的特定含义。（各个记号和记号所表示的对象之间表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）的关系）语用语用表示在各个记号所出现的行为中，它们的来源、使用和影响。表示在各个记号所出现的行为中，它们的来源、使用和影响。每每种种语语言言具具有有两两个个可可开开始始的的特特性性，即即语语言言的的形形式式和和该该形形式式相相关关联联的

3、的意意义。义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。意义。幽默、双关语和谜语就是利用这两方面意义间的差异。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的如果不考虑语义和语用，即只从语法这一侧面来看语言，这

4、种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式形式”是指这是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。分析研究的基础。第2页/共61页任何语言均可看作一个集合。这个集合中的每个元素都是在任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集一定符号集（字母表）上的一个符号串

5、（字母表）上的一个符号串。对于自然语言来说，它们是定义在某个字母表上的对于自然语言来说，它们是定义在某个字母表上的句子的集合句子的集合。对于程序语言来说，它们也是定义在某个字母表上的对于程序语言来说，它们也是定义在某个字母表上的句子句子的集合。的集合。这里这里的句子，就是一个源程序的句子，就是一个源程序。通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。这些语法成分统称为单词或单词符号。单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法单词符号是语言中具有独立意义的最基

6、本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。规则所确定的，即词法规则规定了单词符号的形成规则。当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，就存在着如何给出它的有穷表示的问题。言来讲，就存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则

7、，用这些规则来说明用这些规则来说明(或者定义或者定义)句子的组成结构，比如汉语句子可以是由主语句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。后随谓语而成，构成谓语的是动词和直接宾语。第3页/共61页“我是大学生我是大学生”。是汉语的一个句子。是汉语的一个句子用语法来描述：用语法来描述：句子句子=主语主语谓语谓语主语主语=代词代词名词名词代词代词=我我你你他他名词名词=王明王明大学生大学生工人工人英语英语谓语谓语=动词动词直接宾语直接宾语动词动词=是是学习学习直接宾语直接宾语=代词代词名词名词第4页/共61页有了一组规则以后，按照如下方式用它们导出句子：

8、开始去找有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的左端的带有带有句子句子的规则并把它由的规则并把它由=右端的符号串代替，这个动作表示成：右端的符号串代替，这个动作表示成：句子句子主语主语谓语谓语，然后在得到的串，然后在得到的串主语主语谓语谓语中，选取中，选取主语主语或或谓语谓语，再用相应规则的，再用相应规则的=右端代替之。比如，选取了右端代替之。比如，选取了主语主语，并采用规则，并采用规则主语主语=代词代词，那么得到：那么得到：主语主语谓语谓语代词代词谓语谓语，重复做下去，重复做下去，句子：句子：“我是大学生我是大学生”的全部动作过程是：的全部动作过程是：句子句子主语

9、主语谓语谓语代词代词谓语谓语我我谓语谓语我我动词动词直接宾语直接宾语我是我是直接宾语直接宾语我是我是名词名词我是大学生我是大学生 “我是大学生我是大学生”的构成符合上述规则，而的构成符合上述规则，而“我大学生是我大学生是”不符合上不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。仅仅涉及汉语句子的结构描述。其中一种描述元语言

10、称为文法。第5页/共61页3.1 3.1 形式语言基础基本概念:一、字母表和符号串1.1.字母表：符号的非空有限集合例：=aa，b b，cc2.2.符号：字母表中的元素例：a a，b b，c c3.3.符号串：符号的有穷序列例：a,aa,ac,abca,aa,ac,abc，.特别地,空符号串：无任何符号的符号串()符号串的形式定义有字母表，定义：（1 1）是是上的符号串；（2 2）若x x是上的符号串，且a a ，则axax或xaxa是是上的符号串；（3 3）y y是是上的符号串，iffiff（当且仅当）y y可由（1 1）和（2 2）产生。4.4.符号串集合：符号串集合：由符

11、号串构成的集合。由符号串构成的集合。第6页/共61页二、符号串和符号串集合的运算二、符号串和符号串集合的运算 5.5.符号串相等：符号串相等：若若x x、y y是集合上的两个符号串，则是集合上的两个符号串，则x xy yiffiff（当且仅当）组成（当且仅当）组成x x的每一个符号和组成的每一个符号和组成y y的的每一个每一个符号符号依次相等。依次相等。6.6.符号串的长度：符号串的长度：x x为符号串，其长度为符号串，其长度|x|x|等于组成该符等于组成该符号串的符号个数。号串的符号个数。例：例：x xSTV STV，|x|=3|x|=3 特别地特别地,|=0,|=0第7页/共61页例：例

12、：Aa,b,B=c,d,AB=？8.符号串集合的乘积运算符号串集合的乘积运算：令：令A、B为符号串集合，定义为符号串集合，定义 AB xy|xA，yB ac，ad，bc，bd 因为因为xxx，所以，所以A=A=A 7.7.符号串的联接：符号串的联接：若若x x、y y是定义在是定义在是上的符号串，且是上的符号串，且x xXYXY，y yYXYX，则，则x x和和y y的联接的联接 xyxyXYYXXYYX也是也是上的符号串。上的符号串。注意：一般注意：一般xyyxxyyx，而，而xxxxx x第8页/共61页 9.方幂运算方幂运算：符号串集合的方幂符号串集合的方幂符号串的方幂符号串的方幂有

13、任一符号串集合有任一符号串集合A，定义，定义:有任一符号串有任一符号串X，定义，定义:A0=,X0=A1=A,X1=XA2=AA,X2=XXA3=AAA,X3=XXX AnAn-1A=AAn-1 Xn=XX X A A A n个个 n个个其中其中:n0第9页/共61页10.10.符号串集合的闭包运算：符号串集合的闭包运算：设设A A是符号串集合，定义是符号串集合，定义 A=A1 A2 A3 An 称为集合称为集合A A的的正则闭包正则闭包。A*=A0 A1 A2 A3 An =A0 A 称为集合称为集合A A的的星闭包星闭包。例：例：A=x,y A？A*？x,y,xx,xy,yx,yy,xxx

14、,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3第10页/共61页为什么对符号、符号串、符号串集合以及它们的运算感兴趣为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若若A为某语言的基本字符集为某语言的基本字符集 Aa,b,z,0,1,9,+,_/,(,),=B为单词集为单词集 B=begin,end,if,then,else,for,则则B A*。语言的句子是定义在语言的句子是定义在B上的符号串上的符号串。若令若令C为句子集合，则为句子集合，则C B*,程序程序 C第11页/共61页3.2文法的直观理解

15、文法的直观理解1.1.什么是文法：什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：例：有一句子：“我是大学生我是大学生”。这是一个在语法、这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的它的语法决定的。在本例中它为。在本例中它为“主谓结构主谓结构”。如何定义句子的合法性？有穷语言无穷语言第12页/共61页 2.2.语法规则语法规则：我们通过建立一组规则（产生式），来描述句子我们通过建立一组规则（产生式），来描述句子的的语法结构语法结构。

18、 big elephant ate the peanut.:=:=:=:=:=:=the:=:=big:=:=elephant:=:=:=:=ate:=:=:=:=peanut第16页/共61页 =the =the big =the big elephant =the big elephant =the big elephant ate =the big elephant ate =the big elephant ate the =the big elephant ate the peanut:=:=:=:=:=:=the:=:=big:=:=elephant|peanut:=:=:=:=a

19、te:=:=The big elephant ate the peanut.第17页/共61页上述推导可写成上述推导可写成=the big elephant ate the peanut+说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2)从一组产生式可推出不同的句子，如以上产生式还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们在语法上都正确，但在语义上都不正确。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。第18页/共61页 4.4.语法树：我们用语法树来描述一个句子的语法结构。T

20、hebigelephantatethepeanut语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)第19页/共61页文法的定义3.3 3.3 文法和语言的形式定义文法和语言的形式定义定义1:文法G=（VN，VT，P，Z）VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号）ZVNVVN VT称为文法的字汇表产生式：U:xU VN,x V*其中:产生式：产生式是一个有序对(U,x),通常写为:U:x 或U x；|U|=1|x|0非终结符号：出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为VN。终结符

21、号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为VT。第20页/共61页P=；00；11；99；Z=；例：无符号整数的文法：例：无符号整数的文法：G=（VN，VT，P，Z）VN,VT =0,1,2,3,9第21页/共61页几点说明几点说明：产生式左边符号构成集合VN，且 Z VN有些产生式具有相同的左部，可以合在一起例、例、；|；00|1|2|3|9 文法的BNF表示给定一个文法，实际只需给出产生式集合，并指定开始符号例、例、G ；|；00|1|2|3|9第22页/共61页推导与归约定义2：直接推导：文法G：vx Uy，wxuy,其中x、y V*，U

22、VN,u V*,若U:u P，则v w，即x Uy xuy。若xy，有U:u，则U u 换句话说，换句话说，x和和y是符号串，若使用一次产生式可以从是符号串，若使用一次产生式可以从x变换出变换出y，则称，则称x直接推导出直接推导出y(或者说或者说y是是x的直接推导），记的直接推导），记为为x y。第23页/共61页当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。例如：例如：GN：N ND|D D 0|1|2|3|4|5|6|7|8|9N ND NDD ND9 N09 D09 109 (6)=(1)=(3)(4)=(2)

23、(5)=第24页/共61页 N=109定义定义3：+推导：推导：x和和y是符号串，若使用若干次产生式可以从是符号串，若使用若干次产生式可以从x变换出变换出y，则称，则称x推导出推导出y(或者说或者说y是是x的推导），记为的推导），记为x y。N ND NDD ND9 N09 D09 109 (6)=(1)=(3)(4)=(2)(5)=例：例：则有：则有：定义定义4：*推导：推导：x和和y是符号串，若使用是符号串，若使用0次或若干次产生式可以从次或若干次产生式可以从x变变换出换出y，则称，则称x*推导出推导出y(或者说或者说y是是x的的*推导），记为推导），记为x y。*N=109则有：则有：*

24、N=N或者说或者说：若有直接推导序列：若有直接推导序列：x=U0=U1=U2=Un=y,则则 x=y 。+第25页/共61页直观意义：规范推导最右推导直观意义：规范推导最右推导定义定义5：最右推导：最右推导：若符号串若符号串中有两个以上的非终结符时，对推中有两个以上的非终结符时，对推导的每一步坚持把导的每一步坚持把中的最右中的最右非终结符进行替换，称为最非终结符进行替换，称为最右右推推导。导。最左推导：最左推导：若符号串若符号串中有两个以上的非终结符时，对推中有两个以上的非终结符时，对推导的每一步坚持把导的每一步坚持把中的最左中的最左非终结符进行替换，称为最非终结符进行替换，称为最左左推推导

25、。导。定义定义6：推导的逆过程称之为推导的逆过程称之为归约归约。例：例：x=y,可称为可称为x直接推导出直接推导出y，也可称为，也可称为y直接归约出直接归约出x。x=y,可称为可称为x推导出推导出y，也可称为，也可称为y归约出归约出x。第26页/共61页语言的形式定义文法GZGZ所产生的所有句子的集合定义7：文法GZ （1）句型：x是句型 Z x,且x V*；*（2）句子句子：x是句子是句子 Z x,且且xVT*；*（3）语言语言：L（GZ）=x|Z x，xVT*；即：即：句型是由文法开始符号推导出来的句型是由文法开始符号推导出来的由终结符和非终结符组成的符号串。由终结符和非终结符组成的符号

26、串。即：即：句子是由文法开始符号推导出来的句子是由文法开始符号推导出来的由终结符组成的符号串。由终结符组成的符号串。第27页/共61页例：例：abna|n1,构造其文法构造其文法 G1Z：ZaBa,Bb|bB G2Z：ZaBa,Bb|Bb 定义8:G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。第28页/共61页编译感兴趣的问题是编译感兴趣的问题是:给定x,G,求x L(G)?x算法算法1算法算法2x L(G)?Gyn出错处理出错处理停机停机第29页/共61页递归文法1.递归产生式：产生式右部有与左部相同的符号对于 U:=xUy 若x=,即U:=Uy，左递归；若y=,即U

27、:=xU，右递归；2.递归文法：文法G，存在U VN if U=U,则G为递归文法；if U=U,则G为左递归文法；if U=U,则G为右递归文法；+第30页/共61页4.递归文法的优点：可用有穷条产生式，定义无穷语言例：对于前面给出的无符号整数的文法是有递归文法，用例：对于前面给出的无符号整数的文法是有递归文法，用13条产生式就可以定义出所有的无符号整数。若不用递归文法，条产生式就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条产生式呢？那将要用多少条产生式呢？!3.左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）第31页/共61页3.4 文法分

28、类文法分类形式语言：用文法和自动机所描述的没有语义的语言。文法定义：乔姆斯基将所有文法都定义为一个四元组：G=（VN，VT，P，Z）VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 Z：开始符号（开始符号）ZVN 语言定义：L（GZ）=x|Z=x,x VT*,*第32页/共61页文法和语言分类：0型、1型、2型、3型这几类文法的差别在于对产生式施加不同的限制。定义9：0型文法：P：u:=v 其中u V*，v V*0型语言：L0 这种语言可以用图灵机(Turing)接受.0型文法称为短语结构文法。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。第33页/共61页定

29、义10：1型文法：P：xUy:=xuy 其中 U VN，x、y、u V*1型语言：L1 这种语言可以由一种线性界限自动机接受.称为上下文敏感或上下文有关。也即只有在x、y这样的上下文中才能把U改写为u定义10：1型文法：P：u:=v u v u,v V*第34页/共61页定义11：2型文法：P：U:=u 其中 U VN，u V*2型语言：L2 这种语言可以由下推自动机接受.称为上下文无关文法。也即把U改写为u时，不必考虑上下文。注意：2型文法与BNF表示相等价。第35页/共61页（右线性）P：U:=t 或 U:=tW 其中 U、W VN t VT 3型语言：L3 又称正则语言、正则集合这种语

30、言可以由有穷自动机接受.3型文法又被称为正则文法。它是对2型文法进行进一步限制。（左线性）P：U:=t 或 U:=Wt 其中 U、W VN t VT定义12：3型文法：第36页/共61页根据上述讨论，根据上述讨论，L0 L1 L2 L30型文法可以产生型文法可以产生L0、L1、L2、L3，但，但2型文法只能产型文法只能产生生L2，不能产生，不能产生L1。第37页/共61页3.5 语法树与二义性文法语法树与二义性文法推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。结点：符号根结点：开始符号中间结点：非终结符叶结点：终结符或非终结符有向边：表示结点间的派

31、生关系。Z ZU UV Va abcd第38页/共61页注意一个重要事实：文法所能产生的句子，可以用不同的推导原则（使用产生式顺序不同）将其推导出来。语法树的生成规律不同，但最终生成的语法树形状完全相同。某些文法有此性质，而某些文法不具此性质。(2)句型的推导及语法树的生成（自顶向下）给定给定GZ，句型，句型w：可建立可建立推导序列推导序列，Zw 可建立可建立语法树语法树，以，以Z为树根结点，每步推导生成语法树为树根结点，每步推导生成语法树的一层分支，最终可生成句型的语法树。的一层分支，最终可生成句型的语法树。*第39页/共61页 1(1)(2)(3)(5)(4)0一般推导：一般推导

32、：第40页/共61页(3)子树与简单子树子树：子树：语法树中的某个结点（子语法树中的某个结点（子树的根）连同它向下派生的部分树的根）连同它向下派生的部分所组成。所组成。简单子树：简单子树：只有单层分枝的子树只有单层分枝的子树称为简单子树。称为简单子树。1(1)(2)(3)(5)(4)0第41页/共61页(4)树与推导句型推导过程句型语法树的生长过程由推导构造语法树1从从开始符号开始符号开始，开始，自左向右自左向右建立建立推导推导序列。序列。由由根结点根结点开始，开始，自上而下自上而下建立建立语法树语法树。第42页/共61页例：给定文法例：给定文法G和句型和句型10,考察考察语法语法树与推

33、导树与推导过程。过程。规范推导R R 0R0 0R110R第43页/共61页由语法树构造归约2自下而上自下而上地修剪子树的末端结点，直至把整棵树剪掉地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。（留根），每剪一次对应一次归约。从句型开始，从句型开始，自右向左自右向左地逐步进行地逐步进行归约归约，建立，建立归约归约序列。序列。第44页/共61页规范归约与规范推导互为逆过程01R R 0R 0R10R第45页/共61页定义14：通过规范推导或规范归约所得到的句型称为规范句型。不是规范推导在上例中，在上例中，就不是规范句型，因为：就不是规范句型，因为：RR第46页/共61

34、页文法的二义性定义14.1：若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。换而言之，无二义性文法的句子换而言之，无二义性文法的句子只有一棵语法树只有一棵语法树，尽管推，尽管推导过程可以不同。导过程可以不同。下面举一个二义性文法的例子：下面举一个二义性文法的例子：GE:E:=E+E|E*E|(E)|i VN=E VT=+,*,(,),i 第47页/共61页对于句子对于句子Sii *i L（GE），存在不同的规范推导：），存在不同的规范推导：EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1)E E+E E+E*E E+E

35、*i E+i*i ii *iRRRRR(2)E E*E E*i E+E*i E+i*i ii*iRRRRRGE:E:=E+E|E*E|(E)|i 第48页/共61页定义14.2：若一个文法的某句子存在两个不同的规范推导，则该文法是二义性的，否则是无二义性的。以上是以上是自顶向下自顶向下来看文法的二义性，我们还可以来看文法的二义性，我们还可以自底向上自底向上来看文法的二来看文法的二义性。义性。上例中，规范句型上例中，规范句型E+E*i 是由是由ii*i通过两步规范规约得到的，但对于通过两步规范规约得到的，但对于同一个句型同一个句型E+E*i，它有两个不同的，它有两个不同的句柄句柄（对应上述两棵

36、不同的语法树）：（对应上述两棵不同的语法树）：i 和和 EE。因此语法的二义性意味着句型的句柄不唯一。因此语法的二义性意味着句型的句柄不唯一。EEE+EE*iEEE*EE+i句柄：i句柄：EE第49页/共61页若文法是二义性的，则在编译时就会产生不确定性，遗若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：憾的是在理论上已经证明：文法的二义性是不可判定的文法的二义性是不可判定的，即，即不可能构造出一个算法，通过有限步骤来判定任一文法是否不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。有二义性。现在的解决办法是：提出一些现在的解决办法是：提出一些限制条件限制

37、条件，称为无二义性，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。二义性的。由于无二义性文法比较简单，我们也可以采用另一种解由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种决办法：即不改变二义性文法，而是确定一种编译算法编译算法，使，使该算法满足无二义性充分条件。该算法满足无二义性充分条件。定义14.3 若一个文法的某规范句型的句柄不唯一，则该文法是二义性的，否则是无二义性的。第50页/共61页例:算术表达式的文法：E:=E+E|E*E|(E)|iE:=E+T|TT:=T*F

38、|FF:=(E)|i例例:Pascal 语言条件语句的文法语言条件语句的文法:=If then|If then else :=|.第51页/共61页3.6 句型的分析句型的分析任务：给定GZ:S VT*,判定是否有 S L(GE)?这是词法分析和语法分析所要做的工作，将在第三、四章中详细介绍。第52页/共61页句型的短语、简单短语和句柄*定义15:给定文法GZ,w=xuy V+，为该文法的句型,若 ZxUy,且U u,则u是句型w相对于U的短语；其中U VN，u V+，x,y V*直观理解：短语是前面句型中的某个非终结符所能推出直观理解：短语是前面句型中的某个非终结符所能推出的符号串。的符号

39、串。或短语定义或短语定义:设设GZ是给定文法是给定文法,w=xuyV+，为该文法的句型，为该文法的句型,如果如果满足下面两个条件满足下面两个条件:Z xUy；U u；则称句型则称句型xuy 中的子串中的子串u是句型是句型xuy的短语。的短语。*第53页/共61页定义17.任一句型的最左简单短语称为该句型的句柄。给定句型找句柄的步骤：给定句型找句柄的步骤：短语短语简单短语简单短语句柄句柄注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。定义16:给定文法GZ,w=xuy V+，为该文法的句型,若 Z xUy,且U u,则u是句型w相对于U的简单短语。其中

40、U VN，u V+，x,y V*第54页/共61页例：例：给定文法给定文法G：ET|E+T|ET TF|T*F|TF Fi|(E)符号串（符号串（T+i）*iF F是文法是文法G G的一个句型，求其短语、简单短语和句柄。的一个句型，求其短语、简单短语和句柄。E ET T TT T T*FT T F*FT T (E)*FT T (T+T)*FT T (T+F)*FT T (T+i)*FT T (T+i)*iT T (T+i)*iT T解：短语有解：短语有8个：个：1.E E，E（T+i）*iF 则有：则有：（T+i）*iF2.E TF，T（T+i）*i 则有：则有：（T+i）*i3.E T*iF

41、，T（T+i）则有：则有：（T+i）4.E(E)*iF，ET+i 则有：则有：T+i5.E(E+i)*iF，ET 则有：则有：T6.E(T+F)*iF，Fi 则有：则有：第一个第一个i7.E(T+i)*FF，Fi 则有：则有：第二个第二个i8.E(T+i)*FT，TF 则有：则有：F*+*+*+*+*+*+*+*+定义:给定文法GZ,w=xuy V+，为该文法的句型,若 ZxUy,且U u,则u是句型w相对于U的短语；若 Z xUy,且U u,则u是句型w相对于U的简单短语。其中U VN，u V+，x,y V*U第55页/共61页其简单短语有其简单短语有4个：个：1.E(E+i)*iF,EF,

42、ET 则有：则有：T2.E(T+F)*iF,FF,Fi 则有：则有：第一个第一个i i3.E(T+i)*FF,FF,Fi 则有：则有：第二个第二个i i4.E(T+i)*FT T,T,TF 则有：则有：F F句柄有句柄有1 1个：个：T TEETT TT*FF F(E E)F Fi iE+TT TF Fi i用语法树求用语法树求短语、简单短语和句柄短语、简单短语和句柄的方法：的方法：1）每个句型都有一棵语法树；）每个句型都有一棵语法树；2）每棵语法树的叶（从左到右）组成一句型；）每棵语法树的叶（从左到右）组成一句型；3）每个子树）每个子树的叶（从左到右）组成一短语；的叶（从左到右）组成一短语

43、；4）每个简单子树）每个简单子树的叶（从左到右）组成一简单短语；的叶（从左到右）组成一简单短语；5）最左简单子树）最左简单子树的叶（从左到右）组成一句柄。的叶（从左到右）组成一句柄。只需画出句型的语法树，然后根据子树找短语只需画出句型的语法树，然后根据子树找短语简单短语简单短语句柄。句柄。第56页/共61页3.7 有关文法的实用限制有关文法的实用限制若文法中有如U:=U的产生式，则这就是有害产生式，它会引起二义性。例如存在例如存在U:=U，U:=a|b,则有两棵语法树：则有两棵语法树：UaUUa第57页/共61页多余产生式：（1）在推导文法的所有句子中，始终用不到的产生式。即该产生式的

44、左部非终结符不出现在任何句型中。（2）在推导句子的过程中，一旦使用了该产生式，将推不出任何终结符号串。即该产生式中含有推不出任何终结符号串的非终结符。例如给定例如给定GZ，若其中关于，若其中关于U的产生式的产生式只只有如下一条：有如下一条：U:=xUy 该产生式是多余产生式。该产生式是多余产生式。若还有U:=a，则此产生式并非多余若某文法中无有害产生式或多余产生式，则称该文法是压缩过的。第58页/共61页小小结结掌握符号串和符号串集合的运算、文法、句型、句子和语言的定义掌握符号串和符号串集合的运算、文法、句型、句子和语言的定义几个重要概念：推导、归约、递归、短语、简单短语和句柄、语法树、文法的几个重要概念：推导、归约、递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等。二义性、文法的实用限制等。掌握文法的表示：掌握文法的表示：BNFBNF、扩充的、扩充的BNFBNF范式、语法图。范式、语法图。了解文法分类。了解文法分类。第59页/共61页本章作业 48页：3题，4题，5题，7题，11题第60页/共61页感谢您的观看。第61页/共61页

展开阅读全文