编译原理文法和语言.ppt

编译原理,3.1符号和符号串3.2文法和语言的形式定义3.3文法的分类3.4语法树和二义性3.5有关文法的实用限制,第三章文法和语言,程序设计语言和自然语言的组成结构,语言定义的方法,枚举方法一个语言中的句子有限（非形式化描述）形式化描述方法（文法）一组数学符号（形式化描述）产生语言中全部句子的有限个规则自动机方法识别某字母表上所有符号串是否是该语言句子的一种装置（算法或过程）,产生的观点,识别的观点,3.1符号和符号串,一、字母表与符号,1.字母表：元素的非空有限集合例：=a，b，c=begin,end,if,then,else2.符号：字母表中的元素例：a，b，cbegin,end,if,then,else,3.1符号和符号串,字母表辨析：例：1=aa，bb，cc2=a,a,b,b3=a，b，a4=,解析：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=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(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,则BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序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=SVT=0,1P=S0S1,S01S为开始符号,或写成文法GS:S0S1S01,给定一个文法，实际只需给出产生式集合，并指定识别符号,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，记作vw,1.直接推导/直接归约,例1：文法GS:S0S1，S01若v=0S1，w=0011,有直接推导0S10011,三、推导和归约,3.2文法和语言的形式定义,如是文法G的产生式，和V*,若有v,w满足：v=,w=,其中则称v直接推导到w，也称w直接归约到v，记作vw,1.直接推导/直接归约,例2：文法GS:S0S1，S01若v=S，w=0S1,有直接推导S0S1,三、推导和归约,3.2文法和语言的形式定义,如是文法G的产生式，和V*,若有v,w满足：v=,w=,其中则称v直接推导到w，也称w直接归约到v，记作vw,1.直接推导/直接归约,例3：文法GS:S0S1，S01若v=0S1，w=00S11,有直接推导0S100S11,三、推导和归约,3.2文法和语言的形式定义,若存在直接推导序列vw0w1.wn=w，(n0)+则记为vw，称v推导出（产生）w，或w归约到v。,2.推导/归约,三、推导和归约,3.2文法和语言的形式定义,例：GN：NND|DD0|1|2|3|4|5|6|7|8|9NNDNDDND9N09D09109,2.推导/归约,若存在直接推导序列vw0w1.wn=w，(n0)+则记为vw，称v推导出（产生）w，或w归约到v。,说明：当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。,三、推导和归约,3.2文法和语言的形式定义,若存在直接推导序列vw0w1.wn=w，(n0)+则记为vw，称v推导出（产生）w，或w归约到v。,2.推导/归约,+*如果vw，或vw，则记作vw。,三、推导和归约,3.2文法和语言的形式定义,例：S0S100S11000S11100001111+则有S00001111*S00001111,2.推导/归约,3.2文法和语言的形式定义,例：无符号整数的文法G:；0|1|2|9；,如整数10的推导过程：0010,四、句型、句子和语言,3.2文法和语言的形式定义,1.句型,*有文法GS，若Sx，则称x是文法G的句型。,例：GS：S0S1，S01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111等G的句子00001111,01等,四、句型、句子和语言,3.2文法和语言的形式定义,3.语言,例：GS：S0S1，S01S0S100S110n-1S1n-10n1nL(G)=0n1n|n1,四、句型、句子和语言,3.2文法和语言的形式定义,4.等价文法,例：GA：A0R，A01，RA1A0R0A100R100A110n1n故GA和GS所产生的语言是相同的，GA和GS是等价文法。,G和G是两个不同的文法，若L(G)=L(G),则G和G为等价文法。,给定文法GA：AbA|cc，下面的符号串中，为该文法句子的是：ccbcbcbcbccbccbccbbbcc,练习,注意：已知文法求语言，通过推导；已知语言构造文法，全凭经验。,已知句子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,SVT=0,1P=S0AB1B0BSA|01A1SB1A0S0B,3.3文法的分类,对任一产生式，都有|，仅仅S除外,二、1型文法(上下文有关文法),说明：文法左部符号个数不超过右部符号的个数,1A212，其中1,2,(VNVT)*，AVN,3.3文法的分类,对任一产生式，都有|，仅仅S除外,二、1型文法(上下文有关文法),说明：文法左部符号个数不超过右部符号的个数,例：文法GS：SCDAbbACaCABaaBCbCBBbbBADaDBDbDAabD,3.3文法的分类,对任一产生式，都有VN，(VNVT)*,三、2型文法(上下文无关文法),说明：程序设计语言的文法是上下文无关的，如C，Pascal,例：文法GS：SaB|bAAa|aS|bAABb|bS|aBB,3.3文法的分类,任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT,四、3型文法(正规文法),说明：通常用来描述单词结构，其中包括标识符、常量、保留字、运算符、界符等。,例：文法GS：S0A|1B|0A0A|1B|0SB1B|1|0,此处限定产生式形如AaB或Aa为右线性文法；若限定为ABa或Aa即为左线性文法,l|ll|d|l|dd|d+|-|*|/|=|=，|；|(|)|其中l表示az中的任何一英文字母，d表示09中的任一数字。,例：标识符等单词的定义的规则,3.3文法的分类,3.3文法的分类,五、四种文法的关系,由于四种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含”的关系。即：3型语言类2型语言类1型语言类0型语言类,1：已知文法GP：PaPQR|abRRQQRbQbbbRbccRcc它是Chomsky哪一型文法？,答：由于G的每一个产生式都满足|，故该文法是1型文法。,练习,2：已知文法GZ：ZU0|V1UZ1|1VZ0|0它是Chomsky哪一型文法？并写出全部由此文法描述的只含有四个符号的句子。,答：该文法是3型文法。由此文法描述的只含有四个符号的句子是：1010，0110，1001，0101。,练习,ZU0|V1UZ1|1VZ0|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语法树和二义性,语法树的画法,方法：把开始符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。,例如：推导SABAcBdAccddabccdd,3.4语法树和二义性,语法树的用途,用于描述句型和句子的语法结构。句型的推导过程对应于语法树的构造过程。,例:GS:SaAS|aASbA|SS|ba构造句型aabbaa的语法树,从左到右读出语法树的叶子标记连接成的文法符号串，为GS的句型。,3.4语法树和二义性,语法树的用途,问题：看不出推导过程中产生式被施用的顺序,例:GS:SaAS|aASbA|SS|ba构造句型aabbaa的语法树,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,3.4语法树和二义性,二、短语与句柄,对文法GS，是文法的一个句型。如果有SA且A，则称是句型相对于非终结符A的短语。如有A，则称是句型相对于非终结符A的直接短语，也称简单短语。一个句型的最左直接短语称为该句型的句柄。,*,*,P44,3.4语法树和二义性,二、短语与句柄,子树的末端结点从左到右排列形成的符号串是相对于子树根的短语。,对文法GS，是文法的一个句型。如果有SA且A，则称是句型相对于非终结符A的短语。,例：对于文法GS：SABAAa|bBBa|Sb求句型baSb的全部短语、直接短语和句柄？,句型baSb的短语：a,ba,Sb,baSb,*,*,3.4语法树和二义性,二、短语与句柄,如有A，则称是句型相对于非终结符A的直接短语，也称简单短语。,例：对于文法GS：SABAAa|bBBa|Sb求句型baSb的全部短语、直接短语和句柄？,句型baSb的直接短语：a,Sb,简单子树(只有父子两代)的末端结点形成的符号串是相对于简单子树根的直接短语。,3.4语法树和二义性,二、短语与句柄,一个句型的最左直接短语称为该句型的句柄。,例：对于文法GS：SABAAa|bBBa|Sb求句型baSb的全部短语、直接短语和句柄？,句型baSb的句柄：a,最左简单子树的末端结点形成的符号串是句柄。,E,T,T,GE：EE+T|TTT*F|FF(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:Ei|E+E|E*E|(E)，写出句型i*i+i的最左推导。,例：GE:Ei|E+E|E*E|(E)，写出句型i*i+i的最左推导。,推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i,每一个句型是否都对应唯一的最左(最右)推导?,3.4语法树和二义性,四、文法的二义性,若一个文法存在某个句子对应两棵不同的语法树，则称该句子是二义性的，如果一个文法含有二义性的句子，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。,3.4语法树和二义性,四、文法的二义性,以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。语法的二义性意味着句型的句柄不唯一。如句型E+E*i。,3.4语法树和二义性,四、文法的二义性,例：条件语句的语法定义SifEthenSelseSSifEthenS考察句型ifE1thenifE2thenS1elseS2,3.4语法树和二义性,四、文法的二义性,若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判