编译原理：文法和语言.ppt

1,第二章文法和语言,2.1文法的直观表示2.2符号和符号串2.3文法和语言的形式定义2.4文法的类型2.5上下文无关文法及语法树2.6句型分析2.7文法的实用限制,2,第2章文法和语言,【学习目标】本章是为语言的语法描述寻求工具掌握对程序设计语言给出精确、无二义（严谨、易读）的语法描述的手段之一文法。对形式语言的理论有一个初步基础根据文法的特点指导语法分析过程,3,2.1文法的直观表示,文法：阐明语法的一个工具，也可以说是以有穷的集合刻画无穷的集合的一个工具。语言：程序设计语言。一、语言概述语言是由符合语法的句子组成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体每个句子构成的规律语法研究语言每个句子的含义语义每个句子和使用者的关系语用,4,形式语言：只考虑语法而不考虑语义的符号语言。每种语言具有两个可识别的特性语言的形式与该形式相关联的意义“形式”指语言的所有规则，描述出现什么符号串语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。,5,表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述例：汉语句子的构成规则：句子=主语谓语主语=代词|名词代词=我|你|他名词=王明|大学生|工人|英语谓语=动词直接宾语动词=是|学习直接宾语=代词|名词,二、文法的直观概念,6,推导：“我是大学生”是汉语的一个句子句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生,7,2.2符号与符号串,一、相关概念程序设计语言是由程序构成的集合，程序是由基本符号按照一定的规则构成的集合。1.符号、字母表和符号串基本符号：可以相互区别的基本元素，如字母，数字，标点符号。字母表：基本符号的非空有穷集合，常用表示。例：=0,1，=a,b,c,x,y,z,8,符号串：由字母表中的符号构成的任何有穷序列称为符号串。符号串中的符号是有顺序的。,例如=0,1上的符号串0,1,00,01,11,10注意：表示空符号串,它表示不包含任何符号串，不是空格符。,符号串集合：字母表上若干个符号串组成的集合.例：字母表=0,1的符号串集合A=1,00,01;约定：小写字母a,b,r表示符号.小写字母s,t,z表示符号串;,9,符号串s的头（前缀）和尾（后缀）：如果s=xy是一符号串，那么x是s的头，y是s的尾。若x是非空，则y是固有尾；若y非空，则x是固有头。前缀：移走符号串s尾部的零个或多个符号得到的串。如：设s=abc,那么s的前缀是，a，ab，abc后缀：移走符号串s头部的零个或多个符号得到的串。如：s=abc的后缀是，c，bc，abc，s的固有尾是，c，bc。,10,符号串s的子串：从s中删去任何前缀或后缀得到的串.如:bc是符号串abc的一个子串.对符号串s，s和两者都是符号串s的前缀、后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x，是s的前缀，后缀或子串，并且sx,11,2.符号串的运算(1)符号串相等：符号串x，y，如果两者诸符号依次相等，则两符号串相等。(2)符号串的长度：符号串中包含符号的个数。|abc|=3；|=0；(3)符号串的连结：x=abc，y=def则xy=abcdef；yx=defabc；xyyxx=x=x；,12,(4)符号串集合的乘积：设A、B为两个符号串集合，其乘积为AB=xy|xA，yB；例：A=aa，bb，B=cc，dd，则AB=aacc，aadd，bbcc，bbddA=A=A；(5)空集：不含任何元素的集合称为空集。记为；对任何集合A：A=A=;注意：,13,(6)符号串的方幂：x是字母表上的符号串，则x的幂运算为：x0=;x1=x;x2=xx;xn=xn-1x=xxn-1(n0)xn表示n个x相连结。eg：x=ok；则x0=;x1=ok;x2=okok;(7)符号串集合的方幂：A为符号串集合，则A的幂运算为：A0=;A1=A;A2=AA;.An=An-1A=AAn-1;(n0)A=aa，bb，则A0=；A1=aa，bb；A2=AA=aaaa，aabb，bbaa，bbbb;.,14,(8)符号串集合的闭包和正闭包集合A的闭包表示为A*（亦称为自反闭包或星闭包）定义为：A*=A0A1A2A3=Ak，k0正闭包表示为A+具体定义为A+=A1A2A3=Ak，k1由定义可以看到A*=A0A+,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,15,3、语言(1)由一组符号所构成的集合。即：字母表上的每个语言是*的一个子集。例如：字母表=a,b，*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*，且w=an，n1为字母表上的一个语言。(2)是一个语言。(3)即是一个语言。,16,2.3文法和语言的形式定义,如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途径：,生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一个任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,17,一、规则（重写规则、产生式或生成式）,规则是形如或=的(，)有序对，其中V+，V*中的一个符号称为规则的左部称作规则的右部。例：文法可利用规则来描述。,18,二、文法的定义,1、文法G定义为四元组(VN，VT，P，S)其中VN：非终结符号；VT：终结符号集；P：规则集合；VN，VT和P是非空有穷集。S：开始符或识别符，是一个非终结符，至少要在一条规则的左部出现。VNVT=，V=VNVT，V称为文法G的字母表,例1：文法G=(VN，VT，P，S)，其中VN=S，VT=0，1，P=S0S1，S01。,19,文法G习惯上只将规则写出。如例1还可以写成：G：S0S1S01或GS：S0S1S01或GS：S0S1|S01,20,总结一个文法的几种写法G=(S,A，a,b，P，S)其中P：SaAbAabAaAbAG：SaAbAabAaAbAGS：SaAbAabAaAbAGS：SaAbAab|aAb|,21,三、推导的定义,用文法定义语言的中心思想是：从文法的开始符号出发，反复使用合适规则，对非终结符施行替换和展开。1、直接推导：是文法G的产生式，若有v，w满足：v=，w=,其中V*,V*。则称v直接推导到w,或w直接归约到v记作vw，2、推导：如果存在直接推导的序列：v=W0W1W2Wn=w,(n0)；称v推导出w(推导长度为n)，或称w归约到v。记作vw。若有vw，或v=w，则记作vw，(n=0),*,22,例3：G：S0S1，S010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S00001111SS00S1100S11,+,*,*,23,3、规范推导最左(最右)推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。例4：GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a（最左推导）EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*a（最右推导）,24,四、句型、句子和语言的定义,1.句型:文法GS，若Sx，则称x是G的句型。2.句子:文法GS，若Sx，且xVT*，则称x是G的句子。句子是句型的特殊，只包含终结符。例5：G：S0S1，S01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子000011113.语言:文法G的一切句子的集合,记为L(G)，,*,*,25,例6文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeSanBnEnanbnen则L（G）=anbnen|n1因为San-1S（BE）n-1an（BE）n，继续推导时，将用规则(3)(7)替换,*,*,26,SaSBE(SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,27,五、语言和文法,给定一个文法，能从结构上唯一确定其语言给定一个语言，不能唯一确定其文法，即一个语言可有多个文法与之对应已知语言描述，写出文法，应满足：所描述的语言的任何句子都能由该文法产生该文法推导不出不是已知语言的任何句子已知文法，写出语言描述，应满足：该文法能推导出的任何句子都包含在所描述的语言中描述的语言中不包含该文法推导不出的句子,28,六、文法的等价,若L（G1）=L（G2），称文法G1和G2是等价的如文法G1A：A0R与G2S：S0S1等价A01S01RA1作业：P47:1，4，5,29,2.4文法的类型,一、文法分类通过对产生式施加不同的限制，将文法分为四类设有文法G=(VN，VT，P，S);0型文法：（短语结构文法）图灵机对任一产生式，都有(VNVT)+，且至少包含一个非终结符，(VNVT)*1型文法：（上下文有关文法）对任一产生式，都有|，仅仅S除外。,30,文法GS是1型文法SaSBC|aBCCBDBDBDCDCBCaBabbBbbbCbccCccSaSBCaaBCBCaabCBCaabbcc,*,31,2型文法：（上下文无关文法）对任一产生式，都有VN，(VNVT)*设文法G(VN,VT,P,S)是一个2型文法，VNS,A,B,VTa,b其中P为:(0)SaB(1)SbA(2)Aa(3)AaS|bAA(4)Bb(5)BbS|aBB,32,3型文法：（正规文法）右线性文法任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT(a可为)左线性文法任一产生式的形式都为ABa或Aa，其中AVN，BVN，aVT(a可为),33,例：GE：EE+T|TTT*F|FF(E)|aG是上下文无关文法。例文法G=(S,A,B,0,1,P,S)，其中P由下列产生式组成：S0AA1BS1BB1BS0B1A0AB0A0SG是正规文法。,34,二、四类文法之间的关系,四种文法之间的逐级“包含”关系,35,2.5上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构例:文法GE：Ea|E+E|E*E|(E)E表示算术表达式,a表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构,句型推导的直观表示-语法树,36,设G为一上下文无关文法，若一棵树满足下列4个条件，则称作G的语法树(推导树，派生树）1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是文法开始符号S3.如果结点n至少有一个除自己外的子孙并有标记A，则肯定AVN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行,一、语法树,37,GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a,E,E,+,T,E,E,+,T,T,E,E,+,T,T,F,E,E,+,T,T,F,a,T,*,F,F,a,a,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树),38,用于描述上下文无关文法句型推导的直观方法,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。该推导树称为该句型的语法树。,用于描述上下文无关文法句型推导的直观方法,用于描述上下文无关文法句型推导的直观方法,例:GS:SaASASbAASSSaAba,用于描述上下文无关文法句型推导的直观方法,句型aabbaa的语法树（推导树）,39,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,40,例：GE：EE+T|TTT*F|FF(E)|a试给出表达式a+a*a的推导，并画出语法树。左:EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a右:EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*a混合:EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a,41,例如，有一个2型文法G=(S,A,B,a,b,P,S),其中P:(0)SaB|bA(1)Aa|aS|bAA(2)Bb|bS|aBB采用最左推导产生句子aabbab:SaBaaBBaabSBaabbABaabbaBaabbab,一棵语法树表示了一个句型的种种可能的不同推导过程，一个句型是否只对应唯一的一棵语法树呢?是否只有唯一的一个最左(最右)推导呢?,42,语法树其中P:(0)SaB|bA(1)Aa|aS|bAA(2)Bb|bS|aBB分析句子aabbab,43,例：GE:EaEE+EEE*EE(E),句型a*a+a的两个不同的最左推导：(1)EE+EE*E+Ea*E+Ea*a+Ea*a+a(2)EE*Ea*Ea*E+Ea*a+Ea*a+a,44,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。,45,如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。二义文法改造为无二义文法GE:EaGE：ET|E+TEE+ETF|T*FEE*EF（E）|aE(E)规定优先顺序和结合律,46,2.6句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，完成句型分析的程序称为分析程序或识别程序。分析算法称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,47,一、句型的分析算法分类,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程。,48,1、自上而下的语法分析,例：文法G：ScAdAabAa识别输入串w=cabd是否为该文法的句子,49,2、自下而上的语法分析,例：文法G：ScAdAabAa识别输入串w=cabd是否该文法的句子,SAAcabdcabdcabd规约过程构造的推导：cAdcabdScAd,50,3、句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符是B，且有n条规则：BA1|A2|An，如何确定用哪个右部去替代B？2）自下而上分析法中，分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符，该子串称为“可归约串”,如何识别可归约串？3）存在确定和不确定分析，本课只讨论确定分析,51,4、短语、直接短语、句柄的定义,对于文法GS（1）句型的短语:S=A且A=，则称是句型相对于非终结符A的短语。（2）句型的直接短语：若有A，则称是句型相对于非终结符A的直接短语。（3）句型的句柄：一个句型的最左直接短语称为该句型的句柄。,*,+,52,语法树子树分析法：短语：任意一颗子树的叶子结点从左至右顺序排列的字符串（按给定句型排除）。直接短语：只有父子两层的子树的叶子结点从左至右顺序排列的字符串。句柄：最左最下的只有父子两层的子树的叶子结点从左至右