编译原理课程设计之第三章上下文无关文法及分析.ppt
mcy,1,课程内容第一章 概论第二章 词法分析第三章上下文无关文法及分析第四章自上而下的语法分析第五章自下而上的语法分析第六章语义分析第七章运行时环境第八章代码生成,mcy,2,第三章 上下文无关文法及分析,本章的目的是为语言的语法描述寻求形式工具，要求该工具对程序设计语言给出精确无二义的语法描述。,mcy,3,3.1 语法分析过程3.2 上下文无关文法的形式定义3.3 二义性文法,形式工具,作业,第三章 上下文无关文法及分析,mcy,4,语法分析以词法分析程序输出的单词序列为输入，分析源程序的语法结构，判断它是否为相应程序设计语言的合法程序。通常语法分析的结果是构造出表示该语法结构的分析树（parse tree）或语法树(syntax tree)。语法分析阶段可以确定单词流中违反源语言语法结构规则的错误。,语法分析程序的任务：,3.1 语法分析过程,mcy,5,如何来描述一种语言(符号串的集合)？,如果语言是有穷的(只含有有穷个句子)，可以将句子逐一列出来表示。,如果语言是无穷的，找出语言的有穷表示。,mcy,6,语言的有穷表示有两个途经：,生成方式(文法)：语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机)：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,mcy,7,Number=digit digit*Digit=0|1|2|3|4|5|6|7|8|9,正规表达式：？,有穷自动机：？,寻求程序设计语言语法结构的形式化描述：,mcy,8,Noam Chomsky研究了自然语言的结构，提出了一种用来描述语言的数学系统(Chomsky文法)，并以此定义了四类性质不同的语言，称为语言（文法）的Chomsky分类。,mcy,9,Chomsky文法分为四个层次：0型，1型，2型和3型文法。其中2型文法（或上下文无关文法）被证明是程序设计语言中最有用的。今天2型语言已代表着程序设计语言语法结构的标准方式。,mcy,10,Chomsky文法就是用生成方式来描述语言的：语言中的每个句子可以用严格定义的规则来构造。,文法示例：简单句子的语法结构可有以下规则表示:,mcy,11,问:下面的语句是否是一个符合上述语法结构的简单句子？The big elephant ate the peanut.冠词 形容词 名词 动词 冠词 名词我们把上述两个字符串中间用一箭头分隔构成的有序对称为产生式。其中，“”表示“由组成”,“”也可以用=，:=，:来代替。,mcy,12,例如：包含加法、减法和乘法的简单整型算术表达式的语法结构可由下面的上下文无关文法(2型文法)给出：exp exp op expexp(exp)exp numberop+|-|*,mcy,13,3.1 语法分析过程3.2 上下文无关文法的形式定义3.3 二义性文法,形式工具,作业,第三章 上下文无关文法及分析,mcy,14,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,15,终结符集合VT非终结符集合VN(与VT不相交)产生式或文法规则A形成的集合P,其中AVN,(VTVN)*开始符号S，其中SVN令G是一个如上所定义的文法，则G=(VT,VN,P,S),产生式的左部,产生式的右部,上下文无关文法(即2型文法)的形式定义：上下文无关文法是一个四元组(VT,VN,P,S)：,mcy,16,例 G1=(N,0，1,其中:非终结符集合：VN=N,终结符集合：VT=0，1,产生式的集合：P=N0N，N1N，N0，N1,开始符号为：N,文法举例,N0N,N1N,N0,N1,N）,mcy,17,通常情况下，文法只用产生式的集合表示：,G1N:N0N N1N N0 N1,G1N:N0N|1N|0|1,也可写成：,mcy,18,文法Gexpexp exp op expexp(exp)exp numberop+|-|*的终结符、非终结符、开始符号分别为？,mcy,19,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,20,chomsky文法的分类,通过对产生式施加不同的限制，chomsky将文法分为四种类型：,0型文法：若文法G中任一产生式，都有(VNVT)+，(VNVT)*，则称G为0型文法1型文法：若文法G中任一产生式，都有(VNVT)+，(VNVT)*|，仅仅 S除外，则称G为1型文法2型文法：若文法G中任一产生式，都有VN，(VNVT)*，则称G为2型文法，也称为上下文无关文法,mcy,21,3型文法：通常，我们把右线性文法及左线性文法统称为3型文法或正规文法。若文法G中任一产生式的形式都为AaB 或 Aa，其中 AVN，BVN，aVT，则称G为右线性文法；类似地，如果G中仅含有形如ABa 或 Aa的产生式，则称G为左线性文法；,mcy,22,例：1型（上下文有关）文法 文法GS：SCD AbbA CaCA BaaB CbCB BbbB ADaD C BDbD D AabD,mcy,23,例：2型（上下文无关）文法 文法GS：SAB ABS|0 BSA|1,mcy,24,GS：S0A|1B|0 A0A|1B|0S B1B|1|0,例：3型（上下文无关）文法,mcy,25,文法Gexp：exp exp op expexp(exp)exp numberop+|-|*,下面的2型文法描述了包含加法、减法和乘法的简单整型算术表达式的语法结构。,34-3 是符合该语法结构的简单整型算术表达式(句子)吗？,mcy,26,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,27,推导和规约的定义,用产生式(规则)按一定方式产生句子的过程：exp exp op exp number op exp number-exp number-number,mcy,28,直接推导“”或一步推导若有v,w满足：v=,w=其中：是文法G的产生式，(VT VN)*,(VT VN)*则称v直接推导到w,记作 v w，称w直接归约到v。注：直接推导就是产生式规则的一次运用，即用产生式的右部替换左部。,mcy,29,例：GS：S0S1，S01 直接推导：,S 0S1,0S1 00S11,00S11 000S111,000S111 00001111,mcy,30,推导的定义,若存在v=w0w1.wn=w(n0),我们用v=+w表示一步或多步推导，称v推导出w，或w归约到v；若有v=+w，或v=w，则记为v=*w，表示零步或多步推导。,mcy,31,例：GS：S0S1，S01,S 0S100S11000S11100001111,S+00001111,给出字符串00001111的一个推导：,mcy,32,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,33,定义4 句型和句子:设G=(VN,VT,P,S)是一文法,且 V=VNVT,若S=*,V*,则称为文法G的句型；若S=+,VT*,则称为文法G的句子；,句型和句子的定义,mcy,34,简单整型算术表达式文法：exp exp op exp|(exp)|numberop+|-|*给出算术表达式（34-3）*42的一个推导，请列出推导过程中出现的句型和句子。,mcy,35,算术表达式（34-3）*42的推导：exp exp op exp exp op number exp*number(exp)*number(exp op exp)*number(exp op number)*number(exp-number)*number(number-number)*number,mcy,36,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,37,最左和最右推导,最左推导 对于文法GS:S*是一个最左推导是指：在推导过程中的任何一步直接推导，都是对字符串中的最左非终结符进行替换，其中、是句型。简单整型算术表达式文法：exp exp op exp|(exp)|number op+|-|*,mcy,38,exp exp op exp(exp)op exp(exp op exp)op exp(number op exp)op exp(number-exp)op exp(number-number)op exp(number-number)*exp(number-number)*number,算术表达式（34-3）*42的最左推导：,mcy,39,最右推导：S*是一个最右推导是指：在推导过程中的任何一步直接推导，都是对字符串中的最右非终结符进行替换，其中、是句型。最右推导也被称为规范推导。由规范推导所得的句型称为规范句型。,mcy,40,算术表达式（34-3）*42的最右推导：exp exp op exp exp op number exp*number(exp)*number(exp op exp)*number(exp op number)*number(exp-number)*number(number-number)*number,mcy,41,expexp op exp number op exp number+exp number+number,简单整型算术表达式文法：exp exp op exp|(exp)|numberop+|-|*,给出符号串3+4的最左推导:？,mcy,42,expexp op exp exp op number exp+number number+number,给出符号串3+4的最右推导？,mcy,43,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,44,文法定义的语言,文法定义的语言：根据文法可以推导出任一句型和句子，而所有句子的集合则为该文法所对应的语言；即语言是所有句子构成的集合，它是所有终结符号串所组成的集合VT*的子集。,mcy,45,文法GS定义的语言L(G)表示为：L(G)=x|S=+x,其中S为开始符号,x VT*L(G)VT*即L(G)是由开始符号S推导出的句子的集合。上下文无关文法定义的语言称作上下文无关语言。,mcy,46,文法定义的语言举例例1：有文法GZ:(1)Z aZb(2)Z ab它定义的语言是什么？,由(2)知:Zab 故ab是文法的一个句子,mcy,47,由(1)(2)知:ZaZba2b2 故a2b2是文法的一个句子反复使用产生式(1)：ZaZba2Zb2 an-1Zbn-1 anbn所以上述文法所定义的语言为：L(GZ)=anbn|n1,mcy,48,例2：已知语言为 L(G)=abna|n1 试给出其文法。,G1Z:Z aBa B bB|b,G2Z:Z aBa B Bb|b,结论：给定一种语言L，能确定其文法，但这种文法可能不是唯一的：LG1或G2等价文法：如果L(G1)=L(G2)，那么称G1和G2为等价文法。,mcy,49,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,50,设给定文法G=(VN,VT,P,S),若存在产生式AxAyP，则称产生式AxAy是递归产生式；x，y(VNVT)*,若x=且y,则称产生式AAy是左递归产生式；若x且y=,则称产生式AxA是右递归产生式。,递归产生式和递归文法,mcy,51,递归文法：若文法中至少存在一条递归产生式则称该文法是直接递归的文法；若有A+xAy,x,y(VNVT)*则称文法为间接递归的文法。即对于文法中任一非终结符号，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符号本身，则文法是递归的。一般的文法都是递归的，文法G只有递归定义，L(G)中的句子才是无穷的。,mcy,52,例：有文法GS:S aB|bBB a|b是否是递归文法，定义的语言为？,非递归文法，L(GS)=aa,ab,ba,bb,mcy,53,3.2 上下文无关文法的形式定义,上下文无关文法(即2型文法)的形式定义chomsky文法的分类推导和规约的定义句型和句子的定义最左和最右推导文法定义的语言递归产生式和递归文法文法和语言,mcy,54,文法和语言,0型文法产生的语言称为0型语言，它可由图灵机识别。1型文法或上下文有关文法(CSG）产生的语言称为1型语言或上下文有关语言(CSL)，它可由线性线界自动机识别。2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL），它可由下推自动机识别。,mcy,55,3型文法或正则(正规)文法(RG)产生的语言称为3型语言正则(正规)语言(RL)，它可由有限自动机识别。语言之间的关系依次：有不是1型语言的0型语言，有不是2型语言的1型语言，有不是3型语言的2型语言。,mcy,56,Number=digit digit*Digit=0|1|2|3|4|5|6|7|8|9,正规式Number定义的正规集？,Number(0|1|2|3|4|5|6|7|8|9)NumberNumber 0|1|2|3|4|5|6|7|8|9,例如，3型文法(正规文法)产生的语言？,mcy,57,对上的正规式r,存在一个3型文法G=(VN，VT，P，S)：L(G)=L(r)对3型文法G=(VN，VT，P，S),存在一个=VT上的正规式r:L(r)=L(G)设G=（VN,VT,P,S）是3型文法，则存在一个有穷自动机 M=(S,T,s0,A)，使得L(M)=L(G)已知一有穷自动机M=(S,T,s0,A),存在有一个3型文法G=(VN,VT,P,S),使得L(G)=L(M)。,与3型文法有关的定理,mcy,58,对上的正规式r,存在一个3型文法G=(VN，VT，P，S)：L(G)=L(r),初始令VT=，引入开始符号S，生成正规产生式 Sr 对形如Ar1r2的正规产生式：Ar1B Br2 BVN,mcy,59,对形如Arr1的正规产生式：ArB Ar1 BrB Br1 BVN,mcy,60,对形如Ar1r2的正规产生式:Ar1 Ar2 不断应用2)、3)、4)做变换，直到每个产生式都符合3型文法的要求；,mcy,61,例 r=a(ad),Sa(ad),A(ad),mcy,62,对上的正规式r,存在一个3型文法G=(VN，VT，P，S)：L(G)=L(r)对3型文法G=(VN，VT，P，S),存在一个=VT上的正规式r:L(r)=L(G)设G=（VN,VT,P,S）是3型文法，则存在一个有穷自动机 M=(S,T,s0,A)，使得L(M)=L(G)已知一有穷自动机M=(S,T,s0,A),存在有一个3型文法G=(VN,VT,P,S),使得L(G)=L(M)。,与3型文法有关的定理,mcy,63,AxB,By A=xy,AxAy A=xy,Axy A=xy其中，A,BVN x,yVT,对3型文法G=(VN，VT，P，S),存在一个=VT上的正规式r:L(r)=L(G),mcy,64,例：Gs:SaA|a,AaAadAd,A(ad)A(ad),A=(ad)(ad),S=a(ad)(ad)a,=a(ad)(ad),=a(ad),R=a(ad),mcy,65,对上的正规式r,存在一个3型文法G=(VN，VT，P，S)：L(G)=L(r)对3型文法G=(VN，VT，P，S),存在一个=VT上的正规式r:L(r)=L(G)设G=（VN,VT,P,S）是3型文法，则存在一个有穷自动机 M=(S,T,s0,A)，使得L(M)=L(G)已知一有穷自动机M=(S,T,s0,A),存在有一个3型文法G=(VN,VT,P,S),使得L(G)=L(M),与3型文法有关的定理,mcy,66,设G=（VN,VT,P,S）是3型文法，则存在一个有穷自动机 M=(S,T,s0,A)，使得L(M)=L(G),有穷自动机NFA M 构造方法：=VTS=VN N,N为一个新状态,它不在VN中s0=S A=N,mcy,67,对G中的形如DtB的产生式,t为终结符,有T(D,t)=B对G中形如Dt的产生式,t为终结符或,有 T(D,t)=N对VT中的每一个a,有T(N,a)=,mcy,68,G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b,mcy,69,对上的正规式r,存在一个3型文法G=(VN，VT，P，S)：L(G)=L(r)对3型文法G=(VN，VT，P，S),存在一个=VT上的正规式r:L(r)=L(G)设G=（VN,VT,P,S）是3型文法，则存在一个有穷自动机 M=(S,T,s0,A)，使得L(M)=L(G)已知一有穷自动机M=(S,T,s0,A),存在有一个3型文法G=(VN,VT,P,S),使得L(G)=L(M),与3型文法有关的定理,mcy,70,所求文法G的构造方法：VT=VN=SS=s0若T(D,t)=B，则产生式DtB加入P中,如果BA，则将产生式Dt也加入P中,已知一有穷自动机M=(S,T,s0,A),存在有一个3型文法G=(VN,VT,P,S),使得L(G)=L(M),mcy,71,G：SaA|bB AbB|aD BaA|bD DaD|bD,B,A,S,a,a,a,b,b,a,b,b,|b,|a,|a,|b,mcy,72,3.1 语法分析过程3.2 上下文无关文法的形式定义3.3 二义性文法,作业,第三章 上下文无关文法及分析,mcy,73,3.3二义性文法,对于文法G，若存在某个句子wL(G),w对应多个不同的最左（或最右）推导(即w对应两个结构不同的分析树,详见4.1节)，这类文法称为二义性文法。,mcy,74,例1，GE：EE+E|E*E|(E)|i 的句子i+i*i对应两个最右推导(即两个结构不同的分析树)，故该文法是二义性文法。,mcy,75,例2，文法GC Cif B then C|if B then C else C C S句子 if B1 then if B2 then S1 else S2对应两个最右推导(有两个结构不同的分析树)，所以，它也是二义性文法。,mcy,76,mcy,77,由于二义性文法不能准确地指出程序设计语言的语法结构，所以它是分析程序表示的一个严重问题。为解决二义性文法的不确定性，通常有两种方法：修改文法常用设置消除二义性规则(优先权和结合性),关于二义性文法的几点声明,mcy,78,任一前后文无关文法是否是二义性的是不可判定的。但存在一些判定文法是否二义性的充分条件：若一文法含有既是左递归又是右递归的文法符号，即有A+AvA v(VNVT)*或A+A 或A+A 及 A+A 则G必定是二义性的。,mcy,79,本章小结,本章给出了chomsky文法的形式定义,其中2型文法(即上下文无关文法)是描述程序设计语言语法的形式化工具；3型文法是是描述程序设计语言词法的形式化工具；举例：一个简化的C+类声明的语法的形式化定义,mcy,80,作业,_是描述程序设计语言语法结构的形式工具。设G=(VN，VT，P，S)是一文法，且 V=VNVT，若S=*，V*，则称为文法G的，若S=*，VT*，则称为文法G的。,两个文法G1S和G2S等价，当且仅当 _。给出语言L=aibj|ji=1的上下文无关文法;,mcy,81,文法GS的产生式如下：S-S+S S-S*S S-i S-(S)对于输入串 i+i*i:(1)给出一个推导；(2)画出一棵分析树；(3)文法G是否是二义性的，请证明你的结论。,
