编译原理讲义(文法与语言)

《编译原理讲义(文法与语言)》由会员分享，可在线阅读，更多相关《编译原理讲义(文法与语言)（81页珍藏版）》请在金锄头文库上搜索。

1、编译原理讲义(第二章:文法与语言)南京大学计算机系 赵建华文法与语言 文法被用来精确而无歧义地描述语言的 句子的构成方式. 文法描述语言的时候不考虑语言的含义 。字母表定义：字母表是有穷非空集合。 字母表包含了语言中所允许出现的一切 符号。符号串 定义：符号串是由字母表中的符号所组 成的有穷序列。 一个语言的句子总是它的字母表的符号 串。这个符号串的组成必须是按照文法 规则组合而成的。 语法分析的一个重要任务就是：判断一 个符号串的组成是否满足某个文法的规 定，并且分析出是如何按照规则组成的 。关于符号串的概念和操作 运算： 联结(并置)：x=123, y=45那么xy=12345 方幂：x的

2、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上的所有的非空符号 串的集合。文法和语言的定义（重写规则 ） 重写规则：一个重写规

3、则是一个有序对 (U,u)，通常写作U := u。其中U是一个 符号，称为左部；u是一个符号串称为右 部。有时也说这个规则是U的一个规则。 重写规则总是基于某个字汇表的。U和u 中的符号必须都在这个字汇表内。这个 字汇表中有些符号不能作为左部。 存在更加复杂的规则，但是这样的规则 足够描述程序设计语言的文法。文法和语言的定义（重写规则 ） 例如: 标识符:= 字母 标识符:= 字母|标识符字母 第二个规则实际使用了BNF的表示方法 。BNF表示方法的还包括: 花括号表示重复:字母 方括号表示可选:参数文法和语言的定义（文法） 文法：文法GZ是一组有穷非空的重写 规则的集合。其中Z称为识别符号。

4、G为 文法名字 文法例子：P22, 例子2.10。 所有的规则都是基于同一个符号表V。符 号表又可分划非终结符号集合VN和终结 符号结合VT。 句子:= := :=Peter | Berry | River := :=Swims := in := 文法和语言的定义（推导） 文法的作用是描述某种语言的句子的构 成方式。使用文法我们可以产生对应语 言的句子。 从识别符号开始，不断将当前符号串中 的非终结符号替换为该符号的某个规则 的右部。直到当前的符号串中所有的符 号都是终结符号为止。文法和语言的定义（推导） 例子： 句子=主语谓语状语 =名词谓语状语 = = Peter swims in riv

5、er文法和语言的定义（推导） 直接推导：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 |

6、 3 | | 9 VT0,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。语言的定义

7、（短语，句柄） 注意：在寻找一个句型的短语（或简单 短语）时，必须要求将这个短语规约为 相应的非终结符号后所得到的符号串仍 然是句型。 句柄：一个句型的最左简单短语称为该 句型的句柄。 定义句柄的原因：在自底向上识别一个 符号串时，总是规约这个句柄。语言的定义（文法的语言） 文法的语言：一个文法GZ的语言，用 L(GZ)表示，定义如下： L(GZ) = x | Z=* x 并且 x VT+ 一个文法的语言就是该文法的所有的句子的 集合。 文法的语言是所有终结符号串所组成的集合 的子集，一般是真子集。语言的定义（递归与语言） 递归的规则：U := U 左右递归规则：U := U；U := U 文

8、法的递归：U =+ U，称文法递归 于U。 文法的左右递归： 如果文法是非递归的，那么其语言是有 穷的。文法与语言（例子） GA：A:=bA|a； L(GA)=bia|i=0 GZ：Z:=Ab；A:= aaA A:=aa L(GZ) = a2nb|n=1语言的分类 Chomsky文法的定义： (VN,VT,P,Z) 该定义是我们前面讲的定义的一个更加 形式化的表达。 在这个定义中，文法规则的左部可以是 一个非空符号串。 Chomsky文法被分为四类，我们主要用2 型和3型文法。Chomsky文法类（0型文法PSG ） 0型文法的规则形如：u:=v，u,v为符号 串，且u非空。0型文法的相应语言

9、称为0 型语言，又称为递归可枚举集合。 0型语言是不可判定的。 例子：G：Z:=#A1#；#A:=#；A1:=11A ；A# := B#；1B := B1；#B := #A L(G)=#1i#|i=2n,n=0Chomsky文法类（1型文法CSG ） 1型文法的规则如下：xUy:=xuy，其中U 为非终结符号，x,y,u为符号串，且u非空 。1型文法又称为上下文相关文法。 1型文法也可以如下定义：所有的规则的 右部都不比左部短。 1型文法是可判定的。但是现在没有找到 有效的方法。Chomsky文法类（2型文法CFG ） 2型文法的规则有如下形状：U:=u，其 中U是非终结符号，u是符号串。2型

10、文法 又称为上下文无关文法。 一般的程序设计语言的语法都使用2型文 法描述。 2型文法是可判定的，且又有效的判定方 法。Chomsky文法类（3型文法RG ） 文法规则的形状：U:=T或者U:=WT， 其中U，W是非终结符号，T是终结符号 。 3型文法又称为正则文法，其语言也称为 正则语言。语言类对运算的封闭性 给定某个语言类中的语言，如果对它们 进行某种运算之后得到的新语言仍旧是 该类语言，那么该语言类对此运算封闭 。 所有语言类对并，乘积，闭包运算封闭 。 CFG语言类对交，补运算不封闭。 正则语言类对交并补运算封闭。3型语言与有穷自动机 任何一个3型语言都可以使用一个有穷自 动机来识别。

11、 有穷自动机包括一个有限控制器，和一 个输入带。机器从输入带从左到右逐个 读入输入符号，最终根据有限控制器的 状态确定输入的符号串是否是该型语言 的句子。机器的每一个动作根据当前读 入的符号和当前状态确定。有穷自动机例子aacbbabcabcaabc2型语言与下推自动机 任何一个2型语言都可以使用一个下推自 动机来识别。 下推自动机相当与一个有穷自动机和一 个栈。自动机的每一步动作根据栈顶的 符号，当前读入的符号，一个有限控制 器的当前状态来确定，可以包括读入符 号，压栈，出栈，和确定接受。形式语言与程序设计语言 虽然程序设计语言的语法都使用上下文 无关文法来描述，但是通常语言都是上 下文相关

12、的。 使用上下文无关文法描述语言的原因是 ：存在高效处理上下文无关文法的技术 。关于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)必然是一个正则语言。 但是，

13、自嵌套的上下文无关文法也可能 产生正则语言。例: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:=空. 这个定理表示：在语言中增加和删除一 个空串，并不会改变

14、语言的类别。文法等价 定义：设G和G是两个文法，如果L(G)等 于L(G)，那么我们说G和G等价。 例子： GS S:=ABC A:=Aa|a B:=Bb|b C:=Cc|c GS S:=Sc|Bc B:=Bb|Ab A:=Aa|a 两个CFG文法是否等价是不可判定的。文法的等价变换 当有些技术不能处理一种文法时，我们 可以将它处理为另外一个等价文法来处 理。这就是等价变换。 使文法和语言类一致。 消除二义性。 使文法适用于某种分析技术。 文法满足某种特殊需要。文法等价变换的种类 压缩文法等价变换 增广文法等价变换 范式文法等价变换 消去左递归等价变换压缩文法等价变换 主要作用是删除文法中不可

15、能被使用的 规则，称为多余规则。包括： 规则的左部不可能在句型中出现。 使用了此规则之后，句型永远也不能推导得 到句子。 一个规则U:=u不是多余的，当且仅当： Z=* xUy，且（条件1） U=+t, 且t是终结符号串。（条件2）压缩文法等价变换 已压缩文法定义：没有多余规则的文法 称为压缩了的（或已压缩的）文法。 压缩算法： 算法重复执行下面两个部分，直到不能 删除更多的规则： 删除不满足条件一的规则。（子算法1） 删除不满足条件二的规则。（子算法2）压缩文法等价变换（子算法1） 步骤1：对规则中识别符号z加标记； 步骤2：对左部非终结符号加有标记的规 则，将其右部中的所有非终结符号加标 记。 步骤3：检查是否一切非终结符号都加过 标记。是，结束；否，执行步骤4。 步骤4：如果上一次步骤2中没有多加标 记，删除所有左部没有加标记的规