编译原理第二章(2-1)

1、北京交通大学 于双元1第二章第二章 上下文无关文法和语言上下文无关文法和语言2.1 文法和语言的表示文法和语言的表示2.2 文法和语言的定义文法和语言的定义2.3 句型的分析句型的分析2.4 文法的化简与改造文法的化简与改造2.5 文法和语言的文法和语言的ChomskyChomsky分类分类北京交通大学 于双元2 提要提要 所谓形式化方法，简单地说，就是用一整套所谓形式化方法，简单地说，就是用一整套带有严格规定的符号体系来描述问题的理论带有严格规定的符号体系来描述问题的理论和方法，用形式化方法描述的语言（语法和和方法，用形式化方法描述的语言（语法和语义）便是形式语言。语义）便是形式语言。 本章

2、将从形式语言的角度系统地介绍什么本章将从形式语言的角度系统地介绍什么是程序设计语言的文法，文法和语言的关系是程序设计语言的文法，文法和语言的关系等问题，本章是本课程的理论基础。等问题，本章是本课程的理论基础。北京交通大学 于双元321 文法和语言的表示语言的定义可采用下列三种方法语言的定义可采用下列三种方法 1.1.枚举法枚举法把该语言的所有句子列出放把该语言的所有句子列出放 在一集合内。（有限个句子时）在一集合内。（有限个句子时） 2.2.有限条规则有限条规则描述语言的全部句子。描述语言的全部句子。 （有限或无限个句子），即文法表示（有限或无限个句子），即文法表示 3.3.装置装置检验和识别

3、句子。检验和识别句子。 （有限或无限个句子）即自动机（有限或无限个句子）即自动机北京交通大学 于双元4 22 文法和语言的定义2 22 21 1 基本概念和术语基本概念和术语2 22 22 2 文法和语言的形式定义文法和语言的形式定义2 22 23 3 递归规则与递归文法递归规则与递归文法 北京交通大学 于双元5 22 文法和语言的定义1 1、字母表：、字母表：元素的非空有穷集合，元素的非空有穷集合，元素称符号。元素称符号。例例:=0,1:=0,12 2、符号串：、符号串：字母表中的符号所组成的任何有穷序列字母表中的符号所组成的任何有穷序列. .特别：特别： 空符号串空符号串 （不包含任何符号

4、）（不包含任何符号）=a,b=a,b221、 基本概念和术语 北京交通大学 于双元63 3 、字母表、字母表上的符号串的上的符号串的递归定义递归定义。 （1 1）是是上的符号串上的符号串 （2 2）若）若x x是是上的符号串，且上的符号串，且a, a, 则则xaxa或或axax是是 上的符号串上的符号串 特别：特别： x = x = x x = x = x （3 3）若）若y y是是上的符号串，上的符号串， 当且仅当当且仅当y y可由（可由（1 1）和（）和（2 2）产生。）产生。北京交通大学 于双元7例：例： =b，c ,求求上的上的 所有符号串所有符号串根据根据1 是是 上的符号串上的符号

5、串上的上的 所有符号串所有符号串 ，b , c, bb，bc，cb，cc, bbb，bbc ，bcb ，bcc ，cbb ，bcb ，ccb ， ccc根据根据2 b和和c 即即b，c 是是上的符号串上的符号串bb，bc，cb，cc 是是上的符号串上的符号串bbb，bbc ，bcb ，bcc ，cbb ，bcb ，ccb ， ccc是是上的符号串上的符号串.北京交通大学 于双元85 5 、符号串的前缀、后缀和子串：、符号串的前缀、后缀和子串： 前缀前缀：设：设x x是一符号串，从是一符号串，从x x的尾部删去若干个（包括的尾部删去若干个（包括 0 0个）符号之后所剩余下的部分称为个）符号之后所

6、剩余下的部分称为x x的的前缀前缀 ; ; 若若x x的前缀不是的前缀不是x x本身，则称为本身，则称为x x的的真前缀真前缀。 后缀后缀：设：设x x是一符号串，从是一符号串，从x x的头部删去若干个（包括的头部删去若干个（包括 0 0个）符号之后所剩余下的部分称为个）符号之后所剩余下的部分称为x x的的后缀后缀 ; ; 若若x x的后缀不是的后缀不是x x本身，则称为本身，则称为x x的的真后缀真后缀。 子串子串：从一个符号串中删去它的一个前缀和一个后缀：从一个符号串中删去它的一个前缀和一个后缀 之后所剩下的部分称为此符号串的之后所剩下的部分称为此符号串的子串子串。 若若x x的子串不是的

7、子串不是x x本身，则称为本身，则称为x x的的真子串真子串北京交通大学 于双元9例例 设设x=abcx=abcx= x= a a b b c c x x的前缀的前缀: :abcabcababa( ,a,ab( ,a,ab为真前缀）为真前缀）x x的后缀的后缀: :abcabcc cbcbc（ , c, c，bc bc 为真后缀）为真后缀）x x的子串的子串: :abcabcababbcbca ab bc c( ,a,ab,b,c,bc( ,a,ab,b,c,bc为真子串为真子串) )用法用法： z=xz=x. .（x x为为z z的前缀）的前缀） z=z=x x （x x为为z z的后缀）的

8、后缀） 对某些感兴趣对某些感兴趣 z=z=x x. .（x x 为为z z的子串）的子串） 北京交通大学 于双元105 5、符号串的、符号串的长度长度：符号串所含符号的个数：符号串所含符号的个数6 6 、符号串的连接和方幂、符号串的连接和方幂 连接连接：设有符号串：设有符号串x,yx,y，把，把y y的符号写在的符号写在x x的符号的符号 之后所得的符号串，叫做之后所得的符号串，叫做x x与与y y的连接，的连接， 记记xyxy 方幂方幂：设有符号串：设有符号串x x，则，则x x的的n n次自身连接称为次自身连接称为x x的的 n n次方幂，记为次方幂，记为x xn n 特别特别:x:x0

9、0 = = 北京交通大学 于双元11 7 7 、符号串集合、符号串集合A A与与B B的和与积：的和与积： 和和： A+B=w|w AA+B=w|w A或或w B w B 积积： AB=xy|x AAB=xy|x A且且y By B 8 8 、符号串集合的方幂：、符号串集合的方幂： 设有符号串集合设有符号串集合A A 则定义则定义A A0 0 = = A A1 1=A=A A A2 2=AA=AA A An n=AA=AAA A n n个个 北京交通大学 于双元129 9 、 符号串符号串( (符号）集合的正闭包符号）集合的正闭包 设设A A为符号集合，则定义为符号集合，则定义A A的正闭包的

10、正闭包A A+ +为：为： A A+ +=A=A1 1AA2 2 A A3 3 A An n 例例: :设设=b , c=b , c 则则 A A=b , c bb,bc,cb,cc =b , c bb,bc,cb,cc = = b , c, bb，bc，cb，cc, bbb，bbc ，bcb ，bcc ，cbb ，bcb ，ccb ， ccc 例：例： =b=b，c ,c ,求求上的所有符号串上的所有符号串 ，b , c, bbb , c, bb，bcbc，cbcb，cc, bbbcc, bbb，bbc bbc ，bcb bcb ，bcc bcc ，cbb cbb ，bcb bcb ，ccb

11、 ccb ， ccccccA A是由是由A A上的元素构成的符号串上的元素构成的符号串( (除除)的集合的集合. .北京交通大学 于双元1310 10 、 符号串（符号）集合的闭包符号串（符号）集合的闭包A A* *设设A A为符号集合，则定义为符号集合，则定义A A的闭包的闭包A A* *为：为：A A* *=A=A0 0 A A+ += = A A+ +则则A A* *=b,cbb,bc,cb,cc =b,cbb,bc,cb,cc = = ，b , c, bb，bc，cb，cc, bbb，bbc ，bcb ， bcc ，cbb ，bcb ，ccb ， ccc A A* *由由A A上的元素

12、构成的所有符号串的集合上的元素构成的所有符号串的集合. .设字母表设字母表V V且且x Vx V* * ? ?例：例： =b=b，c ,c ,求求上的所有符号串上的所有符号串 ，b , c, bbb , c, bb，bcbc，cbcb，cc, bbbcc, bbb，bbc bbc ，bcb bcb ，bcc bcc ，cbb cbb ，bcb bcb ，ccb ccb ， cccccc北京交通大学 于双元14例：C语言的基本字符集定义 字符是组成语言的最基本的元素。字符是组成语言的最基本的元素。C语言字符集由语言字符集由字母、数字、空白符、标点和特殊字符组成。字母、数字、空白符、标点和特殊字符

13、组成。n字母字母小写字母小写字母az共共26个个,大写字母大写字母AZ共共26个个(大小写敏感）。大小写敏感）。n数字数字09共共10个。个。n空白符空白符空格符、制表符和换行符等统称为空白符空格符、制表符和换行符等统称为空白符n标点和特殊字符标点和特殊字符主要有主要有, ,”,:, ?,%,&, - , +等等问题问题：C语言基本字符集与字母表的关联性？语言基本字符集与字母表的关联性？ C语言中的源程序是语言中的什么概念？语言中的源程序是语言中的什么概念？北京交通大学 于双元15222、文法和语言的形式定义1 1 、文法的形式定义、文法的形式定义(1)(1) 规则（产生式）规则（产生

14、式）一有序对（一有序对（U U，x x） 记为记为U:=xU:=x或或UxUx规则的左部：规则的左部：U U是符号（是符号（有的文法也可为符号串）有的文法也可为符号串）规则的右部：规则的右部： X X是有穷符号串是有穷符号串表示表示: :U U定义为定义为x x例：例：S abcS abc if ( if () if (if () else else 北京交通大学 于双元16(2) (2) 文法文法GZ:GZ:规则的非空有穷集合规则的非空有穷集合. .Z Z：开始符号开始符号（识别符号），至少在一条规则（识别符号），至少在一条规则 的左部出现。的左部出现。(3) (3) 字汇表字汇表V V:

15、: 规则左右部中所有符号组成的集合规则左右部中所有符号组成的集合非终结符号：非终结符号：规则左部出现的符号规则左部出现的符号组成非终结符号集合组成非终结符号集合V Vn n终结符号：终结符号：规则中不属于规则中不属于V Vn n的符号的符号组成终结符号集合组成终结符号集合V Vt t非终结符号以非终结符号以括起括起, ,但当是大写字母是时常省略但当是大写字母是时常省略V=VV=Vn n U VU Vt t北京交通大学 于双元17(4) (4) 文法的四元组表示文法的四元组表示 G=(VG=(Vn n, V, Vt t , P, Z ) , P, Z ) 其中其中 V Vn n ：非终结符号集：

16、非终结符号集 V Vt t ：终结符号集：终结符号集 P P：规则的集合：规则的集合 Z Z：文法的开始符号：文法的开始符号北京交通大学 于双元18规则中有相同的左部时规则中有相同的左部时：V x V y V z 写成：写成：V x|y|V x|y|z |z （| |表达表达或或） 称为巴科斯范式（称为巴科斯范式（BNFBNF范式）描述。范式）描述。元符号元符号： (:=(:=），），| | ，元语言元语言: : 元符号处理的语言元符号处理的语言由元符号组成的巴科斯范式是用以描述算法语由元符号组成的巴科斯范式是用以描述算法语言的元语言。言的元语言。 北京交通大学 于双元19 例例:G=(V:G

17、=(Vn n,V,Vt t,P,S),P,S) 其中其中: : V Vn n=S,A,B=S,A,B V Vt t=a,b=a,b S: S:文法的开始符号文法的开始符号 P: S aB | bAP: S aB | bA A a | aS | bAA A a | aS | bAA B b | bS | aBB B b | bS | aBB一般规定：第一条规则的左部为开始符号，一般规定：第一条规则的左部为开始符号， 那么文法有规则的集合就完全确定那么文法有规则的集合就完全确定了。了。文法文法BNFBNF表示为表示为GS: GS: S aB | bA S aB | bA A a | aS | bA

18、A A a | aS | bAA B b | bS | aBB B b | bS | aBB北京交通大学 于双元202 2、推导的形式定义、推导的形式定义 (1) (1) 直接推导直接推导：如果如果UuUu是是G G中的一条规则，中的一条规则， x x，yVyV* *， 则将规则则将规则UuUu用于符号串用于符号串r=xUyr=xUy上上 得到符号串得到符号串w =xuy w =xuy 记为：记为： xUy = xuy (r=w)xUy = xuy (r=w) 称符号串称符号串w w是符号串是符号串r r的直接推导的直接推导, ,或符号串或符号串 r r直接产生了符号串直接产生了符号串w,w,

19、也称也称w w直接归约到直接归约到r.r.北京交通大学 于双元21例例: :上述文法上述文法GSGS可进行的直接推导可进行的直接推导 S=aB S=aB( (规则规则S aB )S aB )文法文法BNFBNF表示为表示为GS: GS: S aB | bA S aB | bA A a | aS | bAA A a | aS | bAA B b | bS | aBB B b | bS | aBBU =u U =u ( (规则规则U u , x,yU u , x,y均为均为 ) ) abS=abbA abS=abbA( (规则规则S bA)S bA)xU =xu xU =xu ( (规则规则U u

20、 , xU u , x为为ab,yab,y为为 ) ) aB=aaBB aB=aaBB ( (规则规则B aBB)B aBB) xU =xu xU =xu ( (规则规则U u , xU u , x为为aaB,yaaB,y为为 ) )北京交通大学 于双元22例例: :上述文法上述文法GSGS可进行的系列直接推导可进行的系列直接推导推导过程推导过程 使用规则使用规则 S=aB S=aB S aB S aB =abS =abS B bSB bS =abbA =abbA S bA S bA =abbbAA =abbbAA A bAAA bAA =abbbaA =abbbaA A aA a =abbb

21、aa =abbbaa A aA a只要符号串中存在非终结符号只要符号串中存在非终结符号, ,推导就能继续推导就能继续, ,直至符号直至符号 串全由终结符号组成串全由终结符号组成, ,这也是为什么称终结符和非终结这也是为什么称终结符和非终结 符的原因符的原因文法文法BNFBNF表示为表示为GS: GS: S aB | bA S aB | bA A a | aS | bAA A a | aS | bAA B b | bS | aBB B b | bS | aBB北京交通大学 于双元23 (2)(2)推导推导( (长度为长度为n):n): 设设u u0 0,u,u1 1, ,u un n(n0)(n

22、0)均均V V* *, ,且有且有 r=ur=u0 0=u=u1 1=u =u n-1n-1=u=un n=w=w 记为记为r =r =+ +ww 则称以上序列为长度则称以上序列为长度n n的推导的推导, ,也称也称r r产生产生w(ww(w归约为归约为r)r)特例特例: :如果如果r= r= + + w( w(一步或一步以上）或一步或一步以上）或r=w(0r=w(0步步) ) 记为记为 r=r=* *ww北京交通大学 于双元243 3、语言的形式定义、语言的形式定义(1)(1)句型句型: :设有文法设有文法GZ,GZ,如果有如果有Z=Z=* *x , x Vx , x V* *, , 则称则

23、称x x是文法是文法G G的一个句型的一个句型. .p凡是由开始符号（识别符号）推导出来的字凡是由开始符号（识别符号）推导出来的字汇表汇表V V上的终结和非终结符号组成的符号串上的终结和非终结符号组成的符号串叫做句型叫做句型. . (2)(2)句子句子: :如有如有Z=Z=+ +xx（或（或Z=Z=* *xx）且）且xVxVt t* *, , 则称则称x x是文法是文法G G的一个句子的一个句子. .p由由Z Z推导的终结符号组成的符号串为句子。推导的终结符号组成的符号串为句子。北京交通大学 于双元25(3)(3)语言语言L(GZ):L(GZ):文法文法GZGZ产生的所有句子产生的所有句子的集

24、合的集合, , 称文法称文法GZGZ所定义的语言所定义的语言 L(GZ)=x|xVL(GZ)=x|xVt t* *且且Z=Z=+ +xx例例:G:G | | | a|b|a|b|z|A|z|A|Z|Z 0|1|2|0|1|2|9|9问题问题: :符号串符号串“a8ya8y”是不是文法的句子是不是文法的句子? ?北京交通大学 于双元26推导过程推导过程1 1 y y y y 8 8y y 8y8ya a8y8y推导过程推导过程2 2 = a a a a8 8 a8a8y y例例:G:G | | | a|b|a|b|z|A|z|A|Z|Z 0|1|2|0|1|2|9|9结论：a8y是文法的合法句子

25、什么样的推导过程什么样的推导过程是可编程的？是可编程的？推导过程推导过程如何选规则？如何选规则？北京交通大学 于双元27例例:G=(Vn,Vt,P,E)其中其中:Vn=E,T,F Vt=+,*,(,),i E:文法的开始符号文法的开始符号 P: EE+T|T TT*F|F F(E)|iGE:EE+T|T TT*F|F F(E)|iE代表代表 表达式表达式T代表代表 项项F代表代表 因子因子i代表代表 标识符（变量）标识符（变量）i*(i+i)是不是文法合法的句子？是不是文法合法的句子？文法是如何体现文法是如何体现四则运算法则的？四则运算法则的？北京交通大学 于双元28例例:G1A:ABb:G1

26、A:ABb Ba L(G1)=ab Ba L(G1)=ab G2A:Aab L(G2)=ab G2A:Aab L(G2)=ab G1G2G1G2但但L(G1)=L(G2)L(G1)=L(G2)称称G1G1和和G2G2为等价文法为等价文法 ( (不同文法不同文法, ,相同语言相同语言).).等价文法的概念可以进行文法的等价变换，等价文法的概念可以进行文法的等价变换，以期得到需要的文法形式。以期得到需要的文法形式。给定文法后给定文法后, ,可以确定它的语言可以确定它的语言, ,但由语言写但由语言写出的文法是比较难的出的文法是比较难的, ,这里形式语言理论可以这里形式语言理论可以证明。证明。北京交通

27、大学 于双元291给定一文法给定一文法, ,就能从结构上唯一确定其语言就能从结构上唯一确定其语言. . 即即 G G 唯一确定唯一确定 L(G)L(G)2 2给定一语言给定一语言, ,能确定其文法能确定其文法, ,但这种文法不是但这种文法不是 唯一的。唯一的。 即即L L 确定确定 G1,G1,或或G2G23 3设设G=(VG=(Vn n,V,Vt t,P,S),P,S)为一文法为一文法, , 并设并设UxVy,UxVy,是是P P中一产生式中一产生式, , 且且V V1 1|2 2|3 3|n n 是是P P中中V V的全部产生式的全部产生式 又设又设G1=(VG1=(Vn n,V,Vt t

28、,P,P1 1,S),S)是其中是其中P P1 1从从P P中删去中删去UxVy,UxVy, 加入加入UxUx1 1y, Uxy, Ux2 2y,y,， Uxny,Uxny, 则则L(GL(G1 1)=L(G)=L(G)北京交通大学 于双元30G3S:S A | | S-A A a | | b | | cG4S:S A | | A-S A a | | b | | c 符号串符号串a-b-c是是G3S 、G4S合法句子，但语义不同。合法句子，但语义不同。G3解释为解释为（a-b）-c G4解释为解释为 a-（b-c）为什么会有为什么会有不同的语义？不同的语义？北京交通大学 于双元31回答和理解几

29、个问题： 字母表与字母表与C语言的字符集合语言的字符集合 字母表上的符号串与字母表上的符号串与C语言的源程序语言的源程序 语言的句子与语言的句子与C语言的源程序语言的源程序p什么是什么是C语言正确的源程序？语言正确的源程序？p编译程序是对什么进行翻译？编译程序是对什么进行翻译？北京交通大学 于双元322 22 23 3 递归规则与递归文法递归规则与递归文法 -用有穷的规则刻划无穷的语言用有穷的规则刻划无穷的语言 1 1、递归规则、递归规则 形如形如UxUy UVn, x,yVUxUy UVn, x,yV* * 左右具有相同的非终结符号的规则左右具有相同的非终结符号的规则 特别特别: :UUy

30、(x=)UUy (x=)左递归规则左递归规则 UxU (y=)UxU (y=)右递归规则右递归规则 UxUy (x,y)UxUy (x,y)自嵌入递归规则自嵌入递归规则递归规则是对其左部的非终结符号进行递归定义递归规则是对其左部的非终结符号进行递归定义 北京交通大学 于双元332 2. .文法的递归性文法的递归性 1)1)直接递归性直接递归性: :文法中至少包含一条递归规则文法中至少包含一条递归规则 2)2)间接递归性间接递归性: :文法的任一非终结符号经一步文法的任一非终结符号经一步 以上推导产生的递归性。以上推导产生的递归性。 3)3)文法的递归性原则文法的递归性原则: :文法具有直接递归

31、性或文法具有直接递归性或 间接递归性间接递归性, ,否则否则, ,文法无递归性文法无递归性。 例例1 1：GZGZ：ZaZbZaZb ab ab 具有直接递归性具有直接递归性 例例2 2：GZGZ：U VxU Vx V Uy V Uy z z 具有间接递归性具有间接递归性 原因：原因：U=Vx=UyxU=Vx=Uyx GE:EE+T|T TT*F|F F(E)|i北京交通大学 于双元34 23 句型的分析2 23 31 1 规范推导和规范规约规范推导和规范规约2 23 32 2 短语、简单短语和句柄短语、简单短语和句柄2 23 33 3 语法树语法树2 23 34 4 子树与短语、简单短语子树

32、与短语、简单短语2 23 35 5 文法的二义性文法的二义性北京交通大学 于双元352.3 句型的分析2.3.1 2.3.1 规范推导和归约规范推导和归约1 1、最左最左( (右右) )推导推导: :在任一步推导在任一步推导V=wV=w中，都是中，都是 对符号串对符号串V V的最左的最左( (右）右）非终结符号进行替换非终结符号进行替换, , 称最左称最左（右）（右）推导。推导。2 2、规范推导规范推导: :即最右推导即最右推导3 3、规范句型规范句型：由规范推导所得的句型：由规范推导所得的句型. .4 4、规范归约规范归约：规范推导的逆过程，称规范归约或：规范推导的逆过程，称规范归约或 最左

33、归约。最左归约。 北京交通大学 于双元36例例:G:G | | | a|b|a|b|z|A|z|A|Z|Z 0|1|2|0|1|2|9|9问题问题: :给出句子给出句子a4ya4y的规范推导和规范归约的规范推导和规范归约. . 给出句子给出句子a4ya4y的最左推导的最左推导. .北京交通大学 于双元37请注意请注意: :规范推导和规范归约互为逆过程规范推导和规范归约互为逆过程. .规范推导规范推导 y y y y 4 4y y 4y4ya a4y4y问题问题: :如何正确选择规则如何正确选择规则? ?规范归约规范归约a4ya4y 4y4y 4 4y y y y y y 问题问题: : 如何准

34、确选择可归如何准确选择可归 约串约串? ?为什么要研究为什么要研究规范推导和规范规约？规范推导和规范规约？北京交通大学 于双元382.3.2 2.3.2 短语、简单短语和句柄短语、简单短语和句柄 -语言句型中的几个概念语言句型中的几个概念1 1、短语短语: :文法文法GZ, =xuyGZ, =xuy是一句型是一句型,x,yV,x,yV* * 如有如有 Z=Z=* *xUy,xUy,且且U=U=+ +u, UVu, UVn n, u V, u V+ + 称称u u是一个相对于非终结符号是一个相对于非终结符号U U句型句型的的短语短语. .2 2、简单短语简单短语: :文法文法GZ, =xuyGZ

35、, =xuy是一句型是一句型, , 如有如有 Z=Z=* *xUy,xUy,且且U=u, UVU=u, UVn n, u V, u V+ + 称称u u是一个相对于非终结符号是一个相对于非终结符号U U句型句型的的简单短语简单短语. .3 3、句柄句柄: :句型最左边的简单短语为该句型的句型最左边的简单短语为该句型的句柄句柄. .北京交通大学 于双元39 =x =xu uy y是一句型是一句型结论结论：u u是一个相对于非终结符号是一个相对于非终结符号U U句型句型的的短语短语u? U?UVn, u V+ ,x,y V* Z=*xUyU=+uZ=*xUy=+ xuy短语短语: :文法文法GZ,

36、 =xuyGZ, =xuy是一句型是一句型, , 如有如有 Z=Z=* *xUy,xUy,且且U=U=+ +u, UVu, UVn n, u V, u V+ + 称称u u是一个相对于非终结符号是一个相对于非终结符号U U句型句型的短语的短语. .北京交通大学 于双元40 =x =xu uy y是一句型是一句型结论结论：u u是一个相对于非终结符号是一个相对于非终结符号U U句型句型的的简单短语简单短语u? U?UVn, u V+ ,x,y V* Z=*xUyU=uZ=*xUy= xuy简单短语简单短语: :文法文法GZ, =xuyGZ, =xuy是一句型是一句型, , 如有如有 Z=Z=*

37、*xUy,xUy,且且U=u, UVU=u, UVn n, u V, u V+ + 称称u u是一个相对于非终结符号是一个相对于非终结符号U U句型句型的简单短语的简单短语. .句柄句柄: :句型最左边的简单短语为该句型的句柄句型最左边的简单短语为该句型的句柄. .u是某产生式的右部北京交通大学 于双元41说明说明: :短语或简单短语必须是针对某一句型来短语或简单短语必须是针对某一句型来说的，说的， 并且是该句型的一个子串并且是该句型的一个子串. .短语或简单短语必须是相对某一非终结短语或简单短语必须是相对某一非终结符号的符号的. .两个条件缺一不可两个条件缺一不可. .一句型可以有几个短语和

38、简单短语一句型可以有几个短语和简单短语. .一句型只有一个句柄一句型只有一个句柄( (无二义性的文法无二义性的文法) )。最左归约归约的是当前句型的句柄最左归约归约的是当前句型的句柄 北京交通大学 于双元42例例GSGS：SABSABAAa|bBAAa|bBBa|SbBa|Sb问题问题: :给出句型给出句型baSbbaSb的短语、简单短语和句柄的短语、简单短语和句柄. .(1) S=AB(1) S=AB短语短语: :文法文法GZ, =xuyGZ, =xuy是一句型是一句型, , 如有如有 Z=Z=* *xUy,xUy,且且U=U=+ +u, UVn, u Vu, UVn, u V+ + 称称u

39、 u是一个相对于非终结符号是一个相对于非终结符号U U句型句型的短语的短语. .=bBB=bBB =baB=baB且且B=B=SbSbUu=ba=baSbSbuSbSb是相对于是相对于B B句型句型baSbbaSb的短语且为的短语且为简单短语简单短语(2) S=AB(2) S=AB =ASb=ASb =bBSb=bBSb且且B=aB=a=baSb=baSba a是相对于是相对于B B句型句型baSbbaSb的短语且为的短语且为简单短语简单短语. .(3) S=AB(3) S=AB= =+ +baSbbaSb且且A=A=+ +baba=ASb=ASbbaba是相对是相对A A句型句型baSbba

40、Sb的的短语短语. .句柄句柄为为a a. .如何快速准确找到当前句型的短语、简单短语、句柄如何快速准确找到当前句型的短语、简单短语、句柄？北京交通大学 于双元432.3.3 2.3.3 语法树语法树1 1、语法树、语法树: :一个句型或句子推导过程的图示法表示，一个句型或句子推导过程的图示法表示， 形成一棵语法树形成一棵语法树. .例例GSGS：SABSABAAa|bBAAa|bBBa|SbBa|Sb句型句型baSbbaSb最左推导最左推导语法树语法树S=ABSAB=bBBbB=baBa=baSbSb北京交通大学 于双元44语法树语法树BSAbBaSb2 2、语法树与子树、语法树与子树 根根

41、: :开始符号开始符号子树子树: :某一非终结符号某一非终结符号 ( (子树的根子树的根) )及其下面的分支及其下面的分支叶叶: :树的末端结点树的末端结点根子树子树的根语法树的全部末端结点（自左向右）形成当前句型语法树的全部末端结点（自左向右）形成当前句型叶北京交通大学 于双元452.3.4 2.3.4 子树与短语、句柄子树与短语、句柄 -通过树来寻找短语、简单短语、句柄通过树来寻找短语、简单短语、句柄1 1、短语短语: :子树的末端结点形成的符号串子树的末端结点形成的符号串. . 这个短语相对的句型这个短语相对的句型: :整个树的末端结点整个树的末端结点. . 非终结符号非终结符号: :子

42、树的根子树的根 2 2、简单子树简单子树: :只有一层分支的子树只有一层分支的子树3 3、简单短语简单短语: :简单子树的末端结点形成的符号串简单子树的末端结点形成的符号串. . 北京交通大学 于双元46上例上例GS: GS: 句型句型baSbbaSb的语法树的语法树共有三棵子树共有三棵子树, ,三个短语三个短语:ba ,a, Sb:ba ,a, Sb简单短语简单短语: a, Sb: a, Sb句柄句柄: a: a这样的结论与短语定义这样的结论与短语定义完全符合完全符合, ,为什么为什么? ?BSAbBaSb北京交通大学 于双元474 4、归约归约 语法树由下向上生长语法树由下向上生长, ,

43、通过规则替换到达开始符号的过程。通过规则替换到达开始符号的过程。无二义性文法最左归约归约的是当前句型的句柄无二义性文法最左归约归约的是当前句型的句柄. .这个过程也非常重要，因为源程序都是符号串形这个过程也非常重要，因为源程序都是符号串形式的，这就需要把它归约为开始符号（程序）才式的，这就需要把它归约为开始符号（程序）才算正确。算正确。最左归约关键是最左归约关键是找当前句型的句柄找当前句型的句柄, ,这个问题这个问题, ,到到语法分析时再着重讲解语法分析时再着重讲解. . 北京交通大学 于双元48句型句型baSbbaSb的归约过程的归约过程. .归约过程归约过程baSbBABSbaSbbBSb

44、ASbABABSAB=ASbSb=bBSbbB=baSba产生相同的语法树产生相同的语法树是否：对同一个句子不同的是否：对同一个句子不同的推导都产生相同的语法树？推导都产生相同的语法树？北京交通大学 于双元50几个结论几个结论: :1 1、对每个语法树、对每个语法树, ,至少存在一个推导过程。至少存在一个推导过程。2 2、对于每个推导、对于每个推导, ,都有一个相应的语法树，但不都有一个相应的语法树，但不 同的推导可能有相同的语法树。同的推导可能有相同的语法树。3 3、树的末端结点形成所要推导的句型。、树的末端结点形成所要推导的句型。4 4、但某个句型也可能对应两棵不同的语法树，、但某个句型也

45、可能对应两棵不同的语法树，这就是文法的这就是文法的二义性二义性问题问题. .北京交通大学 于双元512.3.5 2.3.5 文法的二义性文法的二义性1 1、文法二义性的定义、文法二义性的定义 如果文法如果文法G G的某一个句子存在两棵或两的某一个句子存在两棵或两棵以上不同的语法树，棵以上不同的语法树，则称句子是二义则称句子是二义性的性的. . 如果一文法含有二义性的句子，如果一文法含有二义性的句子，则称该则称该文法是二义性的文法是二义性的，否则该文法是无二义，否则该文法是无二义性的性的. .北京交通大学 于双元52句子句子i+ii+i* *i i 同是最左推导同是最左推导, ,对应两棵不同的语法树对应两棵不同的语法树 例例GE:EE+E|EGE:EE+E|E* *E|(E)|iE|(E)|i最左推导最左推导1:1:E=E+EE=E+E=i+E=i+E=i+E=i+E* *E E=i+i=i+i* *E E=i+i=i+i* *i iEE+EiE*Eii北京交通大学 于双元53句子句子i+ii+i* *i i 同是最左推导同是最左推导, ,对应两棵不同的语法树对应两棵不同的语法树 例