内容简介

《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》主要讲述设计和构造编译程序的一般原理、基本设计方法和主要实现技术，以高级语言程序编译的6个主要阶段——词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成为线索，阐述了各阶段的主要功能、原理、设计技术和实现方法。
《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》适合作为工程实践型、应用型本科院校计算机相关专业的教材，也适合作为工程技术人员的参考书。

精彩书摘

第3章语法分析





语法分析就是根据高级语言的语法规则对程序的语法结构进行分析，是编译过程的核心。它的任务是判断读入的单词符号串是否符合语言的语法规则，为语义分析和代码生成做准备。执行语法分析的程序称为语法分析程序，也称为语法分析器。
为了能够更精确地描述高级语言程序的语法结构，需要对高级语言的语法规则进行形式化描述，这种描述称为文法，适合描述高级语言语法规则的文法是上下文无关文法。因此本章首先介绍文法的相关概念。
语法分析的方法很多，不同的语法分析方法适用于不同的文法，有不同的使用场合和限制条件。语法分析不仅可以手工构造，也可以自动生成，本章最后介绍自动生成器YACC的基本原理和使用方法。

3.1语法分析概述
语法分析在编译过程中处于核心地位，如图3.1所示。其任务是在词法分析识别出正确的单词符号串的基础上，根据语言定义的语法规则，分析并识别出各种语法成分，同时进行语法检查和错误处理。根据第1章的介绍，语法分析程序的输入是token串，输出是语法树。实际上，有时并不需要显式地构造语法树，因为很多时候，语法分析可能会和后续的翻译交错进行。



图3.1语法分析器在编译程序中的地位


每一种程序设计语言都有描述其语法结构的规则，如C语言程序由一个或多个函数构成，至少包含一个main()函数，每个函数定义为一个复合语句，每个复合语句定义为由一对花括号{和}括起来的多个顺序执行的语句，语句有多种类型，多数语句由表达式组成，表达式由表达式、标识符、常量和运算符等构成。如果仅仅用文字这样表述，不便于计算机精确处理和判断。因此，需要对程序设计语言的语法构成规则进行形式化描述。程序设计语言的语法规则一般用上下文无关文法来描述。
上下文无关文法用递归的方式描述语法规则。语法分析的过程就是按文法规则对读入的token串(又称为输入符号串)进行分析的过程。token串中的每个单词符号对应于文法中的一个符号。
根据文法可以手工或自动生成一个有效的语法分析程序，用来判断输入的符号串在语法上是否正确。判断的依据就是对给定的输入符号串能否根据文法规则建立起一棵语法树。
按照语法树的建立方法，可以粗略地把语法分析方法分成两类：自上而下分析法和自下而上分析法。
自上而下分析法是在自左至右扫描输入符号串的过程中，从树根开始逐步向下建立语法树。使用自上而下的语法分析的困难在于表示源语言语法结构的文法需要满足特定的要求，但由于多数程序设计语言的控制流结构具有不同的关键字，如if、while、for，因此这种方法的优势在于一旦检测出关键字，就知道哪个文法规则是唯一的选择，实现起来简单、直观，便于手工构造或自动生成语法分析器，它仍是目前常用的方法之一。常用的自上而下的分析方法有递归下降分析和预测分析两种方法，我们将在3.3节详细介绍。
自下而上分析法是在自左至右扫描输入符号串的过程中，沿着从树叶向树根的方向逐步建立语法树，直到树根结点。自下而上的语法分析方法对文法的限制条件少，对大多数常见的高级语言的语法分析都能使用。常用的自下而上的语法分析方法有算符优先分析和LR分析两种，多数商业化的编译器和语法分析的自动生成器也都采用自下而上的语法分析方法。算符优先分析方法是多数编译器中用来分析算术表达式的方法；对于几乎所有的程序设计语言，只要能够构造出它的上下文无关文法，就能够构造出识别它的LR语法分析器，语法分析的自动生成器YACC采用的是LR分析方法，将在3.4节详细介绍自下而上的语法分析方法，并在3.5节介绍语法分析自动生成器YACC的原理和使用。

3.2上下文无关文法
对于高级程序设计语言而言，程序的语法结构是基于语法规则的，因此语法规则的定义和描述非常重要。程序设计语言的语法规则的形式化描述称为文法。本节主要介绍文法及其产生语言的方法——推导，并用语法树的方式描述推导过程。

3.2.1文法的定义
文法(Grammar)是描述语言的语法结构的形式规则(即语法规则)，这些规则必须准确而且可理解。文法是从产生语言中的句子的观点来描述一个语言，也就是说语言中的每个句子都可以用严格定义的规则来产生。
下面以自然语言为例，用语法规则来分析句子，从而得出文法的形式化定义。
例3.1有如下规则：
(1)→
(2)→|
(3)→我
(4)→大学生
(5)→
(6)→是
(7)→|
其中，“”表示该应用规则的开始；“→”表示“由……组成”或“定义为”；“|”表示“或”，具有相同左部的几个规则可以用“|”写在一起，如上述第2条和第7条规则实际各自代表了两条规则。
现在根据上述规则可以得到一个符合定义的规则的句子：我是大学生。分析过程如下。
应用规则(1)

应用规则(2)

我应用规则(3)

我应用规则(5)

我是应用规则(6)

我是应用规则(7)

我是大学生应用规则(4)
这说明，从出发，反复使用上述规则中“→”右边的成分替换左边的成分，产生“我是大学生”这样一个句子，从而说明按照上述规则“我是大学生”在语法上是正确的。
上述自然语言的定义就是一个文法。根据上述实例可以抽象出如下一些概念。
(1)非终结符(Nonterminator)：在上述规则中用尖括号括起来的符号，它们各自代表一个语法范畴，表示一类具有某种性质的语法单位，有时也称为语法变量。可以通过它们替换出其他句子成分，它们不会出现在最终的句子中，如例3.1中的、等。在程序设计语言中的非终结符有“算术表达式”“赋值语句”等。用VN表示非终结符的集合。非终结符给出了语言的层次和结构，这种层次化结构是语法分析和翻译的关键。
(2)终结符(Terminator)：出现在最终的句子中的符号，它是一个语言的基本单位的集合，如例3.1中不带尖括号的符号“我”“是”“大学生”。在程序设计语言的语法规则中终结符就是单词符号，如关键字、标识符和界符等。用VT表示终结符的集合。
V=VN∪VT，构成文法G的字母表，是该文法中可以使用的全部符号，VN∩VT=Φ。
(3)产生式(Production)：按一定格式书写的、用于定义语法范畴的规则，又称为规则或生成式，说明了终结符和非终结符组合成符号串的方式。形如α→β或α∷=β，称α为左部，α∈V+，α至少包含一个非终结符；β为右部，β∈V*。如例3.1中“→”是一个产生式。用P表示产生式的集合，如例3.1中有9个产生式。

(4)开始符号(Starter)：是一个特殊的非终结符，至少在一个产生式的左部出现。用S表示，代表该文法定义的语言最终要得到的语法范畴，如例3.1中的。在程序设计语言中，开始符号就是，文法定义的其他语法范畴都为此服务。
由此，给出文法的形式化定义：文法G是一个四元组，G=(VN，VT，P，S)，VN是非终结符集，VT是终结符集，S是开始符号，P是产生式集合。
对例3.1的文法可表示为：G=(VN，VT，P，)，其中VN＝{，，，，，，}，VT＝{我，是，大学生}，P就是例3.1中给出的9条规则。

前言/序言


前言


编译程序在计算机科学与技术的发展历史中发挥着巨大作用，是计算机系统的核心支撑软件。编译原理蕴含着计算机学科中解决问题的思路、形式化问题和解决问题的方法，对应用软件和系统软件的设计和开发有一定的启发和指导作用。构造编译程序所涉及的方法和技术在软件工程、语言转换等许多领域中有广泛的应用。
《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》主要讲述设计和构造编译程序的一般原理、基本方法和主要实现技术，贯穿高级语言、系统环境、体系结构和目标代码，体现了从软件到硬件的整机概念。以高级语言程序编译的6个主要阶段——词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成为线索，阐述了各阶段的主要功能、原理、设计技术和实现方法。
为适应新工科建设的需要，《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》的修订基于OBE的理念，将编译的基本理论与具体实现技术有机地结合起来，既注重理论的完整性，又将理论融于具体实例中。书中的实例具有连贯性，力求让读者建立一个完整的编译系统的模型，加深对程序设计语言的理解，掌握常用的编译技术和方法，构建一个具有一定规模的完整的编译程序，为今后从事应用软件和系统软件的开发打下一定的理论和实践基础。
《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》第3版延续了前两个版本的风格和主体内容，与前两个版本衔接得比较好；同时对一些章节进行了适当的充实、删减和重新组织，力求在各主要知识点之间达到较为合理的均衡，使读者对编译程序的构造方法和实现技术能从整体上全面地掌握。第3版修改的内容主要有：
(1)由于C语言的广泛使用，《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》选用的源语言改为C语言的子集。
(2)在第1章中增加了对高级语言的认识。在后面的章节中逐步对源语言进行分析，以便读者在了解编译方法的基础上，从高级语言的使用者过渡到高级语言的实现者和设计者。
(3)增加了语义分析的内容及方法，使编译程序的结构更清晰。
(4)细化了目标代码生成。目标代码选用Intel80x86汇编代码，降低学习的难度；生成的汇编代码能直接通过常见汇编器(masm)汇编成可执行文件，直观看到运行结果，加深对整个编译过程的理解。
(5)函数是C语言的精髓，《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》增加了函数的声明、定义和调用的编译过程，并以实例展示了C语言函数的详细执行过程及内存的变化，使读者对程序的运行环境有更透彻的认识，加深对计算机系统的理解。
《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》主要面向以工程实践、应用为主的本科院校，建议理论学时为32~40学时，实验学时为16~24学时，根据需要可安排专门的课程设计。《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》中加*的章节为较难的可选内容，教师可根据具体情况选择。《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》也可作为工程技术人员的参考书。
《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》参考和引用了国内外大量优秀编译教材和著作中的相关内容，也参考了网络上的相关内容，在此谨向原书作(译)者深表敬意和感谢；感谢中国科学技术大学物理学院张智浩同学，他根据《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》内容完整地实现了一个编译程序，验证了《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》的所有算法和思想；同时感谢刘恒洋老师在《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》配套的教学辅助系统的可视化方面所做的工作；感谢重庆理工大学研究生阳安志、刘野和刘广峰等对《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》提出的宝贵意见和建议。
《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》获得了重庆理工大学教材出版基金的资助。使用《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》第1版、第2版的院校的教师和学生也为《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》的改版提出了宝贵意见和建议，在此也表示衷心的感谢。
由于作者水平有限，书中难免存在疏漏之处，恳请广大读者批评指正。
《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》的配套课件和源代码等资源可以从清华大学出版社网站下载，如果遇到资源下载与使用的问题，请联系《编译原理及实践教程（第3版）（21世纪高等学校计算机专业核心课程规划教材）》的编辑，邮箱为。


编者
2018年12月





其他推荐