编译原理及其习题解答课件

1、编译原理及其习题解答课件1第二章 文法和语言 要点要点( (本章是基础本章是基础) )1 1、概念、概念:,:,推导推导, ,直接推导直接推导, ,最左最左( (右右) )推导推导, ,产生式产生式, ,句句型型, ,短语短语, ,直接短语直接短语, ,句柄句柄, ,语法树语法树, ,规范推导规范推导, ,二义文二义文法等法等2 2、4 4种文法的定义、文法的构造和文法的推导种文法的定义、文法的构造和文法的推导3 3、语法树的构造和最左（右）推导；、语法树的构造和最左（右）推导；4 4、二义文法、二义性的证明；、二义文法、二义性的证明；5 5、句型分析；、句型分析；编译原理及其习题解答课件2

2、词法规则：自动机 语法规则：上下文无关文法编译原理及其习题解答课件3引言引言 语言包括语法和语义两方面。 语法语法是一组规则，用以判断什么样的符号序列是合法的； 语义语义指含义，如变量的类型、作用域是否符合正确的语法。常把程序设计语言的语义分为二类：静态语义和动态语义。静态语义静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；动态语义动态语义（或称运行语义、执行语义），表明程序要做些什么，要计算什么。 阐明语法的一个工具是文法，常采用上下文无关文法作为程序设计语言语法的描述工具。编译原理及其习题解答课件4补充： 文法的直观概念(1/5) 描述一种语言，无非是说明这种语言的句子。如果该

3、语言所含的句子是有限的，那么只要一一列举出即可；若是无限的，则存在如何给出有穷表示的问题。但无论如何，某语言的句子总是存在着一种组成结构，即所谓的规则（或称文法）。 文法文法：描述语言的语法结构的形式规则（即语法：描述语言的语法结构的形式规则（即语法规则）。规则）。编译原理及其习题解答课件5直观文法举例(2/5)例如：简单的汉语句子的构成规则:= := | := 我 | 你 | 他 :=王明| 大学生|工人|英语:= :=是 |学习:= | 则 “我是大学生”是句子编译原理及其习题解答课件6“我是大学生”的推导过程： 我 我 我是 我是 我是大学生 依次可以推导出句子“王明是大学生”、“我学习

4、英语”等等推导过程(3/5)编译原理及其习题解答课件7程序设计语言对文法的要求(4/5) 这些规则必须是准确的，易于理解的，且应当有相当强的描述能力，足以描述各种不同的结构。编译原理及其习题解答课件8文法作用(5/5)（1）定义句子的结构；（2）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划无穷集合。编译原理及其习题解答课件9 2 符号串及其运算符号串及其运算 （1）符号串：由字母表中的符号组成的任何有穷序列。符号串：由字母表中的符号组成的任何有穷序列。 说明说明: 字母间的顺序字母间的顺序 不同顺序组成的符号串是不同的；不同顺序组成的符号串是不同的； （2）符号串长度符号串长度 符

5、号串内所含符号的个数，若符号串内所含符号的个数，若x=string,则则|x|=6; 其中不含任何符号的符号串称为空符号串其中不含任何符号的符号串称为空符号串，长度长度| |02.1 语言成分 1 字母表（符号表）与符号字母表（符号表）与符号 元素（或称符号）的元素（或称符号）的非空有穷非空有穷集合，用符号集合，用符号表示。表示。 不同语言有不同的字母表。如汉语包括汉字、数字、标不同语言有不同的字母表。如汉语包括汉字、数字、标点符号等；点符号等；C语言包括字母、数字和保留字等等。语言包括字母、数字和保留字等等。编译原理及其习题解答课件10符号串的运算符号串的运算(1/3)符号串的头尾，固有头和

6、固有尾：符号串的头尾，固有头和固有尾： 设设 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。如果只是为了强调如果只是为了强调

7、x在符号在符号串中的某处出现，则可表示为：串中的某处出现，则可表示为：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 4） 符号串集合的乘积符号

8、串集合的乘积 设设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 = 请区别：请区别： ，三种表示方法的含义三种表示方法的含义编译原理及其习题解答课件13（5） 符号串的方幂符号串的方幂 同一符号串的连接可以写成方幂的形式。 设x是符号串，把x自身连接n次得到的符号串z，即z=xxxx，称为符号串x的方幂，记作z=xn，有

9、： x0= x1= x x2= xx x3= xxx 当n0时， xn x xn-1 = xn-1 x编译原理及其习题解答课件14（6 6）符号串集合的方幂）符号串集合的方幂同一符号串集合的连接也可以写成方幂的形式。 设符号串集合为A，则有：A0=A1= AA2= AAA3= AAA 当n0时， An A An-1 = An-1 A例如：A=ab，c，则AA= AAA= 编译原理及其习题解答课件15（7 7）符号串集合的正闭包）符号串集合的正闭包设符号串集合为A，则A的正闭包记为A+ ，定义为： A+ = A1 A2 An 表示A上所有有穷长串的集合例如：A=ab，c，AA= ， AAA= （

10、8 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*编译原理及其习题解答课件162.2 产生式文法和语言2.2.1 文法的形式定义文法的形式定义是一个四元组是一个四元组 G =（VN，VT，P，S） VN 非终结符号集，非终结符号代表的是语法范畴，也就是它是一类（或集合）的记号，而不是一个个体记号。如“表达式”、“语句”、“分程序”等等，都是表达一定的语法概念

11、。因此，每个非终结符表示一定符号串的集合（由终结符和非终结符 组成）；(如简单汉语句子中。） VT 终结符号集合，终结符是构成语言的基本符号，也就是说，它是一个语言的不可再分的基本符号； P 产生式（或称规则,重写规则,生成式）集合。所谓产生式是定义语法范畴的一种书写规则。一个产生式的形式是 （或:= )，其中 “”读为“是”或“定义为”； 产生式的左部 (VNVT )*且至少含有一个非终结符号，右部(VNVT)* ,即由终结符或（与）非终结符组成的一符号串，允许是空字 编译原理及其习题解答课件172.2 产生式文法和语言例如：简单的汉语句子的构成规则:= := | := 我 | 你 | 他

12、:=王明| 大学生|工人|英语:= :=是 |学习:= | 则 “我是大学生”是句子编译原理及其习题解答课件18文法的形式定义文法的形式定义S S 开始符号，即文法的第一个非终结符。开始符号代表了所定义的语言中我们最感兴趣的语法范畴，如在程序语言中，我们感兴趣的是“程序” 注意：1、 VN VT 即不含公共元素 ；2 、产生式是有限的；3、开始符号S至少必须在某个产生式的左部出现一次； 4、为书写方便，若干个左部相同的产生式如： P1, P2，Pn 合并成： P1|2|n其中i称为P的一个候选式。编译原理及其习题解答课件19文法定义举例文法定义举例1 1例2.1 表示算术表达式的文法描述：G1

13、 =（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例例2 文法文法G =（VN，VT，P，S）其中其中VN标识符，字母，数字标识符，字母，数字， VT a, b, c, , x, y, z, 0,1, , 8, 9 P= | | , a|b|c| a|b|c|x|y|z,|x|y|z, 0|1

14、|2| 0|1|2|8|9|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所定义的一个算术表达式。2.2.2 文法

15、的推导文法的推导编译原理及其习题解答课件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 。编译原理及其习题解答课件232.2.3 句型、句子

16、、语言句型、句子、语言例1：证明终结符号串( i*i+i )是文法G：E E+E | E*E | (E)| i的一个句子证明： 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所产生的句子的全体是一个语言

17、，记作L(G) L(G)=|S ,且VT*编译原理及其习题解答课件24语言的例子例2：文法G2 A ：A bA | cc，证明cc、bcc、bbcc属于L(G2)。证明： A=cc， A= Ba=bcc， A =bA =bbA = bbcc cc、bcc、bbcc、是属于L(G2)的例3：文法GS： (1) S0S1；(2) S01。GS的语言是什么？解：对第一个产生式使用n-1次，然后使用第二个产生式一次，得到：S = 0S1 = 00S11= S = 0S1 = 00S11= = 0 = 0n-1n-1S1S1n-1 n-1 = 0= 0n n1 1n n因此L(G)=0L(G)=0n n

18、1 1n n|n |n 1 1 例4：下列文法的语言是什么？GS=（S, , S - , S ） GA=（A， ， ，A ）编译原理及其习题解答课件252.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，P由下列产生式组成： (1) A 0R ; (2) A 01; (3) R A1编译原理及其习题解答课件26什么是递归文法？1.递归规则递归规则：

19、规则右部有与左部相同的符号 对于 U - xUy 若x=,即U - Uy，左递归； 若y=,即U - xU，右递归； 2.递归文法递归文法：文法G，存在U VN 若 U=U, 则G为递归文法； 若 U=U, 则G为左递归文法； 若 U=U, 则G为右递归文法；编译原理及其习题解答课件274. 递归文法递归文法的优点优点：可用有穷条规则，定义无穷语言 例：对于前面给出的标识符的文法是有递归文法，用y有限条规则就可以定义出所有的标识符。若不用递归文法，那将要用多少条规则呢？!3. 左递归文法左递归文法的缺点缺点：不能用自顶向下的方法来进行语分析,会造成死循环编译原理及其习题解答课件282.3 文法

20、的分类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)+且至少含有一个非终结符，且至少含有一个非终结符， (V

21、NVT)*。任何任何0型文法都是递归可枚举的。型文法都是递归可枚举的。 0型文法的能力相当型文法的能力相当于图灵机（计算机的一种简单的理论模型）。于图灵机（计算机的一种简单的理论模型）。称称L为为递归可枚举递归可枚举的：若存在一个产生的：若存在一个产生L的过程。的过程。称称L为为递归递归的：若存在一个识别的：若存在一个识别L的算法。的算法。编译原理及其习题解答课件30定义定义 1型文法（或称上下文有关文型文法（或称上下文有关文法法,CSG Context Sensitive Grammar）如果对如果对0型文法加以以下的限制，则可得到型文法加以以下的限制，则可得到1型文法。型文法。设设G=(

22、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接上页例子接上页例子编译原理及其习题解答课件

23、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说明：上述分析中，步骤是关键一步，否则不能推导出终结符号串。例如假设n=3，S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE编译原理及其习题解答课件33 上下文有关，顾名思义就是对非终结符进行替上下文有关，顾名思义就是对非终结符进行替换时必须考虑

24、上下文。例如，换时必须考虑上下文。例如，1型文法型文法G的产生式的产生式也可写成也可写成A ，其中其中、都在都在( (VNVT) )* *中，且中，且 ，A VN ，则说明了非终，则说明了非终结符结符A必须在必须在、这样一个上下文环境中才可以这样一个上下文环境中才可以替换。替换。 上下文有关文法能生成上下文有关文法能生成anbncn类特征的语言。但类特征的语言。但它不能描述它不能描述L=c|(a|b)*类语言。类语言。对上下文有关文法的说明对上下文有关文法的说明编译原理及其习题解答课件34定义定义 2型文法（或称上下文无关文法，型文法（或称上下文无关文法，CFG Context Free Gr

25、ammar） 设设G=( VN, 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上下文无关文法的说明上下文无关文法的说明上下文无关，顾名思义就是非终结符的替换上下文无关，顾名思义就是非终结符的替换可以不必考

26、虑上下文。由于这种文法对程序已可以不必考虑上下文。由于这种文法对程序已基本可以描述，因此，上下文无关文法常简称基本可以描述，因此，上下文无关文法常简称为文法。为文法。上下文无关文法最多能生成上下文无关文法最多能生成anbn类特征的语类特征的语言，不能生成言，不能生成anbncn类特征的语言。类特征的语言。编译原理及其习题解答课件36 设设G=( VN, VT, P, S)为一文法，若为一文法，若G的任何产生式的任何产生式A 或或A B ，其中，其中A、B VN ， VT* 。 对任何正规文法对任何正规文法G，都可以设计一个不确定的有穷自动都可以设计一个不确定的有穷自动机机NFA，它能够而且只能

27、够识别它能够而且只能够识别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

28、= VN+S,P转化方式为：PPA BB A AS AS编译原理及其习题解答课件382.3.2 文法分类的意义文法分类的意义自动机自动机 具有有穷描述的某种机器，对于给定文法，可接收某个终结具有有穷描述的某种机器，对于给定文法，可接收某个终结符号串，并确定是否能从该文法推导出来。符号串，并确定是否能从该文法推导出来。分析器分析器 判定（分析）一个终结符号串是否是某个文法的句子，给出判定（分析）一个终结符号串是否是某个文法的句子，给出给定串的推导序列，完成此工作的自动机，称为分析器。给定串的推导序列，完成此工作的自动机，称为分析器。正规文法与自动机正规文法与自动机 自动机由一个有穷状态集和一个状

29、态对偶之间的转换集组成。自动机由一个有穷状态集和一个状态对偶之间的转换集组成。CFG与自动机与自动机 CFG可以由下推自动机来识别。可以由下推自动机来识别。编译原理及其习题解答课件39文法分类的意义文法分类的意义 文法的分类，对于实现程序设计语言的编译程序，具有重要意义。语言的词法规则词法规则：用正规文法（RG）描述。语言的语法规则语法规则：局部语法用CFG描述； 全局语法用CSG描述。语言的语义描述语义描述：CSG（实际定义采用CFG）。编译程序在实现时，一般采用CFG识别技术（易实现，高效）。编译原理及其习题解答课件402.3.3 文法举例文法举例例2.6 1型文法G6 = ( VN, V

30、T, 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 | cL(G6) = xnynzn | n0 L(G7) = ad | b, c+ 编译原理及其习题解答课件412.3.3 文法举例文法举例(2)例2.8 2型文法G8 = ( VN, VT, P, B)，其中 VN B VT = ( , ) P= B -

31、( B ) | BB | ( ) 例2.9 2型文法G9 = ( VN, VT, P, S)，其中 VN S VT =0 , 1 P= S-0S1 , S - 01L(G8) = (n )n (m )m (k )k | n0, m=0, k=0 L(G9) = 0n 1n | n0 编译原理及其习题解答课件422.3.3 文法举例文法举例(3)例2.10 所有以0开头，以零个或多个10组成的符号串的语言。（1）右线性文法G10 S：S - 0A A -10A | （2）左线性文法G11 S：S - S10 | 0（3）正规文法G12 S：S - 0B | 0 B -1S编译原理及其习题解答课件

32、432.3.4 文法的构造（补充）文法的构造（补充） 以an、anbn、anbncn、r0|1*的构造为基础，以它们为依据来构造其它文法。给出下面语言相应的文法1、L1=abna | n 0； 2、L2=an bn+mcm | m,n 1；3、L3=anbnci | n 1，i 0；4、L4=aibncn | n 1，i 0；5、L5=anbncn|n 1 对文法的构造的求解要多做练习。编译原理及其习题解答课件44文法的构造的分析（补充）类型：A A或A A对应于an| n 1类 A A对应于anbcn| n 1类 分步：先用A A对应于an(BC)n| n 1，然后再通过改变排列顺序，最终实

33、现anbncn| n 1类编译原理及其习题解答课件45文法构造的方法（补充）文法构造的方法（补充）分析所用文法的类型对照典型的几种文法构造方法，来指导构造新的文法利用模块化设计思想来指导构造过程注意边界问题编译原理及其习题解答课件46文法的构造举例(1/3)1、L1=abna | n 0； 对应模板： A 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 划分模块： ； 对应a

34、n bn， 对应 ci4、L4=aibncn | n 1，i 0；同编译原理及其习题解答课件48文法的构造举例（3/3）5、L5=anbncn|n 1 对应模板： A A 划分模块： ； 对应an bn， 对应 cn或 对应an ， 对应 bn cn编译原理及其习题解答课件492.4 文法及其语法树文法和语言文法和语言一、语法树（推导树）语法树（推导树）直观定义：用图表示上下文无关文法句型的推导的直观方法。语法树有助于理解一个句子的语法层结构的层次，语法树通常表示成一棵倒立的树，根在上，枝叶在下。2. 形式定义形式定义对文法G=( VN, VT, P, S)相关联的语法树49满足以下4个条件：

35、（1）根结点由开始符号S所标记；（2）每个结点都有一个标记，此标记是V(即VN VT)的一个符号；（3） 若某结点至少有一个子孙结点，则该结点所标记的符号是个非终结符；（4）从左到右，若结点A1 , A2 , , Ak是结点A的孩子结点，则存在产生式A A1 A2 Ak。 ZUVabcd编译原理及其习题解答课件50 从根结点S开始推导，当非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生出下一代新结点，候选式中自左向右的每个符号对应一个新结点，并用这些符号标记其相应的新结点。每个新结点与其父结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左向右排列起

36、来就是一个句型。语法树构造的过程例1 文法G= ( E, +, *, i , (, ), P, E)，其中P为： E E+E | E*E | (E) | i对该文法关于(i*i+i)的推导的语法树如下所示：编译原理及其习题解答课件51接语法树构造举例E(根)（E）E+ +EE*Eiii什么是树的边沿？编译原理及其习题解答课件52文法和语言文法和语言语法树的问题分析语法树的问题分析（1）允许产生同名结点（反映递归性）；（2）没有后代的结点为端末结；（3）语法树不能反映产生后代的先后顺序；（例子在下一页）（4）一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程。编译原理及其习题解答课

37、件53语法树例子n推导过程中施用产生式的推导过程中施用产生式的顺序顺序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa编译原理及其习题解答课件542.5 文法和语言的一些特性文法和语言的一些特性文法和语言文法和语言2.5.1 无用非终结符号无用非终结符号如果文法的某个非终结符不出现在文法的任何一个句型中，并且不能从它推导出终结符号串，则称该非终结符为无用非终结符。例2.13 设文法G13 A：A - a

38、aBbb B - aBb | abC -cD | c D -Ef哪些符号是无用非终结符号？无用非终结符号：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文法

39、和语言文法和语言多余符号和多余规则多余符号和多余规则无用非终结符和不可达文法符号都是多余符号多余符号。包含有多余符号的规则（产生式），是多余规则多余规则。形如 U - U 的产生式，也是多余规则。例1 设文法G13 A：A - aaBbb | a B - aBb | aCbC -cD | CD -Ef应删除哪些多余规则？编译原理及其习题解答课件57文法和语言文法和语言多余符号和多余规则多余符号和多余规则应删除哪些多余规则？例例2：GS 1) SBe2) BCe3) BAf 4) AAe5) Ae 6) CCf7) DfSBeBAfAAe Ae 编译原理及其习题解答课件58文法和语言文法和语言2

40、.5.3 可空非终结符可空非终结符若存在产生式 A - ，则该产生式称为空产生式空产生式，A称为可空非终结符。 空产生式有时候带来方便，所以，可以往一个文法里增加空产生式。编译原理及其习题解答课件59 2.5.4 最左推导/最右推导/规范推导最左推导最左推导：任何一步= 都是对中的最左非终结符进行替换。最右推导最右推导（又称规范推导规范推导）：任何一步=都是对中的最右非终结符进行替换。由规范推导所得到的句型称为规范句型规范句型。从一个句型到另一个句型的推导过程往往是不唯一的。例如 E+E (i+i)：（a）E+E = E+i = i+i 最右推导（b）E+E = i+E = i+i 最左推导编

41、译原理及其习题解答课件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)但两种推导的语法树相同。编译原理及其习题解答课件61文法和语言文法和语言一个句型是否只对应唯一的一棵语法树？一个句型是否只对应唯一的一棵语法树？n例：例：GE:G

42、E:E iE iE E+EE E+EE EE E* *E EE (E)E (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 E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i编译原理及其习题解答课件62文法和语言文法和语言 定义2.13 ： 一个文法，如果它的一个句子对应有两棵或两棵以上不同的语法树，则这个文法是二义的。或 一个文

43、法的某个句子有两个不同的最左（右）推导，则这个文法是二义的。2.5.5 二义性区别区别 文法的二义性：存在两个不同文法G(二义)、G(无二义)，却有L(G)=L(G)，即产生语言相同。 语言的二义性：若不存在无二义性的文法，则该语言是二义性的。编译原理及其习题解答课件63二义性其它问题文法和语言文法和语言 人们已证明，二义性问题是不可判定的二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。我们所能做的就是为无二义性寻找一些充分条件。 例如对文法GE： E E+E | E*E | (E) | i 修改，规定运算符“+”与“*”的优先关系和结合规则优先关系

44、和结合规则，设“*”的优先性高于“+”，且服从左结合。 G： E T | E+T T F | T*F F (E) | i 编译原理及其习题解答课件64文法和语言文法和语言2.6 分析方法简介分析方法简介 句型分析的任务就是按文法的产生式，识别输入的符号是否是该文法的句型。语法树是句型推导过程的几何表示，可以十分直观的显示某句型的结构。因此在句型时，对输入符号串构造语法树，以此识别它是否是该文法的一个句型（或句子）。因此，语法树又可称为语法分析树或分析树语法分析树或分析树。我们把完成句型分析的程序称为分析程序或识别程序分析程序或识别程序，分析算法又称识别算法。分析算法又分为：从左到右分析算法；从

45、右到左分析算法；自上而下的分析法自下而上的分析法编译原理及其习题解答课件65文法和语言文法和语言自上而下的分析法 基本思想基本思想：从文法的开始符号出发，反复使用各种产生式，寻找“匹配”输入符号串的推导。即对任何输入符号串，从文法的开始符号（根结）出发，自上而下地为输入串建立一棵语法树，直到语法树结果正好是输入的符号串为止。例如：文法GS: S xAy A aa | a，识别输入串xay是否是该文法的一个句子。解：SS S S x A y (2) S S S x A y (3) a (1)编译原理及其习题解答课件66文法和语言文法和语言自上而下分析法的缺陷关键：回溯问题回溯问题（ 其分析过程是

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

47、法分析举例n例例1：文法：文法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解：a b b c d e(1)a b b c d

48、eA A(2)a b b c d eAA(3)a b b c d eAA(4)Ba b b c d eAA(5)BAS编译原理及其习题解答课件71自下而上分析法存在的问题文法和语言文法和语言可归约串的问题可归约串的问题；（ 该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号） 自下而上分析法的关键关键就是找哪个子串是“可归约串”，哪个不是“可归约串”。例如上例中的(3)a b b c d eA A(3) 用产生式(2)而非(3)，则不能归约到S 因此必须精确定义“可归约串”，事实上存在着种种不同的方法刻画“可归约串”，对这个概念的不同定义，形成了不同的自下而上的

49、分析法。在“规范归约”的分析中，用“句柄”来刻画“可归约串”。编译原理及其习题解答课件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 证明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接上例接上例文法和语言文法和语