编译原理讲义(第二章文法与语言).ppt

编译原理讲义(第二章:文法与语言),南京大学计算机系赵建华,文法与语言,文法被用来精确而无歧义地描述语言的句子的构成方式.文法描述语言的时候不考虑语言的含义。,字母表,定义：字母表是有穷非空集合。字母表包含了语言中所允许出现的一切符号。,符号串,定义：符号串是由字母表中的符号所组成的有穷序列。一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合而成的。语法分析的一个重要任务就是：判断一个符号串的组成是否满足某个文法的规定，并且分析出是如何按照规则组成的。,关于符号串的概念和操作,运算：联结(并置)：x=123,y=45那么xy=12345方幂：x的n次方幂即将n个x联结。子符号串：v是xvy的子符号串。v非空头，尾：x是xy的头，y是xy的尾。,符号串集合,定义：若集合A中的一切元素都是同一个字母表上的集合，那么A被称为该字母表上的符号串集合。在本课程中，语言被认为是句子的集合。（外延定义？）所以，一个语言就是对应于它的字母表上的一个符号串集合。,符号串集合的运算,乘积：AB=xy|xA且y B方幂：A的n次方幂就是将n个A相乘。字母表的闭包与正闭包：字母表A的闭包是A上的所有符号串（包括空字符串）的集合。字母表A的正闭包是A上的所有的非空符号串的集合。,文法和语言的定义（重写规则）,重写规则：一个重写规则是一个有序对(U,u)，通常写作U:=u。其中U是一个符号，称为左部；u是一个符号串称为右部。有时也说这个规则是U的一个规则。重写规则总是基于某个字汇表的。U和u中的符号必须都在这个字汇表内。这个字汇表中有些符号不能作为左部。存在更加复杂的规则，但是这样的规则足够描述程序设计语言的文法。,文法和语言的定义（重写规则）,例如:标识符:=字母标识符:=字母|标识符字母第二个规则实际使用了BNF的表示方法。BNF表示方法的还包括:花括号表示重复:字母方括号表示可选:参数,文法和语言的定义（文法）,文法：文法GZ是一组有穷非空的重写规则的集合。其中Z称为识别符号。G为文法名字文法例子：P22,例子2.10。所有的规则都是基于同一个符号表V。符号表又可分划非终结符号集合VN和终结符号结合VT。,句子:=:=:=Peter|Berry|River:=:=Swims:=in:=,文法和语言的定义（推导）,文法的作用是描述某种语言的句子的构成方式。使用文法我们可以产生对应语言的句子。从识别符号开始，不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。,文法和语言的定义（推导）,例子：句子=主语谓语状语=名词谓语状语=Peter swims in river,文法和语言的定义（推导）,直接推导：v=xUy，w=xuy，并且U:=u是文法中的一个重写规则，那么我们说v可以直接推导到w，或者w可以直接规约到v。记作 v=w。例如：主语谓语状语=名词谓语状语,文法和语言的定义（推导）,推导：对于符号串v和w，如果存在一个直接推导序列u0=u1=un，并且u0=v，un=w，那么我们说v可以推导到w，或者w规约到v。记作v=+w。这个推导长度为n，且称w为对应于v的一个字。v=*w表示v=w或者v=+w。,文法和语言的定义（推导）,推导的例子：P25页例2.12。文法：:=:=|:=0|1|2|3|9VT0,1,2,3,4,5,6,7,8,9,VN=,推导的例子,=23=123,语言的定义（句型,句子）,对于文法GZ，x称为G的一个句型如果：Z=*x识别符号是最简单的句型。GZ的一个句型x被称为句子，如果：xVT*也就是说句子是全部由终结符号组成的句型。,语言的定义（短语，简单短语）,短语：对于文法GZ，如果Z=*xUy，U=+u。显然，w=xuy是一个句型。我们称u是句型w中相对于U的短语。简单短语：在上面的定义中，如果U:=u是G的一个规则，那么，u是句型w中相对于U的简单短语。例子：P22页例2.13。,语言的定义（短语，句柄）,注意：在寻找一个句型的短语（或简单短语）时，必须要求将这个短语规约为相应的非终结符号后所得到的符号串仍然是句型。句柄：一个句型的最左简单短语称为该句型的句柄。定义句柄的原因：在自底向上识别一个符号串时，总是规约这个句柄。,语言的定义（文法的语言）,文法的语言：一个文法GZ的语言，用L(GZ)表示，定义如下：L(GZ)=x|Z=*x 并且 x VT+一个文法的语言就是该文法的所有的句子的集合。文法的语言是所有终结符号串所组成的集合的子集，一般是真子集。,语言的定义（递归与语言）,递归的规则：U:=U左右递归规则：U:=U；U:=U文法的递归：U=+U，称文法递归于U。文法的左右递归：如果文法是非递归的，那么其语言是有穷的。,文法与语言（例子）,GA：A:=bA|a；L(GA)=bia|i=0GZ：Z:=Ab；A:=aaA A:=aaL(GZ)=a2nb|n=1,语言的分类,Chomsky文法的定义：(VN,VT,P,Z)该定义是我们前面讲的定义的一个更加形式化的表达。在这个定义中，文法规则的左部可以是一个非空符号串。Chomsky文法被分为四类，我们主要用2型和3型文法。,Chomsky文法类（0型文法PSG）,0型文法的规则形如：u:=v，u,v为符号串，且u非空。0型文法的相应语言称为0型语言，又称为递归可枚举集合。0型语言是不可判定的。例子：G：Z:=#A1#；#A:=#；A1:=11A；A#:=B#；1B:=B1；#B:=#AL(G)=#1i#|i=2n,n=0,Chomsky文法类（1型文法CSG）,1型文法的规则如下：xUy:=xuy，其中U为非终结符号，x,y,u为符号串，且u非空。1型文法又称为上下文相关文法。1型文法也可以如下定义：所有的规则的右部都不比左部短。1型文法是可判定的。但是现在没有找到有效的方法。,Chomsky文法类（2型文法CFG）,2型文法的规则有如下形状：U:=u，其中U是非终结符号，u是符号串。2型文法又称为上下文无关文法。一般的程序设计语言的语法都使用2型文法描述。2型文法是可判定的，且又有效的判定方法。,Chomsky文法类（3型文法RG）,文法规则的形状：U:=T或者U:=WT，其中U，W是非终结符号，T是终结符号。3型文法又称为正则文法，其语言也称为正则语言。,语言类对运算的封闭性,给定某个语言类中的语言，如果对它们进行某种运算之后得到的新语言仍旧是该类语言，那么该语言类对此运算封闭。所有语言类对并，乘积，闭包运算封闭。CFG语言类对交，补运算不封闭。正则语言类对交并补运算封闭。,3型语言与有穷自动机,任何一个3型语言都可以使用一个有穷自动机来识别。有穷自动机包括一个有限控制器，和一个输入带。机器从输入带从左到右逐个读入输入符号，最终根据有限控制器的状态确定输入的符号串是否是该型语言的句子。机器的每一个动作根据当前读入的符号和当前状态确定。,有穷自动机例子,a,a,c,b,b,abcabcaabc,2型语言与下推自动机,任何一个2型语言都可以使用一个下推自动机来识别。下推自动机相当与一个有穷自动机和一个栈。自动机的每一步动作根据栈顶的符号，当前读入的符号，一个有限控制器的当前状态来确定，可以包括读入符号，压栈，出栈，和确定接受。,形式语言与程序设计语言,虽然程序设计语言的语法都使用上下文无关文法来描述，但是通常语言都是上下文相关的。使用上下文无关文法描述语言的原因是：存在高效处理上下文无关文法的技术。,关于CFG的进一步讨论,Chomsky范式：所有的上下文无关语言都可以用如下形式的文法产生：所有的规则都形如：U:=VW 或者 U:=T，其中U,V,W为非终结符号，T为终结符号。Greibach范式：所有上下文无关语言都能由这样的文法产生：U:=Tu，这里U为非终结符号，T为终结符号。,关于CFG的进一步讨论,自嵌套：一个上下文无关文法为自嵌套的，如果存在一个非终结符号U满足:U=*xUy，且x,y非空。定理2.6若一个CFG GZ不是自嵌套的，那么L(G)必然是一个正则语言。但是，自嵌套的上下文无关文法也可能产生正则语言。例:P35页,关于推导的性质,定理2.7 对于CFG，如果存在句型x=x1x2xn且x=*y，必然存在y1,y2,yn使得:xi=*yi且y=y1y2yn。定理2.8 如果:x=*y，如果x的首符号是终结符号，则y的首符号也是终结符号；反之，如果y的首符号是非终结符号，那么x的首符号也是非终结符号。,空规则,定理2.9 设L是由上下文无关文法G=(VN,VT,P,Z)产生的语言，P中可能包含空规则，则L能由这样的文法产生，在这样的文法中每一个规则或者是U:=u，或者Z:=空.这个定理表示：在语言中增加和删除一个空串，并不会改变语言的类别。,文法等价,定义：设G和G是两个文法，如果L(G)等于L(G)，那么我们说G和G等价。例子：GS S:=ABC A:=Aa|a B:=Bb|b C:=Cc|cGS S:=Sc|Bc B:=Bb|Ab A:=Aa|a两个CFG文法是否等价是不可判定的。,文法的等价变换,当有些技术不能处理一种文法时，我们可以将它处理为另外一个等价文法来处理。这就是等价变换。使文法和语言类一致。消除二义性。使文法适用于某种分析技术。文法满足某种特殊需要。,文法等价变换的种类,压缩文法等价变换增广文法等价变换范式文法等价变换消去左递归等价变换,压缩文法等价变换,主要作用是删除文法中不可能被使用的规则，称为多余规则。包括：规则的左部不可能在句型中出现。使用了此规则之后，句型永远也不能推导得到句子。一个规则U:=u不是多余的，当且仅当：Z=*xUy，且（条件1）U=+t,且t是终结符号串。（条件2）,压缩文法等价变换,已压缩文法定义：没有多余规则的文法称为压缩了的（或已压缩的）文法。压缩算法：算法重复执行下面两个部分，直到不能删除更多的规则：删除不满足条件一的规则。（子算法1）删除不满足条件二的规则。（子算法2）,压缩文法等价变换（子算法1）,步骤1：对规则中识别符号z加标记；步骤2：对左部非终结符号加有标记的规则，将其右部中的所有非终结符号加标记。步骤3：检查是否一切非终结符号都加过标记。是，结束；否，执行步骤4。步骤4：如果上一次步骤2中没有多加标记，删除所有左部没有加标记的规则，结束。否则，转向步骤2。,压缩文法等价变换（子算法1）,例子：Z:=BeA:=AeA:=eB:=CeB:=AfC:=CfD:=f,压缩文法等价变换（子算法2）,步骤1：对uVT+的规则U:=u的左部非终结符号U加标记。步骤2：对右部仅包含终结符号和已加标记的非终结符号的规则的左部加标记。步骤3：检查是否对一切非终结符号加过标记。是，结束；否则，执行步骤4。步骤4：如果上一次步骤2执行时没有多加任何标记，那么删除左部没有加标记的规则，否则，转到步骤2。,压缩文法等价变换（子算法2）,例子：Z:=BeA:=AeA:=eB:=CeB:=AfC:=Cf,增广文法等价变换,一般来讲，以识别符号为左部的规则有多个。在规约的时候使用的规则也时不唯一的。增广文法变换使得文法只有一个以识别符号为左部的规则。变换方法：GZ变换为GZ，且增加规则Z:=Z。有时候，新的规则为Z:=Z#。此时所得到的语言有所不同。是一种变换的特例：P40页。,消单规则等价变换,目的：提高分析算法的效率。注意：单规则有时是有用的，但是，太多的单规则会影响分析的效率。算法的基本思想是：首先，对于每个U，求解出所有的V，使得U=*V。对于所有的U=*V，且V:=u，增加规则 U:=u，得到的文法依旧是等价的。,消单规则等价变换（算法）,步骤1：对每个UVN，构造NU=V|U=*V，V VN步骤2：构造P=Ui:=u|V:=u P,V NU,|u|1或uVN步骤3：新的不含单规则的文法为：（VN,VT,P,Z),消单规则等价变换（例子）,G2.10E：E:=E+TE:=TT:=T*FT:=FF:=(E)F:=iNE=E,T,F E:=E+T|T*F|(E)|i.,习题,GA A:=aAb|ab,证明：L(G)=anbn设计文法：anbmcmdn,Chomsky范式范式变换,步骤1：消单规则。步骤2：变换成为：U:=T 或者 U:=V1V2Vm步骤3：引入新的非终结符号。U:=V1V2Vm修改为 U:=V1W1；W1:=V2W2；Wm-1:=Vm-1Vm；,Chomsky范式范式变换（例子）,步骤1：对于文法G2.10E，消除单规则:E:=E+T E:=T*F E:=(E)E:=i 步骤2：引入规则A:=+M:=*原来的规则变为:E:=EAT E:=TMF 步骤3：原来的规则变为:E:=EB B:=AT.,消规则左递归等价变换,改写规则左递归成为右递归将E:=E+T|T改写为:E:=TEE:=+TE|,消规则左递归等价变换(例子),E:=E+T|TT:=T*F|FF:=(E)|i变换得到如下文法:E:=TEE=+TE|T:=FTT=*FT|F:=(E)|i,消规则左递归等价变换(BNF),沿用扩充BNF表示法 E:=E+T|T 改写为E:=T+T步骤1：提取左因子：U:=ux|uy|uz=U:=u(x|y|z)步骤2：假定U:=x|y|z|Uu；替换为U:=(x|y|z)u,消规则左递归等价变换(例子2),E:=T|-T|E+T|E-T步骤1：提因子E:=(T|-T)|E(+T|-T)步骤2：E:=(T|-T)+T|-T或者E:=(-|)T(+|-)T,消文法左递归(方法),要求：文法不包含回路，无空规则步骤1：排列非终结符号U1,U2,Un步骤2：执行程序（见下一页）步骤3：删除无用规则。原理：将非终结符号排序之后，消除所有形如Ui:=Ujx的规则，其中i=j。这样，对于任何非终结符号Ui，如果Ui=+Ujx，必然有ji。不可能有文法左递归。,消文法左递归(步骤2的程序),For(i=1;I=n;I+)for(j:=1;j=i-1;j+)将形如Ui:=Ujr的规则改写为Ui:=xj1r|xj2r|xjkr 消除Ui的规则左递归，新的规则加 入文法。,消文法左递归(步骤2的解释),在改写规则的时候，对于每个i,得到的规则保证：Ui:=Ujx时，必然有ji。改写的规则也包括新加入的规则。,消文法左递归（例子）,S:=Sa|Tbc|TdT:=Se|gh步骤1：排序:ST步骤2：循环：i=1,j=1;消除规则左递归。i=2,j=1;消除T:=Sx的情况，并消除规则左递归。步骤3：,语法树的概念,定义：语法树是这样的一个语法结构，它的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。,语法树的相关概念,结点：每个树的结点对应于一个符号。结点的名字就是该符号。边：两个结点之间的连线。根结点：没有边进入的结点。分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）子树：语法树的某个结点和它向下射出的部分。,语法树的相关概念（续）,末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。,语法树的例子,语法GS:S:=ABA:=aAb|abB:=cBd|cd,S,A,B,a,b,c,B,d,c,d,S=AB=abB=abcBd=abccdd,从推导构造语法树,步骤1：根结点为识别符号。步骤2：对于每一次推导使用的规则U:=u，找出U对应的结点（此时应该是末端结点），从该结点向下画分支，子结点从左到右分别是u中从左到右的符号。重复步骤2直到推导的最后一步。,语法树中子树的性质,定理2.12：一个子树的末端结点的组成的符号串是相对于子树的根结点的短语。如果这个子树的高度是1（两层）的话，其末端结点组成的符号串是根结点的简单短语。,从语法树构造推导,构造的过程是一个剪枝的过程。每剪掉一个分支，添加一步规约过程。首先，任意找一个高度为1的子树，确定这个子树对应的规则。将子树的分支剪掉，得到一个新的语法树。该语法树的末端结点对应的符号串就是经过一步规约之后得到的句型。如此循环，直到语法树只剩下一个根结点。,从语法树构造推导（续）,同一棵语法树可以得到不同的推导，但是其实质上是使用规则的顺序不同。这些推导的过程实际是等价的。例如：S=AB=AcBd=Accdd=abccddS=AB=abB=abcBd=abccdd,文法的二义性,定义：如果对于某文法的同一个句子存在两棵不同的语法树，则该句子是二义性的。而该文法是二义性文法。这里的二义性是指语法结构上的。如果一个句子具有二义性，那么对这个句子的结构可能有多种正确的解释。通常情况下，句子的语义要通过其语法结构来定义，所以，二义性一般是有害的。,文法二义性（例子）,文法GE：E:=E+E|E*E|(E)|i文法的句子:i+i*i，其语法树如下：,E,E,+,E,E,*,E,二义性,一般来讲，二义性是针对文法而言的，说语言二义性是无意义的。定义2.35：如果某个语言对应的文法都是二义性的，那么这个语言被称为先天二义性的。定理2.13：文法的二义性是不可判定的。即使文法是无二义性的，其句子对应的语义仍然必须有严格的定义，才可以避免语义的二义性。,句型分析（概念）,句型分析就是识别一个符号串是否是某文法的句型。它是一种推导或语法树的构造过程。对于一个给定的符号串，试图按照文法的规则构造其对应的推导，或语法树。,分析技术分类,自顶向下技术:从文法的识别符号开始，由它推导出与输入符号相同的符号串。从语法树的角度看,自顶向下的分析过程就是：以识别符号作为根结点，试图从根结点开始逐步建立语法树。该语法树的末端结点组成的符号串正是输入符号串。,自顶向下分析例子,文法G2.16S:S:=ABA:=aAb|abB:=cBd|cdS=AB(S:=AB)=aAbB(A:=aAb)=aabbB(A:=ab)=aabbcd(B:=cd)在构造推导的过程中，我们总是选择正确的规则。实际上，如何正确选择规则恰恰是自顶向下分析技术的核心。,最左（右）推导,最左（右）推导定义：在一个推导的过程中，如果每一步直接推导所被替换的总是最左（右）的非终结符号，那么这种推导称为最左（右）推导。一个语法树只对应与一个最左（右）推导。,自底向上分析技术,自底向上分析技术：从输入符号串出发，试图把它规约为识别符号。从语法树的角度看，这个技术首先以输入符号作为语法树的末端结点，然后向根结点方向构造语法树。,自底向上分析例子,文法G2.16S:S:=ABA:=aAb|abB:=cBd|cdaAbcd=aabbcd(A:=ab)Acd=(A:=aAb)AB=(B:=cd)S=(S:=AB)在上面的例子中间，我们总是找到了正确的简单短语进行规约。实际上，如何找到正确的简单短语（句柄）是自底向上分析技术的核心。,最左（右）规约,最左（右）规约定义：在一个规约的过程中，如果每步直接规约的总是最左（右）的简单短语那么这种规约称为最左（右）规约。在自底向上分析技术中，使用的一般都是最左规约。所以我们会特别地定义句柄（最左简单短语）的概念。最左规约和最右推导使用的规则顺序恰好相反。,句型分析的基本问题,自顶向下过程中，如何确定使用哪个规则？自底向上的过程中，如何找出简单短语？如何进行规约？需要让计算机自动高效地解决上面的问题。,规范推导与规范规约,规范直接推导：xUy=xuy中，y不包含非终结符号。记作xUy=|xuy.规范推导：推导中的每一步直接推导都是规范的。记作v=|+w。规范句型：可以从识别符号开始，通过规范推导得到的句型称为规范句型。,