编译原理 第三章

1、第三章第三章 文法和语言文法和语言第第3章章 文法和语言文法和语言 3.1 文法的直观概念 3.2 符号和符号串 3.3 文法和语言的形式定义 3.4 文法的类型 3.5 上下文无关文法及其语法树 3.6 句型的分析 3.7 有关文法实用中的一些说明 3.8 典型例题及解答学习目标学习目标本章目的是为语言的语法描述寻求工具掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一-文法。熟练使用文法定义程序设计语言的单词和语法成分对形式语言的理论有一个初步基础本章知识点(内容)引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些

2、说明学习内容学习内容什么是文法,什么是它定义的语言？在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？什么是语法分析？语法分析方法的分类？ 一个程序设计语言一个记号系统，如同自然语言一样，它的完整定义包括语法和语意两个方面。 语法：是指一组规则，用它可以形成和产生一个合法的程序。目前，文法是广泛使用的语法描述工具。 语法只定义什么样的符号序列是合法的，与这些符号的含义毫无关系，如类型匹配、变量作用域等就无法使用使用文法来检查，这些工作属于语义分析的工作。 语义有静态语义和动态语义。静态语义是一系列限定规则，确定那些合乎语法的程序是合适的；动态语义是指运行语义或执行语义，表

3、明程序程序要做些什么，要计算什么。3.1 文法的直观概念文法的直观概念 当我们表述一种语言时，无非是说明这种语言的句子n如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了n对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。n以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构-汉语规则 3.1 文法的直观概念文法的直观概念 比如：“我是大学生”是汉语的一个句子。采用EBNF来表示汉语的构成规则：n句子 =主语谓语n主语 =代词|名词n代词 = 我 | 你 | 他n名词 = 王明 | 大学生 | 工人 | 英语n谓语 =动词

4、直接宾语n动词 = 是 | 学习n直接宾语 =代词|名词3.1 文法的直观概念文法的直观概念 有了句子的一组规则以后，我们可以按照如下方式用它们去推导或产生句子。 从句子开始，逐渐用规则的右边代替左边，直到产生字符串。这个动作过程为：3.1 文法的直观概念文法的直观概念 句子：“我是大学生”的全部动作过程是：句子 主语谓语代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生3.1 文法的直观概念文法的直观概念 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。 这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它

5、描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。 文法是描述语言的语法结构的形式规则。语言概述 语言是由句子组成的集合，是由一组符号所构成的集合。语言是由句子组成的集合，是由一组符号所构成的集合。 汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系 程序设计语言程序设计语言-所有该语言的程序的全体。所有该语言的程序的全体。 研究程序设计语言研究程序设计语言n每个程序构成的规律每个程序构成的规律n每个程序的含义每个程序的含义n每个程序和使用者的关系每个程序和使用者的关系

6、语言研究的三个方面语言研究的三个方面n语法语法 Syntaxn语义语义 Semanticsn语用语用 Pragmatics 语法语法 ：n表示构成语言句子的各个记号之间的组合规律表示构成语言句子的各个记号之间的组合规律 语义：语义：n表示各个记号的特定含义。（各个记号和记号所表示表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）的对象之间的关系） 语用：语用：n表示在各个记号所出现的行为中，它们的来源、使用表示在各个记号所出现的行为中，它们的来源、使用和影响。和影响。 如果不考虑语义和语用，即只从语法这一侧面来看语如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言

7、称作言，这种意义下的语言称作形式语言形式语言。 形式语言抽象地定义为一个数学系统。形式语言抽象地定义为一个数学系统。 “形式形式”是指这样的事实：语言的所有规则只以什么符是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。号串能出现的方式来陈述。 形式语言理论是对形式语言理论是对符号串集合符号串集合的的表示法表示法、结构结构及其及其特性特性的研究。是程序设计语言语法分析研究的基础。的研究。是程序设计语言语法分析研究的基础。3.2 符号和符号串符号和符号串 符号：可以相互区别的记号（元素）。 字母表：是字母的非空有穷集合；用、V表示。 符号串：字母表中符号组成的任意有穷序列。n空串：

8、不含有任何符号的串称作空串，记作。n1、空符号串(没有符号的符号串)是上的符号串n2、若x是上的符号串，a是的元素，则xa和ax是上的符号串；ny是上的符号串，当且仅当它可以由1和2导出。n例：=a,b ，则,a,b,aa,ab,aabba都是上的符号串 3.2 符号和符号串符号和符号串 符号串的运算n符号串s的头头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串. 如： b是符号串banana的一个前缀.n符号串s的尾尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串. 如:nana是符号串banana的一个后缀.n符号串s的子串子串：从s中删去一个前缀和一个后缀得到的符

9、号串. 如:ana是符号串banana的一个子串.3.2 符号和符号串符号和符号串 固有头和固有尾固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。 例子:设z=abc,n那么z的头是,a,ab,abc,除abc外，其它都是固有头；nz的尾是,c,bc,abc，z的固有尾是,c,bc。几种写法几种写法当我们对符号z=xy的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法：z=x；如果只是为了强调x在符号串z中的某处出现，则可表示为：z=x；符号t是符号串z的第一个符号，则表示为z=t。符号串的运算符号串的运算

10、 符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 的长度为0 连接（乘积）运算：n定义：符号串x、y的连接,是把符号串y写在符号串x之后的新符号串xy；如 x=ab,y=cd 则 xy=abcd；又如，a = a n若串集A=1， 2， ，串集B=1， 2， ，则乘积AB= | A and B3.2 符号和符号串符号和符号串 方幂：符号串自身连接n次得到的符号串an 定义为 aaaa ，即n个a； a1=a, a2=aa则a0=。使用A*表示A上的一切符号串（包括）组成的集合。 字母表A的闭包（A*）： A*=A0A1A2n即：由A上符号组成的所有串的集合（包括空串 ）。 字母表

11、A的正闭包（A+）：A + = A1 A2 =A*-n即：由A上符号组成的所有串的集合（不包括空串 ）。3.2 符号和符号串符号和符号串 例如：A=a,b; B=c,e,d则AB=ac,ae,ad,bc,be,bd 例如：串集Aa的各次方幂定义为：nA0=nA1=A=annAn=AAn-1(n0)=aa =a,b=a,bn* *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,n+ +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab, 如何描述一种语言？如何描述一种语言？n如果语言是有穷的（

12、只含有有穷多个句子），可以将句子逐一列出来表示n如果语言是无穷的，找出语言的有穷表示。n语言的有穷表示有两个途经：n生成方式 （文法）n识别方式（自动机）3.3 文法和语言的形式定义文法和语言的形式定义n生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。n识别方式（自动机）：用一个模型，当输入的一任意串属于语言时，该过程经有限次计算后就会停机并回答“是”，若不属于，要麽能停机并回答“不是”，要麽不停机永远继续下去。 文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.3.3 文法和语言的形式定义文法和语言的形式定义3.3 文法和语言的形式定义文法和语言的形式定

13、义 文法文法G定义为四元组(VN，VT，P，S)。其中：nVN为非终结符号非终结符号(或语法实体，或变量)集；nVT为终结符号终结符号集；nP为产生式产生式(也称规则规则)的集合；n VN，VT和 P是非空有穷集。n VN和VT不含公共的元素，即VNVT=n通常用V表示VNVT，V称为文法G的字母表nS称作识别符号识别符号或开始符号开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 3.3 文法和语言的形式定义文法和语言的形式定义 规则，也称重写规则、产生式或生成式，是形如或 = 的( , )有序对，其中：n是字母表V的正闭包V+中的一个符号，n是V*中的一个符号。n称为规则的左部

14、，n称为规则的右部。3.3 文法和语言的形式定义文法和语言的形式定义 例3.1 文法G=(VN，VT，P，S)，其中VN=S，VT=0，1，P=S0S1，S01。n非终结符集中只含一个元素S；n终结符集由两个元素0和1组成；n两条产生式；n开始符号是S。3.3 文法和语言的形式定义文法和语言的形式定义 例3.2 文法G=(VN，VT，P，S)，其中nVN =标识符，字母，数字nVT=a,b,c,，x,y,z,0,1,，9nP =标识符字母n标识符标识符字母n标识符标识符数字n字母a |b|zn数字0 |1 |9n S =标识符3.3 文法和语言的形式定义文法和语言的形式定义 元元符号: ， =

15、 ， |， 文法习惯上只将产生式写出，并可有如下的约定：第一条产生式的左部是开始符号用尖括号括起来的是非终结符，否则为终结符；或者大写字母表示非终结符，小写字母或其他字母表示终结符G写成GS，S是开始符号S3.3 文法和语言的形式定义文法和语言的形式定义 文法的写法：n1、 G：SaAb Aab AaAb A,其中S是开始符 n2、 GS： Aab AaAb A SaAbn3、 GS： Aab |aAb | SaAb3.3 文法和语言的形式定义文法和语言的形式定义 推导的概念:如是文法G=(VN，VT，P，S)的规则(或说是P中的一产生式)，和是V*中的任意符号，若有符号串v，w满足：nv=

16、，w= 则说v(应用规则)直接产生w，或者说，w是v的直接直接推导推导，也可以说，w直接归约直接归约到v，记作v w3.3 文法和语言的形式定义文法和语言的形式定义 例：文法G=(VN，VT，P，S)，其中VN=S，VT=0，1，P=S0S1，S01,可以给出直接推导的一些例子如下：nv=0S1,w=0011,直接推导：0S1 0011，使用的规则：S01，这里=0，=1。nv=S,w=0S1，直接推导：S 0S1使用的规则：S0S1，这里=，=nv=0S1,w=00S11,直接推导：0S1 00S11，使用的规则：S0S1，这里=0，=1 3.3 文法和语言的形式定义文法和语言的形式定义 长

17、度为n(n1)的推导:n如果存在直接推导的序列：v= w0 w1 . wn=w,(n0)则称v推导出 (产生)w(推导长度为n)，或称w归约到v。记作v =+ w，读作经过1步或多步推导。 长度为n(n0)的推导:n若有若有v + w，或，或v=w， 则记为则记为v * w，读作经过0步或多步推导。3.3 文法和语言的形式定义文法和语言的形式定义例 G： S0S1， S01n0S1 00S11n00S11 000S111n000S111 00001111n S 0S1 00S11 000S111 00001111n S =+ 000011113.3 文法和语言的形式定义文法和语言的形式定义 句

18、型：句型：n有文法G，若符号串x是从识别符号S推导出来的， S =* x，则称x是文法G的句型。 句子：句子：n有文法G，若S =* x，且xVT*，则称x是文法G的句子。是仅含终结符的句型。 例：G： S0S1， S01nS 0S1 00S11 000S111 00001111nG的句型S,0S1 ,00S11 ,000S111,00001111nG的句子000011113.3 文法和语言的形式定义文法和语言的形式定义 例：GE： EE+T|T TT*F|F F(E)|anEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 句子：用符号a，+，*，( 和 ) 构

19、成的算术表达式3.3 文法和语言的形式定义文法和语言的形式定义 语言的概念：n 由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S为文法的开始符号，且x VT* 例：G： S0S1， S01nL(G)=0n1n|n13.3 文法和语言的形式定义文法和语言的形式定义 例 文法GS：n（1）SaSBEn（2）SaBEn（3）EBBEn（4）aBabn（5）bBbbn（6）bEben（7）eEeeL（G）=？ L（G）= anbnen | n1 G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成3.3 文

20、法和语言的形式定义文法和语言的形式定义 文法的等价性n若L(G1)=L(G2)，则称文法G1和G2是等价的。n如文法G1A:A0R 与与G2S：S0S1 等价 A01 S01 RA13.4文法的类型文法的类型Chomsky（乔姆斯基）对文法的分类： 根据对产生式施加的限制，可分为：n0型文法n1型文法n2型文法n3型文法3.4文法的类型文法的类型 0型文法(短语文法或无限制文法)nP中产生式 其中V+ 并至少含有一个非终结符, V*.na)识别0型语言的自动机称为图灵机(TM).nb)0型文法是对产生式限制最少的文法。nc)任何0型语言都是递归可枚举的。nd)对0型文法产生式的形式作某些限制，

21、可得到其他类型文法的定义。3.4文法的类型文法的类型1型文法nP中产生式,除可能有S 外均有|.n或者，除可能有S 外,均有A ,其中, V* ,A VN, V+.na)1型文法又称为长度增加文法、上下文有关文法nb)识别1型语言的自动机称为线性界限自动机(LBA) ; nc)1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成 ，除非是开始符号产生3.4文法的类型文法的类型 1型文法的例子：n设文法G(VN,VT,P,S)， VN S,B,E, VT a,b,e 其中P为: n (0) S aSBEn (1) S aBEn (2) EB BEn (3) aB abn (

22、4) bB bbn (5) bE ben (6) eE ee3.4文法的类型文法的类型 2型文法：nP中产生式具有形式A 其中AVN ， V*.na)2型文法对产生式的要求是：产生式左部一定是非终结符，产生式右部可以是VN 、 VT或 ；非终结符的替换不必考虑上下文; nb)识别2型语言的自动机称为下推自动机(PDA);nc) 2型文法也称为上下文无关文法。3.4文法的类型文法的类型 2型文法例子:n设文法G(VN,VT,P,S)， VN S,A,B, VT a,b 其中P为: n(0) S aBn(1) S bAn(2) A an(3) A aS | bAAn(4) B bn(5) B bS

23、 | aBB3.4文法的类型文法的类型3型文法：nP中产生式具有形式A B， A ，或者A B， A ， 其中A，BVN，VT*。na)3型文法也称为正规文法RG、右线性文法或左线性文法；n b) 3型文法中的产生式要么均是右线性产生式，要么是左线性产生式，不能既有左线性产生式，又有右线性产生式；若所有产生式均是左线性，则称为左线性文法；若所有产生式均是右线性，则称为右线性文法；nc)识别3型语言的自动机称为有限状态自动机3.4文法的类型文法的类型 3型文法例子：n设文法G(VN,VT,P,S)，VN S,A,B, VT 0,1 其中P为: n (0) S 0A | 1B | 0n (1) A

24、 0A | 1B | 0Sn (2) B 1B | 1 | 03.4文法的类型文法的类型 四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系2型文法型文法1型文法型文法0型文法型文法3型文法型文法3.4文法的类型文法的类型 0型文法产生的语言称为0型语言 1型文法或上下文有关文法(CSG)产生的语言称为1型语言或上下文有关语言(CSL) 2型文法或上下文无关文法(CFG)产生的语言称为2型语言或上下文无关语言(CFL) 3型文法或正则(正规)文法(RG)产生的语言称为3型语言正则(正规)语言(RL)3.4文法的类型文法的类型 0型文法(短语结构文法)的能力相当于图灵机，可以表征任何递归可

25、枚举集，而且任何0型语言都是递归可枚举的 1型文法(上下文有关文法)：产生式的形式为 1A2 12，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。 2型文法(上下文无关文法CFG)：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法(正规文法RG)：产生的语言是有穷自动机(FA)所接受的集合。例例1 设L1=a2nbn|n=1 且a,b VT 试构造生成L1的文法G1n设n=1， L1 =aabn n=2， L1 =aaaabbn n=3， L1 =aaaaaabbbn 所以得：S aaSbn S aab例例2 设L2=aibj

26、ck | i,j,k=1 且a,b,c VT试构造生成L2的文法G2nS aS S aBnB bB B bCnC cC | c3.5 上下文无关文法及其语法树上下文无关文法及其语法树一、语法树1、定义：n用来表示语言句子结构的树。2、作用：n使用语法树可以使语法分析过程直观、形象，易于判断文法二义性。3.5 上下文无关文法及其语法树上下文无关文法及其语法树 语法树应满足以下四个条件：n每个节点都有一个V中的符号作为标记n根的标记是开始符号Sn若一个节点n至少有一个它自己除外的子孙，并且n有标记A则A VNn若节点n的直接子孙，从左到右的次序是节点n1 ， n2 nk,其标记分别为A1，A2 A

27、k,那么A A1A2 Ak一定是P中的一个产生式。3.5 上下文无关文法及其语法树上下文无关文法及其语法树 最左（最右）推导n如果在推导的任何一步 ，其中，是句型，都是对中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。3.5 上下文无关文法及其语法树上下文无关文法及其语法树 例如，有一个2型文法nG= (S,A,a,b,P,S),其中P:n(0) S aAS (1)A SbA (2)A SS (3) S a (4) A ba 利用推导产生句子aabbaa:nS aAS aAa aSbAa aSbbaa aabbaanS aAS aSbAS aabAS aabbaS aabba

28、anS aAS aSbAS aSbAa aabAa aabbaa3.5 上下文无关文法及其语法树上下文无关文法及其语法树S最左推导S (0) S aAS (1)A SbA (2)A SS (3) S a (4) A ba3.5 上下文无关文法及其语法树上下文无关文法及其语法树Sa A S最左推导S aAS(0) S aAS (1)A SbA (2)A SS (3) S a (4) A ba3.5 上下文无关文法及其语法树上下文无关文法及其语法树Sa A S最左推导S aAS aSbASS b A(0) S aAS (1)A SbA (2)A SS (3) S a (4) A ba3.5 上下文

29、无关文法及其语法树上下文无关文法及其语法树S aa A S最左推导S aAS aSbAS aabASS b A(0) S aAS (1)A SbA (2)A SS (3) S a (4) A ba3.5 上下文无关文法及其语法树上下文无关文法及其语法树S aa A Sb a最左推导S aAS aSbAS aabAS aabbaSS b A(0) S aAS (1)A SbA (2)A SS (3) S a (4) A ba3.5 上下文无关文法及其语法树上下文无关文法及其语法树S aa A Sb a a最左推导S aAS aSbAS aabAS aabbaS aabbaaS b A(0) S

30、aAS (1)A SbA (2)A SS (3) S a (4) A ba3.5 上下文无关文法及其语法树上下文无关文法及其语法树 语法规则为：n n n n n Young | popn men | music n like能否用最左推导得出“Young men like pop music”是个语法正确的句子?在推导过程中有哪些句型?3.5 上下文无关文法及其语法树上下文无关文法及其语法树 Young Young men Young men Young men like Young men like Young men like pop Young men like pop music最右

31、归约最左推导用语法树表示用语法树表示Young men likepop music例题例题 已给GE：EE+T|T TT*F|F F(E)|a构造a+a*a的语法树，最左推导，最右推导。3.5 上下文无关文法及其语法树上下文无关文法及其语法树 二义性 1、句子二义性：n如果文法的一个句子存在对应的两棵或两棵以上的语法树，则该句子是二义的。 2、文法二义性：n包含二义性句子的文法是二义文法。3.5 上下文无关文法及其语法树上下文无关文法及其语法树 例如：文法G=(E，+,*,(,),i，P，E),其中：E i | E+E | E*E | (E),对于句子（ i* i+ i)有几种最左推导?n1）

32、 E (E) (E+E) (E*E+E) ( i*E+E) ( i*i+E) ( i* i+ i) n2） E (E) (E*E) ( i*E) ( i*E+E) ( i*i+E) ( i* i+ i)3.5 上下文无关文法及其语法树上下文无关文法及其语法树1） E n(E)n(E+E) n(E*E+E) n( i*E+E) n( i*i+E) n( i* i+ i)E( E )E + EE * E i i i3.5 上下文无关文法及其语法树上下文无关文法及其语法树2） E n(E) n(E*E)n( i*E)n( i*E+E) n( i*i+E) n( i* i+ i)E( E )E * E

33、E + E i i i3.5 上下文无关文法及其语法树上下文无关文法及其语法树 二义性的几点说明：n1）二义性会给语法分析带来不确定性。n2）文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法。n3）若要证明是二义性，只要举出一例n4）若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事。3.5 上下文无关文法及其语法树上下文无关文法及其语法树 例如：if语句结构采用下面的产生式：nS if C then S else SnS if C then SnS 其他语句 C 具体条件表达式 判断它是不是二义性文法？ 解法：只要找到一个例子，一个句子

34、有两个语法树，就可以证明它是二义性文法。，如n if c1 then if c2 then s1 else s2S if C then S else S c1 if C then S s2 c2 s1S if C then S c1 if C then S else S c2 s1 s23.6 句型的分析句型的分析 句型分析：n一个识别输入符号串是否是语法上正确的程序的过程。n在语言的编译实现过程中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称为识别算法。3.6 句型的分析句型的分析 分析算法分为两大类:n1）自上而下语法分析n从文法的开始符号出发，反复使用不同产生式进行推导以谋求

35、与输入符号串相匹配。n 2）自下而上语法分析n对输入符号串寻找不同产生式进行归约直到文法开始符号。 注：这里所说的输入符号指词法分析所识别的单词。3.6 句型的分析句型的分析 自上而下的分析方法 例：考虑文法GS: (1)S cAd (2) A ab (3) A a 识别输入串wcabd是否是该文法的句子？Sc A da bS cAd cabd3.6 句型的分析句型的分析 自下而上的分析方法 例：考虑文法GS: (1)S cAd (2) A ab (3) A a 识别输入串wcabd是否是该文法的句子？c a b dASS cAd cabd3.6 句型的分析句型的分析 句型分析的有关问题n在自

36、上而下的分析中，在扩展非终结符A时，存在两个A的产生式，若利用产生式2可以顺利完成识别过程，若利用产生式1就无法往下推，导致识别程序得出错误的结论。n当存在非终结符V的多条规测时用哪一个右部去替换的问题。解决方法为回溯。n在自下而上的分析中，每一步采用哪一个子串进行规约？因此需要精确定义规约串。3.6 句型的分析句型的分析 令G是一个文法，S是文法的开始符号， 是文法G的句型，若有S *A，且A +，则称是句型相对于非终结符A的短语。若有A 则是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。n短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。n简单短语（直

37、接短语）：若短语是某子树根经过1步推导得到的，则称之为该子树根的简单短语。n句柄：句型中的最左简单短语。 注：句柄是最左归约时要寻找的简单短语。3.6 句型的分析句型的分析 文法GE：nE T | E+TnT F | T*FnF (E) | in句型i*i+iEE + TTFi3T * F i2i1F短语：直接短语：句柄：i1*i2+i3，i1*i2，i1，i2，i3i1，i2，i3i1 文法中文法中不得含有有害规则和多余规则n有害规则：形如UU的产生式。会引起文法的二义性n多余规则：指文法中任何句子的推导都不会用到的规则，n多余规则也可表示为：文法中不含有不可到达和不可终止的非终结符，分以下

38、两种情况：n1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。n2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。3.7 有关文法实用中的一些说明有关文法实用中的一些说明例： 文法GS:S BeB Ce | AfA Ae | eC CfD f请判断其中是否有请判断其中是否有多余规则多余规则化简文法化简文法:3.7 有关文法实用中的一些说明有关文法实用中的一些说明1)文法中某些非终结符不在任何规则的右部出现；2）文法中某些非终结符，由它不能推出终结符号串 例：例：GS ： 1) SBe 2) BCe D为不可到达为不可到达 3) BAf C为不可终止为不

39、可终止 4) AAe 5) Ae 6) CCf 7) Df 产生式产生式 2），），6），），7）为）为多余规则多余规则应去掉。应去掉。3.7 有关文法实用中的一些说明有关文法实用中的一些说明 对于文法对于文法GS，为了保证任一非终结符，为了保证任一非终结符A在在句子句子推导中出现，推导中出现，必须满足如下两个条件：必须满足如下两个条件：n1. A必须在某句型中出现必须在某句型中出现n即有即有S =* A，其中，其中，属于属于V*n2. 必须能够从必须能够从A推出终结符号串推出终结符号串t来来n即即A =* t，其中，其中tVT*3.7 有关文法实用中的一些说明有关文法实用中的一些说明3.8典

40、型例题及解答典型例题及解答 证明文法G( E,O,(,),+,*,v,d,P,E )是二义的。n E EOE | (E) | v | dn O + |* 解：对于句子v*v+d的语法树不只一棵。 消除二义性nE E+T |T nT T* F | F n F (E) | v | d语言和文法构造方法小结 语言语言L(G)=L(G)文法文法G文法文法Gbn | n0bn | n0abn | n0bna | n0(ab)n | n0ambn|m0,n0ambn|m0,n0anbn | n0(akcd) nbn | k,n0a2n+1bn| n=0语言和文法构造方法小结 语言语言L(G)=L(G)文法

41、文法G文法文法Gbn | n0BbB | bBBb | bbn | n0PbP |PPb |abn | n0SDB Da BbB | bSaB BBb | bbna | n0TPD Da PbP |TPa PPb |(ab)n | n0UEU | E EabUUab | abambn|m0,n0VAB AaA | aBbB | bVaV | aBBbB | bambn|m0,n0WAB AaA |BbB | bWaW | BBbB | banbn | n0XaXb | ab(akcd) nbn | k,n0XDXH | DH DAcdAaA |a Hba2n+1bn| n=0YaaYb |aYKYH | a KaaHb本章目的为语言的语法描述寻求工具为语言的语法描述寻求工具,以便：以便：对源程