compiler-course-outline.md

教学日历（教学大纲）（32学时）

• Ver1
• Ver2

课程简介

• 课程名称 编译原理 Principles and Practice of Compiler Construction
• 课程编号 30240382
• 课程类型 专业核心课
• 学分 2
• 学时 32
• 开课学期 大三秋季学期
• 教学方式 讲授为主+实验
• 授课语言 中文
• 考核方式 考试
• 成绩评定 书面作业+实验+期末考试
• 教材 无固定教材

课程概述

本课程主要内容包括：编译程序/系统概述，形式语言、文法和自动机的基础知识，词法分析，语法分析，语法制导的语义处理基础，语义分析和中间代码生成，符号表组织，运行时存储组织，代码优化和目标代码生成。

先修课程

• 程序设计，数据结构，形式语言与自动机
• 至少掌握一种课程实验用的编程语言（C/C++, Java, Scala, Rust, Go）

CC200X相关知识领域

CE—ALG/CS—AL，CE—CAO/CS—AR，CE—OPS/CS—OS，CE—PRF/CS—PF，CE—SWE/CS—SE，CE—DSC/CS—DS，CS—PL，CS—IS，SE—CMP，SE—FND，SE—MAA，SE—VAV，SE—QUA.

参考资料

• Aho, Sethi, Lam, and Ullman (龙书)， Compilers: Principles, Techniques, and Tools . 第一版（1986）第二版（2007），Addison Wesley.
• Andrew W.Appel (虎书)，Modern Compiler Implementation in C. Andrew W.Appel，人民邮电出版社影印，2005

课程定位

编译程序/系统在计算机科学技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。编译原理一直以来是国内外大学计算机相关专业的重要课程，其知识结构贯穿程序设计语言、系统环境以及体系结构，其理论基础是联系计算机科学和计算机系统的典范。 本课程是计算机专业核心课，主要讲授编译程序/系统构造的基本原理和技术，为学生深入学习计算机系统相关的专业知识以及今后从事科学研究或技术开发工作打下扎实的基础。

教学要求

本课程的教学目的是系统掌握编译程序/系统的设计原理以及实现技术。要求学生：

1. 深入理解编译程序/系统的基本构造原理；
2. 掌握常用语言机制的实现技术；
3. 经历开发一个小型编译程序的主要阶段；
4. 具有学习和使用特定编译构造工具的能力；
5. 会将所学的通用方法和技术应用于类似软件的设计和实现中；
6. 具备综合运用知识开发具有一定规模的软件系统的能力。

教学特色

本课程有以下特色：

1. 课程涉及三个方面的训练，即原理、技术与工具。课堂讲授和课后训练内容互补：基础原理以课堂讲授为主，实现技术采取以课堂讲解和课后实验相结合的方式，相关工具的使用由同学课外自己掌握。
2. 课程实验为实现一个小型面向对象语言的编译程序；分几个阶段，但各阶段相互关联融为一体；保持一定的强度，旨在激发学生兴趣，强化实践动手能力。
3. 注意计算机系统相关课程之间的相关性，旨在培养学生学习专业知识的大局观。

教学内容

第1讲 课程概述 (2课时)

1.1 基础概念；

1.2 逻辑结构；

1.3 组织方式；

1.4 伙伴程序；

1.5 生成环境；

第2讲 实验项目介绍 (4课时,穿插介绍)

2.1 项目框架的总体结构；

2.2 实验内容；

2.3 实验环境；

2.4 实验安排；

2.5 考核方案；

第3讲 文法/正规式/有限自动机 ─ 基础知识(1课时)

3.1 形式语言概念；

3.2 上下文无关文法及语言；

3.3 正规语言及其描述；

第4讲 词法分析 (1课时)

4.1 词法分析概述；

4.2 词法分析程序的设计与实现；

4.3 词法分析程序的自动构造；

第5讲 符号表(1课时)

5.1 符号表的作用；

5.2 符号表的常见属性；

5.3 符号表上的操作；

5.4 符号表的组织；

5.5 符号表与作用域；

第6讲 自顶向下语法分析(2.5课时)

6.1 自顶向下分析思想；

6.2 自顶向下预测分析；

6.3 LL(1)分析；

6.4 几种文法变换；

6.5 LL(1)分析的出错处理；

第7讲 自底向上语法分析(4.5课时)

7.1 自底向上分析思想；

7.2 移进-归约分析；

7.3 LR分析基础；

7.4 LR（0）、SLR（1）、LR（1）、LALR（1）等系列分析方法；

7.5 二义文法在LR 分析中的应用；

7.6 LR 分析的出错处理；

7.7 几类分析文法之间的关系

第8讲 语法制导的语义处理基础(3课时)

8.1 属性文法；

8.2 基于属性文法的语义处理；

8.3 翻译模式；

8.4 基于翻译模式的语义处理

第9讲 语义分析(2.5课时)

9.1 语义分析概述；

• 以类型检查程序设计为重点

9.2 常规处理介绍;

• 类型检查、说明语句、赋值语句及算数表达式、数组说明和数组元素引用、布尔表达式、控制语句、拉链与代码回填技术、过程调用

第10讲 中间代码生成(3课时)

10.1 中间代码生成概述；

• 以常用语言机制的实现技术为主线

10.2 常规处理介绍;

• 类型检查、说明语句、赋值语句及算数表达式、数组说明和数组元素引用、布尔表达式、控制语句、拉链与代码回填技术、过程调用

第11讲 运行时存储组织(2.5课时)

11.1 运行时存储组织概述；

11.2 程序运行时存储空间的布局；

11.3 存储分配策略；

11.4 活动记录；

11.5 过程调用与参数传递；

11.6 面向对象程序运行时组织;

第12讲 代码优化(2.5课时)

12.1 基本块、流图和循环；

12.2 数据流分析基础（数据流方程，典型数据流分析举例，UD链，DU链）；

12.3 基于 DAG 表示的局部优化；

第13讲 目标代码生成(2.5课时)

13.1 目标代码生成技术（代码生成基础，一个简单的代码生成算法，图着色物理寄存器分配算法）；

13.2 目标代码优化技术简述;

课程实验

实验名称

一个简单面向对象语言编译程序的实现

实验目的

经历开发一个小型编译程序的主要阶段，掌握编译程序设计的基本方法、常用语言机制的实现技术，具有学习和使用特定编译构造工具的能力，培养综合运用所学知识开发具有一定规模的软件系统的能力。

实验环境

普通PC机，Windows或Linux操作系统，Java编程环境，Lex & YACC 工具，MIPS SPIM (Wisconsin大学）。

实验内容

在给定实验框架基础上实现一个简单的强类型单继承面向对象语言的编译程序。实验框架分5个阶段，目前课程的实验内容包括前4个阶段：

1. 借助 Lex 和 Yacc 实现词法和语法分析，经过一遍扫描产生一种高级中间表示（实验框架指定的抽象语法树）。
2. 遍历抽象语法树构造符号表、实现静态语义分析，产生带标注的抽象语法树。
3. 从带标注的抽象语法树生成 TAC 中间表示，后者可由实验框架转成MIPS 汇编码在SPIM 模拟器上运行。
4. 基于 TAC 实现一些简单的数据流分析。

创新或扩展实验

对于有余力的同学，可以自行选择在已有实验框架基础上进行有意义的改进工作，通常需要与教师或助教沟通后方可确定创新或扩展实验的选题。

实验评测

##各阶段1525个测试程序（510不公开）；检查与标准输出的一致程度；实验报告的质量占20%成绩；必要时个别抽查。创新或扩展实验的评价需综合考虑创新性、实用性、合理性、难度、工作量等因素。