编译原理
约 626 个字 2 张图片 预计阅读时间 2 分钟
Abstract
课程信息 浙江大学计算机科学与技术专业专业模块课程，培养方案推荐大三春夏修读。
-
姚培森老师授课。
-
Grading Policy: 75% Lecture Grade (Homework 10%+Quizzes 10%+Mid-Term 15%+Final 40%) + 25% Lab Grade; Final < 40/100 then you will fail this course.
Introduction¶
编程语言及设计¶
编译器及其形式¶
什么是编译器?
编译器是一个程序，读入源程序并将其翻译成语义等价的目标程序。
源程序用某种高级语言编写；目标程序从狭义上来看可以是用目标代码或机器语言编写，广义上来看就是某种“中间语言”。
Example
编译器的各种形式
-
交叉编译器
-
增量编译器
-
即时编译器
-
预先编译器
编译器的阶段(编译过程)¶
-
[ 前端 ]词法分析 → 语法分析 → 语义分析
-
[ 中端 ]中间代码生成 → 机器无关代码优化
-
[ 后端 ]指令选择 → 寄存器分配 → 指令调度
词法分析 Lexical Analysis¶
我们容易理解，程序代码是以字符串的形式传给编译器的。词法分析就是将输入的字符串识别为 有意义的子串。这样会带来其他的辅助任务，例如过滤注释和空格等。
Definition: Token (词法记号，单词)
可以说是一类关键字的统称。以英语举例，名词 (noun) 就是一类 token。
Definition: Lexeme (词素)
抽象地说，一个词素就是一类 token 的一个实例。
该部分内容和计算理论课程有很多重合: TonyCrane/计算理论-语言、自动机与正则表达式
语法分析 Parse Analysis¶
从词法分析器获得 token 序列后，我们需要确认该 token 序列是否可以由语言的文法生成，或者说输入是否合法。这就是语法分析器的作用。一般而言，如果语法错误则报错，如果语法正确则生成语法分析树 (通常生成 AST ，抽象语法树)。
这就需要我们
- 首先规定好合法的基本单元(token)
- 还要理解一个表达式的构成，直到看到基本单元。
语法分析器可以自己使用向下递归(recursive descent)的方式手写(clang ， gcc 3.4 后的版本都是)，也可以使用语法生成器(Bison ， Yacc 等等)
我们可以利用上下文无关文法来描述语法。