【教学课件】第三章文法和语言.ppt

第三章文法和语言,第一节 文法的直观概念,第二节 符号和符号串,第三节 文法和语言的形式定义,第四节 文法的类型,第五节 上下文无关文法及其语法树,第六节 句型分析,第八节 典型例题及解答,第七节 有关文法实用中的一些说明,知识结构,3.1 文法的直观概念,第三章 方法和语言,所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具,程序设计语言的描述：语法：程序的结构或形式语义：语言所代表的含义语用：语言的实际应用,例如，对于赋值语句 x:=a+b*c 的非形式描述是：语法：赋值语句变量:=表达式语义：先求右部，然后把结果给左部变量语用：赋值语句可用来计算和保存表达式的值形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法形式语言：一种不考虑含义的符号语言,程序设计语言的语义分成：静态语义：是一系列限定规则，并确定哪些合乎语法的程序是合适的动态语义（运行语义、执行语义）：表明程序要做什么，要计算什么,以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构：,例如,有一组规则:=:=:=the:=a:=big:=:=ate:=:=cat:=mouse 显然,由这一组规则可以产生句子:The big cat/mouse ate a mouse/cat,这样的语言描述称为文法使用文法作为工具，不仅为了严格地定义句子的结构，也是为了适当条数的规则把语言的全部句子描述出来，可以说文法是以有穷的集合刻画无穷的集合的一个工具,3.2 符号和符号串,一.字母表和符号串1.语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合2.字母表（符号集）：是一个非空有穷集合3.符号（字符）：字母表中的元素4.符号串：符号的有穷序列。注意：表示空符号串！5.符号串集合：字母表上若干个符号串组成的集合,重要约定：小写字母 a,b,c,r 表示符号 小写字母 s,t,u,z 表示符号串 大写字母 A,B,C,Z 表示符号串集合,二.符号串的运算1.符号串相等：设 x、y 是字母表 上的两个符号串，若 x 与 y 的诸符号依次相等，则该两符号串相等，记为 x=y,2.符号串长度：设 x 是字母表上的符号串，符号串中包含符号的个数称为符号串 x 的长度，用 x 表示例:(1).|=0;(2).|a x|=|x a|=|x|+1(a),3.符号串的连结：设 x 与 y 是字母表 上的两个符号串，把 y 的所有符号相继写在 x 的符号之后所得到的符号串称为x 与 y 的连结，用 x y 表示注意:|x y|=|x|+|y|x=x=x x y y x(一般说来),5.符号串的前缀、后缀和子串：设 x、y、z 是字母表 上的符号串，则称 x 为符号串 x y 的前缀，y 是符号 串 x y 的后缀，x、y、z、xy、yz 是符号串 x y z 的子串例:abcd,6.符号串集合的乘积：设A、B为两个符号串集合，其乘积为 AB=xy|xA,y B例:(1).若 A=ab,cd,B=ef,gh 则:AB=abef,abgh,cdef,cdgh(2).x=x=x A=A=A,7.空集：不含任何元素的集合，记为 注意:(1).A=A=;(2).,8.符号串的幂：设 x 是字母表 上的符号串，则 x 的幂运算为x 0=x 1=x x 2=xx x n=x n-1x(xx n-1)例:若 x=ab 则:x 0=,x 1=ab,x 2=abab,x n=abab ab,9.符号串集合的幂：设 A 是符号串集合，则符号串 A 的幂运算为：A0=A1=A A2=AA An=A n-1A(AA n-1)例:若 A=ab,cd 则:A 0=,A 1=ab,cd,A 2=abab,abcd,cdab,cdcd,注意:A*=A0A+A+=AA*=A*A 若 A=a,b 则:A*=,a,b,aa,ab,ba,bb,aaa,A+=a,b,aa,ab,ba,bb,aaa,3.3 文法和语言的形式定义,规则（重写规则、产生式、生成式）：一个规则是一个二元组,通常写作:=或 称为规则的左部，称为规则的右部，(:=)读作“定义为”，这是一条关于的规则（产生式）,定义3.1：文法G定义为四元组（VN，VT，P，S）VN：非终结符（语法实体、变量）集VT：终结符集P：规则（）集合，(VNVT)*且至少包含一个非终结符，(VNVT)*VN、VT、P是非空有穷集S：开始符（识别符），它是一个非终结符，至少要在一条规则中作为左部出现VNVT=V=VNVT，称为文法G的字母表（字汇表）,例3.1 文法G=（VN，VT，P，S），其中VN=S，VT=0,1，P=S0S1,S01,例3.2文法G=（VN，VT，P，S），其中VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P a z 0 9 S=,很多时候，不用将文法G的四元组显式地表示出来，而只将产生式写出,一般约定：第一条产生式的左部是识别符用尖括号括起来的是非终结符（或者用大写字母表示）不用尖括号括起来的是终结符（或者用小写字母表示）将G也写成GS，其中S是识别符,推导：定义V*中的符号之间的关系：直接推导：长度为n(n1)的推导：长度为n(n 0)的推导：,定义3.2：文法G（VN，VT，P，S），是一条规则，和是V*中的任意符号，若有符号串v，w满足：v=，w=，则称v直接推导到w，v w，或w直接归约到v例：G：S0S1，S01S 0S1 00S11 000S111 00001111,定义3.3：如果存在直接推导的序列：v=w0w1w2wn=w(n0)则称v推导出w（推导长度为n），或称w归约到V，记作,定义3.4：若有vw，或v=w，则记作：,定义3.5：若有Sx，则称x是文法GS的句型，若x仅由终结符组成，则称x为GS的句子,定义3.6：文法G所产生的语言定义为集合L(G)=x|Sx，其中S为文法识别符号，且xVT*文法描述的语言是该文法一切句子的集合例：G：S0S1，S01L(G)=0n1n|n1,例3.3文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee,L（G）=anbnen|n1,思考：a4b4e4怎么推导？,定义3.7：若L(G1)L(G2)，则称文法G1和G2是等价的例如文法GA：A0RA01RA1和文法GS：S0S1 S01等价L(G)=0n1n|n1,3.4 文法的类型,乔姆斯基(Chomsky)于1956年建立形式语言的描述他把文法分成：0型、1型、2型、3型四个文法类的定义是逐渐增加限制的,设G（VN，VT，P，S），如果它的每个产生式是这样一种结构：(VNVT)*且至少包含一个非终结符，(VNVT)*，则G是一个0型文法（短语文法、无限制文法）,思考：这样定义可以吗？设G（VN，VT，P，S），如果它的每个产生式是这样一种结构：(VNVT)+，(VNVT)*，则G是一个0型文法,重要的理论结果：0型文法的能力相当于图灵机（Turing）或者说，任何0型语言都是递归可枚举的反之，递归可枚举集必定是一个0型语言,设G（VN，VT，P，S），如果它的每个产生式均满足：|，仅仅S除外，则文法G是1型文法（上下文有关文法）例3.1、3.2、3.3,例：文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabD,L(G)=w|wa,b*,有些定义中，将上下文有关文法的产生式的形式描述为1A212，其中1、2和都在V*中，A在VN中,设G（VN，VT，P，S），如果它的每个产生式均满足：是一个非终结符，V*，则文法G是2型文法（上下文无关文法）,有时将2型文法的产生式表示为A的形式，其中AVN，也就是用取代非终结符A时，与A所在的上下文无关，因此取名为上下文无关例3.1、3.2,例3.4：文法GS：SaB|bAAa|aS|bAABb|bS|aBB,设G（VN，VT，P，S），如果它的每个产生式AB或A，其中A和B都是非终结符，VT*，则文法G是3型文法（正规文法）,例3.5：文法GS：S0A|1B|0A0A|1B|0SB1B|1|0,你会忘记我吗？,4个文法类的定义是逐渐增加限制的，因此，每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法称0型文法产生的语言为0型语言，上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言,3.5 上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式、描述各种语句等例3.6：文法G=(E,+,*,i,(,),P,E)其中P为：EiEE+EEE*E E(E)ifthen|ifthenelse,给定文法G=（VN，VT，P，S），对于G的任何句型都能构造与之关联的语法树（推导树、语法分析树、分析树）。这棵树满足下列4个条件：（1）每个结点都有一个V中的符号作标记（2）根的标记是开始符号S（3）若一结点n至少有一个它自己除外的子孙，并且有标记A，则AVN（4）如果结点n的直接子孙，从左到右的次序是结点n1,n2,nk，其标记分别为A1,A2,Ak，那么AA1A2Ak一定是P中的一个产生式,例3.7：文法G=(S，A,a,b,P,E)其中P为：(1)SaAS(2)ASbA(3)ASS(4)S a(5)A ba图3.1的推导树是文法G的句型aabbaa的推导过程把aabbaa叫做推导树的结果，把推导树叫做句型aabbaa的语法树,图3.1 推导树,文法G的句型aabbaa的推导过程：,（1）SaASaAaaSbAaaSbbaaaabbaa（2）SaASaSbASaabASaabbaSaabbaa（3）SaASaSbASaSbAaaabAaaabbaa,如果在推导的任何一步，其中、是句型，都是对中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。在形式语言中，最右推导被称为规范推导，由规范推导所得的句型称为规范句型,例：GE:E iE E+EE E*EE(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.2推导1的语法树,图3.3推导2的语法树,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的注意，文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的,判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件二义文法改造为无二义文法例3.8：GE：E T|E+T GE:E i T F|T*FE E+E F（E）|i E E*E 规定优先顺序和结合律 E(E),3.6 句型的分析,句型分析是一个识别输入符号是否为语法上正确的程序的过程在语言的编译实现中，把完成句型分析的程序称为分析程序（识别程序），分析算法又称为识别算法介绍的分析算法都称之为从左到右的分析算法分析算法分为：自上而下分析法：从文法的开始符号出发，反复使用各种产生，寻找匹配于输入串的推导自下而上的方法：从输入符号串开始，逐步进行归约，直到归约到文法的开始符号,一.自上而下分析方法例3.9考虑文法GS（1）ScAd（2）Aab（3）Aa识别输入串w=cabd是否该文法的句子所构造的推导过程为：ScAdcabd,图3.4自上而下的分析步骤,二.自下而上分析方法例3.9考虑文法GS（1）ScAd（2）Aab（3）Aa识别输入串w=cabd是否该文法的句子所构造的推导过程为：ScAdcabd,图3.5自下而上的分析,三.句型分析的有关问题在自上而下的分析中，对于例3.9的文法，在扩展A时，有两个选择，如果选择另一个，推导序列为ScAdcad，语法树如图3.6所示这时，就与w=cabd不符，宣告失败应该用哪条规则去替换呢？一种解决办法从各种可能的选择中随机挑选一种，并希望它是正确的，如果失败，退回去，再试另一种，这种方式称为回溯。显然这种方式代价极高，效率很低,图3.6 cad的语法树,在自下而上的分析中，对于例3.9的文法，在归约的时候，也存在选择哪一条规则进行归约的问题，因此需要精确定义“可归约串”。事实上，存在种种不同的方法刻画“可归约串”。对这个概念的不同定义形成了不同的自下而上分析文法。在一种“规范归约”的分析中，这种“可归约串”称作“句柄”,定义3.8令G是一文法，S是文法的开始符号，是文法G的一个句型。如果有：S A且A 则称是句型相对于规则A 的直接短语（简单短语）。一个句型的最左直接短语称为该句型的句柄,例GE:E T|E+T T F|T*F F（E）|i句型i*i+i短语：i1、i2、i3、i1*i2、i1*i2+i3直接短语：i1、i2、i3句柄：i1,3.7 有关文法实用中的一些说明,一.有关文法的实用限制有害规则：形如UU的产生式多余规则：文法中那些连一个句子的推导都用不到的规则某些非终结符不在任何规则的右部出现（不可到达的）不能够从这些非终结符推出终结符号串（不可终止的）,例3.10文法GS：（1）SBe（2）BCe（3）BAf（4）AAe（5）Ae（6）CCf（7）Df,对文法G=(VN,VT,S,P)来说，为了保证其任一非终结符A在句子推导中出现，必须满足如下两个条件：A必须在某句型中出现。即SA,其中,属于V*必须能够从A推出终结符号串t。即At,其中tVT*,二.上下文无关文法中的规则规则：形如A 的产生式，其中AVN某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂两种定义的唯一差别是句子在不在语言中如果语言L有一个有穷的描述，则L也同样有一个有穷描述。并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言,定理3.1若L是由文法G=(VN,VT,P,S)产生的语言，P中的每一个产生式的形式均为A,其中AVN，V*，则L能由这样的一种文法产生，即每一个产生式或者为A形式，其中AVN，V+,或者 S形式，且 S不出现在任何产生式右边,定理3.2如果G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边又如果G是一个上下文无关文法，也能找到这样一个上下 文无关文法G1如果G是是一个正规文法，则也能找到这样一个正规文法 G1,3.8 典型例题及解答,1.证明文法G=(E,O,(,),+,*,v,d,P,E)是二义的E EOE|(E)|v|dO+|*2.考虑下述两个语言L1=anb2ncm|n,m=0L2=anbmc2m|n,m=0通过分别给出上述语言的文法来证明这些语言都是上下文无关的,【本章小结】本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的“形式”的含义-只涉及语言的语法不涉及语言的语义.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,考察本章知识点最典型的题目是：已知文法GA，写出它定义的语言描述GA:A 0B|1CB 1|1A|0BBC 0|0A|1CC答案:GA定义的语言由0、1符号串组成，串中0和1的个数相同。给出语言描述，构造文法。构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案1:GE EE+T|TTT*F|FF(E)|a答案2:GE EE+E|E*E|(E)|a,编译原理第3章习题第1题：写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。第2题：证明下述文法G表达式是二义的。表达式=a|(表达式)|表达式运算符表达式 运算符=+|-|*|/第3题：令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。,第4题：给出生成下述语言的上下文无关文法：（1）anbnambm|n，m=0（2）1n0m 1m0n|n，m=0第5题：给出生成下述语言的三型文法：(1)anbm|n,m=1(2)anbmck|n,m,k=0 第6题：给出下述文法所对应的正规式：S0A|1BA1S|1 B0S|0,第3章作业题P47：1.6.(5)(6)8.9.13.14.,