购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP
作者简介

许畅,南京大学计算机科学与技术系教授,教育部“101计划”编译课程建设专家。2008年在香港科技大学获得博士学位,2010年入选教育部新世纪优秀人才支持计划,2011年获得国家科技进步二等奖,2015年获得CCF青年科学家奖,2021年入选教育部长江学者奖励计划。主持和参与了多项国家和省部级科研项目,包括国家重点研发计划和自然科学基金重点项目等。研究兴趣包括大数据、软件工程、智能软件测试与分析,以及自适应与自控软件系统。发表了180余篇学术论文,工作被包括 TOSEM TSE 、ESEC/FSE、ICSE和《中国科学》等在内的国内外知名期刊和会议收录,曾获ACMSIGSOFT杰出论文奖4次和国际会议最佳论文奖3次。服务于ESEC/FSE、ICSE和ASE等程序委员会,担任 JSEP JCST FCS 和《计算机科学》等期刊编委。

冯洋,南京大学计算机科学与技术系助理研究员。2019年在加州大学欧文分校获得博士学位。主要研究方向为复杂软件系统的质量保障及可信程序设计语言工程技术,研究课题包括大型复杂软件系统的质量保障问题及可信软件基础设施构建与工程技术问题。主持和参与了多项国家和省部级科研项目,包括国家重大专项计划、自然科学基金面上项目和青年项目。近年来在软件工程领域的ICSE、FSE、ASE、ISSTA、 TSE TOSEM 、《中国科学》《软件学报》等期刊和会议发表学术论文40余篇,获得ACM杰出论文奖两次。申请发明专利多项,部分专利成果已经在华为、百度等知名公司转化应用。

郑艳伟,山东大学计算机科学与技术学院副研究员。2019年在北京航空航天大学获博士学位。主要研究方向包括计算机视觉、目标驱动的视觉导航、编译器构造。主持了国家重点研发计划与课题和自然科学基金重点项目与课题;主持多项横向项目,曾参与华为昇腾芯片算子和众智项目开发,曾在RPA中设计了一种脚本语言并开发了解释器。近年来在ICDE、 Com-Com IoT-J 、WASA、《中国科学》等期刊和会议发表学术论文20余篇,申请发明专利30余项,担任 IoT-J JMLC SPL CIT 等期刊审稿人。

本书是在教育部计算机领域本科教育教学改革试点工作计划(简称“101计划”)“编译原理”课程组的组织下编写的理论教材之一。本书从理论和实践两个方面指导与帮助学生深刻理解编译器的工作原理。其中,理论方法的教学使得学生能够理解编译器运行过程中的核心算法,而实践技术则帮助学生掌握理论方法及算法在代码实现层面的设计与编码要点,最后结合实践内容对理论方法与实践技术进行巩固。

本书适合作为高校计算机及相关专业编译原理课程的教材,也适合作为研发人员了解编译技术的参考书。 HmVFNwXUyaqsbqNBNfSr+ODvdG4hUPrRTdBE4Y3Ek1NB7ULhCHsXPBfMVrWSnwpa



出版说明

为深入实施新时代人才强国战略,加快建设世界重要人才中心和创新高地,教育部在2021年年底正式启动实施计算机领域本科教育教学改革试点工作(简称“101计划”)。“101计划”以计算机类专业教育教学改革为突破口与试验区,从教育教学的基本规律和基础要素着手,充分借鉴国际先进资源和经验,首批改革试点工作以33所计算机类基础学科拔尖学生培养基地建设高校为主,探索建立核心课程体系和核心教材体系,提高课堂教学质量和水平,引领高校人才培养质量的整体提升。

核心教材体系建设是“101计划”的重要组成部分。“101计划”系列教材基于核心课程体系的建设成果,以计算概论(计算机科学导论)、数据结构、算法设计与分析、离散数学、计算机系统导论、操作系统、计算机组成与系统结构、编译原理、计算机网络、数据库系统、软件工程、人工智能引论这12门核心课程的知识体系为基础,充分调研国际先进课程和教材建设经验,汇聚国内具有丰富教学经验与学术水平的教师,成立本土化“核心课程建设及教材写作团队”,由12门核心课程负责人牵头,组织教材调研、确定教材编写方向以及把关教材内容。工作组成员协同分工,一体化建设教材内容、课程教学资源和实践教学内容,打造了一批具有“中国特色、世界一流、101风格”的精品教材。

在教材内容上,“101计划”系列教材确立了如下的建设思路和特色:坚持思政元素的多元性,积极贯彻《习近平新时代中国特色社会主义思想进课程教材指南》,落实立德树人根本任务;坚持知识体系的系统性,构建核心课程的知识图谱,系统规划教学内容;坚持融合出版的创新性,规划“新形态教材+网络资源+实践平台+案例库”等多种出版形态;坚持能力提升的导向性,借助“虚拟教研室”组织形式、“导教班”培训方式等多渠道开展师资培训,提升课堂教学水平,提高学生综合能力;坚持产学协同的实践性,遴选一批领军企业参与,为教材的实践环节及平台建设提供技术支持。总体而言,“101计划”系列教材将探索适应专业知识快速更新的融合教材,在体现爱国精神、科学精神和创新精神的同时,推进教学理念、教学内容和教学手段方面的有效提升,为构建高质量教材体系提供建设经验。

本系列教材在教育部高等教育司的精心指导下,由高等教育出版社牵头,联合机械工业出版社、清华大学出版社、北京大学出版社等共同完成系列教材出版任务。“101计划”工作组从项目启动实施至今,联合参与高校、教材编写组、参与出版社,经过多次协调研讨,确定了教材出版规划和出版方案。同时,为保障教材质量,工作组邀请23所高校的33位院士和资深专家完成了规划教材的编写方案评审工作,并由21位院士、专家组成了教材主审专家组,对每本教材的撰写质量进行把关。

感谢“101计划”工作组33所成员高校的大力支持,感谢教育部高等教育司的悉心指导,感谢北京大学郝平书记、龚旗煌校长和学校教师教学发展中心、教务部等相关部门对“101计划”从酝酿、启动到建设全过程给予的悉心指导和大力支持。感谢各参与出版社在教材申报、立项、评审、撰写、试用等出版环节的大力投入与支持,也特别感谢12位课程建设负责人和各位教材编写教师的辛勤付出。

“101计划”是一个起点,其目标是探索适合中国本科教育教学的新理念、新体系和新方法。“101计划”系列教材将作为计算机类专业12门核心课程建设的一个里程碑,与“101计划”建设中的课程体系、知识点教案、课堂提升、师资培训等环节相辅相成,有力推动我国计算机领域本科教育教学改革,全面促进课堂教学效果的进一步提升。

“101计划”工作组 HmVFNwXUyaqsbqNBNfSr+ODvdG4hUPrRTdBE4Y3Ek1NB7ULhCHsXPBfMVrWSnwpa



前言

本书是在教育部计算机领域本科教育教学改革试点工作计划(简称“101计划”)“编译原理”课程组的组织下编写的理论教材之一。与其他同类理论教材相比,本书在介绍编译理论和方法的同时,更强调实践技术,并注重编译理论与实践的结合。在内容方面,本书的理论部分涵盖了当前主流编译器编译过程中的核心技术要点,实践部分则引导学生基于理论知识构建一个能够将以类C语言编写的源程序编译为MIPS目标语言代码的完整编译器。在教学中,教师能够参考本书完整地进行理论教学和实践指导,其内容已经包括了相关资料。

一方面,当前许多“编译原理”课程理论教材以传授理论知识为主,其中的内容离编译器具体实践尚有一定的距离。这可能使学生偏重学习理论和方法,而对编译器实现缺乏更为深刻的理解。另一方面,常规的“编译原理”实践课程大多基于一门相对简易的编程语言,要求学生实现支持该语言语法和语义处理部分的编译器。由于缺乏规范化的实践指导,有时会降低教学要求,不得不允许学生“灵活”(较为随意)地实现编译器的功能;又或者由于教学要求过高,学生在无实践指导的情况下对编译器实现无法下手,而对课程产生较大的抵触心理。针对这些问题,本书面向开设计算机学科的大专院校,提供一门接近实际C语言的C--语言,从理论方法的解说到实践指导的进行,引导性地讲解理论知识和编译器的具体实现,并提供充分的测试样例来验证编译器实现的正确性。

整体而言,基于本书介绍的理论方法和实践技术,我们设计了相应的实践内容,系统性地覆盖理论方法和实践技术部分的各个知识点。本书的实践内容具有四个特点:一是接近实际,所采用的语言是C--语言,该语言接近现实中常用的C语言,这使得所设计与实现的编译器更为实用,甚至在特定领域可以直接或经过少量修改后使用;二是结合相关的实践技术进行介绍,引导学生完成一个完整编译器的设计与实现,不会使学生出现面对编译器实现要求无从下手或不得不求助于第三方额外资料的情况;三是具备相关的实现验证帮助,我们提供了充分的测试样例来帮助验证编译器实现的正确性,而无须自行设计测试用例;四是难度可调,我们提供了实践内容的多种执行方案,既可以统一难度要求,也可以区分必做内容和选做内容,还可以采用学生分组方案,使得每个组队实现不同的功能组合,激发学生的思考创新能力,并锻炼其合作能力。

下面我们就本书的使用方式、时间安排以及质量控制给出一些建议。

使用方式

本书包含五个核心章(从第2章至第6章),前后贯穿,分别为词法分析和语法分析、语义分析、中间代码生成、目标代码生成以及中间代码优化。每章的理论和实践内容依赖于前续章,教学需按顺序进行。

在这五章中,除了第5章之外,其他章节的实践内容均分为必做部分和选做部分,而选做部分则进一步分为几种不同的要求(第5章仅有必做部分)。这五章中的实践内容特别考虑了不同院校的教学要求以及学生之间的能力差异,因而可以采用多种方式教学:

1. 对所有学生要求相同 :这是最简单的使用方式,适用于学习编译原理的所有学生都需要通过相同考核要求的情况。具体而言,可进一步划分为下面三种情况:

(1) 对所有学生要求最低 :完成所有实践的必做部分,即可获得满分。

(2) 对所有学生要求最高 :完成所有实践的必做部分和选做部分,才可获得满分。

(3) 对所有学生要求自选 :完成所有实践的必做部分,即可得满分。但若能额外完成实践的选做部分,则可视完成的情况获得额外奖励。

2. 对不同学生要求不同 :这种使用方式适用于学习编译原理的学生需要通过不同考核要求的情况。比如强化班和普通班的学生一起上编译原理课程,则要求强化班学生完成所有实践的必做部分和选做部分才可获得满分,而普通班学生完成所有实践的必做部分即可得满分,但若能额外完成实践的选做部分,则可获得额外奖励。

3. 对不同组队要求不同 :这是最复杂的使用方式,适用于允许学生自由组队以共同完成实践要求的情况。推荐的组队规模是一至三人,比如,若双人组队则为正常模式,可获得实践满分,若三人组队则为互助模式,需适当减少实践总分(如变为原来满分的90%),若单人组队则为高手模式,可适当提高实践总分(如变为原来满分的110%)。在实践要求方面,仍可考虑不同的考核要求而组合不同的必做和选做部分,或者完成指定或随机选择的实践要求。比如,一位强化班学生需要完成所有实践的必做部分和选做部分才可获得满分,他可以单人组队进入高手模式以获得更高的总分,也可以双人组队进入正常模式,以减少实践难度。

时间安排

本书从第2章至第6章是核心教学内容,一个学期完成教学,预计时长17周,每周2~3课时。各章的内容应依顺序进行教学,每完成前一章中理论方法和实践技术部分的教学即可开始后一章中对应部分的教学。实践内容部分作为课程项目布置,可略晚开始,比如,第2章的实践内容可从第2周开始布置,以保证前期进行了必要的理论方法和实践技术的讲授和准备,而后续章节的实践内容可与教学同步进行。一般而言,如果一个学期时长17周,建议第1章和第2章的教学内容在第1~5周内完成,第3章的教学内容在第6~9周内完成,第4章的教学内容在第10~12周内完成,第5章和第6章的教学内容在第13~17周内完成,其中第5章的理论教学在第13周和第14周内完成,第6章的理论教学内容在第15~17周内完成。下图展示了一个教学计划的安排示例。

教学安排计划甘特图

需要说明的是,第5章和第6章实践内容的输入均是中间代码。在我们完成了第5章的实践内容之后,基本上就实现了从C--源程序到MIPS目标程序的整个编译过程。我们设计第6章实践内容的目的是引导学生完成中间代码的优化,让编译器生成更为高效的目标代码。因此,第6章的实践内容相对于其他章节较为独立,可以根据教学和实践情况进行取舍。对于学有余力的学生,建议将第4章实践内容输出的中间代码,输入至第6章实践内容构建的中间代码优化模块中完成优化之后,再输入至第5章构建的中间代码到目标代码的翻译器内,完成整个编译过程。基于此,我们建议从第2周开始第2章词法和语法分析的实践内容,在第5周末结束这部分实践内容并开始第3章语义分析的实践内容,在第9周末结束语义分析的实践内容并开始第4章中间代码生成的实践内容,在第12周末结束中间代码生成的实践内容并同时开始第5章目标代码生成和第6章中间代码优化的实践内容。在第17周末结束时完成第5章和第6章的实践内容,内部可以自由分配两者的时间,最终实现整个编译器。如果一个学期的教学时长更短或更长,可做相应微调,比如,在学时更短的情况下,可以适当提前第2章实践内容的结束时间(由四周变为三周)。

如果由于教学上的特殊安排或其他原因,导致本书的理论方法和实践技术教学落后于实践内容的安排,也可以推迟部分实践内容的结束时间并同时保证后续实践内容的开始时间来形成更为紧凑的安排。比如,若第2章的理论方法和实践技术教学无法在第5周完成,那么可以允许第2章的实践内容推迟一周结束(即在第6周结束),但第3章的实践内容仍保持在第5周开始(即两者重叠一周时间)。这样既可以帮助部分学生更好地完成第2章的实践内容,也可以允许其余学生正常地开始第3章的实践内容。

质量控制

编译原理课程实践的质量控制旨在鼓励学生在完成实践内容的过程中增强学习兴趣,提高所实现编译器的质量,以及抑制不良行为(如抄袭代码)的发生。本书的实践内容设计也正有这方面的考虑。

1. 提高实践质量:本书从测试用例方面来提高实践内容的质量。

本书的实践内容部分提供了大量测试样例来帮助学生自检编译器的实现是否符合实践要求,在教学中也可引入更多的测试用例(可根据实践内容的要求和已有的测试样例推导)来进一步测试学生所实现的编译器的质量,这将促使学生考虑更多的细节来更好地实现编译器。对于教师,我们也可提供更多的测试用例。

2. 抑制不良行为:本书从分组实践和克隆检测两方面来抑制不良行为。

(1)分组实践:本书的实践内容设计了必做部分和选做部分,而选做部分又分为不同的要求,它们之间相互独立。在允许学生自由组队来协作完成实践内容的情况下,可进行必做部分和选做部分的随机组合。比如,根据抽签随机决定一组学生必须完成第2章实践内容的必做部分和选做部分的要求2.1,而另一组学生必须完成必做部分和选做部分的要求2.2,以此类推,后续章节的实践内容也可随机组合。如此可以增强不同组队间所完成内容的差异性,增大抄袭的难度。也可以进一步要求不允许完成其他组队的实践要求,这样也可以抑制不同组队之间的抄袭行为(可以通过测试用例的执行结果区别出是否完成了不允许的实践要求)。但要注意这种做法将与前述使用方式中的“对所有学生要求自选”的情况相抵触。

(2)克隆检测:本书的实践内容设计也允许在不同的学生代码之间进行克隆检测,特别是在分组实践的情况下,学生提交的代码不会完全类似(因为需要实现不同的要求)。为避免代码复制后经过简单变量名和函数名替换后重新提交为新的代码,建议采用基于可执行代码的二进制级克隆检测,并加以源码人工比对确认。采用必要的克隆检测可以进一步抑制学生抄袭代码的行为。

整体而言,本书强调从理论和实践两个方面指导与帮助学生深刻理解编译器的工作原理。其中,理论方法的教学使学生能够理解编译器运行过程中的核心算法,而实践技术则可帮助学生掌握理论方法及算法在代码实现层面的设计与编码要点,最后结合实践内容对理论方法与实践技术进行巩固。同时,本书在设计过程中加入了不同难度的实验要求,教师可以针对实际教学需求,选择不同的教学内容进行授课。

另外,采用本书作为教材的教师可登录https://g.cmptt.com/8ewcx,注册后加入本书数字教研室,下载教辅和相关教学资源、进行教学交流等。

如果在阅读本书的过程中发现谬误,也请各位读者不吝赐教! HmVFNwXUyaqsbqNBNfSr+ODvdG4hUPrRTdBE4Y3Ek1NB7ULhCHsXPBfMVrWSnwpa

点击中间区域
呼出菜单
上一章
目录
下一章
×