第2章前后文无关文法和语言(2)

1、编译原理第2章 前后文无关文法和语言计算机与软件学院 陆克中12.1 文法及语言的表示2n程序设计语言的定义l汉语符合汉语语法的句子的全体l英语符合英语语法的句子的全体l程序设计语言符合该语言语法的程序的全体l如何表示或定义一种语言？枚举法：当一个语言仅含有限个句子时，可把该语言中的全部句子一一列举出来生成法(文法)：制定有限条规则，用来产生所要描述的语言之中的全部句子识别法(自动机)：建立一种装置，此装置以某一字母表上的所有符号串作为输入，并检验或识别这些符号串，当一个符号串是此字母表上某给定语言中的句子时，就接受它，反之，则拒绝接受2.2.1 基本概念和术语3n字母表l由若干元素所组成的有

2、限非空集合l元素称为符号，字母表也称为符号集l通常，在一个字母表中，可用阿拉伯数字、大写及小写英文字母、各种算术运算符、常用的标点符号以及使用上认为方便的其他符号来表示它的元素=0, 1, =a b, c, a, b, c, +, .2.2.1 基本概念和术语4n符号串l用字母表中的符号所组成的任何有限序列0, 1, 00, 01, 10,11, 000等都是字母表=01上的符号串a, b, c, aa, ab, ac, ba, bb, bc, ca, cc, cb, aaa等都是=a b c上的符号串l一个字母表上全部符号串所组成的集合显然为一无限集l在符号串中，符号是有顺序的，顺序不同，

3、代表不同的符号串abbal空符号串: 不包含任何符号的符号串，记为l符号串长度: 符号串中所含符号的个数|abc|=3, |=0l约定: 常用a, b, c, 及S, T, U, , X, Y, Z等表示符号，用t, u, , x, y, z等给符号串命名，用A, B, C等给符号串集合命名x=abc, y=11, A=a, b, c, B=00, 112.2.1 基本概念和术语5n符号串的前缀、后缀及子串lx的前缀: 从x的尾部删去若干个(包括0个)符号之后所余下的部分, a, ab, abc都是x=abc的前缀lx的后缀: 从x的头部删去若干个(包括0个)符号之后所余下的部分, c, bc

4、, abc都是x=abc的后缀lx的真前缀(真后缀): x的前缀(后缀), 且不是x本身lx的子串: 从x中删去它的一个前缀和一个后缀之后所余下的部分, a, b, c, d, ab, bc, cd, abc, bcd及abcd都是x=abcd的子串x的任何前缀和后缀都是x的子串，但其子串不一定是x的前缀或后缀和x本身既是x的前缀和后缀，也是它的子串l例: x=a+b*(c+d)的前缀、后缀和子串有哪些？2.2.1 基本概念和术语6n2.2.1 基本概念和术语7n2.2.1 基本概念和术语8n2.2.1 基本概念和术语9n例题: 定义标识符是以小写字母打头的、由小写字母或数字构成的任意非空序列

5、，设A=a, b, z, B=0, 1, 9，将所有标识符的集合表示为A和B的某种运算形式lA(A+B)*2.2.2 文法和语言的形式定义10n从“产生语言”的角度出发，给出文法和语言的形式定义l例: 描述某些具有简单结构的英语句子的语法规则：(1) 句子 主语短语动词短语(2) 主语短语the名词(3) 动词短语动词宾语短语(4) 宾语短语冠词名词(5) 名词monkey(6) 名词banana(7) 动词ate(8) 动词has(9) 冠词the(10)冠词a2.2.2 文法和语言的形式定义11l句子the monkey ate a banana的推导序列：从语言最大的一个语法结构句子出发

6、，反复用语法规则中右边的符号串去替换它的左部符号推导步序所用的规则所得的符号串1(1)句子主语短语动词短语2(3) 主语短语动词宾语短语3(2) the名词动词宾语短语4(4) the名词动词冠词名词5(5) the monkey动词冠词名词6(7) the monkey ate冠词名词7(10) the monkey ate a名词8(6) the monkey ate a banana2.2.2 文法和语言的形式定义12l文法的抽象定义一系列需要定义的语法结构，称为非终结符号，用VN记之VN=句子,主语短语,动词短语,宾语短语,名词,动词,冠词若干个基本符号，称为终结符号，用VT记之VT=

7、monkey, banana, ate, has, the, a在非终结符号中，有一个最终需定义的语法结构句子，称为开始符号句子一组规则，每一规则都是用符号链接起来的有序对Uu，其中，U是一个非终结符号，u是一个由终结符号和(或)非终结符号所组成的符号串，称为产生式2.2.2 文法和语言的形式定义13n2.2.2 文法和语言的形式定义14l定义某文法时，习惯上只将其产生式写出，约定如下第一条产生式的左部是开始符号，或用GS表示S是开始符号用尖括号括起的符号串表示非终结符号用大写的拉丁字母表示非终结符号用小写的拉丁字母表示终结符号用希腊字母代表符号串左部相同的产生式A, A, 可以记为A | |

8、 ，符号“|”读作“或”，, , 都称为A的侯选式2.2.2 文法和语言的形式定义15l例: 文法GS=(VN, VT, P, S)，其中：VN=S, VT=0, 1, P=S0S1, S01GS: S0S1 | 01l例: 文法G1S=(VN, VT, P, S), VN =标识符, 字母, 数字, VT =a, b, c, , z, 0, 1, 2, , 9, P=标识符字母, 标识符标识符字母, 标识符标识符数字, 字母a, , 字母z, 数字0, 数字9, S=标识符G1S: SA | SA | SDAa | b | c | | zD0 | 1 | 2 | | 92.2.2 文法和语言

9、的形式定义16n2.2.2 文法和语言的形式定义17n2.2.2 文法和语言的形式定义18n2.2.2 文法和语言的形式定义19n2.2.2 文法和语言的形式定义20n2.2.2 文法和语言的形式定义21lL(G)中的每个符号串确实能被文法G生成有了语言的要求，也可以为该语言设计文法例: 若语言由0、1符号串组成，且串中0和1的个数相同，构造其文法A: 0=1的符号串B: 0=1-1的符号串C: 0=1+1的符号串GA:A0B | 1CB1 | 1A | 0BBC0 | 0A | 1CC2.2.2 文法和语言的形式定义22n2.2.2 文法和语言的形式定义23n例题: 试分别构造产生下列语言的

10、文法(1) an+1bn | n0=anabn | n0, G: SaSb | a(2) a2nb3n | n0=(aa)n(bbb)n | n0, G: SaaSbbb | (3) a2n+1cmb3n+2 | n0, m1=(aa)nacmbb(bbb)n | n0, m1, G: SaaSbbb | aCbb, CcC | c(4) ancmbn | n0, m1 andmbn | n0, m0 G: SaSb | C | D, CcC | c, DdD | 2.2.2 文法和语言的形式定义24n2.2.2 文法和语言的形式定义25n文法的等价l若L(G1)=L(G2)，则称文法G1和G

11、2是等价的l例: 文法G1A: A0R A01 RA1G2S: S0S1 S01所定义的语言都是0n1n，两文法等价l引理引理2.1 G=(VN, VT, P, S)，AB，B1, B2, Bn是P中的全部B-产生式，又设G1=(VN, VT, P1, S)是这样的方法，其中，P1是从P中删去AB并添加产生式A1, A2, An所组成的集合，则L(G1)=L(G)2.3 句型的分析26n构造一种算法，用以判断所给的符号串是否为某一文法的句型(或句子)n对于一个编译程序来说，不论在词法分析阶段，还是在语法分析阶段，都存在句型分析的问题2.3.1 规范推导与规范归约27n最左推导和最右推导l对于一

12、个推导序列中的每一直接推导，被替换的总是当前符号串中的最左(右)非终结符号l常把最右推导称为规范推导l每一句子都必定有最左和最右推导，但对一句型来说则不尽然EE+TE+T*FT+T*FT+T*iF+T*ii+T*ii+F*ii+i*iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iT*i+Tn左(右)句型l由最左(右)推导推出的句型l常把右句型称为规范句型2.3.1 规范推导与规范归约28n自顶向下的语法分析l试图为w建立一个从G的开始符号S到w的最左推导l若当前被替换的非终结符号U是由若干个候选式

13、定义的，即有U1 | 2 | | n，如何选用候选式带回溯：逐个用这些候选式进行试探，以期获得正确的选择效率很低不带回溯：在第4章中介绍l例:EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i2.3.1 规范推导与规范归约29n2.3.2 语法树和二义性30n树的性质l有且仅有一个没有任何前驱的结点，称之为“根”l除根之外，每一结点都恰好有一个直接前驱（父结点）l对于每一结点，都有唯一一条从根到此结点的通路l若一个结点有多个直接后继（子结点），则按自左向右的顺序进行排序l没有任何后继的节点称为树的末端节点（叶子）l由某个结点ni及其全部后继所组成的结点集合Di构成了以ni为根的

14、子树Til若一个子树的根只有直接后继，则称为直接子树2.3.2 语法树和二义性31n设G=(VN, VT, P, S)为一文法，则G的一棵语法树满足：l每一结点均有一标记，此标记为VN VT中的一个符号l树的根结点以文法的开始符号S标记l若一个结点至少有一个直接后继，则此结点上的标记为VN中的一个符号l若一个以A为标记的结点有k个直接后继，且按从左至右的顺序，这些结点的标记分别为X1, X2, Xk，则AX1X2Xk必然是G的一个产生式EE+TTT *FFFiiiEE+TE2.3.2 语法树和二义性32n由推导构造语法树l自顶向下的构造：把开始符号作为语法树的根，在各步推导中，每当句型中的一个

15、非终结符号被某一产生式的一个候选式替换时，就从此非终结符号所标记的结点出发，向下建立一个直接子树，此子树的末端结点标以该候选式中的各个符号l例: EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE + TTT * FFFiiiEE + TTT * FFFiiEE + TTT * FFFiEE + TTT * FFiEE + TTFiEE + TTFEE + TTEE + T2.3.2 语法树和二义性33nE + TTT * FFFiii+*Fiii+T*FiiiE +T*FiiiE +T*FFiiiE +TT *FFiiiE +TT * FFFiiiEE + TTT * F

16、FFiii2.3.2 语法树和二义性34n语法树与句型l对于任一句型的推导序列，总能为它构造一颗语法树，此末端结点从左到右依次排列起来，也就组成了所给的句型l反之，当给定一颗语法树时，把它的末端结点从左到右排列起来所组成的符号串也必然是一个句型l语法树表明了在推导过程中使用了哪些产生式和使用在哪个非终结符号上，但它并没有表明使用产生式的顺序l例:EE+TE+T*FT+T*FT+T*iF+T*ii+T*ii+F*ii+i*iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iEE+TTT *FFFiii2

17、.3.2 语法树和二义性35n文法的二义性l如果一个文法存在某个句子w，与w相应的语法树不止一个，则称这个文法为有二义性的文法。如果一个文法所产生的每一个句子都仅有一颗语法树，则称此文法为无二义性的l例: 文法G3E: EE+E | E*E | (E) | i，句子i+i*i有两个不同的最右推导：EE+EE+E*EE+E*iE+i*ii+i*iEE*EE*iE+E*iE+i*ii*i+iEE+EiE *EiiEE*EiE +Eii2.3.2 语法树和二义性36n文法的二义性l例: 在PASCAL语言中将if语句定义为Cif B then CCif B then C else CCS句子if B

18、1 then if B2 then S1 else S2存在两棵不同的语法树CifB1thenCifB2thenCCelseS1S2CifB1thenCifB2thenCCelseS1S22.3.2 语法树和二义性37n二义性文法的问题l当编译程序对句子的结构进行语法分析时，就可能会产生两种甚至更多种不同的理解l语法结构上的不确定性，将必然会导致语义处理上的不确定性l就会出现对同一源程序符号串在目标代码生成上的不确定性l前后文无关文法的二义性是不可判定的EE+EiE *EiiEE*EiE +Eii2.3.2 语法树和二义性38n二义性的消除l附加一些约定 在复合if 语句中，else子句总是属

19、于最靠近的、尚无else子句的那个if语句l构造一个等价的无二义性文法L(G3E: EE+E | E*E | (E) | i)=L(G2E: EE+T | T, TT*F | F, F(E) | i)n先天二义性的语言l用来定义该语言的一切文法都是二义性的l例: L=anbncmdm | n1, m1 anbmcmdn | n1, m1l前后文无关语言的先天二义性是不可判定的2.3.3 短语和句柄39n语法树与短语和句柄l语法树的句型为 ，子树根为A，子树的末端结点自左至右排列所形成的符号串为l短语：是句型相对A的一个短语l直接短语：若此子树为直接子树，则是句型相对于产生式A的直接短语l句柄：若此子树为最左直接子树，则是句型的句柄EE(1)+T(1)E(2)+T(2)T(3)*F(2)F(1)i2.3.3 短语和句柄40nEE(1)+T(1)E(2)+T(2)T(3)*F(2)F(1)i2.3.3 短语和句柄41nEE+TE+TT *FFiTFiiF