163-compiler

http://mooc.study.163.com/course/USTC-1000002001

http://staff.ustc.edu.cn/~bjhua/courses/compiler/2014/

LAB

第一单元作业 编译器介绍

题目:(本题目是一个动手实践类题目,需要具备C语言和数据结构基础。)
在课程中,我们讨论一个小型的从表达式语言Sum到栈计算机Stack的编译器,
在附件中,你能找到对该编译器的一个C语言实现,但这个实现是不完整的,请你
把缺少的代码补充完整(不超过10行代码)。
加分题:实现常量折叠优化。

第二单元作业 词法分析(Part I):词法分析器

在这部分中,你将使用图转移算法手工实现一个小型的词法分析器。
* 分析器的输入:存储在文本文件中的字符序列,字符取自ASCII字符集。文件中可能包括下面几种记号:关键字if、符合C语言标准的标识符、无符号整型数字、空格符、回车符\n。
* 分析器的输出:打印出所识别的记号的种类、及记号开始行号、开始列号信息。
注意:1. 忽略空格及回车符;2. 对于标识符和数字,要输出符号的具体词法单元(见下面的示例)。
【示例】对于下面的文本文件:
ifx if iif if 234
iff if
你的输出应该是(注意,因为文本显示的原因,列号信息可能不一定准确):
ID(ifx) (1, 1)
IF (1, 4)
ID(iif) (1, 8)
IF (1, 13)
NUM(234) (1, 16)
ID(iff) (2, 1)
IF (2, 8)

第三单元作业 词法分析(Part II)

给定如下的正则表达式 (a|b)((c|d)*),请完成如下练习:
(1)使用Thompson算法,将该正则表达式转换成非确定状态有限自动机(NFA);
(2)使用子集构造算法,将该上述的非确定有限状态自动机(NFA)转换成确定状态有限自动机(DFA);
(3)使用Hopcroft算法,对该DFA最小化

第四单元作业 语法分析(Part I):算术表达式的语法分析器

在这个题目中,要求你完成一个针对算术表达式的语法分析器。该算术表达式的上下文无关文法是:
E -> E + T
 | E - T
 | T
T -> T * F
 | T / F
 | F
F -> num
 | (E)
请下载我们提供的C代码框架,并把其中缺少的部分补充完整。
代码下载地址:
http://staff.ustc.edu.cn/~bjhua/mooc/exp.zip

第五单元作业 语法分析(Part II):台式计算器的设计与实现

在这个题目中,你将实现一个简单的台式计算器。这个台式计算器的功能像在最后一个讲义中演示的例子一样:即用户可以在控制台上交互输入算术表达式,你的程序判断该表达式是否合法,不合法的话报错并退出运行。
你的程序涉及表达式的部分要支持如下的表达式:
E -> n
 | E + E
 | E - E
 | E * E
 | E / E
 | (E)
其中n是任意的非负整数(注意:在我们演示的例子中,n只是单个字符的整数,所以这个地方你需要做些扩展,这些扩展同时需要涉及修改词法分析yylex函数)。
如果在Linux系统上,那么bison应该是默认安装可用的;如果你需要在Windows上完成,你可以下载Windows平台上的bison:
http://staff.ustc.edu.cn/~bjhua/mooc/bison.exe
注意:1。安装目录不能包含空格汉字等特殊字符;2。安装完成后把安装目录加到环境变量中。

第六单元作业 语法制导翻译与抽象语法树:抽象语法树

【抽象语法树】
在这个题目中,你将完整的实现抽象语法树(包括数据结构的定义、语法树的生成等)。首先,请下载我们提供的代码包:
http://staff.ustc.edu.cn/~bjhua/mooc/ast.zip 
代码的运行方式是:
首先生成语法分析器:
 $ bison exp.y
然后生成编译器:
 $ gcc main.c exp.tab.c ast.c
最后使用编译器编译某个源文件:
 $ a.exe <test.txt
在提供的代码里,我们已经提供了抽象语法树的定义、若干操作、及由bison生成语法树的代码框架。你的任务是:
进一步完善该代码框架,使其能够分析减法、除法和括号表达式;(你需要修改语法树的定义,修改bison源文件及其它代码)
重新研究第一次作业中的从Sum编译到Stack的小型编译器代码,把他移植到目前的代码框架中,这样你的编译器能够从文本文件中读入程序,然后输出编译的结果。(注意,你必须扩展你的编译器,让他能够支持减法和除法。)

第七单元作业 语义分析:C--语言的语义分析器

在这个题目中,你将亲自动手实现C--语义的语义分析器。具体的题目要求见:
http://staff.ustc.edu.cn/~bjhua/mooc/semant.html

第八单元作业 代码生成:C--语言的代码生成器

在这个题目中,你将亲自动手实现C--语义的语义分析器。具体的题目要求见:
http://staff.ustc.edu.cn/~bjhua/mooc/codegen.html

课程目录

第一单元: 编译器介绍
 第一讲 编译器概述
 第二讲 编译器结构
 第三讲 编译器实例
第二单元:词法分析(Part I)
 第一讲 词法分析的任务
 第二讲 词法分析器的手工构造
 第三讲 正则表达式
 第四讲 有限状态自动机
第三单元:词法分析(Part II)
 第一讲 RE 转换成 NFA : Thompson 算法
 第二讲 NFA 转换成 DFA : 子集构造算法
 第三讲 DFA 的最小化 : Hopcroft 算法
 第四讲 从 DFA 生成分析算法 
第四单元:语法分析(Part I)
 第一讲 语法分析的任务
 第二讲 上下文无关文法和推导
 第三讲 分析树和二义性文法
 第四讲 自顶向下分析
 第五讲 递归下降分析算法
第五单元:语法分析(Part II)
 第一讲 LL(1) 分析算法
 第二讲 LL(1) 分析算法的冲突处理
 第三讲 LR(0) 分析算法
 第四讲 SLR 分析算法
 第五讲 LR(1) 分析算法
 第六讲 LR(1) 分析工具
第六单元:语法制导与抽象语法树
 第一讲 语法制导翻译
 第二讲 语法制导翻译的实现原理
 第三讲 抽象语法树
 第四讲 抽象语法树的自动生成
第七单元:语义分析
 第一讲 语义分析的任务
 第二讲 语义规则及实现
 第三讲 符号表
 第四讲 语义分析的其他问题
第八单元:代码生成
 第一讲 代码生成的任务
 第二讲 栈计算机
 第三讲 面向栈计算机的代码生成
 第四讲 寄存器计算机及其代码生成
第九单元:中间代码与程序分析
 第一讲 中间代码的地位和作用
 第二讲 三地址码
 第三讲 控制流图
 第四讲 数据流分析
 第五讲 到达定义分析
 第六讲 活性分析
第十单元:代码优化
 第一讲 代码优化概述
 第一讲 早期优化
 第一讲 中间代码优化