编译原理实验指导

1、yu zhang, ustc 编译原理实验指导编译原理实验指导张昱张昱计算机科学与技术学院计算机科学与技术学院中国科学技术大学中国科学技术大学 合肥合肥2010.4.26yu zhang, ustcyu zhang, ustc编译原理实验指导编译原理实验指导2资源资源v 编译原理实验教程及实验软件包编译原理实验教程及实验软件包 http:/ 张昱，陈意云张昱，陈意云.编译原理实验教程编译原理实验教程.高等教育出版社，高等教育出版社，2009.5v 开发环境与工具（参见实验教程开发环境与工具（参见实验教程1.3节）节） java语言语言规范规范（第（第3版）版）jls3- http:/ java

2、 1.5的文法规范文件：的文法规范文件：java15.cup，java15.jj 抽象语法树：抽象语法树：eclipse ast- jdt plug-in developer guide referenceapi reference org.eclipse.jdt.core.dom java开发运行环境：开发运行环境：jdk+ant eclipse ide 编译器的自动生成工具：编译器的自动生成工具：jflex，java cup(lalr)/javacc（ll(k)） 目标代码的运行：目标代码的运行：gcc( mingw)，spimyu zhang, ustcyu zhang, ustc编译原

3、理实验指导编译原理实验指导3编译器实现框架编译器实现框架yu zhang, ustcyu zhang, ustc编译原理实验指导编译原理实验指导4实验入门指南实验入门指南初步了解初步了解v 开发基础开发基础 eclipse ide + jdk + ant（实验教程第（实验教程第1章）章）- 命令控制台命令控制台+jdk + ant- 汇编码的运行：汇编码的运行：gcc、spim 自主研发的实验平台及支持库（实验教程第自主研发的实验平台及支持库（实验教程第2章及后续章节）章及后续章节）v 实验语言实验语言 从从simpleminijool语言（见实验教程语言（见实验教程2.1节）及其实现入手节）

4、及其实现入手 最终要求实现最终要求实现skipoominijool语言的编译器语言的编译器- 词法：实验教程词法：实验教程3.2节；语法：节；语法：4.1节；语义：节；语义：5.1节节v 中间表示中间表示 eclipse ast：（见实验教程：（见实验教程2.4，2.5节）节） lir：（见实验教程：（见实验教程6.2节）节）yu zhang, ustcyu zhang, ustc编译原理实验指导编译原理实验指导5实验入门指南实验入门指南初步了解初步了解v目标机目标机x86 cisc生成的汇编码能由生成的汇编码能由gcc编译生成可执行文件编译生成可执行文件mips risc生成的汇编码能由生成

5、的汇编码能由spim模拟器解释执行模拟器解释执行汇编码简介：实验教程汇编码简介：实验教程7.2和和7.3节节v汇编码的内部表示汇编码的内部表示air：实验教程：实验教程7.4节节yu zhang, ustcyu zhang, ustc实验软件包：课程设计开发包目录实验软件包：课程设计开发包目录编译原理实验指导编译原理实验指导6v课程设计开发包目录课程设计开发包目录yu zhang, ustcyu zhang, ustc实验软件包：实验支持库的构成实验软件包：实验支持库的构成编译原理实验指导编译原理实验指导7yu zhang, ustcyu zhang, ustc实验运行平台实验运行平台编译原理

6、实验指导编译原理实验指导8参见实验教程参见实验教程2.3节节v目的目的提供各类编译器组件及组件间信息访问的接口，简称提供各类编译器组件及组件间信息访问的接口，简称实验平台接口。实验平台接口。提供一个实验运行平台，它能够将若干个编译器组件提供一个实验运行平台，它能够将若干个编译器组件连接装配成一个完整的编译器或解释器并控制它们的连接装配成一个完整的编译器或解释器并控制它们的运行。运行。用户可以通过平台配置文件灵活地定制待装配的各个用户可以通过平台配置文件灵活地定制待装配的各个编译器组件以及待编译或解释执行的源程序文件等。编译器组件以及待编译或解释执行的源程序文件等。yu zhang, ustcy

7、u zhang, ustc实验平台接口实验平台接口编译原理实验指导编译原理实验指导9yu zhang, ustcyu zhang, ustc实验任务实验任务(1)v每一学生可选的待开发组件每一学生可选的待开发组件组件组件1：带语义检查的分析器：带语义检查的分析器(生成生成ast) 组件组件2：带语义检查的分析器：带语义检查的分析器(生成生成lir) 组件组件3：基于：基于ast的的x86汇编代码生成器汇编代码生成器组件组件4：基于：基于ast的的mips汇编代码生成器汇编代码生成器组件组件5：基于：基于lir的的x86汇编代码生成器汇编代码生成器组件组件6：基于：基于lir的的mips汇编代码

8、生成器汇编代码生成器v合作伙伴的组合方式合作伙伴的组合方式组件组件1+组件组件3+gcc 组件组件1+组件组件4+spim组件组件2+组件组件5+gcc 组件组件2+组件组件6+spim编译原理实验指导编译原理实验指导10yu zhang, ustcyu zhang, ustc实验任务实验任务(2)v前端任务：组件前端任务：组件1或组件或组件2词法分析、语法分析、静态语义分析、中间表示的生成词法分析、语法分析、静态语义分析、中间表示的生成其中涉及符号表的设计与实现其中涉及符号表的设计与实现v后端任务：组件后端任务：组件3组件组件6之一之一需要考虑动态语义检查（如数组下标越界）、短路计算、需要考

9、虑动态语义检查（如数组下标越界）、短路计算、寄存器分配等，但是对代码优化不作要求。寄存器分配等，但是对代码优化不作要求。独立开发后端时，需要设计和实现符号表独立开发后端时，需要设计和实现符号表生成的生成的x86汇编代码应能直接用汇编代码应能直接用gcc汇编连接得到可执行汇编连接得到可执行文件，生成的文件，生成的mips汇编代码则应能在汇编代码则应能在spim上执行上执行若需要使用其他目标平台，必须在若需要使用其他目标平台，必须在6月月13日前与张昱老日前与张昱老师联系并确认是否可以使用。师联系并确认是否可以使用。编译原理实验指导编译原理实验指导11yu zhang, ustcyu zhang,

10、 ustc实验任务实验任务(3)v最终的编译器最终的编译器自行选择前后端自行选择前后端- 定义好接口，不开放源代码，只提供定义好接口，不开放源代码，只提供jar文件和接口说明，运文件和接口说明，运行时应能输出作者名行时应能输出作者名- 你的前端（后端）被采用得越多，则得分越高你的前端（后端）被采用得越多，则得分越高每个同学只负责自己提交的编译器的质量。每个同学只负责自己提交的编译器的质量。组件发布人不必考虑其发布的版本被使用的所有编译组件发布人不必考虑其发布的版本被使用的所有编译器的质量。器的质量。编译原理实验指导编译原理实验指导12yu zhang, ustcyu zhang, ustc提交

11、和发布时间节点提交和发布时间节点v提交节点提交节点5月月16 提交系统设计书，包括进度表和提交系统设计书，包括进度表和拟开发的组件拟开发的组件5月月22前前 经老师认可学生可调整拟开发的组件经老师认可学生可调整拟开发的组件5月月30 提交已完成源代码和前后端接口描述提交已完成源代码和前后端接口描述6月月13 再次提交已完成源代码和进度报告再次提交已完成源代码和进度报告6月月20 提交源文件、类库文件、测试程序、设计文档提交源文件、类库文件、测试程序、设计文档等等6月月22 提交课程实践的收获、体会和建议（发邮件给提交课程实践的收获、体会和建议（发邮件给张昱老师）张昱老师） v发布节点发布节点6

12、月月13 发布测试程序发布测试程序6月月15 发布测试环境，对最终提交文档的规定发布测试环境，对最终提交文档的规定编译原理实验指导编译原理实验指导13每次提交时需要说明当前的执行进每次提交时需要说明当前的执行进度与计划中的出入与原因，以及对度与计划中的出入与原因，以及对计划的调整（如果有的话）！计划的调整（如果有的话）！yu zhang, ustcyu zhang, ustc课程设计成绩评定课程设计成绩评定(1)v评分方式和过程评分方式和过程10- -12个学生一组，大家参与，公开评分个学生一组，大家参与，公开评分评委：评委：1个教师、助教、同组所有同学个教师、助教、同组所有同学教师主导测试过

13、程、学生自己动手按老师要求操作，教师主导测试过程、学生自己动手按老师要求操作，并用投影机当众显示测试过程并用投影机当众显示测试过程老师提问，同组同学也可以提问，当众回答老师提问，同组同学也可以提问，当众回答问题主要围绕完成的设计和编程，以及测试中暴露出问题主要围绕完成的设计和编程，以及测试中暴露出的设计或编程错误的设计或编程错误编译原理实验指导编译原理实验指导14yu zhang, ustcyu zhang, ustc课程设计成绩评定课程设计成绩评定(2)v评分依据评分依据工程的规范性工程的规范性编译器的正确性编译器的正确性错误定位与恢复能力错误定位与恢复能力所生成的目标代码的质量所生成的目标

14、代码的质量 回答问题时所表现出的对本课程设计所涉及的编译知回答问题时所表现出的对本课程设计所涉及的编译知识的掌握程度识的掌握程度对自己设计和编码的编译器和解释器的熟悉程度对自己设计和编码的编译器和解释器的熟悉程度操作的熟练程度操作的熟练程度所提交文档的完整性、条理性及其中反映的分析和设所提交文档的完整性、条理性及其中反映的分析和设计的思想计的思想编译原理实验指导编译原理实验指导15yu zhang, ustcyu zhang, ustc课程设计成绩评定课程设计成绩评定(3)v成绩确定成绩确定每个评委给该组同学排名次，同学评委的排名要包括自每个评委给该组同学排名次，同学评委的排名要包括自己己由助

15、教根据所有有效排名表，给出最终的排名由助教根据所有有效排名表，给出最终的排名由老师根据本组的情况，确定本组的最高分和最低分，由老师根据本组的情况，确定本组的最高分和最低分，依据排名，按等间隔确定每个同学的分数依据排名，按等间隔确定每个同学的分数被老师、助教和过半数同学认为所提交文档不是自己课被老师、助教和过半数同学认为所提交文档不是自己课程设计成果时，则程设计成果时，则0分分未按时交也是未按时交也是0分分编译原理实验指导编译原理实验指导16yu zhang, ustcyu zhang, ustc课程设计成绩评定课程设计成绩评定(4)v奖惩奖惩若所开发的前端若所开发的前端(或后端或后端)被多个同

16、学被多个同学(开发的合作伙伴除开发的合作伙伴除外外)采用，则在分组评分的基础上加分，加分原则是：采用，则在分组评分的基础上加分，加分原则是：1、每增加两个采用者加、每增加两个采用者加1分；分；2、课程设计和平时作业合计不超过、课程设计和平时作业合计不超过50分。分。独自完成整个编译器，分组评定成绩后降独自完成整个编译器，分组评定成绩后降10分分前后端人数比例严重失调，抬高少数人一端分数前后端人数比例严重失调，抬高少数人一端分数v备注备注成绩评定可能有考虑不周的地方，解释权在老师成绩评定可能有考虑不周的地方，解释权在老师系统地发现所提供的参考源代码中的错误，给予表彰和系统地发现所提供的参考源代码

17、中的错误，给予表彰和奖励奖励编译原理实验指导编译原理实验指导17yu zhang, ustcyu zhang, ustc编译原理实验指导编译原理实验指导18实验入门指南实验入门指南深入学习深入学习1v开发基础开发基础写一个简单的写一个简单的java程序程序 mydir/src/test.java或者直接利用或者直接利用lab1中的代码中的代码lab1/src/用用eclipse编译和调试编译和调试- 尝试按实验教程中尝试按实验教程中1.3.3节介绍的各种方法来建立工程节介绍的各种方法来建立工程- 学习在学习在eclipse下调试和运行下调试和运行在命令控制台下编译和调试在命令控制台下编译和调试

18、- 用用javac编译编译java源程序，得到源程序，得到java字节码字节码- 用用java运行运行java字节码字节码- 写一个写一个ant编译文件（参见实验教程中编译文件（参见实验教程中1.3.4节），用节），用ant来编来编译和运行译和运行java程序程序- 用实验平台运行，熟悉配置文件用实验平台运行，熟悉配置文件yu zhang, ustcyu zhang, ustc编译原理实验指导编译原理实验指导19实验入门指南实验入门指南深入学习深入学习2v skipoominijool语言及其语言及其ast 编写编写skipoominijool程序程序- 目的：了解语言特点，所写程序可以作为测

19、试程序目的：了解语言特点，所写程序可以作为测试程序 查看查看skipoominijool程序的程序的ast- 方法：参见方法：参见lab3- 目的：通过目的：通过ast图形化输出了解一个图形化输出了解一个skipoominijool程序与其程序与其ast的对应关系的对应关系 手工构造手工构造simpleminijool程序的程序的ast- 方法：参见实验教程第方法：参见实验教程第2章，章， testcase.java等等- 从小语言入手来学习从小语言入手来学习ast的构造的构造构造构造ast的一些注意事项的一些注意事项- 关于关于list类型的实例：可以用类型的实例：可以用java.util.

20、linkedlist（或（或arraylist）- 一个一个ast节点不能被多棵节点不能被多棵ast（子树）所引用（子树）所引用yu zhang, ustcyu zhang, ustc编译原理实验指导编译原理实验指导20实验入门指南实验入门指南深入学习深入学习3v前端：词法分析语法分析语义分析前端：词法分析语法分析语义分析做法做法- 使用使用jflex+cup来生成分析器的源码来生成分析器的源码: 参见参见ch4和和ch5- 使用使用javacc来生成分析器的源码来生成分析器的源码: 参见参见ch5- 手工编写分析器手工编写分析器先支持先支持simpleminijool，再扩展到，再扩展到sk

21、ipoo语言中的注意点：语言中的注意点：- 变量的作用域，同名问题的处理，等等变量的作用域，同名问题的处理，等等了解了解ast访问者类、管理符号的一些容器类访问者类、管理符号的一些容器类(如如hashmap)、list等等等等各类符号的描述信息各类符号的描述信息定义符号类、符号表类定义符号类、符号表类yu zhang, ustcyu zhang, ustc编译原理实验指导编译原理实验指导21实验入门指南实验入门指南深入学习深入学习4v前端：词法分析语法分析语义分析前端：词法分析语法分析语义分析利用分析器的生成工具构造分析器时利用分析器的生成工具构造分析器时,- 先构造简单的语法分析器：不构造先

22、构造简单的语法分析器：不构造ast、不进行错误处理、不进行错误处理重点重点：熟悉分析器的生成工具及其使用方法：熟悉分析器的生成工具及其使用方法- 再构造能输出再构造能输出ast的语法分析器，它只能分析正确的源程序的语法分析器，它只能分析正确的源程序重点重点：熟悉在产生式的语义动作中添加构造：熟悉在产生式的语义动作中添加构造ast的代码的代码- 再构造能处理语法错误并产生再构造能处理语法错误并产生ast的语法分析器的语法分析器重点重点：识别哪些错误？如何处理错误？如何恢复错误？错误：识别哪些错误？如何处理错误？如何恢复错误？错误信息？信息？- 以以ast visitor的实现类为基础实现语义检查的实现类为基础实现语义检查重