编译原理 -中南大学出版社

编译原理

【作者】：蒋伟进
【出版时间】：2005-08
【字数】：385（千字）
【定价】：￥22（元）
【出版社】：中南大学出版社
【ISBN】：7-81105-159-1/TP·023
【页码】：237（页）
【开本】：16开

本书全面地介绍了编译程序的基本结构，系统地阐述了编译原理的一般理论、常用方法和实现技术。全书共分九章，包括语言的基础知识、词法分析程序的设计原理和构造方法、常用语法分析技术、属性文法基本概念、中间代码生成、符号表构造、代码优化和目标代码生成及运行时存储空间的组织等。本书叙述严谨、简明，富有启发性，且深入浅出，通俗易懂，便于自学。在各章后面均附有习题和习题参考答案。本书可作为高等院校计算机专业教材，也可以作为成人高等教育计算机专业本科和专科起点本科生的教材，也可以作为计算机专业人员的参考用书。

第1章编译原理概述（1） 1.1 翻译程序与编译程序（1） 1.2 编译过程和编译程序的基本结构（2） 1.3 编译程序的生成方法（5） 1.4 编译技术在软件开发的应用（6） 1.5 编译器的构造工具（7）小结（7）习题一（8）参考答案（9）第2章文法和语言基础（10） 2.1 字母表和符号串的基本概念（10） 2.1.1 字母表和符号串（10） 2.1.2 符号串的运算（11） 2.2 文法和语言的形式定义（12） 2.2.1 形式语言（12） 2.2.2 文法的形式定义（13） 2.2.3 语言的形式定义（16） 2.2.4 规范推导和规范归约（18） 2.2.5 递归规则与文法的递归性（19） 2.3 短语、直接短语和句柄（20） 2.3.1 短语和直接短语（20） 2.3.2 句柄（21） 2.4 语法树与文法的二义性（22） 2.4.1 推导与语法树（22） 2.4.2 文法的二义性（24） 2.4.3 文法二义性的消除（25） 2.5 文法和语言的分类（26） 2.6 有关文法实用中的一些说明（28） 2.6.1 有关文法的使用限制（28） 2.6.2 上下文无关文法中的ε规则（29） 2.7 文法在内存中的表示（29）小结（30）习题二（31）参考答案（33）第3章词法分析与有穷自动机（35） 3.1 词法分析程序的设计（35） 3.1.1 词法分析程序与语法分析程序的接口方式（35） 3.1.2 词法分析程序的输出（35） 3.1.3 将词法分析工作分离的考虑（36） 3.2 语言单词符号的两种定义方式（37） 3.2.1 正规式与正规集（37） 3.2.2 正规文法与正规式（38） 3.3 正规式与有穷自动机（41） 3.3.1 确定有穷自动机（DFA）（41） 3.3.2 非确定有穷自动机（NFA）（42） 3.3.3 由正规表示式R构造NFA（43） 3.3.4 NFA确定化为DFA的方法（44） 3.3.5 DFA的化简（47） 3.3.6 有穷自动机到正规式的转换（49） 3.4 正规文法与有穷自动机（50） 3.4.1 右线性正规文法到有穷自动机的转换方法（50） 3.4.2 左线性正规文法到有穷自动机的转换方法（51） 3.4.3 有穷自动机到正规文法的转换方法（52） 3.5 词法分析程序设计（53）小结（56）习题三（56）参考答案（58）第4章语法分析（62） 4.1 自上而下语法分析法（62） 4.1.1 非确定的自上而下分析法（62） 4.1.2 文法的左递归性和回溯的消除（63） 4.1.3 某些非LL（1）文法改写成LL（1）文法（67） 4.1.4 递归下降分析法（68） 4.1.5 预测分析法与预测分析表（70） 4.2 自下而上的分析法（73） 4.3 算符优先分析法（74） 4.3.1 算符优先文法（74） 4.3.2 算符优先关系表的构造（76） 4.3.3 算符优先分析算法（77） 4.3.4 优先函数（79） 4.4 LR分析法（82） 4.4.1 LR分析器的工作原理和过程（82） 4.4.2 LR（0）分析法（85） 4.4.3 SLR（1）分析法（89） 4.4.4 LR（1）分析法（95） 4.4.5 LALR（1）分析法（98）小结（101）习题四（103）参考答案（106）第5章语法制导翻译和中间代码生成（118） 5.1 属性文法（118） 5.2 语法制导翻译概述（120） 5.3 中间语言（122） 5.3.1 逆波兰式（122） 5.3.2 三元式和树形表示（123） 5.3.3 四元式和三地址码（124） 5.4 自底向上语法制导翻译（125） 5.4.1 简单算术表达式和赋值语句的翻译（125） 5.4.2 布尔表达式的翻译（127） 5.4.3 控制语句的翻译（131） 5.4.4 循环语句的翻译（133） 5.4.5 简单说明语句的翻译（135） 5.4.6 含数组元素的赋值语句的翻译（136） 5.5 递归下降语法制导的翻译（139）小结（141）习题五（141）参考答案（142）第6章符号表的组织和管理（144） 6.1 符号表的内容与作用（145） 6.1.1 符号表的内容（145） 6.1.2 符号表的作用（145） 6.2 符号表的组织（146） 6.2.1 符号表的总体组织（146） 6.2.2 表项属性信息组织（147） 6.2.3 符号表域的组织（148） 6.2.4 Pascal的符号表组织（148） 6.3 符号表的建立与查找（152） 6.3.1 符号表的建立（152） 6.3.2 符号表的查找（152）小结（154）习题六（154）参考答案（155）第7章代码优化（157） 7.1 优化概述（158） 7.1.1 合并常量运算（158） 7.1.2 删除公共子表达式（158） 7.1.3 减少复写传播（158） 7.1.4 消除无用代码（158） 7.1.5 削减运算强度（159） 7.1.6 外提循环中的不变表达式（159） 7.1.7 删除归纳变量（160） 7.2 局部优化（160） 7.2.1 划分基本块的方法（160） 7.2.2 基本块的DAG表示（162） 7.2.3 利用DAG进行基本块的优化处理（163） 7.3 循环优化（166） 7.3.1 程序流程图（166） 7.3.2 循环查找（167） 7.3.3 循环优化（167） 7.4 窥孔优化（170）小结（171）习题七（171）参考答案（174）第8章运行时存储空间组织（179） 8.1 程序运行的存储分配知识（179） 8.1.1 运行时存储空间划分（179） 8.1.2 过程的活动（180） 8.1.3 活动记录（181） 8.1.4 存储分配策略（182） 8.2 静态存储分配（182） 8.3 栈式存储分配（183） 8.3.1 没有局部过程的栈式存储分配（184） 8.3.2 允许过程嵌套定义语言的栈式存储分配（184） 8.4 堆式动态存储分配（187） 8.5 参数传递机制（188） 8.5.1 值传递（188） 8.5.2 地址传递（189） 8.5.3 值结果传递（189） 8.5.4 名字传递（190）习题八（191）参考答案（193）第9章目标代码生成（196） 9.1 概述（196） 9.2 假想的计算机模型（198） 9.3 简单的代码生成器（200） 9.3.1 待用信息和活跃信息（201） 9.3.2 代码生成算法（202） 9.3.3 寄存器分配（205） 9.4 DAG的目标代码（208）小结（211）习题九（211）参考答案（212）附录A LEX（LexicalCompiler）和YACC（YetAnotherCompiler-Compiler）工具（215） A.1 简介（215） A.2 LEX词法分析自动生成程序（215） A.2.1 语言LEX的一般描述（216） A.2.2 LEX的常规表达式（216） A.2.3 LEX编程（218） A.2.4 高级LEX（219） A.3 YACC语法分析自动生成程序（220） A.3.1 YACC规格说明（220） A.3.2 YACC编程（220）附录B 编译程序实验（223） B.1 选择实验题目的途径（223） B.2 实验题（224）实验一（224）实验二（224）实验三（225） 6编译原理实验四（225）实验五（226）实验六（226） B.3 实验报告范例（227）一、分析（228）二、算法（229）三、实现（229）四、总结（230）附录（231）参考文献（237）

一、关于编译原理编译原理是计算机专业的一门核心课程，在计算机本科教学中占有十分重要的地位。设置本课程的目的在于系统地向学生讲述编译程序设计的基本理论、编译系统的结构及编译程序各部分的设计原理和实现技术。通过对这些知识的学习，使学生既能掌握编译理论和编译方法等方面的基本知识，又具有设计、实现、分析和维护编译程序等方面的能力。由于编译原理课程具有很强的理论性和实践性，因而学生在学习过程中普遍感到内容抽象，不易理解，掌握起来难度较大。因此，本书在编写过程中充分考虑到各类学生的特点，力求将基本概念、基本原理和实现方法的思路阐述清楚，条理清晰，通俗易懂，同时书中还穿插了大量的实例，便于自学。为了帮助学生掌握每章的重点和难点，本书每章附有一定数量的习题，以帮助读者巩固所学内容，并附有习题参考答案，方便读者对照课后的习题进行练习。本书部分章节配有丰富的代码，读者在学习过程中可以结合里面的代码进行相关操作，以巩固所学知识。

二、本书结构全书共分9章，各章内容如下：第1章：编译概述。主要介绍了编译程序及其各个阶段、各阶段的分组及构造工具等具体内容。第2章：文法及语言的基本知识。主要介绍形式语言理论，本书给出了便于理解、有助于研究各种分析方法和设计构造编译程序的形式语言理论。第3章：词法分析及有穷自动机。主要介绍词法分析程序的设计原理和构造方法及有穷自动机。有穷自动机是描述词法的有效工具，也是进行词法分析的主要理论基础。因此，我们专门讨论了有穷自动机与正规文法、正规表达式之间的对应关系以及它的确定化和最小化方面的知识。第4章：语法分析。主要介绍语法分析程序的功能、自上向下语法分析、自下向上语法分析、算符优先分析法、LR 分析法等内容。第5章：语法制导翻译技术和中间代码生成。主要介绍属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式和一些常见语法成分的翻译方法。第6章：符号表的组织和管理。主要讨论符号表的组织和存取符号表的各种方法。第7章：代码优化。主要介绍包括了优化技术的相关知识、局部优化、循环优化与全局优化几种常用优化方法。第8章：运行时存储空间组织。其中考虑了一些重要的语言特征，如过程调用、参数传递、数组和记录的存取方式以及多种存储分配技术。第9章：目标代码生成。主要介绍了代码生成器设计中的问题、目标机器、基本块和流图、下次引用信息等内容。附录：设计了实验内容、实验要求、实验参考算法。

三、本书特点本书简明易懂、条理清晰，用简练的语言结合大量的图、表详细介绍了编译原理的基本原理和相关知识。在编写过程中，作者力图将其中的基本概念、基本编译技术和实现方法的思路阐述清楚，同时书中还穿插了大量的实例。本书各章都配有一定数量的习题和参考答案，以帮助读者巩固所学内容。

四、本书适用对象本书可作为高等院校计算机专业教材，也可以作为成人高等教育计算机专业本科和专科起点本科生的教材，也可以作为计算机专业人员的参考用书。本书第1～3章由蒋伟进编写，第4章由万亚平和蒋伟进编写，第5章由卿桐编写，第6～7章由戴英明编写，第8章由雷向东编写，第9章及附录由吴取劲编写，第5～9章部分习题及参考答案由蒋伟进编写，全书由蒋伟进统稿。陈火旺院士担任主审，在本书出版前，陈火旺院士仔细审阅了书稿，提出了很多宝贵意见，在此表示诚挚的谢意。在本书编写过程中还得到湖南省计算机学会、中南大学出版社的领导和有关同志的支持、关心和帮助，对此也表示衷心的感谢。吴超、张亚西、蔡勋良、孙学安、宁兵等同学也倾注了许多劳动并做了大量的校对和整理工作，在此一并表示感谢。在成书过程中，我们参考了许多相关文献，在此，亦谨向它们的作者表示诚挚的感谢。书中如有不妥和纰漏之处，谨请读者和专家指正。本书配有电子教案，需要者可向出版社免费索取。

编者

2005年6月