一、算法的概念 要利用计算机处理问题,需要编写出使计 算机按人们意愿工作的程序。而程序实质上就 是一组计算机指令。每一条指令使计算机执行 特定的操作。因此,每个学习计算机知识以及 希望利用计算机进行某项工作的人都应学习如 何进行程序设计

• 词法分析器的作用 • 词法单元的规约 (正则表达式) • 词法单元的识别 (状态转换图) • 词法分析器生成工具及设计 • 有穷自动机

• 语法分析器 • 上下文无关文法 • 语法分析技术 – 自顶向下 – 自底向上 • 语法分析器生成工具

• 使用上下文无关文法引导语言的翻译 – CFG的非终结符号代表了语言的某个构造 – 程序设计语言的构造由更小的构造组合而成 – 一个构造的语义可以由小构造的含义综合而来 • 比如：表达式x + y的类型由x、y的类型和运算符+决定 – 也可以从附近的构造继承而来 • 比如：声明int x中x的类型由它左边的类型表达式决定

第一章 编译器介绍 ◼ 1.1 编译器概貌 ◼ 1.2 源程序分析 ◼ 1.3 编译器的阶段 ◼ 1.4 编译器的同胞 ◼ 1.5 阶段的组合 ◼ 1.6 编译器构造工具 Chapter2-2 语言的形式化定义基础 Chapter2-2 语言的形式化定义基础（4类语言识别方法） Chapter3.1 词法分析 Chapter3.2 词法分析 Chapter3.3 有限状态机 形式化定义 NFA确定化 DFA最小化 Chapter3.4 正规表达式与正规集 Chapter4 语法分析和语法分析程序 Chapter4.1 自顶向下的语法分析 Chapter4.1.3 递归下降分析法 Chapter4.2.4 LR分析方法

• 运行时刻环境 – 为数据分配安排存储位置 – 确定访问变量时使用的机制 – 过程之间的连接、参数传递 – 和操作系统、输入输出设备相关的其它接口 • 主题 – 存储管理：栈分配、堆管理、垃圾回收 – 对变量、数据的访问

• 代码生成器的设计 • 目标语言 • 目标代码中的地址 • 基本块和流图 • 基本块优化 • 代码生成器 • 寄存器分配

• 中间代码表示 – 表达式的有向无环图DAG – 三地址代码：x = y op z • 类型检查 – 类型、类型检查、表达式的翻译 • 中间代码生成 – 控制流、回填

• 1. 引论 (易) • 3. 词法分析 (难) • 4. 语法分析 (难) • 5. 语法制导的翻译技术 (中) • 6. 中间代码生成 (难) • 7. 运行时刻环境 (易) • 8. 代码生成 (中) • 9. 机器无关优化 (中)

一、自顶向下分析技术与识别算法 1.从推导的角度看,从识别符号出发,试图推导出与输入符号串相同的符号串。一般来讲,构造出的推导是最左推导。 2.从语法树的角度看,从根节点,试图向下一个语法树,其末端节点正好与输入符号串相同