第二章文法与语言ppt课件.ppt

《第二章文法与语言ppt课件.ppt》由会员分享，可在线阅读，更多相关《第二章文法与语言ppt课件.ppt（112页珍藏版）》请在三一办公上搜索。

1、编译原理,Compiler Principles,2013年9月,闫雷鸣,第二章 文法与语言,讨论问题：文法和语言的概念和定义 文法和语言的分类 文法等价变换 句型分析,简单回顾,对程序的理解 程序是计算机执行的一系列指令；程序是计算任务的 处理对象和处理规则的描述。对程序设计语言的理解 程序设计语言是程序的书写规范；程序设计语言的要素：一组记号(符号)和一组规则。程序设计语言程序是 程序设计语言之符号集合上的、按一定规则组成的符号串。,语言是一切句子的集合；程序设计语言是一切程序的集合；把程序看做程序设计语言的句子。程序是(程序设计）语言的句子 如何系统地构造程序？或者，一般地，如何为一个(

2、程序设计)语言生成句子？,2.1 符号串与符号串集合,语言实际上是一个符号串集合；文法规定语言中句子的构造规则。句子是一个语言之字母表上按一定规则构造的符号串。2.1.1 字母表 字母表:有穷非空的符号集合。例 A=a,b,c=0,1 C语言字母表=字母，数字，界限符 不同的语言有不同的字母表。字母表上的元素（即符号）组成符号串。,2.1.2 符号串:1.符号串及其长度 符号串:由字母表上的符号所组成的有穷序列。字母表A=a,b,c上的符号串：a,b,c,ab,ba,aaa,aab,baa,abcab,(空串)注意：顺序是重要的,abba C语言字母表上的符号串？长度：|aabcaca|=7|

3、=0,2.子符号串 若u=xvy，其中|v|0（|u|=|v|）则v是u中的子符号串。（非空符号串）例 a+(b-c)/d中的子符号串3.符号串的头与尾（前缀、后缀）abc的头：a,ab,abc,x=t abc的尾：c,bc,abc,x=t,4.对符号串的运算 联结（或并置）：x=ab y=ba xy=abba yx=baab 对任何符号串x，有x=x=x。方幂：xn=xxx(x自身联结n次)xn=xn-1x=xxn-1 x0=x3=(ab)3=ababab|xy|=|x|+|y|xn|=n|x|x0|=0,2.1.3 符号串集合（语言）1.符号串集合的定义1)它是一切元素都是某字母表上的符号

4、串的集合。2)表示法 枚举法 1，11，111，1111 省略法 1，11，111，1111，描述法 1i|i1 或x|x全由1组成,|x|1 注意：一定不能涉及含义,如 x|x=10i。,字母表上的一个语言就是上的一些符号串组成的集合。空集 是一个语言，仅含一个空符号串集合 也是一个语言。特别需要指出的是，和 是不同的语言。,2.对符号串集合的运算 乘积：AB=xy|x A 且 y B 1,0 a,b,c=?对任何符号串x有x=x=x，A0=因此，A=A=A，但A=A=。方幂：An=AAA(n 个A乘积）An=An-1A=AAn-1 特例，字母表A的方幂，xAn,|x|=n 1,03=?1,

5、0n=?,3.字母表的闭包与正闭包 闭包 A*=A0A1An 0，1，2*正闭包 A+=A1An=A*-0，1，2+xA+,则|x|=1 xA*,则|x|=0 任何一个语言是其字母表之正闭包的真子集。如何找出此真子集？或说，如何找出其句子？,2.2 文法与语言的形式定义,2.2.1 文法的形式定义1.重写规则（产生式规则）定义：有序对（U，u)或 U:=u,A（或A:=）其中，A是一个符号，称为产生式规则的左部，而 是有穷非空符号串，称为产生式规则的右部，“”和“:=”表示“定义为”或“由组合成的”或“生成”，其含义是左部符号用右部的符号串定义或左部符号生成右部符号串。产生式规则可合写，如：A

6、 和 A 可写为A|,1.重写规则（产生式规则）规则表示法：通常的 E:=E+T E:=T 或 E:=E+T|T 扩充的 E:=T+T 术语：非终结符号，非终结符号集VN 终结符号，（不会出现在规则左部）终结符号集VT（VN VT=V=VN VT）单规则：右部是单个非终结符,用于指定重复次数:=05 内中符号至多出现一次:=+|-()提公因子E:=E+T|E-T 可改写为E:=E(+|-)T,16,规则构造的例子,C语言标识符的规则：:=:=:=:=A|Z:=a|z:=_:=0|9,17,用规则产生句子的例子,如：用标识符产生式规则产生句子area.a a ea ea rea rea area

7、 其中，“=”为推导。,2.文法的定义 文法GZ是非空有穷的重写规则集合，其中Z是识别符号（或称开始符号），G是文法名。例G1E：E:=E+T E:=T T:=T*F T:=F F:=(E)F:=i G2E：E:=E+T|T T:=T*F|F F:=(E)F:=i GE：E:=T+T T:=F*F F:=(E)|i文法的四要素：VN，VT，P，ZP有穷非空的重写规则集，识别符号Z VN,3.应用文法产生语言的句子 G:1.:=2.:=3.:=4.:=5.:=Peter 6.:=Berry7.:=river8.:=swims9.:=in,例 试以文法G 为例考察如何应用文法 来生成句子。替换为句

8、子=主语 谓语 状语(规则1)=名词 谓语 状语(规则2)=Peter 谓语 状语(规则5)=Peter 动词 状语(规则3)=Peter swims 状语(规则8)=Peter swims 介词 名词(规则4)=Peter swims in 名词(规则9)=Peter swims in river(规则7),应用文法生成句子的步骤：步骤1 以识别符号为当前符号串；步骤2 对当前符号串中的一个非终结符号进行替换，把它替换为以此非终结符号为左部的规则之右部符号串，生成新的当前符号串；步骤3 重复步骤2,直到当前符号串中不包含非终结符号，最终不包含非终结符号的符号串就是所生成的句子。说明：每步的当

9、前符号串将称为句型，最终的终结符号串称为句子。,按上述步骤应用各个规则，可生成：Berry swims in river 甚至可生成：river swims in Peter 表明：语法上的正确性不能保证语义上的正确性。对当前句型中任一非终结符号进行替换，都将生成新的句型，最终生成句子。但宜用系统的方式进行推导，如，每步对最左的或最右的非终结符号进行替换。这时，分别称为最左推导与最右推导。引进句子生成中的两个重要概念：推导与归约。,直接推导：=xUy=xuy 句子=主语 谓语 状语 主语 谓语 状语=名词 谓语 状语 名词 谓语 状语=Peter 谓语 状语 Peter 谓语 状语=Peter

10、 动词 状语 Peter 动词 状语=Peter swims 状语 Peter swims 状语=Peter swims 介词 名词 Peter swims 介词 名词=Peter swims in 名词 Peter swims in 名词=Peter swims in river,直接推导时，给定 v=xUy,找到规则U:=u，把u代替U，得到 w=xuy称v直接推导到w，记为：v=w 或 xUy=xuy,推导（直接推导序列）：=+=主语 谓语 状语=名词 谓语 状语=Peter 谓语 状语=Peter 动词 状语=Peter swims 状语=Peter swims 介词 名词=Peter

11、 swims in 名词=Peter swims in river 推导时，给定符号串v,找到 v=u1=u2=un-1=w,得到符号串w,称v推导到w，记为：v=+w。一般，从识别符号开始推导，例如，=+Peter 谓语 状语=+Peter swims in river 推导长度：直接推导的步数。,直接推导:=直接推导时，给定v=xUy，在其中找出U，应用规则U:=u,得到 w=xuy，称v直接推导到w,或w直接归约到v,记为 v=w 一般，总有：U:=u xUy=xuy推导:=+推导时，给定符号串v,找出直接推导序列：v=u1=u2=un-1=w得到符号串w,称v推导到w,或w归约到v,记

12、为:v=+w n称为推导的长度。广义推导：=*若 v=+w 或 v=w，则称v广义推导到w,或广义归约到v。,对照：直接推导v=w(U:=u v=xUy w=xuy)(推导长度=1)推导 v=+w(v=u1=un-1=w)(推导长度1)广义推导v=*w(v=+w 或 v=w)(推导长度0)通常考虑的都是从识别符号出发的推导：Z=*x x(VN VT)+直接归约：v=w w直接归约为v 归约:v=+w w归约为v 广义归约:v=*w w广义归约为v 请对照比较推导与归约这两个概念。,重要概念：句型、句子 句型：Z=*x,x(VNVT)+句子：Z=*x,x VT+例 Peter swims in

13、river注意：句子和在概念上的区别注意：应用文法生成句子仅是形式上的。例 river swims in Peter,注：句子也是句型，但句型不一定是句子。,文法产生句型和句子的例子,【例】设有文法GZ:Z:=aZb|有推导：Z=*Z=*aZb=aaZbb=*aaabbb可见，符号串，aZb，aaZbb和aaabbb都是文法GZ的句型，而 和aaabbb才是文法GZ的句子。,30,文法产生句型和句子的例子,【例】设有文法GE:E:=E+T|E-T|T T:=T*F|T/F|F F:=(E)|i 试证明i+i*i是它的一个句子。分析：只有证明i+i*i可由文法G从开始符号E推导出，即可证明i+i

14、*i是它的一个句子。证明：E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i 即有E*i+i*i 又因i+i*i中的每个符号均为终结符号，故i+i*i是它的一个句子。,思考,设计编程语言时，是先设计语言形式，还是先设计BNF形式的文法？例如要表示形如 i+i,i+i*i的表达式建议：学习时注意积累，何种典型文法可以得到某种典型的语言形式考试考查：能够由文法写出语言，也能由语言设计出文法,为什么有穷规则集合的文法能定义无穷的语言？文法G：1）:=2）:=3）:=4）:=0 5):=1 6）:=2 7):=3 8):=4 9):=5 10):=6 11)

15、:=7 11):=8 12):=9VN=,VT=0,1,2,3,4,5,6,7,8,9=1=12=123,=递归地定义规则，即，U:=U,使得有穷个规则可能定义潜在地无穷的语言。,重要概念：短语、简单短语 已知w=xuy是文法G的句型,短语 u:Z=*xUy UVN U=+u 简单短语 u:Z=*xUy UVN U=u 理解：句型w=xuy中 可(直接)归约且(直接)归约后所得新符号串仍为句型 的子符号串u。例 句子 123 中,1、2、3都是简单短语。1、12、123、2、3都是短语。句型 12 中：简单短语有：1、2 短语有：1、1、1、2 句柄:句型中最左的简单短语。,句柄是重要概念之一

16、。归约是自底向上的语法分析关键，何时进行归约则必须依赖句柄。分析句型时，要搞清楚哪些符号串能构成短语和直接短语。,36,求短语、直接短语和句柄的例子,【例】设有文法GE:,求出句型(F+i)T*(ET)的短语、简单短语和句柄。分析：从句型的推导过程中找出其全部短语、直接短语和句柄。,37,可以看出：句型(F+i)T*(ET)包含以下短语：F，i，F+i，(F+i)，ET，(ET)，T*(ET)，(F+i)T*(ET)；简单短语有：F，i，ET；句柄为F。注意：选择符号串判断是否短语时，必须同时满足两个条件：1）可归约；2）归约后仍是句型（即可由识别符号推导出）,概括,文法G:有穷非空的重写规则

17、集合 四要素：VN，VT，P，Z句型：Z=*t,t(VNVT)+句子：Z=*t,t VT+概念：推导，归约 简单短语，短语，句柄,4.文法句子之生成的实现,实质是推导的构造。要点是推导在计算机内的存储表示。,显然每一“列”（垂直链）中各结点相应的符号组成一个句型。这易于用C语言结构类型实现。以最左推导的建立为例，程序控制流程示意图如下。,由于推导过程中，进行替换的非终结符号可能作为多个规则的左部，在尚未讨论分析技术的情况下，宜于采用交互方式由用户自己选择进行直接推导的规则。这涉及到文法规则在计算机内的存放。文法的存储表示：一种是数组表示 一种是链表表示 例 GE：E:=E+T E:=T T:=

18、T*F T:=F F:=(E)F:=i,为便于处理，以符号的序号代替符号本身：typedef struct int 左部符号序号；int 右部符号串MaxRightPartLength+1;int 右部长度；规则;规则 文法MaxRuleNum+1;,为区分非终结符与终结符，将非终结符的序号+100,文法1中的规则E:=E+T,在计算机内的存储表示:文法1：101，0，101，1，102，3 文法2中的规则E:=T，在计算机内的存储表示：文法2：101，0，102，1 TVT：T在VT中的序号 UVN：U在VN中的序号+100 注意：C语言数组元素的下标值从0开始，已把0号 元素弃之不用。,文

19、法的链式表示：,文法GE的数据结构,GE：E:=E+T E:=T T:=T*F T:=F F:=(E)F:=i,2.2.2 语言的定义,程序设计语言L是一切程序P的集合。PL L+（=VT）语言是相应文法一切句子的集合。L(GZ)=x|Z=*x,x VT+一个文法确定唯一的语言。反之？L(G)=P|=*P,PVT+语言可能是有穷的，也可能是无穷的。,重要概念：递归规则递归 规则左递归：U:=U 一般递归：U:=U 规则右递归：U:=U 文法递归 文法左递归:U=+U 一般递归：U=+U 文法右递归：U=+U递归，使有穷多个规则定义的语言可以是无穷的。,C语言中的规则递归和文法递归 规则左递归有

20、：:=规则右递归有：:=!文法右递归于：:=:=:=if()else 因此，=+也可以说，C语言文法递归于=+,注：同一种语言可设计出不同的文法；注意扩展！,L3=ai bi ci|i 1 G3S:S:=abC|aSBC CB:=CD CD:=BD BD:=BC bB:=bb bC:=bc cC:=ccL4=a2i|i 1 G4S:S:=ACaB Ca:=aaC CB:=DB CB:=E aD:=Da AD:=AC aE:=Ea AE:=,56,文法产生语言的例子,【例1】设有文法GZ:Z:=aaZbb|ab 求该文法所描述的语言。,分析：,语言：,57,文法产生语言的例子,【例2】设有文法G

21、Z:求该文法所描述的语言。分析：由括号组成的终结符号，且左右括号匹配。,【例3】设有文法GZ:求该文法所描述的语言。分析：1后面紧跟的符号必为0或为空，即该文法产生的是不包括两个相邻1的所有0、1串。语言：,概括1.程序设计语言是一切程序的集合；程序是在程序设计语言字母表上按一定规则构造的符号串；程序设计语言是其字母表正闭包的真子集。2.文法是重写规则的集合 文法四要素：VN、VT、P、Z 文法的句型：由识别符号推导所得的符号串。文法的句子：全由终结符号组成的句型。3.语言是一切句子的集合；文法确定，则语言确定，语言给定，但可为该语言构造若干文法。递归，使有穷多个规则能定义无穷的语言。,4.重

22、要概念 句型、句子 推导、归约 短语、简单短语、句柄 递归（规则递归、文法递归）,应用文法生成句子的步骤：步骤1 以识别符号为当前句型 步骤2 对当前句型进行直接推导（把其中一个非终结符号替换为以其为左部的规 则之右部符号串）步骤3 重复步骤2，直到无非终结符号可被替换。通常应以系统的有规则的方式进行替换 对最左的非终结符号进行替换（最左推导）对最右的非终结符号进行替换（最右推导）,2.3.1 Chomsky文法类和语言类1.Chomsky分类法 对文法四要素概括与抽象。定义：Chomsky文法G=（VN,VT,P,Z)VN VT P Z文法及例：GS:S:=Sc|Bc B:=Bb|Ab A:

23、=Aa|a,2.3 语言的分类,2.3.1 Chomsky文法类和语言类1.Chomsky分类法 对文法四要素概括与抽象。定义：Chomsky文法G=（VN,VT,P,Z)VN VT P Z文法及例：GS:S:=Sc|Bc B:=Bb|Ab A:=Aa|a,G1=（VN,VT,P1,S1)VN=S1,A,B VT=a,b,c P1:S1:=S1c|Bc B:=Bb|Ab A:=Aa|a L(G1)=ai bj ck|i,j,k1G2=（S2,A,a,b,c,P2,S2)P2:S2:=S2c|Ac A:=aAb|ab L(G2)=ai bi ck|i,k1,G3=(S3,B,C,D,a,b,c,

24、P3,S3)P3:S3:=abC|aS3BC CB:=CD CD:=BD BD:=BC bB:=bb bC:=bc cC:=cc L(G3)=ai bi ci|i1G4=(S4,A,B,C,D,E,a,P4,S4)P4:S4:=ACaB Ca:=aaC CB:=DB CB:=E aD:=Da AD:=AC aE:=Ea AE:=L(G4)=a2i|i 1,分类：按规则的定义形式对文法分类 0型文法（短语结构文法PSG）：u:=v u(VNVT)+,v(VNVT)*1型文法（上下文有关文法CSG）：xUy:=xuy UVN,x,y(VNVT)*,u(VNVT)+2型文法（上下文无关文法CFG）：

25、U:=xuy UVN,x,y(VNVT)*,u(VNVT)+3型文法（正则文法RG）：U:=VT 或 U:=T U,VVN,TVT,相应地有4类Chomsky语言：0型语言（短语结构语言PSL）1型语言（上下文有关语言CSL）2型语言（上下文无关语言CFL）3型语言（正则语言RL）注意：有时对2型文法，扩充有规则与句子 规则：U:=句子：Z=*,2.3.2*形式语言与自动机 Chomsky语言类和自动机的对应关系：3型语言 有穷状态自动机 FA 2型语言 下推自动机 PDA 1型语言 线性界限自动机LBA 0型语言 图灵机TM,2.3.3 形式语言的分类与程序设计语言 1.程序设计语言一般用上

26、下文无关文法定义：U:=u 2.但语言一般是上下文有关的(1):=:=goto:=goto:=:(标识符由所在上下文确定是否标号)(2)()=(标识符由后跟符号确定是函数标识符、数组变量还是变量)3.通常：词法 正则文法 语法 上下文无关文法 语义 口语,2.3.4 对上下文无关文法的进一步讨论1*.上下文无关文法的自嵌套特性 如果一个上下文无关文法G中存在具有下列特性的非终结符号U：U=*xUy其中x,yV+，则称U为自嵌套的非终结符号，包含自嵌套非终结符号的文法G称为自嵌套的上下文无关文法。若一个上下文无关文法G不是自嵌套的，则L(G)是一个正则语言。对任何一个正则语言，必定可构造不是自嵌

27、套的文法。一个严格的上下文无关语言，必不能构造非自嵌套的文法。自嵌套特性把正则语言与严格的上下文无关语言区别开来。,2.与推导有关的特性 对于CFG，若存在句型x=x1x2xn,有 x1x2xn=*y,则必存在y1,y2,yn，使得 xi=*yi(i=1,2,n),Z 且 y=y1y2yn。设x=*y,若x的首符号VT,X1 X2 Xn 则y的首符号也VT。反之，y的首符号VN,则 y1 y2 yn x的首符号也VN。,3.规则 规则：U:=Chomsky 2型文法U:=u中，uVT+,不包含规则，但有时让uVT*,例如进行文法等价变换，便引进规则。引进规则，便可能产生句子：Z=*对于所有非0

28、型的语言，包括上下文无关语言，删去或添加一个句子，不改变原来的语言类。,4*.上下文无关语言的可判定性 对于一个程序设计语言来说，重要的是能机械且高效地在有限的时间内判定一个符号串是否是语法上正确的程序，换句话说，就是判定一个符号串是否是属于该(程序设计)语言的句子。这就是可判定性问题。一般地，可判定性问题可以这样描述：设集合L是集合S的一个子集，而x是S的一个任意元素,问:是否可能机械而高效地判定x是否L的一个成员?对于上下文无关语言，这问题的答案是肯定的。,2.4 文法等价和等价变换2.4.1 文法等价的概念 文法G1与G2等价，若L(G1)=L(G2)。1.例 L1=ai bj ck|i

29、,j,k1 G1 S:S:=ABC A:=Aa|a B:=Bb|b C:=Cc|c G1S:S:=Sc|Bc B:=Bb|Ab A:=Aa|a G1与G1等价。,2.文法等价变换的必要性 文法等价变换的概念：对文法进行变换，使得变换后的文法满足某种要求，并且与原文法等价，这种变换称为文法的等价变换。文法等价变换的必要性 使文法类与语言类一致 消去二义性 使文法适用于某种分析技术 特殊需要 文法等价变换的种类：压缩文法等价变换 消去左递归文法等价变换 消除单规则文法等价变换 增广文法等价变换,2.4.2 压缩文法等价变换1.压缩了的文法 目的：使文法中任一规则都能用来生成文法的句子，使文法中无多

30、余规则。多余规则：U:=U形规则 不满足下列条件的规则:=u：条件=*U(U出现在句型中）条件 u=*t tVT+(可推导到终结符号串）概念：若文法中任一规则都满足上述条件和条件2,则称压缩了的文法。Z=*xUy=xuy=*t t VT+,即，t是句子。,76,文法压缩（化简）的基本思想,条件1）若一符号不能出现在文法的任何句型中，则该符号是无用的。条件2）若一个非终结符不能推导出终结符号串，则该非终结符是无用的。从识别符号开始或从终结符号开始。删除这些规则，不会改变文法描述的语言,2.无用规则的判别算法算法步骤如下:步骤 规则展开成非缩写形式并删除U:=U形规则;步骤 判别条件，删除不满足条

31、件的规则;步骤 判别条件，删除不满足条件的规则;步骤 重复步骤和步骤，直到无规则被删除。实现：采用加标记的算法。,采用加标记的算法。对条件1：U:=xVy中，若规则左部U加过标记，则对右部非终结符号V加标记。对条件2：U:=xVy,若规则右部全由终结符号和加过标记的非终结符号组成,则对左部非终结符号加标记。对于文法GZ：Z=Be A=AeAe B=CeAf C=Cf D=f 步骤1 展开并删除U:=U形规则成：Z=Be A=Ae A=e B=Ce B=Af C=Cf D=f,步骤2 判条件1，加标记：*Z=Be A=Ae A=e B=Ce*B=Af C=Cf D=f规则D=f 是多余的,应删除

32、。从而得到文法 GZ：Z=Be A=Ae A=e B=Ce B=Af C=Cf,步骤3 判条件2，加标记：*Z=Be A=Ae A=e*B=Ce B=Af C=Cf 规则B=Ce与C=Cf是多余的，应删除。重复判条件1与2，最终得到与文法GZ等价的压缩了的文法GZ:Z=Be A=Ae A=e B=Af,压缩文法等价变换的规范步骤：步骤 规则展开成非缩写形式并删除U:=U形规则;步骤 判别条件，删除不满足条件的规则;步骤 判别条件，删除不满足条件的规则;步骤 重复步骤和步骤，直到无规则被删除。3.*实现之考虑,2.4.3消去左递归的文法等价变换,左递归的存在将导致自顶向下语法分析失败自顶向下：即

33、从识别符号出发，使用不同规则进行推导。左递归可使分析陷入无穷循环，导致栈溢出U=Ux=Uxx=Uxxx=因此，对自顶向下分析技术，需要消除左递归。,一般情况下，U:=Ux1|Ux2|Uxm|y1|y2|yn U:=Ux1|Ux2|Uxm|y1|y2|yn U:=U(x1|x2|xm)|(y1|y2|yn)U:=(y1|y2|ym)U U:=(x1|x2|xn)U|b.用扩充表示法 U:=Ux|y U:=y x 一般情况下，U:=Ux1|Ux2|Uxn|y1|y2|ym U:=U(x1|x2|xn)|(y1|y2|ym)U:=(y1|y2|ym)x1|x2|xn,2.文法左递归的消去（间接的规则

34、左递归）基本思想:对非终结符号排序成U1、U2、Un后文法等价变换成呈下形:U1:=Ui1(或 U1:=T)i11 U2:=Ui2(或 U2:=T)i22 Uj:=Uij(或 Uj:=T)ijj Un-1:=Un(或 Un-1:=T)Un:=T TVT一般地，对于Ui:=Uj必有：ji,从而不可能产生U=+U,U-Ua文法左递归,消去文法左递归的算法步骤:步骤 把非终结符号排序成U1,U2,Un 步骤 以上列顺序执行下列程序：for(i=1;i=n;i+)for(j=1;j=i-1;j+)把形如Ui:=Ujr的规则改写成:Ui:=xj1r|xj2r|xjkr 其中Uj:=xj1|xj2|xjk

35、是对于Uj的一切规则 消除关于Ui的规则左递归;,消去文法左递归等价变换的解题规范：步骤1 识别是规则左递归还是文法左递归步骤2 进行相应的文法等价变换步骤3 给出消去了左递归的等价文法,例 设有文法GS：GS：S=SaTbcTd T=Segh 试消去其文法左递归。,GS：S=SaTbcTd T=Segh解:步骤1 排序：U1=S U2=T(n=2)步骤2 执行循环：i=1，j=1：ji1，不执行关于j的循环，消去关于U1=S的规则左递归（改写成右递归）：S=(Tbc|Td)S S=aS|i=2，j=1：有规则T=Se|gh，呈U2:=U1形，把S=(Tbc|Td)S 代入，得 T=(Tbc|

36、Td)Se|gh因此,T=T(bc|d)Se)|gh 消去关于U2=T的规则左递归如下:T=ghT T=(bc|d)SeT|,最后得到文法GS：GS：S=SaTbcTd T=Segh消去了左递归的等价文法GS：S=T(bcd)S S=aS|T=ghT T=(bc|d)SeT|,例 设有文法GA：GA:A=Ba|Cb|c B=dA|Ae|f C=Bg|Ah试消去该文法的左递归。,GA:A=Ba|Cb|c B=dA|Ae|f C=Bg|Ah解：首先判别知，该文法存在文法左递归。步骤1 排序成：U1=A，U2=B,U3=C；步骤2 执行循环：i=1,j=1:ji1，不执行关于j的循环，且关于U1=A

37、不存在规则左递归。i=2,j=1:有规则B=Ae|dA|f，呈U2:=U1形，把规则A=Ba|Cb|c代入，得 B=(Ba|Cb|c)e|dA|f或 B=BaeCbecedAf消去关于U2=B的规则左递归，所以,B=(Cbe|ce|dA|f)B B:=ae B|,i=3,j=1:有规则C:=Ah|Bg，呈U3:=U1形，把规则A:=Ba|Cb|c 代入,C:=(Ba|Cb|c)h|Bg或 C:=B(ah|g)|(Cb|c)h i=3,j=2:由规则C=B(ah|g)|(Cb|c)h,呈U3:=U2形，把规则B=(Cbe|ce|dA|f)B 代入，得 C:=(Cbe|ce|dA|f)B(ah|g

38、)|(Cb|c)h或 C:=C(beB(ah|g)|bh)|(ce|dA|f)B(ah|g)|ch消去关于U3=C的规则左递归，得到 C=(ce|dA|f)B(ah|g)|ch)C|C:=(beB(ah|g)|bh)C|,最后得到消去了左递归的等价文法 GA:A=BaCbc B=(Cbe|ce|dA|f)B B:=ae B|C=(ce|dA|f)B(ah|g)|ch)C|C:=(beB(ah|g)|bh)C|3.*实现之考虑 要点:识别文法是规则左递归还是文法左递归 文法在计算机内的存储表示,2.5 语法分析树与句型分析 2.5.1 语法分析树的概念1.语法分析树的引进 术语：结点 根结点 末

39、端结点 边 分支 分支名字结点 分支结点 Berry swims in river 分支结点符号串 子树 子树末端结点符号串 树 末端结点符号串,语法分析树,一个句型推导过程的树形表示称为语法分析树，或简称语法树。语法树的优点是：它有助于理解一个句子语法结构的层次。语法树通常表示成一棵倒立的树，根在上，树叶在下。语法树离不开句型，一棵语法树是相对于某个句型而存在，脱离句型的语法树是不存在的。,句子 Berry swins in river的推导：=Berry=Berry swins=Berry swins=Berry swins in=Berry swins in river如何为它构造语法分

40、析树？,2.从推导构造语法分析树 从推导构造语法分析树的步骤如下.步骤1 以识别符号为根结点，对应于第一个直接推导向下作分支。步骤2 从第二个直接推导左边被替换的非终结符号相应的结点向下作分支,对应于此直接推导。步骤3 类似地对应于每个直接推导,从左边被替换的非终结符号对应的结点向下作分支,相应于此直接推导。如此继续，直到推导完。,重要性质：分支的分支结点符号串是相应句型中相对于分支名字结点的简单短语。Z=*xUy=xuy U=u 子树的末端结点符号串是相应句型中相对于子树根结点的短语。Z=*xUy=+xuy U=+u利用语法分析树寻找句型中的简单短语和短语。,3.从语法分析树构造推导 这是从

41、推导构造语法分析树的逆过程。E F*i+i=i*i+i T*i+i=F*i+i=i*i+i E+T T*F+i=T*i+i=F*i+i=i*i+i T F E=E+T=T+T=T*F+T=F*F+T=i*F+T T*F i=i*i+T=i*i+F=i*i+i F i 对照：从推导构造语法分析树：i 不断添加分支的过程 从语法分析树构造推导：不断剪去分支的过程,4.二义性 概念：一个句子，若可为它构造两个不同的语法分析树，称此句子是二义性的句子。包含二义性句子的文法称二义性文法。例 GE:E:=E+E|E*E|(E)|i 存在句子i+i*i,对于它存在两个不同的语法分析树，是二义性句子。E E

42、E*E E+E E+E i i E*E i i i i 注意：二义性与多义性的区别。,对于程序设计语言来说，重要的是：描述它的文法应是无二义性的。如何知道它是无二义性的？不存在一种算法，能在有限步骤内确切判定一个文法是否是二义性的。鉴于二义性不可判定，所能做的是寻找一组充分条件，使得满足这些条件的文法必定是无二义性的。注意，这些条件只是充分条件，未必是无二义性的必要条件。,5.语法分析树的存储表示与输出 从图可见，语法分析树上任一结点的位置可由其父结点、紧邻的左兄结点与最右的子结点所确定，因此，语法分析树的数据结构可设计如下。,typedef struct 语法树结点 int 结点序号;int

43、 文法符号序号;int 父结点序号;int 左兄结点序号;int 右子结点序号；语法树结点类型;语法树结点类型 语法分析树MaxNodeNum;,当输出语法分析树时，对照上述数据结构，按下列表列形式输出：结点序号 文法符号 父结点 左兄结点 右子结点 1 E 0 0 4 2 E 1 0 5 3+1 2 0 4 T 1 3 10 5 T 2 0 6 6 F 5 0 7 7 i 6 0 0 8 T 4 0 11 9*4 8 0 10 F 4 9 13 11 F 8 0 12 12 i 11 0 0 13 i 10 0 0,2.5.2 句型分析 1.句型分析的概念 句型分析：识别一个符号串是否是某文

44、法的句型。对于程序设计语言，句子是程序，句型分析的问题就是识别一个输入符号串是否是语法上正确无误的程序。分析程序：实现句型分析的程序。分析算法：分析程序编写的依据。分析技术：分析技术实现思想决定分析算法。,2.分析技术 自顶向下:实现思想：以识别符号作为根结点，试图向下构造语法分析树,使得末端结点符号串正是输入符号串。要解决的基本问题:当按U展开(推导)时，U:=x1|x2|xk 确定按哪个xi(1ik)展开:Z=*vUw=v?w,自底向上：实现思想：以输入符号串作为末端结点符号串,试图向上构造语法分析树，使得根结点正是识别符号。要解决的基本问题：确定要归约的短语，并确定归约成哪个非终结符号。

45、Z=*v？w=vuw(U1:=u U2:=u Uk:=u),例 GS：S=AB A=aAbab B=cBdcd识别输入符号串aabbcd是否是其句子。1.自顶向下2.自底向上,自顶向下,自顶向下：不断进行直接推导的过程。,自底向上：不断进行直接归约的过程。,3.规范推导与规范归约 最左推导、最右推导、最左归约、最右归约 不难发现：最左推导=最右归约 最右推导=最左归约而且最左（右）归约中被直接归约的最左（右）简单短语，其右（左）边总是只包含终结符号。引进规范推导、规范分析,如果某直接推导xUy=xuy中，y不包含非终结符号，则称该直接推导为规范的，记作 xUy xuy 如果某推导v=+w中，每

46、个直接推导都是规范的，则称该推导为规范的，记作v+w。v v1 v2 vn-1 w 由规范推导得到的句型称为规范句型。相应地，有规范归约。规范推导与规范归约，统称规范分析。规范推导=最右推导，最左归约=规范归约,本章概要文法与语言的定义 文法四要素 重要概念：字母表闭包与正闭包，句子、句型，推导与归约，短语、简单短语与句柄等。Chomsky文法与语言及其分类 按规则的定义形式而分类（4类），与编译程序的联系（CFG、RG）。文法等价变换 压缩文法与消去左递归的文法等价变换。句型分析 语法分析技术分类:自顶向下与自底向上；重要工具：语法分析树（众多用途）；二义性句子与二义性文法；相关概念：规范句型，规范分析。,