编译原理实用教程ppt课件(完整版)

1、21世纪高等院校规划教材编译原理实用教程 第一章 编译程序概论本章学习目标编译程序是高级语言的支撑基础，是计算机系统中重要的系统软件之一，本章主要内容：编译程序的功能编译程序的体系结构编译程序的工作过程编译程序的设计1.1 程序设计语言程序设计语言分成两大类，一类是高级语言，一类是低级语言。低级语言又包括机器语言和汇编语言，主要是面向机器的。高级语言则是面向应用的，分成很多种，如FORTRAN、Pascal、C、Ada、Java等。 机器语言本身是有由0和1组成的，符合计算机的硬件特性，因此能够直接执行。但用机器语言编写程序很不方便且容易出错，因此就用助记符代替机器语言，产生了汇编语言。汇编语

2、言比机器语言在可读性方面有了进步，但是其依赖具体机器的特性无法改变，给程序设计语言增添了难度。高级语言不能直接在机器上运行，它不是面向机器，而是面向应用的，因此，要想让高级语言运行必须有编译程序。编译程序就是这样的一种程序，它能将高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，源程序的运行过程如图1-1所示。编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。如果目标程序是汇编语言的形式，则需要在编译阶段和运行阶

3、段之间加一个汇编阶段。源程序目标程序机器语言计算结果编译程序汇编程序图1-1源程序的编译、汇编和运行阶段高级语言编写的程序除了可以通过编译方式外，还可以通过解释程序执行。所谓解释程序是一种语言翻译程序，读入一条语句，解释一条语句，执行一条语句，边读入边执行。解释程序与编译程序的主要区别是：编译程序将源程序翻译成目标程序后再执行目标程序，而解释程序是逐条读出源程序中的语句并执行，即在解释程序的执行过程中并不产生目标程序。1.2编译程序的编译过程和结构编译程序的功能是把高级语言源程序翻译成等价的低级语言目标程序。源程序是由一些基本符号构成的，我们在运行这个程序时，先编译，若某处有错误，就报错，无错

4、误就运行。编译程序在编译时，先将程序中的单词一个个分离出来，登记在一个表中，这叫词法分析，然后检查语句格式，叫做语法分析。然后检查类型是否一致，计算表达式的值叫语义分析。这些功能都是由编译程序相应的程序完成的。一般来说，整个编译过程可以划分成五个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、中间代码的优化和目标代码的生成。1.词法分析阶段词法分析是编译过程的基础，其任务是扫描源程序，根据语言的词法规则，分解和识别出每个单词，并把单词翻译成相应的机内表示。当然，词法分析在识别单词的过程中，同时也做了词法检查。在高级语言中，所谓单词，就是指逻辑上紧密相连的一组字符，这些字符具有集体

5、含义。单词是语言中最小的语义单位，如语言中的关键字、标识符、运算符和界限符。词法分析的依据是词的构造。单词的构造规则在高级语言中有明确的规定，比如哪些为保留字、变量如何定义、常量如何构造、分界符有哪些等。 例如，用C 语言编写的程序段如下：main( )float x=2,y=3,s;s=x+y*5;识别出的单词序列为表1-1所示表1-1词法分析程序类型名单词类型名单词保留字main左括号(右括号)花括号保留字float标识符x等号=常量2逗号,标识符y等号=常量3逗号,标识符s分号;标识符s等号=标识符x运算符+标识符y运算符*常量5分号;花括号2.词法分析语法分析是在词法分析的 基础上进行

6、的，是编译过程的第二个阶段。语法分析的任务是根据语言的语法规则，把单词符号串分解成各类语法单位，如表达式、语句等。通过语法分析，可以确定整个输入符号串是否构成一个正确的程序。3语义分析和中间代码的生成语义分析的任务是对各种不同语句进行翻译，包括两方面的工作：一是对每种语法范畴进行语义检查，如变量是否定义、类型是否正确等；二是在语义检查正确的情况下，进行中间代码的翻译。中间代码是介于高级语言语句和低级语言语句之间的一种独立于具体硬件的记号系统，它即有一定程度的抽象，又和低级语言十分接近，因此，转换成目标代码很容易。中间代码的表示形式有很多种，常见的有四元式、三元式、间接三元式和逆波兰式。其中四元

7、式的形式为（运算符，运算对象1，运算对象2，结果） 4.中间代码优化中间代码优化通过调整和改变中间代码中某些操作次序，以最终产生更加高效的目标代码。优化的主要手段有删除冗余运算、删除无用赋值、合并已知量、循环优化等。 5目标代码的生成这一阶段的任务是对前一阶段的中间代码变换成特定机器上的机器语言或汇编语言程序，实现机器的最终翻译。最后阶段的工作因为目标语言的关系而十分依赖机器的硬件系统，即如何充分利用机器现存的寄存器，合理的选择指令，生成尽可能短的目标代码，这与机器的硬件有关。 编译过程可以划分成五个阶段，这种划分是编译程序的逻辑组织形式。实际上，编译过程往往分成前端和后端。前端包括词法分析、

8、语法分析、语义分析、中间代码生成和中间代码优化，主要依赖于源程序；后端包括目标代码生成，依赖于计算机硬件系统和机器指令系统。这种组织方式，便于编译程序的移植，若要将编译程序移植到不同类型的机器，只需要修改编译程序的后端即可。编译程序还采用“分遍”的形式，即编译过程可以由一遍或多遍编译程序来完成。对于源程序或中间代码，从头到尾扫描一次并完成所规定的工作称为一遍。在一遍中，可以完成一个或相连几个逻辑步骤的工作。例如可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍；从而构成一个四遍扫描的编译程序。词法分析器语法分析器语义分析器中间代码生成器中间

9、代码的优化目标代码生成器源程序表格管理出错处理目标程序图1-3编译程序结构示意图1.3编译程序的设计技术编译程序的任务是把源程序翻译成某台计算机上的目标程序。因此编程人员首先要熟悉源程序语言，对源程序语言的语法和语义要准确无误的理解，同时要确定开发方案。同时还要选择合适的语言编写编译程序，目前一般采用PASCAL、C、ADA等高级语言编写，不仅减少了开发的工作量，缩短了开发周期。最后，开发人员还要熟悉目标机的特点，产生质量较高的目标代码。1高级语言的自编译技术用某种该高级语言书写自己的编译程序称为自编译。2.交叉编译交叉编译是指用A机器上的编译程序来产生可在B机器上运行的目标代码。例如，若A机

10、器上已有C程序可以运行，则可以在A机器上的C程序书写一个编译程序，它的源程序是C语言程序，而产生的目标程序则是基于B机器上的，即能够在B机器上执行的低级语言程序。3编译程序的自展技术Ln=LL1L0图1-4编译系统的自展过程自展的方法是：首先确定一个非常简单的核心语言L0，然后用机器语言或汇编语言书写它的编译程序T0；再把语言L0扩充到L1,此时有L0属于L1，并用L0编写出L1的编译程序T1，然后再把语言L1扩充为L2，此时，L1属于L2，并用L1编写L2的编译程序T2,这样不断的扩展下去，直到完成所要求的编译程序为止。自展技术的使用如图1-4所示。4编译程序的移植技术编译程序可以通过移植得

11、到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序移植到另一个机器（目标机）上。5编译程序的自动化在编译程序的自动化开发过程中，开发较早的是词法分析程序生成器和语法分析程序生成器 。使用的工具是在UNIX 操作系统下的软件工具LEX和YACC。1.4形式语言和编译实现技术形式语言是一种不考虑含义的符号语言，形式语言的理论研究的是组成这种符号语言的符号串集合、它们的表示法、结构和特性。按Chomsky文法分类法，文法可以分成四大类，即短语结构文法、上下文有关文法、上下文无关文法和正则文法。通常的程序设计语言，其符号的定义和正则文法相关联，语法定义和上下文无关文法相关联，而语义一

12、般需要上下文有关文法来定义。形式语言理论采用数学那样的符号形式表示，数学那样的严格推理。采用形式语言方式讨论程序设计语言及其编译程序的构造，可以使我们不仅了解一些编译实现技术如何应用，而且还可以理解如此做的原因。对编译程序的设计中所采用的技术，不但要知其然，而且还要知道所以然。从理论高度上去掌握编译技术。可以用下列公式来表示一种关系，即：编译原理=形式语言理论+编译技术小结自FORTRAN语言产生后，计算机高级语言得到了迅速发展。高级语言的种类越来越多。但计算机只能执行机器语言，不能直接执行高级语言编写的程序。要执行高级语言程序，必须提供该高级语言的翻译程序。翻译有编译和解释两种方式。编译程序

13、将源程序翻译成目标程序，然后再执行目标程序。解释方式则是边翻译边执行。编译程序一般包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序和出错处理程序等。编译过程可以分遍编译。编译程序的构造有多种技术。主要有自编译、移植、交叉编译、自展和自动化技术。 LEX是一个具有代表性的词法分析程序生成器。YACC是一个基于LALR（1）分析法的语法分析程序生成器。习题 1.1完成下列选择题(1) 构造编译程序应掌握 。 a.源程序 b.目标语言 c.编译方法 d .以上三项都是 (2)编译程序绝大多数时间花在 。 a.出错处理 b.词法分析 c.目标代码生成 d

14、.表格管理(3)编译程序是对 。 a.汇编语言的翻译 b.高级语言程序的解释执行 c.机器语言的执行 d .高级语言的翻译 （4）高级语言程序设计是根据 定义的。a.词法规则 b.语法规则 c.语义规则 d .以上三项都不是。 （5）编译程序的各阶段都设及到 。a.词法分析 b.表格管理 c.语法分析 d .语义分析（6）编译程序将源程序加工成目标程序是 之间的转换。 a.词法 b.语义 c.语法 d .规则（7）解释程序和编译程序的区别是 之间的转换。 a.是否生成中间代码 b.加工的对象不同 c.使用的实现技术不同 d .是否生成目标代码（）编译程序不能够检查、处理的错误是程序中的 。 a

15、.静态语义错误 b.动态语义错误 c.语法错误 d .词法错误（9）中间代码生成所依据的是语言的 。 a.词法规则 b.语法规则 c.语义规则 d .产生规则（10）开发一个编译程序应掌握 。 a.源语言 b.目标语言 c.编译技术 d .以上三项都不是1.2判断题（）用高级语言编写的源程序都必须通过编译，产生目标程序后才能运行。（2）源程序和目标程序在功能上具有等价关系。（3）高级语言程序到低级语言程序的转换是结构上的变换。（4）解释程序虽然不产生目标代码，但是它可能产生中间代码。（5）目标程序一定是机器语言程序。1.3问答题（1）.计算机执行用高级语言编写的程序有那些途径?它们之间的区别是

16、什么?（2）.画出编译程序的构造图.（3）.什么是编译程序的前端？什么是编译程序的后端？第二章形式语言概述本章学习目标形式语言由Chomsky于1956年提出，主要讨论语言和文法的数学机制以及语言和文法的分类。形式语言 的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是:文法和语言的形式定义文法的分类句型的分析和语法树2.1字母表和符号串任何一种语言都是由基本符号构成的。计算机高级语言作为计算机的语言，程序有语句构成，语句有一些基本符号构成，这些基本符号是保留字如main，if，then等、字母、数字和专用符号等。每个程序可以看成基本符号串。将所有的基本符号定义成一个基本符号集合，

17、则语言可以看成是在这个基本符号集合上定义的，按一定的规则构成的一切基本符号串组成的集合，给出如下的一些基本概念。 2.1.1字母表定义2.1 字母表是元素的非空有穷集合，字母表中的元素称为符号，因此字母表也称为符号表。高级语言如C语言的字母表是由字母、数字、特殊符号和一些专用符号构成。例=a,b， =0,1，=0,1，2，3，4，5，6，7，8，9，=a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,0)3字母表的闭包与正闭包的运算设有字母表A，由它做方幂A0，A1，A2， An, 。A的闭包定义如下：定义 2.8 A的闭包A*=A0A1 A2 An,其中，A

18、n （n=0，1，2，3，）中所有的符号串的长度为n，因此字母表A的闭包 A*为字母表上一切长度为n的符号串所组成的集合。如果不允许包含空串，则得到字母表A的正闭包。定义2.9 A的正闭包 A+=A1 A2 An显然，A*= A0 A+ ，且A+=AA*=A*A。 例题2.7 设字母表=a,b,c,依次写出长度为1、2的符号串，可得到 的正闭包+ ：+=a,b,c,aa,ab,ac,bb,bc,在+上添入空串即得*。说明：根据闭包和正闭包的定义，则有+=*=* 由于一个字母表的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上某个符号串的集合，因此，在某个字母表上的语言是该字

19、母表上正闭包的子集，且是真子集。对于C语言，可以说，C语言是基本符号集合的正闭包的真子集。 2.2 文法的定义及其分类什么是文法，文法的直观概念是，文法作为一种工具，不仅严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。2.2.2文法的形式定义1重写规则定义2.10重写规则，也叫产生式规则，或称为生成式，是形如或:的（,）有序对,其中, 是某个字母表V+中的一个元素，是V* 中的一个元素。称为规则的左部，称为规则的右部。例如 AB读作“A定义为B”，也就是说它是一条关于A的规则（产生式）。2文法定义2.11 文法G是一个四元组，G=（V

20、N，VT，P，S），其中，VN、VT分别是非空有限的非终结符号集和终结符号集，VNVT=，P是产生式的集合，SVN 称为文法的识别符号或开始符号。例题2.8在程序设计语言中，假设我们定义标识符的命名规则为字母a、b、c开头的，字母a、b、c和数字1、2、3的序列。命名规则为：abc123我们一般用大写字母代表左边的非终结符，设N 代表，D代表，L代表，则定义标识符的文法是：G=(VN，VT，P，N)其中，VN=N，L，DVT=a,b,c,1,2,3P为产生式的规则：NL， NNL ，NND ，La ，Lb ，Lc ，D1 ，D2，D3S 是开始符号,为N.关于产生式的规则说明一点，即若A，A，

21、A可写成A| 。“|”读做“或者”。上面的产生式规则可以改写为：P为产生式的规则：NL|NL|NDLa|b| cD1|2|32.2.3文法的分类自从乔姆斯基（Chomsky）于1956年建立形式语言的描述以来，把文法分成四种类型，即0型、1型、2型和3型文法。0型文法(短语文法)设G=（VN，VT，P，S），如果它的每个产生式是这样一种结构：（VNVT ）+ ，且至少含有一个非终结符，而（VNVT ）*，则称G是一个0型文法。0型文法又称短语文法，它的能力相当于一个图灵机。例如，A1型文法（上下文有关文法）设G=（VN，VT，P，S）为一文法，若P中的每一个产生式均满足，仅仅S除外，则文法G是

22、1型文法或上下文有关文法。所谓上下文有关文法即：=1A2，=12，符号串1 和2可以认为是上下文，A只有出现在上下文之间中，才可以被符号串替代，成为=1A2=12因此，1型文法又称为上下文有关文法。 32型文法（上下文无关文法）设G=(VN，VT，P，S)，若P中的每个产生式满足: 是一个非终结符, (VNVT ) *，则此文法称为2 型文法或上下文无关文法。有时将2型文法的产生式表示为形如：A，其中AVN 。 也就是当用取代非终结符A时，与A所在的上下文无关。上下文无关文法有足够的能力描述现今的程序设计语言。例题2.102 型文法G=（VN，VT，P，N）其中，VN=N，DVT=0，1，2，

23、3，4，5，6，7，8，9P=NNDD，D0123456789该文法描述的符号串的集合是整数。3型文法（右线性文法或正规文法）对2型文法的产生式做进一步的限制，限制产生式右部是单一终结符或单一终结符跟着单一非终结符，即：Aa AaB则称该文法为3型文法，又称为右线性文法或正规文法，其中A、BVN，aVT.例题2.113型文法 G=（VN，VT，P，S）其中，VN=S，A，BVT=0，1P=S011A0B，A1A0B，B010B该文法产生的是二进制整数。2.2.4文法举例例题2.15正规文法G=（VN，VT，P，A）其中, VN=A,B,C,DVT=x,y,z P=AxByCBzB yyC Cx

24、DD yDx例题2.162型文法G=（VN，VT，P，E）其中，VN=E，T，FVT=+，*，（，），iP=EE+T|T, TT*F|T, F(E)|i该文法能推出具有乘和加运算的算术表达式。例题2.17正规文法G=（VN，VT，P，S）其中VN=S，A，B，G，H，VT=d，+，P=SdB|+A|A|.GAdB|.GBdB|.H|dGdHHdH|d其中，d代表十进制数字。 根据以上我们对文法的定义我们不难发现3型文法类是2型文法类的特殊情况，2型文法类是1型文法类的特殊情况。每一类文法都是在前一类文法的基础上加上一些限定规则而产生的。因此，四类文法产生的语言就会有如下关系：3型语言2型语言1

25、型语言0型语言2.2.5各类文法与自动机的关系语言是句子的集合，而句子又是由字母表上的符号串组成的。对于程序设计语言来讲，程序由语句构成，语句则有数字、标识符、保留字、数字等单词构成。因此对程序的编译事实上就是对句子进行检查。方法就是编写一个检查过程，运行该过程来判断编写的程序是否合法。合法就回答“正确”，不合法就回答“不正确”，并且将错误报出。编写该过程的算法，抽象成一个数学模型，该数学模型称为自动机。将算法对程序的合法与否的检查转化为数学模型对程序中的句子的识别过程。自动机给出了用有穷方式来描述潜在的无穷的语言的另一种手段。自动机能够识别的句子的集合称为语言。对于每一类Chomsky语言类

26、，正好有一类自动机与它相对应。10型语言与图灵机图灵机是识别0型文法的识别装置。图灵机被引进作为描述过程的数学模型，过程的直观概念被看成是能机械实现的有穷指令的序列。图灵机的基本模型如图2-1所示。它有一个有限控制器、一个被分成若干单元的输入带和一个一次读入一个单元的读头组成 有限控制器a1a2a3aian读头图2-121型文法与线性界限自动机相对应。上下文有关文法所对应的自动机称为线性界限自动机。其功能是能够识别上下文无关语言，缩写为LBA。32型语言与下推自动机2型语言或上下文无关语言对应的自动机称为下推自动机。它是识别上下文无关语言的数学模型。缩写为PDA。3型语言与有穷状态自动机3型语

27、言或正则语言所对应的自动机称为有穷自动机。缩写为FA。无论那种自动机都分为确定性和非确定性之分 2.2.6文法分类的意义一个文法实际上是某种语言的一个简明、确切的描述，它表示了该语言中所允许的一类语法结构。从一个文法能推导出多个终结符的句子。但是知道了如何去构造属于某一个语言的一个合法串只是问题的一个方面。同时我们还要有能力判定一个串是否合法。也就是说，我们需要确定这个给定串的推导序列。如果从文法出发找不到这个推导序列，则该串就是非法的。以上四类文法都分别与一个相当简单但功能很强的自动机相关。右线性文法可由一种有穷状态自动机识别。2.3文法产生的语言和句型的语法树2.3.1推导和规范推导为了定

28、义文法产生的语言，我们必须给出推导的概念。推导分为三大类：直接推导、，长度为n(n1)的推导和长度为n（ n0）的推导。定义2.12如是文法G=(VN,VT,P,S)的规则（或说是P中的一产生式），,(VNVT)*，则称符号串为符号串应用产生式所得到的直接推导。记为。定义2.13推导长度大于0的推导：如果 对于符号串v 与w存在一个直接推导序列u0 u1u2u3un (n0)其中u0=v与un =w,则称符号串v推导出w或称w归约到v，记作v *w，称这个直接推导序列是长度为n的推导，且称符号串w是相对于符号串v的一个字。定义2.14推导长度大于等于0的推导：如果对于符号串v和w，v=w或v=

29、w，则记作v *w，称符号串v广义推导到符号串w，或称w广义归约到v。例2.18根据文法，考虑以C语言中的无正负号整数作为识别符号的文法。（1）（2）| (3 ) 0|1|2|3|4|5|6|7|8|9VT =0,1,2,3,4,5,6,7,8,9 VN = , ,判断数据2634是否是C语言合法的数据。给出数据2634的推导。4434346342634由此可见，2634是C 语言的合法数据。每一步推导都是直接推导。可以表示为2634定义2.15如果在推导的任何一步，其中、是句型，都是对中的最左非终结符进行替换，则称这种推导为最左推导。定义2.16如果在推导的任何一步，其中、是句型，都是对中的

30、最右非终结符进行替换，则称这种推导为最右推导。定义2.17在形式语言中，最右推导常称为规范推导，由规范推导所得的句型称为规范句型。定义2.15如果在推导的任何一步，其中、是句型，都是对中的最左非终结符进行替换，则称这种推导为最左推导。定义2.16如果在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换，则称这种推导为最右推导。定义2.17在形式语言中，最右推导常称为规范推导，由规范推导所得的句型称为规范句型。例2.19给出了下列文法G（1）（2）| (3 ) 0|1|2|3|4|5|6|7|8|9VT =0,1,2,3,4,5,6,7,8,9 VN = , ,判断数据2634是否是C

31、语言合法的数据。【解】（1）用最右推导，每次用产生式的规则替换最右边的非终结符，推导过程如下：4434346342634（2）用最左推导，每次直接推导都替换最左边的非终结符，推导过程如下：22626326342.3.2句型、句子和语言定义2.18句型：设GS是一个文法，如果符号串x是从开始符号S推导得到的，即有S=+x，xV+，则称符号串x是该文法G的一个句型。定义2.19句子：GS是一个文法，如果符号串x是从开始符号S推导得到的，即有S=+x，并且xVT，则称该符号串为该文法的一个句子。实质上，句子是句型的特殊情况，句子是由终结符组成，而句型是有终结符和非终结符组成。定义2.20语言GS是一

32、个文法，文法G产生的语言L(G)=x|S=x，并且xVT，即文法的语言是文法所有句子的集合。例2.20 2型文法G=(VN，VT，P，S)其中，VN=SVT=0,1P=S0S1,S01该文法产生的语言是L(G)=0n1n,其中n1例2.21 文法GS定义如下Sif E then S| if E then S else S|while E do S|begin L end|A该文法产生的语言就是程序设计语言中的单分支、双分支、循环语句和顺序语句，其中每个非终结符的意义是：S代表语句，L代表语句串、A代表赋值语句，E代表布尔表达式。例2.22 设文法GS：EE+T|TTT*F|FF(E)|i证明符

33、号串E+(E+T)*i是文法的句型，i+i*i 是文法的句子；并说明该文法产生的语言是什么。【证明】由于EE+TE+T*FE+T*iE+F*iE+(E)*i E+(E+T)*i所以 E+(E+T)*i是文法的句型。由EE+TE+FE+F*iE+i*iT+i*iF+i*ii+i*i所以i+i*i 是文法的句子。该文法产生的语言是程序设计语言中的算术运算式，其中包括加、乘和括号运算。2.3.3语法树在自然语言中，句子结构可以借助一种树形表示进行分析。如下面的句子：They are students and teachers of the Physics Department。对该句子的结构进行分析

34、，其树型结构如图2-3所示，由此可以看出，该句子是由主语、系词和表语组成，是一个语法正确的句子。句子主语系词表语代词Theyare名词student连接词and名词teacher定语前置词冠词名词ofthePhysics名词Department图2-3句子结构在自然语言中，可以通过树型表示直观地分析句子的结构；在形式语言中，我们提到了句型、推导的概念，在证明某个符号串是否是某个文法的句型时，采用从文法开始符号推导的方法，这个推导过程可以用语法树直观的表示出来。语法树也称为推导树，其定义如下：给定文法G=(VN,VT,P,S) ，对于G的任何句型都能构造与之关联的语法树，这棵树满足下列四个条件：

35、（1）每个结点都有一个标记，此标记是V的一个符号。（2）根的标记是S。（3）若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中。（4）如果结点n的直接子孙，从左到右的次序是结点n1,n2,n3.nk，其标记分别为A1，A2，A3，AK。那么AA1A2A3AK一定是P中的一个产生式。例2.23 设文法GS ：EE+T|TTT*F|FF(E)|i证明符号串E+(E+T)*i是文法的句型。EE+Ti*FF()TE+ET2.3.4二义性文法及其他1二义性文法及其定义一个文法，如果它的一个句子或句型有两棵或两棵以上的语法树，则称此句子具有二义性。如果一个文法含有二义性的句子，则称该文法

36、具有二义性。例2.24 设文法GS：Sif B then S|if B then S else S|i：=E给出符号串if B then if B then S else S的语法树。语法树的结构如图2-5所示。从上面的语法图我们可以看出，字符串if B then if B then S else S能够画出两棵语法树，所以该文法是一个二义性文法。在语言中，为了避免二义性的文法，往往对文法加以一定的限制，如限制条件语句then之后不允许再是条件语句，或者从语义解释方面限制条件语句中的else只能与其前面的、还没有和其他else配对的then配对。如此限制之后，符号串if B then if B

37、 then S else S就只有图2-5左边的树形结构了。SifBthenSifBthenelseSSSifBthenelseSSifBthenS2二义性文法的证明要判定一个文法是否是二义性文法，或它是否产生一个先天二义性的上下文无关语言，是个递归不可解的。即不存在一个算法，它能在有限的步骤内，确切的判断出某个给定的文法是否是一个二义性文法。我们要证明一个文法是否是一个二义性文法，就是找到该文法的一个句型特例，能够画出这个句型的两棵语法树，该文法就是二义性文法。例2.25 文法G=（E，+，*，I,(,)，P，E）其中P为：Ei EE+EEE*EE(E)证明该文法是二义性文法，并将该文法改为

38、等价的非二义性文法（等价的文法是指产生的语言相等的文法）。【证明】取句型i*i+i，写出该句型的两个不同的推导。画出推导的两棵不同的语法树。推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i推导的两棵语法树如图2-6所示。将文法改为非二义性文法为：ET |E+TTF |T*FF（E）|iEEE+E*EiiiEEEE*E*Eiii2.3.5文法产生的语言和产生语言的文法例2.26 设G=（VN，VT，P，S），VN=S,B,E，VT=a,b,c，P由下列产生式组成：SaSBESaBEEBBEaBabbBbbbEbeeEee（1）问该文法是

39、Chomsky哪一类型的文法？（2）它生成的语言是什么？答：根据文法分类定义，由于文法中存在产生式，其左部由长度大于1的符号串构成，如产生式“EBBE”，显然不符合Chomsky 的2型和3型文法的定义。该文法产生式左部串的长度均小于等于右部串的长度，符合1型文法的定义，所以该文法是上下文有关文法。（2）根据如下推导：对于每一个n1，我们将号产生式使用n-1次，得到推导序列：S an-1S(BE)n-1，然后使用产生式(2)一次，得到：S an(BE)n，然后从an(BE)n.继续推导，总是对EB使用产生式的右部进行替换，而最终在得到的串中，所有的B都限于所有的E。设n=3，aaBEBEBEa

40、aaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S anBnEn.接着，使用产生式(4)一次,得到SanbBn-1En，然后使用产生式n-1 次得到：S anbnEn，然后使用产生式一次，使用产生式n-1次，得到：S anbnen 因此该文法产生的语言是L(G)=anbnen|n1。 例2.27 设有上下文无关文法如下：GS：SABAUTUa|aUTb|bTBc|cC将文法的产生式代入产生如下文法：GS： SUTB Ua| aUTb|bTBc|cC考察文法，用L(S)，L(U)，L(T)和L(B)分别表示从终结符S，U，T和B出发推导出的符号串的集合，不难发现：L（U）=ai|i1

41、=a+L（T）=bj|j1=a+L（B）=ck|k1=a+由于有SUTB，则有：L（S）=L(U)L(T)L(B)=(aibjck|i1,j1, k1)=a+b+c+例2.28 构造一个上下文无关文法G，使其描述的语言L（G）是能够被5整除的无符号整数集合。能够被5整除的整数其结构特点是，末位数一定是0或5。所以，只要保证生成的整数末位数字是0或5即可。据此，构造描述能被5整除的无符号整数集合的文法如下：GS：SN0|N5NDN|D0|1|2|3|4|5|6|7|8|9例2.29 写出一个上下文无关文法G，使得L(G)=anbmcmdn|n0，m1分析该语言的特点，可以看出，a和d的个数是一样

42、的，b和c的个数是一样的。m的取值范围从1开始，所以至少有一个bc，n的最小值为0。写出文法为：SaAd|A AbAc|bc2.4句型分析与句柄对于上下文无关文法，语法树是句型推导过程的几何表示；是进行句型分析极好的工具。所谓句型分析就是识别一个符号串是否是某一个文法的句型。进一步说就是给定一个符号串时，按照某文法的规则为该符号串构造推导或语法树，以此来识别它是文法的一个句型。对于上下文无关文法，其句型分析方法有两大类，一类是自上而下的分析方法（又称自顶向下），另一类是自下而上（自底向上）的分析方法。2.4.1 自上向下的分析方法1基本思想 自上而下的分析方法就是从识别符号出发，看是否能推导出

43、待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的句型或句子，否则就不是。或者说，以文法的识别符号作为根结点，看是否能构造出一个语法树，而且此语法树所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则就不是。例2.30 设文法GS：SaAbc| aBAbaBbeB|d输入串：abed，识别该串是否是该文法的一个句子。方法：从文法的识别符号S开始出发，选择它的一个产生式SaAbc 得到直接推导S aAbc以识别符S作为根结点，构造语法树，如下图2-7所示SaAbcba图2-7自上而下的推导过程SaAbcS

44、aBSaBBebSaBebBd（a）（b）（c）（d）（e）2分析过程符号串aAbc与待检查的符号串abed的第一个符号相匹配。由于符号串aAbc的第2个符号是非终结符，因此需要对它进行替换。A只有一个产生式Aba。以其右部替换A，得推导SaAbcababc得到语法树，如图2-7（b）所示。符号串ababc与待查符号串abed的第2个符号相匹配，但与第3个符号不相匹配，匹配失败。此时，需要退回到非终结符 A，重新选择S另外的产生式，再做试探。这种选择的过程称之为回溯。选择S的另外一条产生式的规则SaB，得到直接推导SaB，得到语法树2-7（c），再选取其中的一条产生式BbeB，得到推导SaBa

45、beB，得到语法树如图（d），将Bd代入即可得到该字符串abed。 3存在问题自上而下分析方法是从文法的识别符号开始，选择相应的产生式规则进行推导。但在推导过程中会出现回溯现象。我们把出现回溯的分析称为不确定的自顶上下分析方法。这种方法花费时间多，效率低，编程实现时复杂，如果对文法加以限制，就可以避免回溯，这就出现了我们后面要提到的LL(1)分析方法2.4.2确定的自上而下的分析方法例2.31 设文法GSSaBc|bCdBeB|fCdC|c试检查符号串aefc是不是该文法的句子。识别符S有两条产生式，它们的右部首符号分别是终结符a和b。待检查符号串aefc的首符号是a，所以从识别符S出发，只能

46、选择其产生式SaBc得到直接推导SaBc得到语法树如图2-8（a）所示。其中，非终结符B有两条产生式，它们右部首符号分别是终结符e与f，而待检查的符号串aefc的第2个符号是终结符e，所以选择B的产生式BeB得到推导SaBcaeBc，得到语法树如图2-8（b）所示。由于待检查的符号串aefc的第3个符号是终结符f，因而对句型aeBc中的非终结符B选择其产生式Bf的推导SaBcaeBcaefc得到语法树如图2-8（c）所示。如此推导出的符号串aefc，语法树的叶子结点序列是aefc，与待检查的符号串aefc相匹配。SaBcSaBceBSaBceBf图2-8语法树例2.32 若有文法GSSAp|B

47、qAaAcABbBdB当输入串W=ccap，那么试图推出输入串的推导过程为：SApcApccApccap很容易构造相应语法树，如图2-9所示。SApSApcASApcAcASApcAcAa图2-9语法树（a）（b）（c）（d）2.4.3自下而上的分析方法1基本思想自下而上的分析方法的基本思想是从待检查的符号串出发，看最终是否能归约到文法的识别符号。如果能归约到文法的开始的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。例2.33 若有文法GSScAdAabAa识别输入串w=cabd是否是该文法的句子。首先从输入串开始，扫描cabd，从中寻找一个子串，该子串与某一产生式的右

48、端相匹配。子串a和子串ab都是合格的，假若我们选用了ab，用产生式的左端A去替代它，即把ab归约到A，得到串cAd。构造一个直接推导cAdcabd，即从cabd叶子开始向上构造语法树，接下去在得到的串cAd中又找到了子串cAd与产生式的右端相匹配，则用S替代cAd，或称将cAd归约到S，得到了又一直接推导ScAd，形成了最终的语法树。分析过程如图2-10所示。图2-10自下而上构造语法树cabdcabdAcabdAS2存在问题在自上向下的分析中，假定要被代换的最左非终结符的符号是V，且有n条规则：V1|2|3|n，那么如何确定用哪个右部去替换V？有一种解决方法是从各种可能的选择中挑选一种，并希

49、望它是正确的。如果发现它是错误的，我们必须退回，再试着进行另外的选择，这种方式称为回溯。在自下向上的分析方法中，在分析程序工作的每一步中，都从当前串中选择一个子串，将它归约到某个非终结符号，我们暂且把这个子串称为“可归约串”。出现的问题是如何确定这个“可归约串”？比如在上例中，我们在对输入串cabd 的分析中，如果不是选择ab，用产生式，而是选择a，用产生式将a归约到A，那么最终就达不到S的结果，也就不知道cabd是一个句子。因此在归约时，ab是“可归约串”而不是a。如何求“可归约串”成为自下而上进行分析的关键。下面我们用“句柄”的概念来描述“可归约3句柄的概念 （1）形式化定义定义2.21令

50、G是一文法，S是文法的开始符号， 是文法的一个句型。如果有：SA且A则称是句型相对于非终结符A的短语。特别地，如有A则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。（2）求一个句型的句柄给定某个句型，要求出该句型的句柄，比较直观的方法就是画出该句型的语法树。该语法树的一棵子树的叶子结点（从左到右）组成的符号串便是这个句型关于子树根结点的一个短语。语法树的一棵简单子树（只有单层子树）的叶子结点组成的符号串是这个句型关于简单子树根结点的一个直接短语。语法树的最左的简单子树叶子结点组成的符号串就是这个句型的句柄。例2.34 已知文法GS：S(R)|a|RTTS,T|S句型=

51、(a,(T),(S,T)的语法树如图2-11所示。【解答】观察该语法树，共有10个非叶子结点，10棵子树。因此有短语aT(T)S,T(S,T)(T), (S,T)a, (T), (S,T)(a, (T), (S,T)S(R)S，TaT，ST(R)TS(R)S，T图2-11语法树2.4.4文法的存储一个文法的语法图由该文法所有非终结符的定义图组成。每个非终结符号的定义图是一个结构型数据。名字定义下一个候选式右部后继写成高级语言的结构型数据形式，则为：type struc=boxesboxes=recordname:array110 of char;def:struc;nextp:struc;ri

52、ghts:struc;end;其中，“名字”是用某种内部形式表示的终结符号或非终结符号的名字。“定义”是一个指针，对于非终结符号，它指向其第一个侯选式结构图的开始位置。对于终结符号，它为0；“下一个侯选式”是一个指针，指向相同左部的下一个侯选式的开始位置。若无侯选式，则它为0；“右部后继”是一个指针，指向同一个右部的下一个符号。另用一个一维数组记录所有的非终结符号定义图的开始地址。也就是说，这个数组的每个元素都是一个指针，分别指向相应的非终结符号的第一个候选式的定义图。例2.35文法EEAT|TTTMF|FF（E）|iA+|M*|/按照上面的存储结构，画出文法的存储结构如图2-12所示：EE+

53、TET文法图2-15文法的链表结构图TT*FTFF(E)Fi小 结文法是形式语言的一个十分重要的基本概念。文法可定义为一个四元组，文法G=（VN，VT，P，S），其中，VN是一个非终结符集，VT是一个终结符集，P是一个产生式集，S是文法的开始符号。Chomsky 将文法分为0 型，1型，2型和3型文法。程序设计语言的词法规则属于3型文法（正规文法），程序设计语言的语法和语义部分一般是采用2型文法来描述。对于一个文法，我们需要研究它的句型，句子和语言。要识别一个符号串是不是一个文法的句子，需要对它进行语法分析。分析方法有两类，一类是自上而下分析法，另一类是自下而上的分析方法。为了进行语法分析，需

54、要事先将产生式存储在计算机中。可以为文法建立一个产生式表，把文法的所有的产生式都放在这个产生式表中。为了在分析过程中能迅速查找到相应的产生式，还可以建立一个目录表。习 题1设字母表A=a，符号串x=aaa，写出下列符号串及其长度：x0，xx，x5以及A+和A*。2令=a,b,c，又令x=abc，y=b，z=aab，写出下列符号串及它们的长度：xy，xyz，(xy)3。3设文法GS：SSS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。4已知文法SAB A|aA Bbc|bBc写出该文法描述的语言。5已知文法ET|E+T|E-TTF|T*F|T/FF(E)|i写出该文法的开始符号、终

55、结符集合VT、非终结符集合VN。6对于文法ET|E+T|E-TTF|T*F|T/FF(E)|i写出句型T+T*F+i的短语、简单短语以及句柄。7设计出语言anbm|n,m1的文法。8文法G=(A，B，S，a,b,c,P,S)其中P为：SAc|AbAabBbc写出LGS）的全部元素。9已知文法ZaZb Zab 写出L（GZ）的全部元素。10为句子i+i*i构造两棵语法树，从而证明下述文 法是二义性的。 i|()| +|*|/11写出生成下述语言的上下文无关文法。 （1）anbnambm|n,m0 (2) 1n0m1m0n|n,m012句型、句子和语言之间有什么关系？第三章 词法分析本章学习目标词

56、法分析程序的主要任务是对源程序进行扫描，从中识别出单词。它是编译程序的第一步，也是编译过程中不可缺少的部分。本章的主要内容是： 正则表达式和有限自动机文法、正规表达式、正规集及自动机的相互转换词法分析器的C语言实现词法分析器的自动生成3.1词法分析器与单词符号3.1.1 词法分析词法分析是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个一个的单词。编译程序中完成词法分析任务的程序段，称为词法分析程序。词法分析程序对源程序进行扫描，从中识别出一个个的单词符号，因此，词法分析程序又称为词法分析器，又称扫描器。词法分析器作

57、为编译程序的一部分，它与语法分析程序之间接口方式有两种。一种方式是词法分析程序独立工作，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件称为语法分析程序的输入而继续编译，如图3-1所示就是将词法分析单独作为一遍的接口方式。源程序词法分析程序单词序列图3-1词法分析单独作为一遍取符号源程序词法分析程序语法分析程序图3-2词法分析作为语法分析子程序送符号另一种方法，也是常用的一种方法就是把词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，就调用该程序。词法分析程序每得到一次调用，就从源程序文件中读入一个字符，直到识别出一个单词为止。这种方法省去了中间文件。源程序词法分析程序

58、单词序列图3-1词法分析单独作为一遍取符号源程序词法分析程序语法分析程序图3-2词法分析作为语法分析子程序送符号3.1.2单词符号单词符号是程序设计语言的基本语法单位和最小语义单位。单词符号一般分为五类。（1）关键字（又称保留字或基本字）如if，then ，else，while，do，begin和end。（2）标识符，用于表示变量名、过程名等。（3）常数，如123，实数型45.67等。（4）运算符，如+，-，*，/，A，且 =*，且# FOLLOW(A)。也可以定义为FOLLOW（A）=a|SAa，a VT若有S=A，则规定#FOLLOW（A）一般来讲，我们用“#”作为输入串的结束符，或称为句

59、子的括号，如#输入串#。4.1.2 LL(1)文法的定义根据上面的分析我们重新定义一个产生式被选择时的集合SELECT如下。定义4.3 给定上下文无关文法的产生式A，AVN，V*，若不能推出，则SELECT(A)=FIRST()如果能够推导出，则SELECT(A)=(FIRST()FOLLOW(A)。LL(1)文法定义：。定义4.4 一个上下文无关文法是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同的产生式，A，A 满足SELECT（A）SELECT（A）=其中，和不同时推出。如果某个文法满足上述条件，称该文法为LL(1)文法。如果一个文法是LL(1)文法，就可以采用确定的自顶向下

60、分析技术进行语法分析。LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可以决定如何推导即选择哪个产生式规则进行推导例4.4 有一文法，判断该文法是否是LL(1)文法，写出判断过程。 SpA | qBAcAd |a BdB |bSELECT(SpA)SELECT(SqB)=pq=SELECT(AcAS)SELECT(Aa)=ca=SELECT(BdB)SELECT(Bb)=db=所以是LL(1)文法，即可以采用确定的自顶向下的分析方法。例4.5 若有文法G4S：SaA | dAbAS| SELECT(SaA)SE