编译原理第三章文法和语言续

北京化工大学信息科学与技术学院计算机系赵瑞莲[e-mail]2019/12/17北京化工大学信息科学与技术学院计算机系2第3章文法和语言的概念和表示3.1预备知识-形式语言基础3.2文法和语言的定义3.3文法和语言的形式定义3.4语法树与二义性文法3.5句子的分析3.6有关文法的实用限制3.7文法的其它表示法3.8文法和语言分类2019/12/17北京化工大学信息科学与技术学院计算机系33.1预备知识一、字母表和符号串字母表：符号的非空有限集例：={a，b，c}符号：字母表中的元素例：a，b，c符号串：符号的有穷序列例：a,aa,c,abc，..空符号串：无任何符号的符号串(ε)符号串集合：由符号串构成的集合。符号串的形式定义有字母表，定义：（1）ε是上的符号串；（2）若x是上的符号串，且a，则ax或xa是上的符号串；（3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。2019/12/17北京化工大学信息科学与技术学院计算机系46.符号串集合的闭包运算：设A是符号串集合，定义A＋＝A1∪A2∪A3∪……∪An∪……称为集合A的正闭包。A*＝A0∪A＋称为集合A的（星）闭包。5.符号串集合的幂运算：有符号串集合A，定义A0={ε},A1=A,A2=AA,A3=AAA,…………An＝An-1A=AAn-1，n0。二、符号串和符号串集合的运算2019/12/17北京化工大学信息科学与技术学院计算机系5若A为某语言的基本字符集A＝{a,b,……z,0,1,……,9,+,－,×,/,(,),=……}B为单词集B={begin,end,if,then,else,for,……,标识符,常量,+,－,×,/,……}为什么对符号、符号串、符号串集合以及它们的运算感兴趣？则BA*语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C。2019/12/17北京化工大学信息科学与技术学院计算机系63.2文法的非形式讨论1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或为“语法”）。2.语法规则：通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由……组成”或“定义为……”。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。2019/12/17北京化工大学信息科学与技术学院计算机系73.由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2)从一组规则可推出不同的句子。2019/12/17北京化工大学信息科学与技术学院计算机系84.语法树：我们用语法树来描述一个句子的语法结构。句子主语谓语冠词形容词名词动词宾语冠词名词Thebigelephantatethepeanut语法成分在形式语言中又称“非终结符”单词符号在形式语言中又称“终结符号”3.2文法的非形式讨论2019/12/17北京化工大学信息科学与技术学院计算机系93.3文法和语言的形式定义3.3.1文法的定义3.3.2推导的形式定义3.3.3语言的形式定义3.3.4递归文法3.3.5句型的短语、简单短语和句柄2019/12/17北京化工大学信息科学与技术学院计算机系103.3.1文法的定义3.3文法和语言的形式定义定义1.文法G=（Vn，Vt，P，Z）Vn：非终结符号集Vt：终结符号集P：产生式或规则的集合Z：开始符号（识别符号）Z∈VnV＝Vn∪Vt称为文法的字母表Φ＝Vn∩Vt规则的定义规则是一个有序对(U,x),通常写为:U::x或Ux|U|=1|x|0U∈Vn,x∈V*。2019/12/17北京化工大学信息科学与技术学院计算机系11P={无符号整数→数字串；数字串→数字串数字；数字串→数字；数字→0；数字→1；…………数字→9；}Z=无符号整数；例：无符号整数的文法：G[无符号整数]=（Vn，Vt，P，Z）Vn＝{无符号整数,数字串,数字}Vt={0,1,2,3,……9}2019/12/17北京化工大学信息科学与技术学院计算机系12几点说明：•产生式左边符号构成集合Vn，且Z∈Vn。•有些产生式具有相同的左部，可以合在一起。例、无符号整数→数字串；数字串→数字串数字|数字；数字→0|1|2|3|……|9文法的BNF表示无符号整数的文法简化为：（产生式集合+识别符号）例、G[无符号整数]无符号整数→数字串；数字串→数字串数字|数字；数字→0|1|2|3|……|92019/12/17北京化工大学信息科学与技术学院计算机系133.3.2推导的形式定义定义2：文法G：v＝xUy，w＝xuy,其中x、y∈V*，U∈Vn,u∈V*,若U::u（U→u）∈P，则vw。若x＝y＝ε，有U::u，则Uu.根据文法和推导定义，可推出终结符号串，所谓文法能推出句子来。3.3文法和语言的形式定义称v直接产生w;或w是v直接推导;或w直接规约到v.2019/12/17北京化工大学信息科学与技术学院计算机系14无符号整数数字串数字串数字数字数字1数字10(6)====(1)==(3)(5)====(2)当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。例如：G[无符号整数](1)无符号整数→数字串；(2)数字串→数字串数字(3)数字串→数字(4)数字→0;(5)数字→1;…………(13)数字→9;请问根据文法G能否推导出10？2019/12/17北京化工大学信息科学与技术学院计算机系15定义3：文法G，U0,U1,U2,……，Un∈V+ifv=U0U1U2……Un＝w则vw＋==G==G==G==G==G例：无符号整数==数字串==数字串数字==数字数字==1数字==10即无符号整数10＋==G3.3.2推导的形式定义称v推导出（产生）w或w规约到v（推导长度为n≥１）.2019/12/17北京化工大学信息科学与技术学院计算机系16定义4：文法G，v，w∈V+ifvw,或v=w，则vw*==G＋==G定义5：规范推导：有xUy==xuy,ify∈Vt*,则此推导为规范的，记为xUy==xuy.|直观意义：规范推导＝最右推导最右推导：若符号串中有两个以上的非终结符时，先推右边的。最左推导：若符号串中有两个以上的非终结符时，先推左边的。称v推导出（产生）w，或w规约到v（推导长度为n≥０）.3.3.2推导的形式定义2019/12/17北京化工大学信息科学与技术学院计算机系17文法G[Z]描述的语言是该文法所产生的所有句子的集合.形式语言理论可以证明以下两点：（1）G→L（G）；（2）L(G)→G1，G2，……，Gn；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验。定义6：文法G[Z]（1）句型：x是句型Zx,且x∈V*；（2）句子：x是句子Zx,且x∈Vt*；（3）语言：L（G[Z]）={x|x∈Vt*,Zx}；++*3.3.3语言的形式定义3.3文法和语言的形式定义2019/12/17北京化工大学信息科学与技术学院计算机系18例：{abna|n≥1},构造其文法。定义7.G和G’是两个不同的文法，若L(G)=L(G’),则G和G’为等价文法。3.3.3语言的形式定义G1[Z]：Z→aBa,B→b|bBG2[Z]：Z→aBa,B→b|Bb2019/12/17北京化工大学信息科学与技术学院计算机系19编译感兴趣的问题是:给定x,G,求xL(G)?x算法1算法2xL(G)?Gyn出错处理停机3.3文法和语言的形式定义2019/12/17北京化工大学信息科学与技术学院计算机系203.3.4递归文法1.递归规则：规则右部有与左部相同的符号对于U::=xUy若x=ε,即U::=Uy，左递归；若y=ε,即U::=xU，右递归。2.递归文法：文法G，存在U∈VnifU==…U…,则G为递归文法；ifU==U…,则G为左递归文法；ifU==…U,则G为右递归文法。+++3.3文法和语言的形式定义2019/12/17北京化工大学信息科学与技术学院计算机系214.递归文法的优点：可用有穷条规则，定义无穷语言。例：对于前面给出的无符号整数的文法是有递归文法，用13条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？!3.左递归文法的缺点：不能用自顶向下的方法来进行语法分析。会造成死循环（后面将详细论述）3.3.4递归文法2019/12/17北京化工大学信息科学与技术学院计算机系22例：Micro语言的定义PbeginVDL;SLend.VDLVD|VD;VDLVDvarid:TSLS|S;SLSid:=E|write(E)|read(id)Tint|realEid|num|E+E|E*E|(E)2019/12/17北京化工大学信息科学与技术学院计算机系233.3.5句型的短语、简单短语和句柄定义8.给定文法G[Z],w=xuy∈V+，为该文法的句型,若Z==xUy,且U==u,则u是句型w相对于U的短语；若Z==xUy,且U==u,则u是句型w相对于U的简单短语。其中U∈Vn，u∈V+，x,y∈V***＋直观理解：短语是前面句型中的某个非终结符所能推出的符号串。3.3文法和语言的形式定义2019/12/17北京化工大学信息科学与技术学院计算机系24定义9.任一句型的最左简单短语称为该句型的句柄。给定句型找句柄的步骤：短语简单短语句柄注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语。句柄只能有一个。3.3.5句型的短语、简单短语和句柄3.3文法和语言的形式定义2019/12/17北京化工大学信息科学与技术学院计算机系253.4语法树与二义性文法3.4.1推导与语法树3.4.2文法的二义性2019/12/17北京化工大学信息科学与技术学院计算机系263.4语法树与二义性文法2.4.1推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。结点：符号根结点：识别符号中间结点：非终结符叶结点：终结符或非终结符有向边：表示结点间的派生关系。ZUVabcd2019/12/17北京化工大学信息科学与技术学院计算机系27(2)句型的推导及语法树的生成（自顶向下）给定G[Z]，句型w：可建立推导序列，Z==w可建立语法树，以Z为树根结点，每步推导生成语法树的一枝，最终可生成句型的语法树。G*2.4.1推导与语法树2019/12/17北京化工大学信息科学与技术学院计算机系28一般推导(最右推导)：例如：G[无符号整数](1)无符号整数→数字串；(2)数字串→数字串数字(3)数字串→数字(4)数字→0;(5)数字→1;…………(13)数字→9;最右推导：根据文法G推导出10.无符号整数数字串数字串数字数字1(1)(2)(3)(5)(4)0(3)(5)(1)(2)(4)无符号整数数字串数字串数字数字串0数字0102019/12/17北京化工大学信息科学与技术学院计算机系29一般推导(最右推导)：例如：G[无符号整数](1)无符号整数→数字串；(2)数字串→数字串数字(3)数字串→数字(4)数字→0;(5)数