资源描述
1,第二章 文法和语言,要点(本章是基础) 1、概念:文法,推导,直接推导,最左(右)推导,产生式,句型,短语,直接短语,句柄,语法树,规范推导,二义文法等 2、4种文法的定义、文法的构造和文法的推导 3、语法树的构造和最左（右）推导； 4、二义文法、二义性的证明； 5、句型分析；,2,词法规则：自动机 语法规则：上下文无关文法,3,引言,语言包括语法和语义两方面。 语法是一组规则，用以判断什么样的符号序列是合法的； 语义指含义，如变量的类型、作用域是否符合正确的语法。常把程序设计语言的语义分为二类：静态语义和动态语义。静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；动态语义（或称运行语义、执行语义），表明程序要做些什么，要计算什么。 阐明语法的一个工具是文法，常采用上下文无关文法作为程序设计语言语法的描述工具。,4,补充： 文法的直观概念(1/5),描述一种语言，无非是说明这种语言的句子。如果该语言所含的句子是有限的，那么只要一一列举出即可；若是无限的，则存在如何给出有穷表示的问题。但无论如何，某语言的句子总是存在着一种组成结构，即所谓的规则（或称文法）。 文法：描述语言的语法结构的形式规则（即语法规则）。,5,直观文法举例(2/5),例如：简单的汉语句子的构成规则 := := | := 我 | 你 | 他 :=王明| 大学生|工人|英语 := :=是 |学习 := | 则 “我是大学生”是句子,6,“我是大学生”的推导过程： 我 我 我是 我是 我是大学生 依次可以推导出句子“王明是大学生”、“我学习英语”等等,推导过程(3/5),7,程序设计语言对文法的要求(4/5),这些规则必须是准确的，易于理解的，且应当有相当强的描述能力，足以描述各种不同的结构。,8,文法作用(5/5),（1）定义句子的结构； （2）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划无穷集合。,9,2 符号串及其运算 （1）符号串：由字母表中的符号组成的任何有穷序列。 说明: 字母间的顺序 不同顺序组成的符号串是不同的； （2）符号串长度 符号串内所含符号的个数，若x=string,则|x|=6; 其中不含任何符号的符号串称为空符号串，长度| |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在符号串中的某处出现，则可表示为：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 = 请区别： ，三种表示方法的含义,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= A A2= AA A3= AAA 当n0时， An A An-1 = An-1 A 例如：A=ab，c，则AA= AAA= ,15,（7）符号串集合的正闭包,设符号串集合为A，则A的正闭包记为A+ ，定义为： A+ = A1 A2 An 表示A上所有有穷长串的集合 例如：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 非终结符号集，非终结符号代表的是语法范畴，也就是它是一类（或集合）的记号，而不是一个个体记号。如“表达式”、“语句”、“分程序”等等，都是表达一定的语法概念。因此，每个非终结符表示一定符号串的集合（由终结符和非终结符 组成）；(如简单汉语句子中。）,VT 终结符号集合，终结符是构成语言的基本符号，也就是说，它是一个语言的不可再分的基本符号；,P 产生式（或称规则,重写规则,生成式）集合。所谓产生式是定义语法范畴的一种书写规则。一个产生式的形式是 （或:= )，其中 “”读为“是”或“定义为”； 产生式的左部 (VNVT )*且至少含有一个非终结符号，右部(VNVT)* ,即由终结符或（与）非终结符组成的一符号串，允许是空字,17,2.2 产生式文法和语言,例如：简单的汉语句子的构成规则 := := | := 我 | 你 | 他 :=王明| 大学生|工人|英语 := :=是 |学习 := | 则 “我是大学生”是句子,18,文法的形式定义,S 开始符号，即文法的第一个非终结符。 开始符号代表了所定义的语言中我们最感兴趣的语法范畴，如在程序语言中，我们感兴趣的是“程序”,注意： 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 文法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所定义的一个算术表达式。,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的一个句子 证明： 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 =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，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.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为递归的：若存在一个识别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,接上页例子,分析：条产生式中只有第条具有递归性，其它的产生式最终都向终结符靠拢。 注意： 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,说明：上述分析中，步骤是关键一步，否则不能推导出终结符号串。例如假设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, VT, P, S)为一文法，若G的任何产生式形似A ，其中A VN， (VNVT)+ 。,例：G=(S,A,B,a,b,P,S)，其中P由下列产生式组成 SaB|bA Aa|aS|bAA Bb|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 或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|0 A 0A|1B|0S B 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.2 文法分类的意义,自动机 具有有穷描述的某种机器，对于给定文法，可接收某个终结符号串，并确定是否能从该文法推导出来。 分析器 判定（分析）一个终结符号串是否是某个文法的句子，给出给定串的推导序列，完成此工作的自动机，称为分析器。 正规文法与自动机 自动机由一个有穷状态集和一个状态对偶之间的转换集组成。 CFG与自动机 CFG可以由下推自动机来识别。,39,文法分类的意义,文法的分类，对于实现程序设计语言的编译程序， 具有重要意义。 语言的词法规则：用正规文法（RG）描述。 语言的语法规则：局部语法用CFG描述； 全局语法用CSG描述。 语言的语义描述：CSG（实际定义采用CFG）。 编译程序在实现时，一般采用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 - zz L(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型文法G9 = ( VN, VT, P, S)，其中 VN S VT =0 , 1 P= S-0S1 , S - 01,L(G8) = (n )n (m )m (k )k | n0, m=0, k=0 ,L(G9) = 0n 1n | n0 ,42,2.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,43,2.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，然后再通过改变排列顺序，最终实现 anbncn| n 1类,45,文法构造的方法（补充）,分析所用文法的类型 对照典型的几种文法构造方法，来指导构造新的文法 利用模块化设计思想来指导构造过程 注意边界问题,46,文法的构造举例(1/3),1、L1=abna | n 0； 对应模板： A A或A A 划分模块：bn 2、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， 对应 ci 4、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 文法及其语法树,文法和语言,一、语法树（推导树） 直观定义：用图表示上下文无关文法句型的推导的直观方法。 语法树有助于理解一个句子的语法层结构的层次，语法树通常表示 成一棵倒立的树，根在上，枝叶在下。,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开始推导，当非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生出下一代新结点，候选式中自左向右的每个符号对应一个新结点，并用这些符号标记其相应的新结点。每个新结点与其父结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左向右排列起来就是一个句型。,语法树构造的过程,例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）一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程。,53,语法树例子,推导过程中施用产生式的顺序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,54,2.5 文法和语言的一些特性,文法和语言,2.5.1 无用非终结符号,如果文法的某个非终结符不出现在文法的任何一个句型中，并且不能从它推导出终结符号串，则称该非终结符为无用非终结符。,例2.13 设文法G13 A： A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符号是无用非终结符号？,无用非终结符号：D E,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件： 1）A必须在某句型中出现。 2）必须能从A推出终结符号串t来。,55,文法和语言,2.5.2 不可达文法符号,如果一个非终结符不出现在文法的任何一条产生式的右部，则称该非终结符为不可达文法符号。,例2.13 设文法G13 A： A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符号是不可达文法符号？,不可达文法符号：C,56,文法和语言,多余符号和多余规则,无用非终结符和不可达文法符号都是多余符号。 包含有多余符号的规则（产生式），是多余规则。 形如 U - U 的产生式，也是多余规则。,例1 设文法G13 A： A - aaBbb | a B - aBb | aCb C -cD | C D -Ef 应删除哪些多余规则？,57,文法和语言,多余符号和多余规则,应删除哪些多余规则？,例2：GS 1) SBe 2) BCe 3) BAf 4) AAe 5) Ae 6) CCf 7) Df,SBe BAf AAe Ae,58,文法和语言,2.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 最左推导,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,文法和语言,一个句型是否只对应唯一的一棵语法树？,例：GE: E i E E+E E E*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,62,文法和语言,定义2.13 ： 一个文法，如果它的一个句子对应有两棵或两棵以上不同的语法树，则这个文法是二义的。 或 一个文法的某个句子有两个不同的最左（右）推导，则这个文法是二义的。,2.5.5 二义性,区别 文法的二义性：存在两个不同文法G(二义)、G(无二义)，却有L(G)=L(G)，即产生语言相同。 语言的二义性：若不存在无二义性的文法，则该语言是二义性的。,63,二义性其它问题,文法和语言,人们已证明，二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。我们所能做的就是为无二义性寻找一些充分条件。 例如对文法GE： E E+E | E*E | (E) | i 修改，规定运算符“+”与“*”的优先关系和结合规则，设“*”的优先性高于“+”，且服从左结合。 G： E T | E+T T F | T*F F (E) | i,64,文法和语言,2.6 分析方法简介,句型分析的任务就是按文法的产生式，识别输入的符号是否是该文法的句型。语法树是句型推导过程的几何表示，可以十分直观的显示某句型的结构。因此在句型时，对输入符号串构造语法树，以此识别它是否是该文法的一个句型（或句子）。因此，语法树又可称为语法分析树或分析树。我们把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。 分析算法又分为：,从左到右分析算法； 从右到左分析算法；,自上而下的分析法 自下而上的分析法,65,文法和语言,自上而下的分析法,基本思想：从文法的开始符号出发，反复使用各种产生式，寻找“匹配”输入符号串的推导。即对任何输入符号串，从文法的开始符号（根结）出发，自上而下地为输入串建立一棵语法树，直到语法树结果正好是输入的符号串为止。,例如：文法GS: S xAy A aa | a，识别输入串xay是否是该文法的一个句子。,66,文法和语言,自上而下分析法的缺陷,关键：回溯问题（ 其分析过程是一种试探过程） 回溯问题是从各种可能的候选式中任选一个，进行推导后发现该候选式是错误的，则退回去重新选择候选式的方式。例如上例中的(3)。,S,S,S,x,A,y,(3) 选用第1个候选式,a,回溯的产生使算法代价极低，效率很低。关于解决回溯问题将在第5章中介绍。,a,67,自下而上的分析法,文法和语言,基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。即从语法树的末端开始，步步向上“归约”，直到根结。 归约：若V= ，W=， 是文法的产生式，如有V=W，则W直接归约到V。,68,自下而上的语法分析举例,例1：文法G：S cAd A ab A a 识别输入串w=cabd是否该文法的句子,S A A 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,自下而上分析法存在的问题,文法和语言,可归约串的问题；（ 该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号） 自下而上分析法的关键就是找哪个子串是“可归约串”，哪个不是“可归约串”。例如上例中的(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 证明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为句柄,75,分析说明,文法和语言,(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 (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 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 , ( 句柄： 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,
展开阅读全文