编译原理及其习题解答(武汉大学出版社)课件chap2.ppt

资源描述

《编译原理及其习题解答(武汉大学出版社)课件chap2.ppt》由会员分享，可在线阅读，更多相关《编译原理及其习题解答(武汉大学出版社)课件chap2.ppt（84页珍藏版）》请在三一办公上搜索。

1、1,第二章文法和语言,要点(本章是基础)1、概念:文法,推导,直接推导,最左(右)推导,产生式,句型,短语,直接短语,句柄,语法树,规范推导,二义文法等2、4种文法的定义、文法的构造和文法的推导3、语法树的构造和最左（右）推导；4、二义文法、二义性的证明；5、句型分析；,2,词法规则：自动机语法规则：上下文无关文法,3,引言,语言包括语法和语义两方面。语法是一组规则，用以判断什么样的符号序列是合法的；语义指含义，如变量的类型、作用域是否符合正确的语法。常把程序设计语言的语义分为二类：静态语义和动态语义。静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；动态语义（或称运行语义、执行

2、语义），表明程序要做些什么，要计算什么。阐明语法的一个工具是文法，常采用上下文无关文法作为程序设计语言语法的描述工具。,4,补充：文法的直观概念(1/5),描述一种语言，无非是说明这种语言的句子。如果该语言所含的句子是有限的，那么只要一一列举出即可；若是无限的，则存在如何给出有穷表示的问题。但无论如何，某语言的句子总是存在着一种组成结构，即所谓的规则（或称文法）。文法：描述语言的语法结构的形式规则（即语法规则）。,5,直观文法举例(2/5),例如：简单的汉语句子的构成规则:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|则“我是大学生”是句子,6,“我是大学生”的推导过

3、程：我我我是我是我是大学生依次可以推导出句子“王明是大学生”、“我学习英语”等等,推导过程(3/5),7,程序设计语言对文法的要求(4/5),这些规则必须是准确的，易于理解的，且应当有相当强的描述能力，足以描述各种不同的结构。,8,文法作用(5/5),（1）定义句子的结构；（2）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划无穷集合。,9,2 符号串及其运算（1）符号串：由字母表中的符号组成的任何有穷序列。说明:字母间的顺序不同顺序组成的符号串是不同的；（2）符号串长度符号串内所含符号的个数，若x=string,则|x|=6;其中不含任何符号的符号串称为空符号串，长度|

4、0,2.1 语言成分,1 字母表（符号表）与符号元素（或称符号）的非空有穷集合，用符号表示。不同语言有不同的字母表。如汉语包括汉字、数字、标点符号等；C语言包括字母、数字和保留字等等。,10,符号串的运算(1/3),符号串的头尾，固有头和固有尾：设 z=xy 是一个符号串，则x是z的头，y是z的尾。如果x是非空的，那么y是是固有尾；如果y是非空的，那么x是固有头。,例：z=abc，则 z的头：、a、ab、abc；固有头：、a、ab；z的尾：、c、bc、abc；固有尾：、c、bc；,当我们对符号z=xy 的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法：z=x。如果只是为了强调x在符号串

5、中的某处出现，则可表示为：z=x；符号t是符号串z的第一个符号，则表示为：z=t。,11,(3)符号串的连接,设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如：x=abc，y=DEF，则xy=abcDEF；,若|x|=n，|y|m，则|xy|=n+m,对任意的符号串x，有 x=x=x,12,（4）符号串集合的乘积,设A、B是两个符号串的集合，则AB表示A与B的乘积，定义为：AB=xy|xA,yB如：若A=ab,c,B=d,efg,则AB=abd,abefg,cd,cefg特别地，有：A=A=A 空集表示不含任何元素的空集。有：A=A=请区别：，三种表示方法的含义

6、,13,（5）符号串的方幂,同一符号串的连接可以写成方幂的形式。设x是符号串，把x自身连接n次得到的符号串z，即z=xxxx，称为符号串x的方幂，记作z=xn，有：x0=x1=x x2=xx x3=xxx 当n0时，xn x xn-1=xn-1 x,14,（6）符号串集合的方幂,同一符号串集合的连接也可以写成方幂的形式。设符号串集合为A，则有：A0=A1=AA2=AAA3=AAA 当n0时，An A An-1=An-1 A例如：A=ab，c，则AA=AAA=,15,（7）符号串集合的正闭包,设符号串集合为A，则A的正闭包记为A+，定义为：A+=A1 A2 An 表示A上所有有穷长串的集合例如：

7、A=ab，c，AA=，AAA=,（8）符号串集合的自反闭包,设符号串集合为A，则A的自反闭包记为A*，定义为：A*=A0 A1 A2 An 即A*=A0 A+=A+例如：A=a,b，则 A*=,a,b,aa,ab,ba,bb,aaa,A+=A*A=AA*,16,2.2 产生式文法和语言,2.2.1 文法的形式定义是一个四元组 G=（VN，VT，P，S）VN 非终结符号集，非终结符号代表的是语法范畴，也就是它是一类（或集合）的记号，而不是一个个体记号。如“表达式”、“语句”、“分程序”等等，都是表达一定的语法概念。因此，每个非终结符表示一定符号串的集合（由终结符和非终结符组成）；(如简单汉语句

8、子中。）,VT 终结符号集合，终结符是构成语言的基本符号，也就是说，它是一个语言的不可再分的基本符号；,P 产生式（或称规则,重写规则,生成式）集合。所谓产生式是定义语法范畴的一种书写规则。一个产生式的形式是（或:=)，其中“”读为“是”或“定义为”；产生式的左部(VNVT)*且至少含有一个非终结符号，右部(VNVT)*,即由终结符或（与）非终结符组成的一符号串，允许是空字,17,2.2 产生式文法和语言,例如：简单的汉语句子的构成规则:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|则“我是大学生”是句子,18,文法的形式定义,S 开始符号，即文法的第一个非终结符。开

9、始符号代表了所定义的语言中我们最感兴趣的语法范畴，如在程序语言中，我们感兴趣的是“程序”,注意：1、VN VT 即不含公共元素；2、产生式是有限的；3、开始符号S至少必须在某个产生式的左部出现一次；4、为书写方便，若干个左部相同的产生式如：P1,P2，Pn 合并成：P1|2|n其中i称为P的一个候选式。,19,文法定义举例1,例2.1 表示算术表达式的文法描述：G1=（VN，VT，P，S）其中VNE VT=i,+,*,(,)P=E i,E E+E,E E*E,E(E)S=E或者直接写为：G1=(E,i,+,*,(,),E i,E E+E,E E*E,E(E),E),20,文法定义举例2,例2

10、文法G=（VN，VT，P，S）其中VN标识符，字母，数字，VT a,b,c,x,y,z,0,1,8,9 P=|,a|b|c|x|y|z,0|1|2|8|9 S=,21,用文法定义语言的中心思想是：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。例如文法G：E E+E|E*E|(E)|i，其中唯一非终结符E可以看成是代表一类算术表达式。从E出发，进行一系列的推导，推出种种不同的算术表达式。如根据上述规则可推出(i+i)：E=(E)=(E+E)=(i+E)=(i+i)我们称这样的一串替换是从E推出(i+i)的一个推导，这个推导提供了一个证明，证明(i+i)是文法G所定义的一个算

11、术表达式。,2.2.2 文法的推导,22,有关推导的定义,定义2.3 直接推导=若A直接推导出，即 A=，当且仅当A-是一个产生式，且、(VNVT)*符号=指推导一步，即推导每前进一步总是引用一条规则（产生式）,定义2.4 长度为n（n1）的推导若存在直接推导序列a1=a2=an，则称a1可推导出an。a1 an 表示：从a1出发经过一步或若干步，可推导出an。,定义2.5 长度为n（n0）的推导 a1 an 表示：从a1出发经过0步（a1 an）或若干步，可推导出an。,23,2.2.3 句型、句子、语言,例1：证明终结符号串(i*i+i)是文法G：E E+E|E*E|(E)|i的一个句子

12、证明：E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)是从开始符号E到(i*i+i)的一个推导。其中E、(E)、(E+E)、(E*E+E)、(i*E+E)、(i*i+E)、(i*i+i)都是这个文法的一个句型,1.句型：设GS是一个文法，S是它的开始符号，若S,则称是文法GS的句型。2.句子：仅含终结符的句型是一个句子，即S，VT*,则是句子。3.语言：文法G所产生的句子的全体是一个语言，记作L(G)L(G)=|S,且VT*,24,语言的例子,例2：文法G2 A：A bA|cc，证明cc、bcc、bbcc属于L(G2)。证明：A=cc，A=Ba=bcc，A

13、=bA=bbA=bbcc cc、bcc、bbcc、是属于L(G2)的,例3：文法GS：(1)S0S1；(2)S01。GS的语言是什么？解：对第一个产生式使用n-1次，然后使用第二个产生式一次，得到：S=0S1=00S11=0n-1S1n-1=0n1n因此L(G)=0n1n|n 1,例4：下列文法的语言是什么？GS=（S,S-,S）GA=（A，A）,25,2.2.4 文法的等价,若L(G1)=L(G2)，则称文法G1和G2是等价的例1：G1=(VN,VT,P,S)，VN=S，VT=0,1，P由下列产生式组成：(1)S0S1；(2)S01；G2=(VN,VT,P,A)，VN=A,R，VT=0,1，

14、P由下列产生式组成：(1)A 0R;(2)A 01;(3)R A1,26,什么是递归文法？,1.递归规则：规则右部有与左部相同的符号对于 U-xUy 若x=,即U-Uy，左递归；若y=,即U-xU，右递归；,2.递归文法：文法G，存在U VN 若 U=U,则G为递归文法；若 U=U,则G为左递归文法；若 U=U,则G为右递归文法；,27,4.递归文法的优点：可用有穷条规则，定义无穷语言,例：对于前面给出的标识符的文法是有递归文法，用y有限条规则就可以定义出所有的标识符。若不用递归文法，那将要用多少条规则呢？,!,3.左递归文法的缺点：不能用自顶向下的方法来进行语分析,会造成死循环,28,2.

15、3 文法的分类,2.3.1 文法分类乔姆斯基（Chomsky)建立的形式语言对计算机科学的发展具有深刻的意义。他把文法分成四种类型：0型、1型、2型和3型。0型强于1型，1型强于2型，2型强于3型，它们的差别在于对产生式施加不同的限制。,29,定义 0型文法（或称短语文法,phrase structure grammar,PSG）,G=(VN,VT,P,S)是0型文法是指：若它的每个产生式是这样一种结构:(VNVT)+且至少含有一个非终结符，(VNVT)*。任何0型文法都是递归可枚举的。0型文法的能力相当于图灵机（计算机的一种简单的理论模型）。称L为递归可枚举的：若存在一个产生L的过程。称L

16、为递归的：若存在一个识别L的算法。,30,定义 1型文法（或称上下文有关文法,CSG Context Sensitive Grammar）,如果对0型文法加以以下的限制，则可得到1型文法。设G=(VN,VT,P,S)为一文法，若G的任何产生式均满足|(指符号串的长度)，仅仅S 例外。课本P24例2.2。,例：设G=(VN,VT,P,S)，VN=S,B,E，VT=a,b,e，P由下列产生式组成：(1)S aSBE；(2)S aBE;(3)EB BE;(4)aB ab;(5)bB bb;(6)bE be;(7)eE ee;求 GS的语言是什么。,31,接上页例子,分析：条产生式中只有第条具有递归

17、性，其它的产生式最终都向终结符靠拢。注意：S aSBE 与S0S1的相似性，都可用同一模板来表示S S 使用产生式(1)n-1次，得推导序列：S an-1S(BE)n-1；使用产生式(2)一次，得到：S an(BE)n；使用产生式(3)的右部替换EB，使最终得到的串中，所有的B都先于所有的E，即S anBnEn；,32,接上例,使用产生式(4)一次，得到S an bBn1En；使用产生式(5)n-1次，得到S an bnEn；使用产生式(6)一次，得到S an bn eEn-1；使用产生式(7)n-1次，得到S an bn en；因此，L(G)=an bn en|n 1,说明：上述分析中，步骤

18、是关键一步，否则不能推导出终结符号串。例如假设n=3，S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE,33,上下文有关，顾名思义就是对非终结符进行替换时必须考虑上下文。例如，1型文法G的产生式也可写成A，其中、都在(VNVT)*中，且，A VN，则说明了非终结符A必须在、这样一个上下文环境中才可以替换。上下文有关文法能生成anbncn类特征的语言。但它不能描述L=c|(a|b)*类语言。,对上下文有关文法的说明,34,定义 2型文法（或称上下文无关文法，CFG Context Free Grammar）,设G=(VN,

19、VT,P,S)为一文法，若G的任何产生式形似A，其中A VN，(VNVT)+。,例：G=(S,A,B,a,b,P,S)，其中P由下列产生式组成SaB|bA Aa|aS|bAABb|bS|aBB例：G=(VN,VT,P,S)，VN=S，VT=0,1，P由下列产生式组成：(1)S0S1；(2)S01；,35,上下文无关文法的说明,上下文无关，顾名思义就是非终结符的替换可以不必考虑上下文。由于这种文法对程序已基本可以描述，因此，上下文无关文法常简称为文法。上下文无关文法最多能生成anbn类特征的语言，不能生成anbncn类特征的语言。,36,设G=(VN,VT,P,S)为一文法，若G的任何产生式A

20、或A B，其中A、B VN，VT*。对任何正规文法G，都可以设计一个不确定的有穷自动机NFA，它能够而且只能够识别G的语言。,定义 3型文法（或称正规文法，RG Regular Grammar）,例：文法G=(S,A,B,0,1,P,S)，其中P由下列产生式组成S 0A|1B|0A 0A|1B|0SB 1B|1|0,37,左线性文法,设G=(VN,VT,P,S)为一文法，若G的任何产生式A或A B，其中A、B VN，VT*。,左线性文法=右线性文法（非严格的转换）设左线性文法为G=(VN,VT,P,S)，右线性文法为G=(VN,VT,P,S)，其中 VN=VN+S,P转化方式为：,38,2.3

21、.2 文法分类的意义,自动机具有有穷描述的某种机器，对于给定文法，可接收某个终结符号串，并确定是否能从该文法推导出来。分析器判定（分析）一个终结符号串是否是某个文法的句子，给出给定串的推导序列，完成此工作的自动机，称为分析器。正规文法与自动机自动机由一个有穷状态集和一个状态对偶之间的转换集组成。CFG与自动机 CFG可以由下推自动机来识别。,39,文法分类的意义,文法的分类，对于实现程序设计语言的编译程序，具有重要意义。语言的词法规则：用正规文法（RG）描述。语言的语法规则：局部语法用CFG描述；全局语法用CSG描述。语言的语义描述：CSG（实际定义采用CFG）。编译程序在实现时，一般采

22、用CFG识别技术（易实现，高效）。,40,2.3.3 文法举例,例2.6 1型文法G6=(VN,VT,P,S)，其中 VN S，X，Y，Z VT=x,y,z P=S-xSYZ|xYZ,xY-xy,yY-yy,yZ-yz,ZY-YZ,zZ-zzL(G6)为？,例2.7 2型文法G7=(VN,VT,P,S)，其中 VN S，T VT=a,b,c,d P=S-aTd,T-bT|cT|b|c,L(G6)=xnynzn|n0,L(G7)=ad|b,c+,41,2.3.3 文法举例(2),例2.8 2型文法G8=(VN,VT,P,B)，其中 VN B VT=(,)P=B-(B)|BB|(),例2.9 2型

25、A或A A划分模块：bn2、L2=an bn+mcm|m,n 1；对应模板：A A 划分模块：；对应an bn，对应 bmcm,47,文法的构造举例（2/3）,3、L3=anbnci|n 1，i 0；对应模板：A A或A A A A 划分模块：；对应an bn，对应 ci4、L4=aibncn|n 1，i 0；同,48,文法的构造举例（3/3）,5、L5=anbncn|n 1 对应模板：A A 划分模块：；对应an bn，对应 cn或对应an，对应 bn cn,49,2.4 文法及其语法树,文法和语言,一、语法树（推导树）直观定义：用图表示上下文无关文法句型的推导的直观方法。语法树有助于理解

26、一个句子的语法层结构的层次，语法树通常表示成一棵倒立的树，根在上，枝叶在下。,2.形式定义对文法G=(VN,VT,P,S)相关联的语法树49满足以下4个条件：（1）根结点由开始符号S所标记；（2）每个结点都有一个标记，此标记是V(即VN VT)的一个符号；（3）若某结点至少有一个子孙结点，则该结点所标记的符号是个非终结符；（4）从左到右，若结点A1,A2,Ak是结点A的孩子结点，则存在产生式A A1 A2 Ak。,50,从根结点S开始推导，当非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生出下一代新结点，候选式中自左向右的每个符号对应一个新结点，并用这些符号标记其相应的新结点。每

27、个新结点与其父结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左向右排列起来就是一个句型。,语法树构造的过程,例1 文法G=(E,+,*,i,(,),P,E)，其中P为：E E+E|E*E|(E)|i对该文法关于(i*i+i)的推导的语法树如下所示：,51,接语法树构造举例,E(根),（,E,）,E,+,+,E,E,*,E,i,i,i,什么是树的边沿？,52,文法和语言,语法树的问题分析,（1）允许产生同名结点（反映递归性）；（2）没有后代的结点为端末结；（3）语法树不能反映产生后代的先后顺序；（例子在下一页）（4）一棵语法树表示了一个句型种种可能的（但未必是所

28、有的）不同推导过程。,53,语法树例子,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,54,2.5 文法和语言的一些特性,文法和语言,2.5.1 无用非终结符号,如果文法的某个非终结符不出现在文法的任何一个句型中，并且不能从它推导出终结符号串，则称该非终结符为无用非终结符。,例2.13 设文法G13 A：A-aaBbb B-aBb|abC-cD|c D-Ef哪些符号是无用非终

29、结符号？,无用非终结符号：D E,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。,55,文法和语言,2.5.2 不可达文法符号,如果一个非终结符不出现在文法的任何一条产生式的右部，则称该非终结符为不可达文法符号。,例2.13 设文法G13 A：A-aaBbbB-aBb|abC-cD|cD-Ef哪些符号是不可达文法符号？,不可达文法符号：C,56,文法和语言,多余符号和多余规则,无用非终结符和不可达文法符号都是多余符号。包含有多余符号的规则（产生式），是多余规则。形如 U-U 的产生式，也是多余规则。,例1

30、设文法G13 A：A-aaBbb|a B-aBb|aCbC-cD|CD-Ef应删除哪些多余规则？,57,文法和语言,多余符号和多余规则,应删除哪些多余规则？,例2：GS 1)SBe2)BCe3)BAf 4)AAe5)Ae 6)CCf7)Df,SBeBAfAAe Ae,58,文法和语言,2.5.3 可空非终结符,若存在产生式 A-，则该产生式称为空产生式，A称为可空非终结符。空产生式有时候带来方便，所以，可以往一个文法里增加空产生式。,59,2.5.4 最左推导/最右推导/规范推导,最左推导：任何一步=都是对中的最左非终结符进行替换。最右推导（又称规范推导）：任何一步=都是对中的最右非终结符进

31、行替换。由规范推导所得到的句型称为规范句型。,从一个句型到另一个句型的推导过程往往是不唯一的。例如 E+E(i+i)：（a）E+E=E+i=i+i 最右推导（b）E+E=i+E=i+i 最左推导,60,语法树的特点,文法和语言,一棵语法树是这些不同推导过程的共性抽象，是它们的代表。一棵语法树完全等价于一个最左（右）推导，这种等价性包括树的步步生长和推导的步步展开是完全一致的。例：推导(i*i+i)最左推导：E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)最右推导：E=(E)=(E+E)=(E+i)=(E*E+i)=(E*i+i)=(i*i+i)但两种推导的

32、语法树相同。,61,文法和语言,一个句型是否只对应唯一的一棵语法树？,例：GE:E iE E+EE E*EE(E),句型 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+i,62,文法和语言,定义2.13：一个文法，如果它的一个句子对应有两棵或两棵以上不同的语法树，则这个文法是二义的。或一个文法的某个句子有两个不同的最左（右）推导，则这个文法是二义的。,2.5.5 二义性,区别文法的二义性：存在两个不同文法G(二义)、G(无二义)，却有L(G)=L(G)，即产生语言相同。语言的二

33、义性：若不存在无二义性的文法，则该语言是二义性的。,63,二义性其它问题,文法和语言,人们已证明，二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。我们所能做的就是为无二义性寻找一些充分条件。例如对文法GE：E E+E|E*E|(E)|i 修改，规定运算符“+”与“*”的优先关系和结合规则，设“*”的优先性高于“+”，且服从左结合。G：E T|E+T T F|T*F F(E)|i,64,文法和语言,2.6 分析方法简介,句型分析的任务就是按文法的产生式，识别输入的符号是否是该文法的句型。语法树是句型推导过程的几何表示，可以十分直观的显示某句型的结构。因

34、此在句型时，对输入符号串构造语法树，以此识别它是否是该文法的一个句型（或句子）。因此，语法树又可称为语法分析树或分析树。我们把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。分析算法又分为：,从左到右分析算法；从右到左分析算法；,自上而下的分析法自下而上的分析法,65,文法和语言,自上而下的分析法,基本思想：从文法的开始符号出发，反复使用各种产生式，寻找“匹配”输入符号串的推导。即对任何输入符号串，从文法的开始符号（根结）出发，自上而下地为输入串建立一棵语法树，直到语法树结果正好是输入的符号串为止。,例如：文法GS:S xAy A aa|a，识别输入串xay是否是该文法的一个句

35、子。,66,文法和语言,自上而下分析法的缺陷,关键：回溯问题（其分析过程是一种试探过程）回溯问题是从各种可能的候选式中任选一个，进行推导后发现该候选式是错误的，则退回去重新选择候选式的方式。例如上例中的(3)。,S,S,S,x,A,y,(3)选用第1个候选式,a,回溯的产生使算法代价极低，效率很低。关于解决回溯问题将在第5章中介绍。,a,67,自下而上的分析法,文法和语言,基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。即从语法树的末端开始，步步向上“归约”，直到根结。归约：若V=，W=，是文法的产生式，如有V=W，则W直接归约到V。,68,自下而上的语法分析举例,例1：文

36、法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SAA c a b d c a b d c a b d 规约过程：S cAd cabd,69,文法和语言,例2：文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d 识别abbcde是否为文法S的一个句子。,解题思想：扫描abbcde，从中找出一个子串，该子串与某一产生式的右部相匹配。,70,自下而上分析法举例,文法和语言,例2解：,71,自下而上分析法存在的问题,文法和语言,可归约串的问题；（该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号）自下而上分析法的关键就是找哪

37、个子串是“可归约串”，哪个不是“可归约串”。例如上例中的(3),因此必须精确定义“可归约串”，事实上存在着种种不同的方法刻画“可归约串”，对这个概念的不同定义，形成了不同的自下而上的分析法。在“规范归约”的分析中，用“句柄”来刻画“可归约串”。,72,短语、直接短语、句柄,文法和语言,1、短语：令文法G，开始符号为S，是G的句型（即S），如果S A且A，则称是句型相对于非终结符A的短语。2、直接短语如短语中有A=，则称是句型相对于规则A 的直接短语。3、句柄一个句型的最左直接短语称为该句型的句柄。,73,解题方法,文法和语言,例：文法GE:E T|E+T T F|T*F F(E)|i 证明

38、i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。,证明：E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i,74,接上例,文法和语言,语法树：,E,E,+,T,T,T,*,F,F,F,i3,i1,i2,第1层 i1+i2*i3 相对于E第2层 i1 相对于E;i2*i3 相对于T第3层 i1,i2 相对于T;i3 相对于F第4层 i1,i2 相对于F(F i直接短语)第5层,i+i*i是G的一个句型，其中i1,i2,i3,i2*i3,i1+i2*i3 都是句型i1+i2*i3 的短语，且i1,i2,i3 为直接短语，i1为句柄,7

39、5,分析说明,文法和语言,(2)作为“短语”的两个条件是不可缺少的，仅仅有A，未必意味着就是句型的一个短语，因为还需要有S 这个条件。,例如：上例中有E i1+i2，但i1+i2并不是该句型的一个短语，因为不存在从E（开始符号）到E*i3的推导。,(1)短语、直接短语、句柄是针对某一句型（S）而言的;,76,解题方法,先证明前提给出语法树（注意文法是否是二义性的）如题文法GE:E E+E|E*E|(E)|i 证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。根据每颗语法树得出短语、直接短语、句柄（注意编号）,77,练习1题目,文法GT:T F|T*F F F P|P P(

40、T)|i 证明T*P(T*F)是文法G的一个句型，并指出这个句型的所有短语、直接短语、句柄。,78,练习解答,证明：T T*F T*FP T*F(T)T*F(T*F)T*P(T*F),语法树：,T,T,*,F,F,P,P,T,(,),T,*,F,第1层 T*P(T*F)相对于T第2层 P(T*F)相对于F;第3层 P 相对于F;(T*F)相对于P第4层 T*F 相对于T第5层,T*P(T*F)是G的一个句型，其中T*F,P,(T*F),P(T*F),T*P(T*F)都是该句型的短语，且T*F,P 为直接短语，P为句柄,79,练习2题目,文法和语言,设有文法GS:S V1 V1 V2|V1iV2

41、 V2 V3|V2+V3 V3)V1*|(1)给出(+(i(的最右推导，并画出相应的语法树；(2)证明V2+V3i(是文法的一个句型，并指出这个句型的短语、直接短语、句柄。,80,练习解答（）,文法和语言,(1)解：S V1 V1iV2 V1iV3 V1i(V2i(V2+V3i(V2+(i(V3+(i(+(i(,语法树：,V1,V1,i,V2,(,S,V2,V2,+,V3,V3,V3,(,(,81,练习解答（）,文法和语言,(2)证明：S V1 V1iV2 V1iV3 V1i(V2i(V2+V3i(V2+V3i(是文法的一个句型短语：V2+V3,(,V2+V3i(直接短语：V2+V3,(句柄

42、：V2+V3,82,3.7 有关文法实用中的一些说明(1/2),作为描述程序语言的上下文无关文法，我们对它有几点小小的限制，在实用中，主要是在文法中不得含有有害规则和多余规则。1、不含有害规则有害规则是指形如PP的产生式，因为这样的产生式除了引起二义外，没有任何用处。2、不含多余规则(1)不可到达的即文法中的某些非终结符不在任何规则的右部出现，则任何句子推导不可能用到它。也就是说对非终结符P，不存在S P，,(VNVT)*,83,有关文法实用中的一些说明(2/2),文法和语言,(2)不可终止的即文法中的某些非终结符不能够从它推出终结符串。也就是说对非终结符P，不存在P t，t VT*若文法均满足以上两个条件，则称这个文法为简化了的文法。,84,本章课后练习,习题二 P45：2、5、6、7,

展开阅读全文