前言

写给华工软院学生

1. 2021 级编译原理考试难度较低，复习优先级低，不建议花太多时间准备。虽然根据老师不同(以徐老师为例)，可能上课的内容比较深入，让学生产生了这门科目难度很大的错觉。诚然要彻底理解编译原理需要花费大量的时间，但考试内容基本都是简单的算法，只要把几个重要算法理解了，都不需要把每个概念搞的非常清楚，考试都基本不会出问题。
2. 编译原理博大精深，作为计算机底层设计的一部分，课堂上教授的内容少之又少，甚至可以说和一些工程实践是严重脱钩的，比如上课会花很大的精力教你自动机和自动机的相关算法，但是在实际工程运用中，我们有诸如 lexer 的工具帮我们完成这个工作，而且如果是编写一个简单的词法分析器，甚至只需要简单的 最长字串匹配 就能实现一个词法分析。仅凭课堂上学的内容，大概率连怎么写一个 TinyC(精简版的 C 语言) 都不知道。感兴趣的同学可以认真钻研一番，这对编程能力会有极大的提高。

编译器的结构

• 词法分析 Lexical analysis (Scanning)
• 语法分析 Syntax analysis (Parsing)
• 语义分析 Semantic analysis

• 中间代码生成 IR Generation
• 中间代码优化 IR Optimization
• 最终代码生成 Generation
• 最终代码优化 Optimization

大纲

• 扫描过程 Scanning Process
• 正则表达式 Regular Expressions
• 有限自动机 Finite Automata(NFA(nondeterministic 非确定性有限自动机) and DFA(deterministic 确定性))
• RE 转换 NFA(McNaughton-Yamda-Thompson algorithm)
• NFA 转换 DFA(子集算法 Subset construction Algorithm)
• 最小化 DFA(State-Minimization Algorithm)

大纲

• 语法分析的形式化——上下文无关文法
• 语法分析算法

上下文无关文法(CFG)

• 是用来描述一个编程语言的语法结构的文法
• 和正则表达式一样，可以表示递归的规则，而且更强大
• 是正则表达式的严格超集

Chomsky 语言层级

Chomsky hierarchy	Production(产生式)	Explanation
unrestricted(type 0)(自然语言)		无严格约束
context sensitive(type 1)(上下文有关文法)		在不同的上下文中，可能被不同的替换
context free(type 2)(上下文无关文法)		在任何出现的地方都会被替换
regular(type 3)(正则表达式)		等价于正则表达式

目录

介绍

• 语义分析核心是类型检查(Type check)和作用域检查(Scope check)
• 语义通过属性的值来刻画
• 通过一系列属性等式来进行计算，按照一定的顺序进行计算

Recursive AST Walk

• 一种语义分析的实现方法，本书暂时不表

Attribute Grammars

语法制导的语法分析(Syntax-Directed Semantics Analysis )

• 又称 SDS、SDT、SDD
• 属性是附着在文法符号上的

介绍

• 代码生成取决于：源代码、目标系统体系结构、运行时环境
• 代码生成可以被划分为三步：

1. 生成中间代码(IR Iermediate code 码)
2. 生成某种汇编形式的代码，而不是真正的可执行代码
3. 优化目标代码

中间代码

• 以三地址码(TAC Three Address code)为例

生成三地址码

运算

前言

写给华工软院学生

1. 2021 级编译原理考试难度较低，复习优先级低，不建议花太多时间准备。虽然根据老师不同(以徐老师为例)，可能上课的内容比较深入，让学生产生了这门科目难度很大的错觉。诚然要彻底理解编译原理需要花费大量的时间，但考试内容基本都是简单的算法，只要把几个重要算法理解了，都不需要把每个概念搞的非常清楚，考试都基本不会出问题。
2. 编译原理博大精深，作为计算机底层设计的一部分，课堂上教授的内容少之又少，甚至可以说和一些工程实践是严重脱钩的，比如上课会花很大的精力教你自动机和自动机的相关算法，但是在实际工程运用中，我们有诸如 lexer 的工具帮我们完成这个工作，而且如果是编写一个简单的词法分析器，甚至只需要简单的 最长字串匹配 就能实现一个词法分析。仅凭课堂上学的内容，大概率连怎么写一个 TinyC(精简版的 C 语言) 都不知道。感兴趣的同学可以认真钻研一番，这对编程能力会有极大的提高。

Chapter1 编译器组成

编译器的结构

• 词法分析 Lexical analysis (Scanning)
• 语法分析 Syntax analysis (Parsing)
• 语义分析 Semantic analysis

大纲

• 扫描过程 Scanning Process
• 正则表达式 Regular Expressions
• 有限自动机 Finite Automata(NFA(nondeterministic 非确定性有限自动机) and DFA(deterministic 确定性))
• RE 转换 NFA(McNaughton-Yamda-Thompson algorithm)
• NFA 转换 DFA(子集算法 Subset construction Algorithm)
• 最小化 DFA(State-Minimization Algorithm)

• 正则表达式的能力有限，无法分析具体的语法细节(例如嵌套、的 n 值)，与其等价的有穷自动机同理，因此引入了下推自动机和上下文有关、无关文法

大纲

• 语法分析的形式化——上下文无关文法
• 语法分析算法

上下文无关文法(CFG)

• 是用来描述一个编程语言的语法结构的文法
• 和正则表达式一样，可以表示递归的规则，而且更强大
• 是正则表达式的严格超集

Chomsky 语言层级

Chomsky hierarchy	Production(产生式)	Explanation
unrestricted(type 0)(自然语言)		无严格约束
context sensitive(type 1)(上下文有关文法)		在不同的上下文中，可能被不同的替换
context free(type 2)(上下文无关文法)		在任何出现的地方都会被替换
regular(type 3)(正则表达式)		等价于正则表达式