“编译原理”是计算机科学与技术专业重要的专业(基础)课程。 本书是普通高等教育“十二五”国家级规划 教材,也是国家精品课程、国家级精品资源共享课程主讲教材,是作者合三十余年在哈尔滨工业大学、北京工业大学讲授该课程的经验和体会,根据将其作为本科生专业技术基础课教学的实际需要选择和组织有关内容撰写而成的,包含了“编译原理”课程所需涵盖的知识。 本书将以知识为载体,对本学科问题求解的典型思想和方法进行探讨,致力于学生四大专业基本能力的培养,为 “能力导向”的课程教学提供有力支持。 为了便于读者学习和掌握有关内容,面向工程应用型学生的培养,在附 录中给出了相应的课程设计。 本书适合于高等学校计算机科学与技术学科本科生“编译原理”课程教学使用,也可供有关专业的学生、教 师和科研人员参考。
从2006年开始,计算机科学与技术专业作为我国工程教育专业认证的试点专业之一,便开始了旨在追求国际等效的工程教育专业认证工作。2016年6月,我国成为《华盛顿协议》的正式成员,标志着我国的工程教育在实现国际接轨上迈出了极其重要的一步。从一定意义上讲,那些通过工程教育专业认证的计算机类专业点的教育是国际等效的。目前,加快包括计算机科学与技术专业在内的计算机类专业的内涵发展步伐,快速提升专业教育水平和质量,使2785个计算机类专业的专业点有更多达到工程教育专业认证的标准,是我们共同的追求。
按照《华盛顿协议》,两年制专科,定位于培养学生解决狭义工程问题的能力;三年制的大专教育,定位于培养学生解决广义工程问题的能力;而本科教育,定位于培养学生解决复杂工程问题的能力。中国工程教育专业认证协会发布的《工程教育认证标准(2015版)》和《华盛顿协议》所给的毕业要求标准,明确地聚焦到了这一基本定位。
那么,什么是复杂工程问题?《华盛顿协议》用如下7个特征进行刻画。其中第(1)条是必备的,第(2)到第(7)条是可选的。必备的条款指出了复杂工程问题的本质,可选的条款可以看作是复杂工程问题的表象。
(1)必须运用深入的工程原理经过分析才可能解决;
(2)需求涉及多方面的技术、工程和其他因素,并可能相互有一定冲突;
(3)需要通过建立合适的抽象模型才能解决,在建模过程中需要体现出创造性;
(4)不是仅靠常用方法就可以完全解决的;
(5)问题中涉及的因素可能没有完全包含在专业标准和规范中;
(6)问题相关各方利益不完全一致;
(7)具有较高的综合性,包含多个相互关联的子问题。
“编译原理”的教学内容几乎吻合了以上全部条款。它包含求解计算机问题和利用计算机技术求解问题的基本原理、最典型最基本的方法;编译原理课程所涉及的问题都需要进行深入的分析;这些问题的解决必须建立恰当的抽象模型,并基于模型进行分析和处理;很多问题需要根据设计开发的实际,综合运用恰当的方法,要在多种因素和“指标”中进行折中,以求全局的优化和良好的系统性能;不仅要设计和实现词法分析器、语法分析器、语义分析器、代码优化器、代码生成器等一系列子系统,还要对它们进行综合和集成,以构成编译系统。所以,该课程不仅使学生掌握“基本原理”“基本技术”“基本方法”,还提供了一个使学生经历计算机“复杂工程”构建过程的机会——构建一个适当规模的教学型编译系统。难怪许多年以前,AlfredV.Aho就在其编著的《编译原理》的开篇写道“编写编译器的原理和技术具有十分普遍的意义,以至于在每个计算机科学家的研究生涯中,本书中的原理和技术都会反复用到。”
就我国目前的教育需求来看,我们不再将编译原理这门课程当作专业课,而是作为专业技术基础课,旨在向学生传授计算机问题求解的基本思想和方法,引导他们经历“复杂工程问题”的求解过程,培养他们包括计算思维能力(狭义的,包括模型的认知、建立和使用在内)、算法设计与分析能力、程序设计与实现能力、系统能力在内的专业能力,以及承担解决复杂工程问题相关的非技术性能力和素质。
按照人才培养方案的系统化设计和实施的要求,本门课程将具体支持相关毕业要求的达成。虽然这门课程全面地体现了支持培养学生解决复杂工程问题能力的需要,我们还是将其目标主要集中在3个方面,并认为通过恰当的教学设计,对另外3个方面也会提供相应的支撑,具体我们将在附录中给出。
蒋宗礼,北京工业大学教授,博士生导师,国家教学名师,CCF杰出教育奖获得者,中国工程教育专业认证资深专家。
1978年3月至1984年7月在哈尔滨工业大学计算机学科学习,先后到美国、加拿大进修,1984年起先后在哈尔滨工业大学和北京工业大学主讲编译原理、形式语言与自动机理论、数据库系统原理、人工神经网络、新生研讨课等课程。
国家精品课程、国家精品资源共享课程“编译原理”负责人,主编国家“十一五”“十二五”规划教材(包括国家普通高等教育精品教材1部,市精品教材多部),《人工神经网络导论》等研究生教材,国家优秀教学团队负责人。获国家教学成果奖2项,各种省市级教学、科研成果20余项。曾获中国高校优秀青年学者、宝钢优秀教师、航天部优秀青年教师等荣誉称号。
主要学术兼职有全国工程教育专业认证协会学术委员会、结论审议委员会、计算机类专业认证委员会委员,教育部高校计算机类专业教学指导委员会副主任,全国高校计算机教育研究会副理事长,中国计算机学会教育专业委员会副主任。
姜守旭,哈尔滨工业大学教授,教学带头人,博士生导师,黑龙江省师德先进个人,宝钢优秀教师奖获得者,国家优秀教学团队骨干成员,中国工程教育专业认证专家。
1986年9月至1990年7月在哈尔滨工业大学计算机系学习,1993年以来在哈尔滨工业大学主讲编译原理、数据库系统、集合论与图论等课程。
主要从事普适计算、无线网络、智能交通系统、物联网等方面的研究,主持或参加国家973计划、国家自然科学基金重点及面上、国防预研及省部级科研项目等20余项,获省部级科技进步三等奖2项,获国家教学成果二等奖1项、省级教学成果一等奖1项、二等奖1项,在VLDB、ICDE、VLDB Journal、TKDE、软件学报等国内外重要学术会议或学术刊物上发表学术论文60余篇,编著国家“十一五”“十二五”规划教材(包括国家精品教材1部,市精品教材多部)、译著1部,国家精品资源共享课“集合论与图论”和黑龙江省精品课“编译原理”负责人,国家双语教学示范课和黑龙江省精品课“形式语言”骨干成员。
第1章 引论
1.1 程序设计语言
1.2 程序设计语言的翻译
1.3 编译程序的总体结构
1.4 编译程序的组织
1.5 编译程序的生成
1.6 本章小结
习题
第2章 高级语言及其文法
2.1 语言概述
2.2 基本定义
2.3 文法的定义
2.4 文法的分类
2.5 CFG的语法树
2.6 CFG的二义性
2.7 本章小结
习题
第3章 词法分析
3.1 词法分析器的功能
3.1.1 单词的分类与表示
3.1.2 词法分析器的输出
3.1.3 源程序的输入缓冲与预处理
3.1.4 词法分析阶段的错误处理
3.1.5 词法分析器的位置
3.2 单词的描述
3.2.1 正则文法
3.2.2 正则表达式
3.2.3 正则表达式与正则文法的等价性
3.2.4 有穷状态自动机
3.2.5 状态转换图
3.2.6 正则表达式转换为状态转换图
3.3 单词的识别
3.3.1 有穷状态自动机与单词识别的关系
3.3.2 单词识别的状态转换图表示
3.3.3 几种典型的单词识别问题
3.3.4 状态转换图的实现
3.3.5 词法分析程序的编写
3.4 词法分析程序的自动生成
3.4.1 Lex源程序
3.4.2 Lex的实现原理
3.5 本章小结
习题
第4章 自顶向下的语法分析
4.1 语法分析概述
4.2 自顶向下的语法分析面临的问题与文法的改造
4.2.1 自顶向下分析面临的问题
4.2.2 对上下文无关文法的改造
4.2.3 11(1)文法
4.3 预测分析法
4.3.1 预测分析器的构成
4.3.2 预测分析表的构造
4.3.3 预测分析中错误的处理
4.4 递归下降分析法
4.4.1 递归下降分析法的基本思想
4.4.2 语法图和递归子程序法
4.4.3 基于语法图的语法分析器的工作方式
4.4.4 语法图的化简与实现
4.4.5 递归子程序法的实现步骤
4.5 本章小结
习题
第5章 自底向上的语法分析
5.1 自底向上的语法分析概述
5.1.1 移进-归约分析
5.1.2 优先法
5.1.3 状态法
5.2 算符优先分析法
5.2.1 算符优先文法
5.2.2 算符优先矩阵的构造
5.2.3 算符优先分析算法
5.2.4 优先函数
5.2.5 算符优先分析的出错处理
5.3 LR分析法
5.3.1 LR分析算法
5.3.2 LR(O)分析表的构造
5.3.3 SLR(1)分析表的构造
5.3.4 LR(1)分析表的构造
5.3.5 LALR(1)分析表的构造
5.3.6 二义性文法的应用
5.3.7 LR分析中的出错处理
5.4 语法分析程序的自动生成工具Yacc
5.4.1 Yacc源程序的结构
5.4.2 Yacc源程序的声明部分
5.4.3 Yacc源程序的规则部分
5.4.4 Yacc源程序的例程部分
5.4.5 Yacc对二义性文法的处理
5.4.6 Yacc的出错处理
5.5 本章小结
习题
第6章 语法制导翻译与属性文法
6.1 语法制导翻译概述
6.2 语法制导定义
6.3 属性计算
6.3.1 依赖图
6.3.2 属性的计算顺序
6.3.3 S-属性定义
6.3.4 1-属性定义
6.3.5 属性计算示例
6.4 翻译模式
6.4.1 翻译模式与语义动作的执行时机
6.4.2 S-属性定义的自底向上翻译
6.4.3 1-属性定义的自顶向下翻译
6.4.4 1-属性定义的自底向上翻译
6.5 本章小结
习题
第7章 语义分析与中间代码生成
7.1 中间代码的形式
7.1.1 逆波兰表示
7.1.2 三地址码
7.1.3 图表示
7.2 声明语句的翻译
……
第8章 符号表管理
第9章 运行时的存储组织
第10章 代码优化
第11章 代码生成
附录 “编译原理”课程教学设计
缩写符号
词汇索引
参考文献