编译原理形式语言基础

1、（优选）编译原理第章形式语言基础第一页，共一百五十二页。1一、语言的定义 任何一种语言都是在某个特定字母表上定义的、按照一定的规则构成的字符串的集合。第二页，共一百五十二页。2二、形式语言提出 形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义，即用数学方法（主要是代数方法）对语言进行形式化描述。 1956年N.Chomsky(乔姆斯基）在研究自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础，成为计算机科学理论一个重要分支，即形式语言与自动机。第三页，共一百五十二页。3三、语言描述方法枚举法文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。自动机识别

2、法：用自动机对语言中的句子进行识别第四页，共一百五十二页。4四、与语言有关的几个概念元语言：可用来描述其它语言的一种语言语法：是在字母表上构造句子的一组规则语义：是按照语法规则所构成结构的含义语用：是表示语言符号与使用者关系第五页，共一百五十二页。52.2 符号和符号串 一、字母表 二、符号串 三、符号串集合第六页，共一百五十二页。6一、字母表 有限个元素的非空集合称字母表，也称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。 习惯上用V、或其它大写字母表示。例如V=a,b,c，V=, | V|表示字母表中符号的个数。 对于不同程序设计语言有不同字母表。例如，机器语言字母表=0,1，

3、PASCAL语言的字母表由字母、数字以及一些特殊符号，如+，-，*，/，(，)，=，等组成。 注意：在一个语言中不能出现字母表以外的符号。第七页，共一百五十二页。7二、符号串 1、定义 符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号行或字) 例如： 设V=a,b,c,则符号串有 a, b, c, aa, ab, ac, ba, abc 又如： 设V=0,1,则符号串有 0，1，00，01，10，11，000 由上例可以看出，符号串与符号组成顺序有关，如符号串ab不同于ba， 符号串01不同于10，今后我们常用t,u,v,x,y,z等小写字母表示符号串。第八页，共一百五十二页。82、

4、空符号串 不包含任何符号的符号串称为空符号串，记为。 3、符号串长度 符号串中所含符号个数称为该符号串的长度，设符号串为x，则用|x|来表示x的长度。例如：x=abc，则|x|=3,显然,|=0。第九页，共一百五十二页。94、关于符号串的几种运算 （1）符号串的联结 设有符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即 x=x1x2x3xm, y=y1y2y3yn 则 x y = x1x2x3xmy1y2y3yn 显然x = x， x= x 第十页，共一百五十二页。10（2）符号串的方幂 若x是符号串 则x0=， x1=x，x2=xx，x3=xxx，xn=xxx(n个） 如

5、x=abc 则x0= , x1 = abc, x2= abcabc X3= abcabcabc第十一页，共一百五十二页。11三、符号串集合 举例：字母表V=a,b，问用V中的符号，可以组成哪些符号串？ 解：,a,b,aa,ab,ba,bb,aaa,bbb,1、定义：若集合A中的一切元素都是字母表V上的符号串，则称A为字母表V上的符号串集合第十二页，共一百五十二页。12V*定义：字母表V上各种长度符号串构成串集合，记为V*，不包括空行的集合记为V+ 即 V*=x|x是V上符号串且包括空符号串 V+=x|x是V上符号串且不包括空符号串 V+=V*- 如：V=a,b，则 V*=,a,b,aa,ab,

6、ba,bb,aaa,bbb, V+=a,b,aa,ab,ba,bb,aaa,bbb,第十三页，共一百五十二页。132、关于串集合的运算（1）串集合乘积设A和B为两个符号串集合，并包含于V*，则A和B的乘积定义为：AB= xy | xA 且 yB 由此定义，乘积AB是满足xA且yB的所有符号串xy所组成的集合。如：V=0，1 V* =,0,1,00,01,10,11,000,001，010，011，100,101如果 A=0，101 B=10，11，110则 AB=010，011，0110，10110，10111，101110符号表示空集 第十四页，共一百五十二页。14（2）符号串集合的方幂设符

7、号串集合A 则A的方幂运算定义为：A0=, A1= A, A2= AA, A3= AAA, An = AAAA (n个）如：设A=a,b，则A0=,A1=a,bA2=a,ba,b=aa,ab,ba,bbA3=aaa,aab,aba,abb,baa,bab,bba,bbb第十五页，共一百五十二页。15(3)符号串集合的闭包和正闭包 设A为符号串集合，则A的正闭包定义为 A+=A1A2An 符号串集合A的闭包定义为 A*=A0A+=A+ 如 A = a,b 则A+=a,baa,ab,ba,bb=a,b,aa,ab,ba,bb,aaa,bbb, A*=, a, b, aa, ab, ba, bb,

8、aaa, bbb, 我们可以证明： A+= AA* = A*A AA* =A（A0A1A2 An ） = A1A2 An = A+第十六页，共一百五十二页。16作业： P.38：习题2、3第十七页，共一百五十二页。172.3 文法与语言 一、巴科斯范式BNF(Backus Normal Form) 二、语法树 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性 第十八页，共一百五十二页。18一、巴科斯范式BNF例子：The man has a dog.(这人有一条狗）我们以“=”符号(或“”符号)表

9、示”定义为”，以“|”符号表示“或”，以“”符号表示语法实体(语法单位)，这些符号是元语言符号，第十九页，共一百五十二页。19=the | a=man | book | dog= =has= 我们把这种描述语法规则方法称巴科斯范式，也称为巴科斯-瑙尔范式(Backus Normal Form)，简称BNF。那么上面叙述的语法规则可写为：第二十页，共一百五十二页。20例如, 在高级语言中大家所熟知的这种语法成分,它用巴科斯范式描述为:=|=A|B|C|D|Z|a|b|z=0|1|2|9 这样便刻画出了是以字母开始的一串字母和数字任意组合这种特点。第二十一页，共一百五十二页。21如果定义的巴科斯范

10、式改为：句子=主语=We | He | I谓语=ran | ate | sat则下面9个句子都是正确的：We ran He ran I ran We ate He ate I ateWe sat He sat I sat 可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。第二十二页，共一百五十二页。22二、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 第二十三页，共一百五十二页。23（句子the man has a book的推导过程及对应的语法树）第二

11、十四页，共一百五十二页。24（句子the man has a book的推导过程及对应的语法树） =第二十五页，共一百五十二页。25（句子the man has a book的推导过程及对应的语法树） =第二十六页，共一百五十二页。26（句子the man has a book的推导过程及对应的语法树）the =the | a第二十七页，共一百五十二页。27（句子the man has a book的推导过程及对应的语法树）manthe =the =man 第二十八页，共一百五十二页。28（句子the man has a book的推导过程及对应的语法树）manthe =the =man =第

12、二十九页，共一百五十二页。29（句子the man has a book的推导过程及对应的语法树）manhasthe =the =has第三十页，共一百五十二页。30（句子the man has a book的推导过程及对应的语法树）manhasthe =the =第三十一页，共一百五十二页。31（句子the man has a book的推导过程及对应的语法树）manhasathe =the =第三十二页，共一百五十二页。32（句子the man has a book的推导过程及对应的语法树）manhasabookthe =the =第三十三页，共一百五十二页。33（句子the man ha

13、s a book的推导过程及对应的语法树）manhasabookthe第三十四页，共一百五十二页。34其中：称为语法树根 带和不带的都称为语法树的结点 一个结点以及向下射出部分称为子树 没有向下射出部分的结点称为末端结点第三十五页，共一百五十二页。35三、产生式（规则） 1. 定义 产生式(规则)就是一个符号与另一个符号串的有序偶(U,x),通常记为 Ux或U=x 其中：U是符号,x是有限非空符号串。 U称为规则的左部, x称为规则的右部 如果 Ux1， Ux2， Ux3， Uxn 可以写成Ux1|x2|xn ,并称xi是U的一个候选式。第三十六页，共一百五十二页。362. 字汇表(符号表)

14、（1）定义 用于规则左部和右部中所有符号形成集合为字汇表，记为V。 第三十七页，共一百五十二页。37（2）分类 1）非终结符号 出现在规则左部,且能派生出符号或符号串的那些符号称为非终结符,也称语法实体或语法单位,它们的全体构成一个非终结符的集合,记为VN 2）终结符 规则中不属于VN的那些符号,称为终结符,它们的全体组成终结符的集合,记为VT 。终结符一般出现在规则的右部。 显然,V= VN VT, VN VT =第三十八页，共一百五十二页。38如：在PASCAL中，对标识符的定义规则为：=|=a|b|z|A|B|Z=0|1|9 由此得： VN =, VT=a,b,z,A,B,Z,0,1,9

15、第三十九页，共一百五十二页。39例如：有产生式: S=0S1 S=01 则 VN =S VT=0,1 V=S,0,1第四十页，共一百五十二页。40四、文法为研究方便，下面给出文法的形式定义定义：文法是规则的有穷集合,形式定义为四元组形式为 G=(VN,VT,P,Z)其中：VN是非终结符集合,VT是终结符集合, P代表产生式集, ZVN是文法G开始符号,也称识别符号,它至少要在一 条产生式左部出现。 文法G通常记为GZ 。第四十一页，共一百五十二页。41对于前面英语句子的例子中用7条文法规则来描述英语句子,其文法可表示为 G=(VN,VT,P,Z)其中:VN=， ，VT=the, a, man,

16、 book, dog P是前述7条规则Z=第四十二页，共一百五十二页。42又例如：标识符文法可定义如下: GZ=(VN,VT,P,Z) VN=, VT=a,b,z,A,B,Z,0,1,9 Z= P由下列规则组成: =| =a|b|z|A|B|Z =0|1|9第四十三页，共一百五十二页。43五、推导和归约 定义1 设G为一个文法，U=u是G中一个规则，x和y是V*上符号串，使得 v=xUy 与 w=xuy 则称符号串v直接推导出符号串w，或称w直接归约到v，并把w叫做v直接派生式，记作 v w 若x=y=，则v=xUy =U， w=xuy=u 可见v w即U u 说明一个规则就是一个直接推导 例

17、如直接推导到，而 直接归约到。 第四十四页，共一百五十二页。44例如: G =(VN,VT,P,S) VN =S, VT =0,1 P: S =0S1 S =01 令 v=xSy ,w=x01y, 因 S =01 (U=u) 即 v w xSy x01y 若 x=y= 则 S 01(一个规则就是一个直接推导) 同样 S =0S1 v=00S11， w=000S111 U u 即 v w 00S11 000S111第四十五页，共一百五十二页。45又如：标识符文法定义如下: GZ=(VN,VT,P,Z) VN=, VT=a,b,z,A,B,Z,0,1,9 P由下列规则组成: =| =a|b|z|A

18、|B|Z =0|1|9 Z=则有： a 第四十六页，共一百五十二页。46定义2 设u0,u1,u2,un均为V*上符号串,若w是v经过一系列直接推导得到的,即 v= u0 u1 u2 un-1 un =w (n0) 则称v推导到w,或称w归约到v,记作 v +w 称这个直接推导序列为长度为n的推导。如果v +w或者v=w(表示0步推导),则记作 v *w 称v广义推导到w或称w广义归约到v。 显然,直接推导 的长度为1,推导 +的长度1,而广义推导 *的长度0 例如在前面的例子中,因 S =0S1 S =01 0S1 00S11 000S111 00001111 所以 0S1 +0000111

19、1 (n=3)第四十七页，共一百五十二页。47例 设有文法G:(1)= (2)=(3)= (4)=0 (5)=1(6)=2 (7)=3 (8)=4 (9)=5 (10)=6 (11)=7 (12)=8 (13)=9整数23的推导过程: 2 23因此,+23,其推导长度为5。显而易见,在推导时,任意地选取规则(4)到(13),就可以推导得到任意整数。第四十八页，共一百五十二页。48六、句型和句子定义：设GZ是一文法,若符号串x是由识别符Z推导而得,即Z *x xV* 则称符号串x为该文法G的一个句型。如果一个句型x仅由终结符组成,即Z*x xVT* 则称句型x为该文法一个句子。 例如： 在书中的

20、例2.16中, 2,23等都是文法G的句型,其中仅23是句子。 可见：句子一定是句型，而句型未必是句子。一个正确的源程序是句子。第四十九页，共一百五十二页。49七、语言定义：设GZ为一文法,由该文法所产生的一切句子的集合称为由该文法所定义的语言,记为L(G)(或记为L(G),即 L(G)=x|Z *x且xVT*有时我们称这样定义的语言为形式语言，以区别于自然语言。上述公式包含两层意思：语言是句子集合，是VT*一个子集合，即VT中行集合子集。句子必须由该语言文法识别符推导出。第五十页，共一百五十二页。50例如：GS=(VN,VT,P,S) VN=S VT=0,1 P:S=01,S=0S1 S:识

21、别符很容易推出：L（G）=0n1n|n1第五十一页，共一百五十二页。51又如：写一个文法，使其语言为偶整数集合。首先分析以下偶整数 （1）偶整数最后一个数字应该是偶数字0，2，4，6，8 （2）偶整数前面符号可以是+，-或不带符号由此得其文法应由下列规则组成：= | |=0|2|4|6|8=1|3|5|7|9|=|=+|-所以文法可表示为：G=(VN,VT,P,)其中：VN =， ， ， VT =0，1，2，3，4，5，6，7，8，9，+，-第五十二页，共一百五十二页。52对于通常的程序设计语言其文法为: G程序=(VN,VT,P,)其中 VN=, VT=0,1,9,a,z,-,(,), P=

22、, =, =, L(G)=w| *w且wVT* 由此可知,每一个w就是一个源程序，所谓PASCAL语言也就是所有PASCAL程序的集合。第五十三页，共一百五十二页。53作业：P.38 习题6、7第五十四页，共一百五十二页。54八、递归文法 构成一个语言的句子集合可以是有穷的，也可以是无穷的，例如文法G所描述的语言L(G)是有穷的。但文法G所描述的语言L(G)是无穷的，它包含无穷多个句子。 第五十五页，共一百五十二页。55例如：文法G()包含的下列规则如下：句子=主语=We | He | I谓语=ran | ate | sat所描述的语言为：We ran He ran I ran We ate

23、He ate I ateWe sat He sat I sat第五十六页，共一百五十二页。56例 如文法G的规则如下：(1)= (2)=(3)= (4)=0 (5)=1(6)=2 (7)=3 (8)=4 (9)=5 (10)=6 (11)=7 (12)=8 (13)=9所描述的语言包括无穷多个句子。第五十七页，共一百五十二页。57不难发现，两个文法其根本差别在于文法G有形如=的规则。 在这个规则中左部和右部皆出现非终结符。这种借助于自己来定义自己的规则，即在规则左部和右部具有相同的非终结符规则称为递归规则。 第五十八页，共一百五十二页。58八、递归文法 1. 定义 对于一个文法,若有一个规则U

24、=U,则称直接递归,若有规则U=U,则称直接左递归,若有规则U=U,则称直接右递归。若有推导式U+U,则称间接递归,若有推导式U+U,则称间接左递归,若有推导式U+U,则称间接右递归。非终结符U称递归非终结符。如果一个文法中至少含有一个递归非终结符,则将此文法称为递归文法。第五十九页，共一百五十二页。59例如：规则 S =0S1 是直接递归 规则 A=Aa 是直接左递归 规则 B=aBB 是直接右递归 第六十页，共一百五十二页。60例如：设有文法G的规则P为 S=Qc|c Q=Rb|b R=Sa|a在这些条规则中,无直接递归规则,但有如下推导: Q Rb Sab Qcab所以 Q +Qcab因

25、此是间接左递归。文法G为递归文法显然，直接递归是间接递归一种特殊情况。 第六十一页，共一百五十二页。61八、递归文法 2.说明 如果一个语言是无穷的，则描述该语言的文法必定是递归的。一般说，程序设计语言是无穷的，因此描述它们的文法必定是递归的。应当指出，从语法定义的角度来看，递归定义使文法的形式比较简练，给无限的语言有限的表示提供了一种可用的方法。然而在后面我们将会看到，文法的左递归性将会给某些语法分析方法的实现带来很大的麻烦。 第六十二页，共一百五十二页。62九、短语和简单短语 1.短语和简单短语 2.句柄(柄短语) 3.再谈语法树第六十三页，共一百五十二页。631. 短语和简单短语定义：设

26、GZ是一文法，w=xuy是其中一句型，若有 Z * xUy,UVN 且 U + u,uV+ 则称u是一个相对于非终结符U、句型w的短语。 若 Z * xUy 且U u 则称u是一个相对于非终结符U、句型w的简单短语。 第六十四页，共一百五十二页。64例 设有文法GS=(S,A,B,a,b,P,S),其中P为 S=AB A=Aa|bB B=a|Sb找出句型baSb的全部短语，简单短语.第六十五页，共一百五十二页。65根据句型推导过程有 S AB bBB baB baSb由上可见，下式成立： S *baB 且 B Sb所以子串Sb是相对于非终结符B，句型baSb的简单短语。同样有 S AB ASb

27、 bBSb baSb即 S * bBSb 且 B a子串a是相对于B，句型baSb的简单短语。还有 S * ASb 且 A + ba即子串ba是相对于非终结符A，句型baSb的短语。对于句型baSb，再没有其它能产生新的短语推导了，所以句型baSb有短语ba简单短语a和Sb第六十六页，共一百五十二页。662、句柄(柄短语) 定义 一个句型最左边的简单短语称为该句型 的句柄(或柄短语)，而且句柄最左边的符号 称句柄的头，句柄最右边的符号称句柄的尾。 如上例句型baSb简单短语为a和Sb ，由于a是 最左简单短语，所以a又是句柄。 第六十七页，共一百五十二页。67例如：设文法GS S=A A=B|

28、A+B B=C|B*C C=|(A)现在我们看w=C+B*C句型 SAA+BB+BC+BC+B*C S* C+B BB*C B*C是相对于B和句型C+B*C的简单短语同样 SAA+BB+BB+B*CC+B*C S* B+B*C BC C是相对于B，句型C+B*C的简单短语。由于C在左边，所以C是句柄，柄头和柄尾都是C第六十八页，共一百五十二页。683. 再谈语法树 前面我们曾利用语法树直观地描述句子语法结构关系，现在我们仍然借助于语法树进行句型和句子的推导，同时，利用它寻找短语和简单短语也是十分直观和方便的。（1）语法树形式定义 设有文法G=（VN，VT，P，Z），满足下列条件的树即为一个语法

29、树 a. 树中每一个结点都有标记，且该标记是VNVT中某一符号 b. 树根标记是识别符号 c. 若有一个结点至少有一个后继结点，则该结点标记必为非终结符 d. 若一个标记为U的结点，它有标记依次为X1，X2, X3，Xn的直接后继结点，则U=X1X2Xn必定是G的一条规则。第六十九页，共一百五十二页。69SABbBSba我们以书中的例2.22的文法GS为例，句型baSb的推导,设有文法GS=(S,A,B,a,b,P,S),其中P为 S=AB A=Aa|bB B=a|SbS AB bBB baB baSb画出语法树如下图所示 第七十页，共一百五十二页。70语法树中的几个术语： 结点：每个符号(终

30、结符或非终结符)对应于一个结点，以符号名为结点名称； 边：两个结点间的连线称为边； 根结点：由文法识别符号标记，如S； 分支：从某结点向下射出的边连同边上的结点称为分支，分支的深度为1。分支的名字是射出该分支结点的名字，分支的各个结点称为分支结点； 子树：语法树的某结点连同从它向下射出的部分称为该语法树的子树，该结点称为子树根结点； 末端结点/叶结点。第七十一页，共一百五十二页。71（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB, 规则S=AB)。SAB第七十二页，共一百五十二页。72（2）语法树构造过程句型baSb的语法

31、树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB), (规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB), (规则A=bB)。SAB第七十三页，共一百五十二页。73（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB), (规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB), (规则A=bB)。SABbB第七十四页，共一百五十二页。74（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支

32、,表示第一个直接推导(SAB), (规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB), (规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB), (规则B=a)。SABbB第七十五页，共一百五十二页。75（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB), (规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB), (规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB), (规则B

33、=a)。SABbBa第七十六页，共一百五十二页。76（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB), (规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB), (规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB), (规则B=a)。(4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb), (规则B=Sb)。SABbBa第七十七页，共一百五十二页。77（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S

34、开始,向下画一分支,表示第一个直接推导(SAB), (规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB), (规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB), (规则B=a)。(4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb), (规则B=Sb)。SABbBSba第七十八页，共一百五十二页。78（2）语法树构造过程句型baSb的语法树构造过程如下：(1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB), (规则S=AB)。(2)从分支结点A出发,向下画一分支,表示第二个直

35、接推导(ABbBB), (规则A=bB)。(3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB), (规则B=a)。(4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb), (规则B=Sb)。SABbBSba这时末端结点自左至右排列起来就是句型baSb。这棵语法树形象地表示了句型baSb上述推导过程。第七十九页，共一百五十二页。79结论：对于每一个语法树（或者子树）至少对应一个推导（可能是直接推导。可能是n步推导）对于每个推导必存在有一个语法树，画语法树过程中，每个分支对应于一个直接推导 。不同推导可能有相同的语法树。 如： S AB bBB b

36、aB baSb S AB ASb bBSb baSb 同一句型的两个不同的推导对应的语法树确是相同的。树的末端结点标记从左到右连接起来就是要推导的句型或句子第八十页，共一百五十二页。80作业P.38：习题8；P.39：习题11(1)、(2)第八十一页，共一百五十二页。81（3）语法树的作用 1）利用语法树可以构造文法的句型；（前面我们已经讲了句型baSb的语法树构造过程） 2）根据语法树可以确定短语、简单短语和句柄；树末端结点的符号串是相对于子树根的短语，分支结点的符号串是相对于分支名字的简单短语，最左简单子树(只有父子两代)的末端结点的符号串是句柄。从右图语法树可直观看出：ba是句型baSb

37、，相对于A的短语，Sb是句型baSb相对于B的简单短语，a是句型baSb相对于B简单短语，也是句柄。 3）当给定文法G后，我们可借助于推导语法树的逆过程把句型推导构造出来 （见下页举例）SABbBSba第八十二页，共一百五十二页。82对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为 bBSb baSbSABbBSba第八十三页，共一百五十二页。83对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为

38、bBSb baSbSABbBSb第八十四页，共一百五十二页。84对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为 bBSb baSb此时该语法树最左末端分支相应规则为A=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为 ASbbBSbbaSbSABSbbB第八十五页，共一百五十二页。85对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为 bBSb baSb此时该语

39、法树最左末端分支相应规则为A=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为 ASbbBSbbaSbSABSb第八十六页，共一百五十二页。86对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为 bBSb baSb此时该语法树最左末端分支相应规则为A=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为 ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbba

40、SbSABSb第八十七页，共一百五十二页。87对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构造了一个直接推导为 bBSb baSb此时该语法树最左末端分支相应规则为A=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为 ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbbaSbSAB第八十八页，共一百五十二页。88对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，

41、则得句型bBSb的语法树，也就是重新构造了一个直接推导为 bBSb baSb此时该语法树最左末端分支相应规则为A=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为 ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbbaSb最后剪去分支AB(将AB归约为S)，得到树根S，建立了句型baSb推导为SABASbbBSbbaSbSAB第八十九页，共一百五十二页。89对于右图baSb语法树，最左末端分支是文法G中一条规则B=a，若剪去此分支(将a归约为B)，则得句型bBSb的语法树，也就是重新构

42、造了一个直接推导为 bBSb baSb此时该语法树最左末端分支相应规则为A=bB，再剪去此分支(即将bB归约为A)，又得到句型ASb的语法树，于是又构造了推导为 ASbbBSbbaSb继续下去，再剪去最左末端分支(将Sb归约为B)，则得句型AB的语法树，又建立了推导为ABASbbBSbbaSb最后剪去分支AB(将AB归约为S)，得到树根S，建立了句型baSb推导为SABASbbBSbbaSbS第九十页，共一百五十二页。90结论： 从语法树构造推导也就是不断地重复构造最后直接推导和剪去相应分支直到无分支可剪过程。对于每个语法树至少存在一个推导。上例我们选用了最左归约，即每次剪去最左末端分支，实际

43、上每次归约是句柄。如果改变剪去相应分支顺序便将得到不同推导。第九十一页，共一百五十二页。91十、最左推导和最右推导 对于一给定的文法来说，从其开始符号到某一句型，或从某一句型到另一句型间的推导序列可能不唯一。为了使句型或句子能按照一确定的推导序列来产生，通常我们仅考虑最左推导或最右推导。第九十二页，共一百五十二页。92定义1：在任何一步推导vw中，都是对符号串v的最左(右)的非终结符进行替换，则称最左(右)推导。 例如：GS S=AB A=Aa|Bb B=a|S SABbBBbaB - 最左推导SABASbAABbAAabAbBab -最右推导SABASbbBSbbaSb - 非左非右推导第九

44、十三页，共一百五十二页。93定义2：最右推导叫规范推导，即在规范推导过程中，每步直接推导xUyxuy中，符号串y只含有终结符。如果推导v+w中每一步直接推导是规范的，则称推导v+w为规范推导。第九十四页，共一百五十二页。94相关概念：规范句型：由规范推导所得的句型称为规范句型。规范归约：我们把最左推导的逆过程称最右归约 最右推导的逆过程称最左归约 最左归约也称为规范归约 第九十五页，共一百五十二页。95应当指出，对于文法中的每一句子都必定有最左和最右推导，但对于一句型来说则不尽然。例如，对于文法GE E=E+T|T T=T*F|F F=(E)|i中句型T*i+T，仅有唯一的推导E E+TT+T

45、T*F+TT*i+T显然，推导E+ T*i+T既非最左推导亦非最右推导。 第九十六页，共一百五十二页。96十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明第九十七页，共一百五十二页。971. 定义 如果一个文法中某个句型对应两棵不同的语法树，则称这个文法是二义性的。也就是说，若一个文法中的某句型对应两个不同的最左推导或最右推导，则这个文法是二义性的。 第九十八页，共一百五十二页。98例如：文法GE E=E+E|E*E|(E)|i符号串i+i*i是L(G)中一个句子,有两个不同的最右推导 EE+EE+E*EE+E*iE+i*ii+i*i (1) EE*EE*iE+E*iE+i*ii+

46、i*i (2)对应两棵不同的语法树推导序列(1)和(2)分别对应两棵不同的语法树, 所以文法GE是二义性的。若将+，*看成算术运算符，则出现对表达式i+i*i 是先做+还是先做*的不确定问题。EE+EiEEii*EE*EiEEii+第九十九页，共一百五十二页。99对于不少高级语言中，例如PASCAL语言，在描述条件语句(IF语句)时，使用文法GC，其规则P为 C=if B then C C=if B then C else C C=S B= B1 | B2 S= S1 | S2其中C是开始符号，B代表布尔表达式，S代表语句，显然，句子 if B1 then if B2 then S1 else

47、 S2存在两种不同最右推导。第一百页，共一百五十二页。100 C if B then C if B1 then if B2 then C else C if B1then if B2 then S1 else S2 CifBCthenifBCthenelseCSSB1B2S1S2第一百零一页，共一百五十二页。101 C if B then C else C if B1 then C else S2 if B1 then if B2 then C else S2 if B1 then if B2 then S1 else S2 CifBCthenelseCifBCthenSSB1S2S1B2第一

48、百零二页，共一百五十二页。1022. 文法二义性消除 由于二义性文法的存在，使得在语法分析时带来了麻烦，为此，们可以具体采用两种途径来解决文法二义性问题。 （1）在语义上加些限制，或者说加一些语法非形式规定 。 例如对于上例中GE文法，我们可以通过规定运算符之间的优先级来避免文法的二义性。又例如对于条件语句文法GC，我们可以规定else永远与最靠近它前面一个尚未匹配then配对，这样就避免文法二义性 。（2）对原二义性文法加上一定条件，将其改造成一个等价的无二义性文法。第一百零三页，共一百五十二页。103例如对于上述GE文法可以构造出一个无二义性文法GE。即E=T|E+T T=F|T*F F=

49、(E)|iEE+TTFiTFFii*第一百零四页，共一百五十二页。1043.几点说明（1）业已证明，文法的二义性是不可判定的。（2）文法的二义性和语言的二义性是两个不同的概念。 产生该语言的文法都是二义性文法，称该语言为二义性语言，也称先天二义性。 至少有一个非二义文法产生该语言称此语言为非二义性语言。 对于由二义性文法描述的语言，有时可以找到等价的无二义性文法描述它，如上例文法GE和GE，因此，我们只说文法二义性，而不说语言的二义性 。第一百零五页，共一百五十二页。105作业P.39：习题15P.41：习题22第一百零六页，共一百五十二页。106 2.4 语法分析初步若已有文法G，如果给定一

50、个符号串w，如何来确定该符号串是否是文法的句子呢? 第一百零七页，共一百五十二页。107一、自顶向下语法分析 1.分析基本思想 2.分析方法二、自底向上语法分析 1.分析基本思想 2.分析方法第一百零八页，共一百五十二页。108一、自顶向下语法分析（导出法） 1.分析基本思想 自顶向下分析就是从文法的开始符号出发，利用其中产生式，逐步推导出要分析的符号串。换言之，对于任何给定的输入串，试图用一切可能的办法，从文法开始符号出发，自上而下、从左到右地为输入串建立语法树。这种分析过程本质上是一个试探过程，是反复使用不同规则谋求匹配输入串的过程。 第一百零九页，共一百五十二页。1092. 分析方法例如

51、： 设有文法G=(VN，VT,P,S),其中 VN=S,A VT=a,b,c,d P: S=cAd A=ab|a试分析符号串x=cad是否是文法G的句子.根据推导ScAdcad容易判断出x=cad是该文法的句子。若用画语法树的方法我们同样可以判断出cad是文法的句子。SAdca第一百一十页，共一百五十二页。110（1）为了自上而下为符号串x建立语法树，首先将文法的开始符号S作为树的根结点，并设输入串指针i指向其第一个符号c，然后用S为左部的产生式来扩展这棵树.若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|aSAdcScAdcadi第一百一十一页，共一百五

52、十二页。111（2） 此时该树最左边末结点c与x的第一个符号c相匹配，于是调整指针i使其指向输入串下一符号a。我们再试图让树的中间端末结点A去匹配a，显然，由于A是非终结符，它不可能直接与终结符a匹配，我们只得在文法中选择以A为左部的产生式，这里以A为左部的产生式有两个，我们试着用第一个选择来匹配输入串 ,并扩展语法树。若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|aSAdcScAd cabdcadiab第一百一十二页，共一百五十二页。112（3）此时子树A最左端末结点a与i所指的符号a匹配。于是再调整i使其指向下一输入符号d，并试图用A的最右端末结点b

53、与之匹配。 但它们不匹配，因此，子树A的匹配失败，这意味着选用A的第一个候选式对此时的情况不适合，不能构造出输入串x的语法树，在这种情况下，我们应该回头看看(回溯)是否还有其它的候选式可供利用.若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|aSAdcScAd cabdcadiabERROR!第一百一十三页，共一百五十二页。113（4） 我们应把A的第一个候选式所扩展的子树剪掉，还应把指针i恢复到进入A时所指的输入符号a，再选用A第二个候选式来构造语法树 .若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|aSAdcSc

54、Adcadi第一百一十四页，共一百五十二页。114（5） 此时子树A的唯一端末结点a与i所指的输入符号a匹配，因此A匹配成功，调整指针i，使其指向下一个输入符号d。若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|aSAdcScAd cadcadia第一百一十五页，共一百五十二页。115（6） 最后考虑S的第三个端末结点d，它与i所指的最后一个输入符号匹配，因此完成了构造输入串x的语法树的任务，从而证明了x是所给文法推导出一个句子。若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|aSAdcScAd cadcadiaSUC

55、CESS!第一百一十六页，共一百五十二页。116下面我们将上述分析过程总结一下：（1）自根开始建树 试图生成一个和所给的符号串相一致的终结符号串 （2）选择不同的规则反复试探 在建树过程中，反复选择不同的规则，每一步试图将语法树最左的叶子与所给的符号串进行匹配 （3）匹配失败退回出错点 当匹配失败时，必须回到出错点，然后再选择其他规则进行试探 这种方法称为回溯采用自顶向下分析时，不仅可能遇到回溯问题，而且还可能由于文法中有左递归规则而陷入无限循环。我们将在第四章中要介绍这两方面问题及其解决办法。 第一百一十七页，共一百五十二页。117二、自底向上语法分析 1.分析基本思想 自底向上分析是从所给

56、的符号串w开始，在其中寻找与文法规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串w归约到文法识别符号，如归约成功，则符号串w是文法的句子。 第一百一十八页，共一百五十二页。118二、自底向上语法分析 2.分析方法例2.24 设有文法G=(VN,VT,P,S),其中 VN=A,B,S VT=a,b,c,d,e P: S=aAcBe A=Ab|b B=d 试分析w=abbcde是否为此文法的句子。 第一百一十九页，共一百五十二页。119归约过程描述: 先设立一个符号栈，即将输入串中符号逐个移进栈，当栈顶符号串形成一个句柄时，就进行一次归约，把栈

57、顶句柄那个符号串用相应规则左部的非终结符号来代替，接着再检查在栈顶是否形成新的句柄，若出现新的句柄，那么再进行归约；若没有形成新句柄，则再从输入符号串中移进新符号，如此继续到整个输入符号串处理完毕。 最终，如栈底为开始符号，则输入符号串是该文法的句子，报告成功，否则，是不合法的符号串，报告错误。第一百二十页，共一百五十二页。120为了具体实现方便，我们统一以符号“#”作为待分析符号串左右分界符，作为初始状态，先将符号串的左分界符压入符号栈，作为栈底符号。对符号串abbcde分析过程如下所示。步骤 符号栈 输入符号串 动作 # abbcde# 左界符进栈 #a bbcde# a进栈 #ab bc

58、de# b进栈 #aA bcde# 用Ab归约 # aAb cde# b进栈 #aA cde# 用AAb归约 #aAc de# c进栈 #aAcd e# d进栈 #aAcB e# 用Bd归约 #aAcBe # e进栈 #S # 用SAcBe归约 # S # 接受 P: S=aAcBe A=Ab|b B=d第一百二十一页，共一百五十二页。121归约过程描述: 先设立一个符号栈，即将输入串中符号逐个移进栈，当栈顶符号串形成一个句柄时，就进行一次归约，把栈顶句柄那个符号串用相应规则左部的非终结符号来代替，接着再检查在栈顶是否形成新的句柄，若出现新的句柄，那么再进行归约；若没有形成新句柄，则再从输入符

59、号串中移进新符号，如此继续到整个输入符号串处理完毕。 最终，如栈底为开始符号，则输入符号串是该文法的句子，报告成功，否则，是不合法的符号串，报告错误。第一百二十二页，共一百五十二页。1222.5 文法和语言分类一、文法分类二、文法和自动机三、压缩过文法第一百二十三页，共一百五十二页。123如前所述，文法G形式定义为G=(VN,VT,P,Z)其规则P呈如下形式:U=w其中,UVN,wV*但仅有这种文法,还不足以描述许多语言,例如语言L(G)=anbncn|n1便不能完全用上述形式规则来描述,因此还得定义其它类型的文法。根据对P中规则施加不同限制,Chomsky将文法和语言分为四类。一、文法分类第

60、一百二十四页，共一百五十二页。124一、文法分类 1.0型文法 2.1型文法 3.2型文法 4.3型文法第一百二十五页，共一百五十二页。1251.0型文法若在文法G中，P中规则具有如下形式：=其中V+，且至少含一个非终结符，*,则文法G称为0型文法或称短语结构文法，简记为PSG(Phrase Structure Grammar)。由0型文法所描述和定义的语言称为0型语言,记PSL,即L0 第一百二十六页，共一百五十二页。126例2.25 设文法G=(VN,VT,P,S),其中 VN=S,A,B,C,D,E VT=a P: S=ACaB, Ca=aaC CB=DB, CB=E aD=Da AD=