结合开源软件的 编译原理教学实践探索 张昱 中国科学技术大学计算机科学与技术学院 2017 年高等院校计算机系统类课程联合研讨会 2017.8.26 恩施
中科大的编译原理课程 计算机专业分两个级别, 同时间段授课, 学生可以选择 英才班 (30+) 从 2010 级开始 54+40 加大实验强度, 基础实验 + 扩展实验, 占总分 50% 普通班 54+40 基础实验, 实验占总分 20~30% 学生均要开发出小型实验型语言的编译器 计算机双学位 54+20 周六上课,4 节 / 次, 弱化实验 (2 个 ), 内容适当删减 2
编译课程实践系统 3
2009 年的软件包 以 源语言 - 抽象语法树 - 低级中间表示 - 汇编代码的内部表示 - x86/mips 汇编 为主线搭建的 基于组件的编译原理实验体系 源语言程序 分析器 高级中间表示 (AST) 解释器 变换器 (AST2LIR) 检查器正确? 低级中间表示 ( 如三地址码 ) 变换器 (IR 优化器 /IR 之间的转换器 ) 寄存器分配器 代码生成器 汇编代码的内部表示 汇编代码 ( 如 x86, MIPS) 4
报告目录 1 问卷调查 -- 实践的重要性 2 3 4 5 教学实践的总体思路 Flex+Bison => ANTLR 引进 LLVM 的课程实践探索下一步的工作 5
报告目录 1 问卷调查 -- 实践的重要性 2 3 4 5 教学实践的总体思路 Flex+Bison => ANTLR 引进 LLVM 的课程实践探索下一步的工作 6
安徽省内高校课程问卷调查 共收集 21 份 20 所高校 1 所 985+2 所 211: 中科大 合工大 安大 6 所本科第一批次 : 安财 安工程 安工业 安建大 安农 10 所本科第二批次 : 安庆师大 淮北师大 合肥学院 皖西学院 淮南师院 铜陵学院 池州学院 阜阳师院 安徽新华学院 安徽信息工程学院 1 所高职专科 : 合肥职业技术学院 7
问卷统计数据 开课学期 4 5 10 2 理论课时实验课时学分每年上编译学生数 平均值 46.2 17.38 3.3 147 最大值 64 54 6 400 最小值 32 0 2 10 合计 :3087 8
问卷统计数据 开课学期 4 5 10 2 合职院 软件技术 专业必修,2 下理论课 3 上实践课, 均是 3 学分 54 学时 理论课时实验课时学分每年上编译学生数 平均值 46.2 17.38 3.3 147 最大值 64 54 6 400 最小值 32 0 2 10 合计 :3087 9
编译教学的困难与问题 普遍反映在实验方面 有 2 所学校无实验, 导致学习过程更为抽象 没有好的实验教材, 缺少案例分析 编译原理技术与实际应用如何结合 即便实验部分简单, 但完成度也不高 有的以实现书上算法为实验内容 教材 偏重理论, 缺乏对具体实现的介绍 内容陈旧 师资 课程难 10
期望解决和推进的工作 加强实验 有好的实验教材, 能建设实验教学案例 尽可能将编译技术与实际应用相结合 实验的可操作性, 实验的平台选择, 增加课时等 教材 理论问题实践化, 抽象问题通俗化 对原理解释的过程中穿插代码, 让学生了解实现 召开省内课程研讨会, 加强交流, 互相促进 师资 11
报告目录 1 问卷调查 -- 实践的重要性 2 3 4 5 教学实践的总体思路 Bison => ANTLR 引进 LLVM 的课程实践探索下一步的工作 12
大环境的变化 开源软件盛行 GitHub(2007-):65+ 百万项目 23+ 百万用户 编程语言百花齐放 众多 :GitHub -- 开源项目涉及 316 种编程语言 发展 :C - C90, C99, C11; C++ - 98, 03, 06, 11, 14 最流行的语言 ( 动态变化 ) GitHub :JavaScript, Java, Python, Ruby, PHP, C Tiobe(8 月 ):Java, C, C++, C#, Python, VB.NET 系统规模日趋庞大 + 多语言混合 + 异构体系 工业界期待更多学习了 PL 原理的学生 [CACM2015.5] 13
编译课程的教学 Alfred V. Aho[SIGCSE Bulletin 2008.12] 过于强调解析和语法制导翻译的理论 理论 + 实践 (AWK,1977-) 早期与现代编译器的差异 ( 规模大 语言多 结构多 ) 教学覆盖编译器各阶段的基本概念 词法分析 语法分析 语义分析 中间代码生成 运行时环境 资源管理 目标代码生成 [ 优化 ] 实现一个小型编程语言的编译器 让学生组队自己定义语言并实现, 写相关的文档 14
教学实践的总体思路 目标 重实践 :20% 期中 +20% 期末 +10% 作业 +50% 实验 形式化能力 : 形式描述语言的词法 语法 语义通过查语言规范和编译器手册来领悟语言的语义 工程能力 : 定义 DSL 操控上规模的软件 过程管理 个人 / 团队 创新 了解现代编译系统 实施方法 基础实验 ( 小型编译器 )+ 阅读理解 ( 开源软件 ) + 可选的综合实践 git 版本管理 上届优秀本科生作助教, 参与实践案例的构造, 形成良性循环 15
报告目录 1 问卷调查 -- 实践的重要性 2 3 4 5 教学实践的总体思路 Flex+Bison => ANTLR 引进 LLVM 的课程实践探索下一步的工作 16
解析器的生成器 生成器 生成 Lexer:Flex(for windows) Jflex 生成 Parser LALR: Bison(for windows) Java CUP LL: JavaCC ANTLR LL(*) [PLDI2011] 文法对 Parser 的影响 LR Parser 的优势 : 速度快 表达能力强 LL Parser 的优势 : 代码结构与文法对应, 易理解, 容易增加错误处理和错误恢复 17
ANTLR ANTLR(ANother Tool for Language Recognition) [http://www.antlr.org/] Prof. Terence Parr, since 1989 支持多种代码生成目标 Java C++ C# Python Go JavaScript Swift 18
基于 开展的实验 开源 : 源码阅读, 消化 理解生成 器基于的原理 各种语言实现 :31 种模式 1. 从文法到递归下降识别器 2. LL(1) 递归下降词法分析器 3. LL(1) 递归下降语法解析器 4. LL(k) 递归下降语法解析器 5. 回溯解析器 6. 记忆解析器 7. 谓词解析器 8. 解析树 ( 分析树 ) 9. 同型抽象语法树 10. 规范化异型 AST 11. 不规则的异型 AST 12. 内嵌遍历器 13. 外部访问者 14. 文法访问者 15. 模式匹配者 ( 子树 ) 16. 单作用域符号表 17. 嵌套作用域符号表 18. 数据聚集的符号表 19. 类的符号表型 20. 计算表达式的类型 21. 自动类型提升 22. 静态类型检查 23. 动态类型检查 24. 语法制导的解释器 25. 基于树的解释器 26. 字节码汇编器 27. 栈式解释器 28. 寄存器解释器 29. 语法制导的翻译器 30. 基于规则的翻译器 31. 模型驱动的转换 19
报告目录 1 问卷调查 -- 实践的重要性 2 3 4 5 教学实践的总体思路 Bison => ANTLR 引进 LLVM 的课程实践探索下一步的工作 20
循序渐进的编译器组件 词法分析器 记号流 http://llvm.org 源代码 Parser0 Parser 是否合法? 高级中间表示 (AST) 解释器 是否合法? 语义检查器 低级中间代码生成器 (AST2LIR) 代码生成器 程序变换器优化器 低级中间表示 ( 如 LLVM IR) LLVM 编译器工具链 寄存器分配器 代码生成器 汇编码的内部表示 汇编码 ( 如 x86, MIPS) 21
结合 LLVM 的实验 理解和扩展 Kaleidoscope(LLVM 教程 ) 词法 语法 代码生成 即时编译 ( 新增 ) 理解 LLVM IR 的生成和使用方法 编译 Clang 和 LLVM 体验大工程的编译 ( 空间 时间 ) 问题及解释 Clang 特定模块代码导读与问题回答 词法 语法 CSA(Clang Static Analyzer) 理解现代编译器的实现技术 软件体系结构 课程资源主页 :http://staff.ustc.edy.cn/~yuzhang/compiler https://www.zybuluo.com/clarazhang/note/190166 2015 年秋 https://guoxing.gitbooks.io/compiler-f2016 2016 年秋 22
2016 秋季学期教学实践 23
2016 秋季学期教学实践 24
2016 秋季学期教学实践 25
助教 : 自己培养 LLVM 2015 年秋 v3.6 2016 年秋 v3.9 2017 年秋 v4.0.1 动员邀请政策配套 改作业检查实验 习题实验讲解 参与实验方案设计 自主研发工具 课程总结合作写教研论文 26
报告目录 1 问卷调查 -- 实践的重要性 2 3 4 5 教学实践的总体思路 Flex+Bison => ANTLR 引进 LLVM 的课程实践探索下一步的工作 27
正在进行的和未来的工作 基于 ANTLR 的小型语言的实现案例 (7 月 -) LLVM JIT( 即时编译 ) 代码导读和实验 (8 月 -) 支持跨课程计算机系统能力培养的教学编译器 目标指令系统 :11 条 55 条 MIPS 指令 ; 基于 LLVM 的工具库开发 IR 检查器 代码生成器 系统能力培养安徽省工作组 推动 FPGA 的省系统能力竞赛 : 培训 ( 本月底 ) 竞赛(11 月 ) 编译课程的研讨 : 微信群交流 (8 月 -) 线下交流(9/10 月 ) ANTLR 的使用案例 经典习题选择与讲解 28
谢谢各位老师! 编译原理课程调查问卷 29