编译原理文法和语言.ppt

编 译 原 理,3.1 符号和符号串3.2 文法和语言的形式定义3.3 文法的分类3.4 语法树和二义性3.5 有关文法的实用限制,第三章 文法和语言,程序设计语言和自然语言的组成结构,语言定义的方法,枚举方法 一个语言中的句子有限（非形式化描述）形式化描述方法（文法）一组数学符号（形式化描述）产生语言中全部句子的有限个规则自动机方法识别某字母表上所有符号串是否是该语言句子的一种装置（算法或过程）,产生的观点,识别的观点,3.1 符号和符号串,一、字母表与符号,1.字母表：元素的非空有限集合 例：=a，b，c=begin,end,if,then,else2.符号：字母表中的元素 例：a，b，c begin,end,if,then,else,3.1 符号和符号串,字母表辨析：例：1=aa，bb，cc 2=a,a,b,b 3=a，b，a 4=,解析：1和2是字母表，体现了字母表的整体性和可辨认性；3中有相同的符号；4也不是字母表，因为要求字母表非空。,3.1 符号和符号串,一、字母表与符号,3.符号串：由字母表中的符号组成的任何有穷序列 例：=a,b,a,b,aa,ab,aabba都是上的符号串,符号串的长度：符号串x中符号的数目,|x|=m空符号串：无任何符号的符号串,记为,|=0,3.1 符号和符号串,一、字母表与符号,4.符号串的头和尾：对于符号串z=xy，x是z的头，y是z的尾。如果x非空，那么y是固有尾；如果y非空，那么x是固有头。,例：设z=abc,z的头是，a，ab，abc，固有头是，a，ab；z的尾是，c，bc，abc，固有尾是，c，bc。,3.1 符号和符号串,二、字符串和字符串集合的运算,1.字符串的连接：设x和y是两个字符串，则xy被称 为符号串x与y连接。x=x=x(xy)z=x(yz)|xy|=|x|+|y|,例：x=ST，y=abu，则xy=STabu，可看出|x|=2，|y|=3，|xy|=5,3.1 符号和符号串,2.字符串x的方幂：即把x重复写n次，记为z=xn。,例：若x=AB 则:x0=x1=AB x2=ABAB x3=ABABAB xn=xxn-1=xn-1 x(n0),二、字符串和字符串集合的运算,对于m,n0 xmxn=xm+n(xm)n=xmn,3.1 符号和符号串,3.字符串A与B的乘积：设A和B为符号串集合，则 A与B的乘积定义为AB=xy|xA且yB,例：若集合A=ab,cde 集合B=0,1 则 AB=ab0,ab1,cde0,cde1,二、字符串和字符串集合的运算,3.1 符号和符号串,4.字符串集合的正闭包：设为字母表，则+=12n，n1,例：若=0,1 则+=0,1,00,01,10,11,000,001,二、字符串和字符串集合的运算,注：指定字母表后，可用n表示上所有长度为n的串的集合。,3.1 符号和符号串,5.字符串集合的闭包(星闭包)：设为字母表，则*=012n,n0,*可表示上所有有穷长的串的集合；*=0+=*=*=+，+=*-,例：若=0,1,则*=,0,1,00,01,10,11,二、字符串和字符串集合的运算,若A为某语言的基本字符集 Aa,b,z,0,1,9,+,_/,(,),=B为单词集 B=begin,end,if,then,则B A*。语言的句子是定义在B上的符号串。若令C为句子集合，则C B*,程序 C,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？,3.2 文法和语言的形式定义,一、文法的直观理解,1.什么是文法 文法是对语言结构的定义与描述，即从形式上描述和规定语言结构，也称为语法。,例：句子：“我是大学生”。该句子的结构（称为语法结构）是由它的语法决定的。如何定义该句子的语法结构呢？语法规则,一、文法的直观理解,2.语法规则 通过建立一组规则（产生式），来描述句子的语法结构。规定用“:=”表示“由组成”或“定义为”。,:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|,3.2 文法和语言的形式定义,一、文法的直观理解,3.由产生式推导句子 推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。,3.2 文法和语言的形式定义,我,我,我是,我是,我是大学生,:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|,推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。,例：给定一组语法规则，考察一个句子：“我是大学生”的推导过程。,一、文法的直观理解,4.语法树,我,大学生,语法成分（在形式语言中又称“非终结符”）,单词符号（在形式语言中又称“终结符号”),是,3.2 文法和语言的形式定义,二、文法的形式定义,定义:文法GS定义为一个四元组，GS=（VN，VT，P，S）VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号）,SVN,其中:非终结符号：出现在产生式的左部或右部,且能推出符号或符号串，用来表示语言的语法成分。终结符号：不出现在产生式的左部,且不能推出符号或符号串，是组成语言的基本单位。VTVN 是字母表。产生式：产生式是一个有序对(,),通常写为:或；读作“定义为”。,3.2 文法和语言的形式定义,35页,二、文法的形式定义,例 1 文法G=（VN，VT，P，S）VN=S VT=0,1 P=S0S1,S01 S为开始符号,或写成 文法GS:S0S1 S01,给定一个 文法，实际只需给出产生式集合，并指定识别符号,3.2 文法和语言的形式定义,P=；0；1；9；S=；,例2：无符号整数的文法：G=（VN，VT，P，S）VN,VT=0,1,2,3,9,有些产生式具有相同的左部，可以合在一起。如0|1|2|3|9,也可以写做：G:；0|1|2|9；,例2：无符号整数的文法：,三、推导和归约,3.2 文法和语言的形式定义,如是文法G的产生式，和V*,若有v,w满足：v=,w=,其中 则称v直接推导到w，也称w直接归约到v，记作 v w,1.直接推导/直接归约,例1：文法GS:S0S1，S01 若v=0S1，w=0011,有直接推导0S10011,三、推导和归约,3.2 文法和语言的形式定义,如是文法G的产生式，和V*,若有v,w满足：v=,w=,其中 则称v直接推导到w，也称w直接归约到v，记作 v w,1.直接推导/直接归约,例2：文法GS:S0S1，S01 若v=S，w=0S1,有直接推导S0S1,三、推导和归约,3.2 文法和语言的形式定义,如是文法G的产生式，和V*,若有v,w满足：v=,w=,其中 则称v直接推导到w，也称w直接归约到v，记作 v w,1.直接推导/直接归约,例3：文法GS:S0S1，S01 若v=0S1，w=00S11,有直接推导0S100S11,三、推导和归约,3.2 文法和语言的形式定义,若存在直接推导序列 v w0 w1.wn=w，(n0)+则记为v w，称v推导出（产生）w，或w归 约到v。,2.推导/归约,三、推导和归约,3.2 文法和语言的形式定义,例：GN：NND|D D0|1|2|3|4|5|6|7|8|9 NNDNDDND9N09D09109,2.推导/归约,若存在直接推导序列 v w0 w1.wn=w，(n0)+则记为v w，称v推导出（产生）w，或w归 约到v。,说明：当符号串已没有非终结符号时，推导就 必须终止。因为终结符不可能出现在产 生式左部，所以将在产生式左部出现的 符号称为非终结符号。,三、推导和归约,3.2 文法和语言的形式定义,若存在直接推导序列 v w0 w1.wn=w，(n0)+则记为v w，称v推导出（产生）w，或w归 约到v。,2.推导/归约,+*如果v w，或v w，则记作v w。,三、推导和归约,3.2 文法和语言的形式定义,例：S 0S1 00S11 000S111 00001111+则有S 00001111*S 00001111,2.推导/归约,3.2 文法和语言的形式定义,例：无符号整数的文法G:；0|1|2|9；,如整数10的推导过程：0 0 10,四、句型、句子和语言,3.2 文法和语言的形式定义,1.句型,*有文法GS，若S x，则称x是文法G的句型。,例：GS：S0S1，S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1,00S11,000S111,00001111等 G的句子00001111,01等,四、句型、句子和语言,3.2 文法和语言的形式定义,3.语言,例：GS：S0S1，S01 S 0S1 00S11 0n-1S1n-1 0n1n L(G)=0n1n|n1,四、句型、句子和语言,3.2 文法和语言的形式定义,4.等价文法,例：GA：A0R，A01，R A1 A 0R 0A1 00R1 00A11 0n1n 故GA和GS所产生的语言是相同的，GA和GS是等价文法。,G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。,给定文法GA：AbA|cc，下面的符号串中，为该文法句子的是：cc bcbc bcbcc bccbcc bbbcc,练 习,注意：已知文法求语言，通过推导；已知语言构造文法，全凭经验。,已知句子L(G)=abna|n1，构造文法。,练 习,G1S：SaBa，Bb|BbG2S：SaBa，Bb|bB,3.3 文法的分类,Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法 0型语言或短语结构语言1型文法 1型语言或上下文有关语言2型文法 2型语言或上下文无关语言3型文法3型语言或正则（正规）语言,3.3 文法的分类,对任一产生式，都有(VNVT)*，且至少含有一个非终结符，(VNVT)*,一、0型文法(短语结构文法),说明：对产生式基本无限制,例：文法G，其中VN=A,B,S VT=0,1 P=S0AB 1B0 BSA|01 A1SB1 A0S0B,3.3 文法的分类,对任一产生式，都有|，仅仅 S除外,二、1型文法(上下文有关文法),说明：文法左部符号个数不超过右部符号的个数,1A212，其中1,2,(VNVT)*，A VN,3.3 文法的分类,对任一产生式，都有|，仅仅 S除外,二、1型文法(上下文有关文法),说明：文法左部符号个数不超过右部符号的个数,例：文法GS：SCD AbbA CaCA BaaB CbCB BbbB ADaD BDbD AabD,3.3 文法的分类,对任一产生式，都有VN，(VNVT)*,三、2型文法(上下文无关文法),说明：程序设计语言的文法是上下文无关的，如 C，Pascal,例：文法GS：SaB|bA Aa|aS|bAA Bb|bS|aBB,3.3 文法的分类,任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT,四、3型文法(正规文法),说明：通常用来描述单词结构，其中包括标识符、常量、保留字、运算符、界符等。,例：文法GS：S0A|1B|0A0A|1B|0SB1B|1|0,此处限定产生式形如AaB或Aa为右线性文法；若限定为ABa或Aa即为左线性文法,l|l l|d|l|dd|d+|-|*|/|=|=，|；|(|)|其中l表示az中的任何一英文字母，d表示09中的任一数字。,例：标识符等单词的定义的规则,3.3 文法的分类,3.3 文法的分类,五、四种文法的关系,由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含”的关系。即：3型语言类 2型语言类 1型语言类 0型语言类,1：已知文法GP：PaPQR|abR RQQR bQbb bRbc cRcc 它是Chomsky哪一型文法？,答：由于G的每一个产生式都满足|，故该文法是1型文法。,练 习,2：已知文法GZ：ZU0|V1 UZ1|1 VZ0|0 它是Chomsky哪一型文法？并写出全部由此文法描述的只含有四个符号的句子。,答：该文法是3型文法。由此文法描述的只含有四 个符号的句子是：1010，0110，1001，0101。,练 习,ZU0|V1 UZ1|1 VZ0|0,Z,U,0,Z,1,Z,Z,V,1,Z,V,1,Z,0,Z,U,0,Z,1,U,0,1,Z,U,0,Z,1,V,1,0,Z,V,1,Z,0,U,0,1,Z,V,1,Z,0,V,1,0,3.4 语法树和二义性,一、语法树的定义,设文法G=(VN,VT,P,S)，若一棵树满足下列4个条件，则此树称作G的语法树(推导树或分析树）：每个结点都有一个标记，此标记是V的一个符号根的标记是S如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式树的叶结点符号从左至右恰好构成句型,3.4 语法树和二义性,一、语法树的定义,假设表达式文法：Eid|(E)|E*E|E+E 则句型id的语法树句型(id)的语法树句型E*E+E的语法树,3.4 语法树和二义性,语法树的画法,方法：把开始符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。,例如：推导S AB AcBd Accdd abccdd,3.4 语法树和二义性,语法树的用途,用于描述句型和句子的语法结构。句型的推导过程对应于语法树的构造过程。,例:GS:SaAS|a ASbA|SS|ba构造句型aabbaa的语法树,从左到右读出语法树的叶子标记连接成的文法符号串，为GS的句型。,3.4 语法树和二义性,语法树的用途,问题：看不出推导过程中产生式被施用的顺序,例:GS:SaAS|a ASbA|SS|ba构造句型aabbaa的语法树,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,3.4 语法树和二义性,二、短语与句柄,对文法GS，是文法的一个句型。如 果有SA且A，则称是句型 相对于非终结符A的短语。如有A，则称是句型相对于非 终结符A 的直接短语，也称简单短语。一个句型的最左直接短语称为该句型的句 柄。,*,*,P44,3.4 语法树和二义性,二、短语与句柄,子树的末端结点从左到右排列形成的符号串是相对于子树根的短语。,对文法GS，是文法的一个句型。如果有SA且A，则称是句型相对于非终结符A的短语。,例：对于文法GS：S AB A Aa|bB B a|Sb 求句型baSb的全部短语、直接短语和句柄？,句型baSb的短语：a,ba,Sb,baSb,*,*,3.4 语法树和二义性,二、短语与句柄,如有A，则称是句型相对于非终结符A 的直接短语，也称简单短语。,例：对于文法GS：S AB A Aa|bB B a|Sb 求句型baSb的全部短语、直接短语和句柄？,句型baSb的直接短语：a,Sb,简单子树(只有父子两代)的末端结点形成的符号串是相对于简单子树根的直接短语。,3.4 语法树和二义性,二、短语与句柄,一个句型的最左直接短语称为该句型的句柄。,例：对于文法GS：S AB A Aa|bB B a|Sb 求句型baSb的全部短语、直接短语和句柄？,句型baSb的句柄：a,最左简单子树的末端结点形成的符号串是句柄。,E,T,T,GE：EE+T|T TT*F|F F(E)|i句型：i*i+i短语：直接短语：句柄：,T,F,F,i,i,i,*,+,E,F,练 习,i1,i2,i3,3.4 语法树和二义性,三、最左推导和最右推导,如果在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换，则称为最左（右）推导。在形式语言中，最右推导常被称作规范 推导。由规范推导所得的句型称为规范 句型。,例：GS：Sa|(T)TT,S|S给出句子(a,(a,a)的最左、最右推导。,答：最左推导：S(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a),3.4 语法树和二义性,三、最左推导和最右推导,答：最右推导：S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,(a,a)(a,(a,a),例：GS：Sa|(T)TT,S|S给出句子(a,(a,a)的最左、最右推导。,3.4 语法树和二义性,三、最左推导和最右推导,3.4 语法树和二义性,三、最左推导和最右推导,每一个句型是否都对应唯一的最左(最右)推导?,例：GE:E i|E+E|E*E|(E)，写出句型 i*i+i的最左推导。,例：GE:E i|E+E|E*E|(E)，写出句型 i*i+i的最左推导。,推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导2：E E*E i*E i*E+E i*i+E i*i+i,每一个句型是否都对应唯一的最左(最右)推导?,3.4 语法树和二义性,四、文法的二义性,若一个文法存在某个句子对应两棵不同的语法树，则称该句子是二义性的，如果一个文法含有二义性的句子，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。,3.4 语法树和二义性,四、文法的二义性,以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。语法的二义性意味着句型的句柄不唯一。如句型E+E*i。,3.4 语法树和二义性,四、文法的二义性,例：条件语句的语法定义 Sif E then S else S Sif E then S 考察句型if E1 then if E2 then S1 else S2,3.4 语法树和二义性,四、文法的二义性,若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。,3.4 语法树和二义性,四、文法的二义性,文法GP：PPaP|PbP|cP|Pe|f证明文法G是二义性文法。,练 习,句型fbfbfb,3.5 有关文法的实用限制,有害规则：形如UU的产生式。会引起文法的二义性，若有，则删去。,3.5 有关文法的实用限制,多余规则：指文法中任何句子的推导都不会用到的规则，若有，则删去。,文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,3.5 有关文法的实用限制,例GS：1)SBe 2)BCe 3)BAf 4)AAe 5)Ae 6)CCf 7)Df,3.5 有关文法的实用限制,3.5 有关文法的实用限制,文法中不含有空规则U：因为有的分 析方法（算符优先分析法）中要求没有空 规则，规则会使得有关文法的一些讨论 和证明变得复杂。后面将详细介绍。,例：对以下文法G1S，构造一个与之等价的文法G2S，使G2S中的每一个非终结符均能导出一个终结符号串。G1S：SBab|cC Bb|bS CDa DCb|CDa,练 习,解：因为从C、D均推导不出终结符号串，所以这两条为多余规则，将其删去，所有含C、D的规则的右部也均应删去。,G2S：SBab Bb|bS,小 结,本章出现的概念较多,应重点理解文法,推导,句型，句子及语言的定义等概念.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的 形式的含义-只涉及语言的语法不涉及语言的语义.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,