编译原理讲义第二章文法与语言

编译原理讲义(第二章:文法与语言)南京大学计算机系赵建华文法与语言•文法被用来精确而无歧义地描述语言的句子的构成方式.•文法描述语言的时候不考虑语言的含义。字母表定义：字母表是有穷非空集合。•字母表包含了语言中所允许出现的一切符号。符号串•定义：符号串是由字母表中的符号所组成的有穷序列。•一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合而成的。•语法分析的一个重要任务就是：判断一个符号串的组成是否满足某个文法的规定，并且分析出是如何按照规则组成的。关于符号串的概念和操作•运算：–联结(并置)：x=123,y=45那么xy=12345–方幂：x的n次方幂即将n个x联结。•子符号串：v是xvy的子符号串。v非空•头，尾：x是xy的头，y是xy的尾。符号串集合•定义：若集合A中的一切元素都是同一个字母表上的集合，那么A被称为该字母表上的符号串集合。•在本课程中，语言被认为是句子的集合。（外延定义？）所以，一个语言就是对应于它的字母表上的一个符号串集合。符号串集合的运算•乘积：AB={xy|xA且yB}•方幂：A的n次方幂就是将n个A相乘。•字母表的闭包与正闭包：–字母表A的闭包是A上的所有符号串（包括空字符串）的集合。–字母表A的正闭包是A上的所有的非空符号串的集合。文法和语言的定义（重写规则）•重写规则：一个重写规则是一个有序对(U,u)，通常写作U::=u。其中U是一个符号，称为左部；u是一个符号串称为右部。有时也说这个规则是U的一个规则。•重写规则总是基于某个字汇表的。U和u中的符号必须都在这个字汇表内。这个字汇表中有些符号不能作为左部。•存在更加复杂的规则，但是这样的规则足够描述程序设计语言的文法。文法和语言的定义（重写规则）•例如:–〈标识符〉::=〈字母〉–〈标识符〉::=〈字母〉|〈标识符〉〈字母〉•第二个规则实际使用了BNF的表示方法。BNF表示方法的还包括:–花括号表示重复:{〈字母〉}–方括号表示可选:[〈参数〉]文法和语言的定义（文法）•文法：文法G[Z]是一组有穷非空的重写规则的集合。其中Z称为识别符号。G为文法名字•文法例子：P22,例子2.10。•所有的规则都是基于同一个符号表V。符号表又可分划非终结符号集合VN和终结符号结合VT。•〈句子〉::=主语谓语状语•主语::=名词•名词::=Peter|Berry|River•谓语::=动词•动词::=Swims•介词::=in•状语::=介词名词文法和语言的定义（推导）•文法的作用是描述某种语言的句子的构成方式。使用文法我们可以产生对应语言的句子。•从识别符号开始，不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。文法和语言的定义（推导）•例子：〈句子〉=〈主语〉〈谓语〉〈状语〉=〈名词〉〈谓语〉〈状语〉=……=Peterswimsinriver文法和语言的定义（推导）•直接推导：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|…|9–VT{0,1,2,3,4,5,6,7,8,9},VN={}推导的例子标号=数字序列=数字序列数字=数字序列数字数字=数字数字数字=数字23=123语言的定义（句型,句子）•对于文法G[Z]，x称为G的一个句型如果：Z=*x识别符号是最简单的句型。•G[Z]的一个句型x被称为句子，如果：xVT*也就是说句子是全部由终结符号组成的句型。语言的定义（短语，简单短语）•短语：对于文法G[Z]，如果Z=*xUy，U=+u。显然，w=xuy是一个句型。我们称u是句型w中相对于U的短语。•简单短语：在上面的定义中，如果U::=u是G的一个规则，那么，u是句型w中相对于U的简单短语。•例子：P22页例2.13。语言的定义（短语，句柄）•注意：在寻找一个句型的短语（或简单短语）时，必须要求将这个短语规约为相应的非终结符号后所得到的符号串仍然是句型。•句柄：一个句型的最左简单短语称为该句型的句柄。•定义句柄的原因：在自底向上识别一个符号串时，总是规约这个句柄。语言的定义（文法的语言）•文法的语言：一个文法G[Z]的语言，用L(G[Z])表示，定义如下：L(G[Z])={x|Z=*x并且xVT+}•一个文法的语言就是该文法的所有的句子的集合。•文法的语言是所有终结符号串所组成的集合的子集，一般是真子集。语言的定义（递归与语言）•递归的规则：U::=…U…•左右递归规则：U::=U…；U::=…U•文法的递归：U=+…U…，称文法递归于U。•文法的左右递归：•如果文法是非递归的，那么其语言是有穷的。文法与语言（例子）•G[A]：A::=bA|a；–L(G[A])={bia|i=0}•G[Z]：Z::=Ab；A::=aaAA::=aa–L(G[Z])={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::=#A–L(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型语言都可以使用一个有穷自动机来识别。•有穷自动机包括一个有限控制器，和一个输入带。机器从输入带从左到右逐个读入输入符号，最终根据有限控制器的状态确定输入的符号串是否是该型语言的句子。机器的每一个动作根据当前读入的符号和当前状态确定。有穷自动机例子aacbbabcabcaabc2型语言与下推自动机•任何一个2型语言都可以使用一个下推自动机来识别。•下推自动机相当与一个有穷自动机和一个栈。自动机的每一步动作根据栈顶的符号，当前读入的符号，一个有限控制器的当前状态来确定，可以包括读入符号，压栈，出栈，和确定接受。形式语言与程序设计语言•虽然程序设计语言的语法都使用上下文无关文法来描述，但是通常语言都是上下文相关的。•使用上下文无关文法描述语言的原因是：存在高效处理上下文无关文法的技术。关于CFG的进一步讨论•Chomsky范式：所有的上下文无关语言都可以用如下形式的文法产生：所有的规则都形如：U::=VW或者U::=T，其中U,V,W为非终结符号，T为终结符号。•Greibach范式：所有上下文无关语言都能由这样的文法产生：U::=Tu，这里U为非终结符号，T为终结符号。关于CFG的进一步讨论•自嵌套：一个上下文无关文法为自嵌套的，如果存在一个非终结符号U满足:U=*xUy，且x,y非空。•定理2.6若一个CFGG[Z]不是自嵌套的，那么L(G)必然是一个正则语言。•但是，自嵌套的上下文无关文法也可能产生正则语言。例:P35页关于推导的性质•定理2.7对于CFG，如果存在句型x=x1x2…xn且x=*y，必然存在y1,y2,…,yn使得:xi=*yi且y=y1y2…yn。•定理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’等价。•例子：–G[S]S::=ABCA::=Aa|aB::=Bb|bC::=Cc|c–G’[S]S::=Sc|BcB::=Bb|AbA::=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：对uVT+的规则U::=u的左部非终结符号U加标记。•步骤2：对右部仅包含终结符号和已加标记的非终结符号的规则的左部加标记。•步骤3：检查是否对一切非终结符号加过标记。是，结束；否则，执行步骤4。•步骤4：如果上一次步骤2执行时没有多加任何标记，那么删除左部没有加标记的规则，否则，转到步骤2。压缩文法等价变换（子算法2）•例子：Z::=BeA::=AeA::=eB::=CeB::=AfC::=Cf增广文法等价变换•一般来讲，以识别符号为左部的规则有多个。在规约的时候使用的规则也时不唯一的。增广文法