Quartz 5

编译原理

Properties2
tags基础知识, 编译原理
aliasesCompiler Principles

7 min read

哈工大课程笔记

第二章

2.3

作业：无符号整数和浮点数的文法 无符号整数： 不能以 0 开头的整数 浮点数： 整数或者带小数点的数

第三章

3.1 正则表达式

正则表达式的定义

3.2 正则定义

3.3 有穷自动机（Finite Automata，FA）

典型例子：电梯控制装置 输入带 input tape 读头 head 有穷控制器 finite control 转换图 Transition Graph 初试状态（开始状态） 终止状态（接收状态） 最长子串匹配原则（Longest String Matching Principle）

3.4 有穷自动机的分类

确定的有穷自动机（DFA） 一个例子：转换图、转换表

非确定的有穷自动机（NFA）

正则文法 <=> 正则表达式 <=> 有穷自动机（FA） DFA 的算法实现

3.5 从正则表达式到有穷自动机

3.6 从 NFA 到 DFA 的转换

例 1：不带 sigma 边的 NFA 到 DFA 的转换 例 2：带 sigma 边的 NFA 到 DFA 的转换 NFA 到 DFA 算法实现：子集构造法

3.7 识别单词的 DFA

第四章

4.1 自顶向下分析概述

Top-Down Parsing 最左推导 Left Most Derivation => 最左句型 left sentential form，逆过程是最右规约 最右推导 Right Most Derivation => 最右句型 right sentential form，逆过程是最左规约 规范推导：最右推导，规范规约：最左规约 但是由于扫描从左向右，所以采用最左推导 递归下降分析 recursive-descent parsing 回溯 预测分析 predictive parsing

4.2 文法转换

A=>Aa 的形式称为直接左递归 immediate left recursive A=>Aa 的形式称为左递归 两步或者两步以上称为间接左递归 消除直接左递归 把左递归转换为右递归（看例子）

消除间接左递归 消除左递归的算法

提取左公因子 Left Factoring 提取左公因子算法

4.3 LL(1)文法

非终结符的后继符号集 产生式的可选集 串首终结符集

4.4 FIRST 集和 FELLOW 集的计算

4.5 递归的预测分析法

4.6 非递归的预测分析法

4.7 预测分析法中的错误处理

4.8 自底向上的分析概述

4.9 LR 分析法概述

4.10 LR0 分析

4.11 LR0 分析表构造

4.12 SLR

4.13 LR1 分析

4.14 LALR 分析法

4.15 二义性文法的 LR 分析

4.16 LR 分析中的错误处理

第五章

5.1 语法制导翻译概述

5.2 语法制导定义

5.3 SSD 的求值顺序

5.4 S 属性定义与 L 属性定义

5.5 语法制导翻译方案

5.6 在非递归的预测分析过程中进行翻译

5.7 在递归预测过程中进行翻译

5.8 L 属性定义的自底向上翻译

第六章

6.1 类型表达式

6.2 声明语句的翻译

6.3 简单赋值语句的翻译

6.4 数组引用的翻译

6.5 控制流语句 SDT

6.6 布尔表达式 SDT

6.7 控制流的例子

6.8 布尔表达式的回填

6.9 控制流语句的回填

6.10 SWITCH 语句的翻译

6.11 过程调用语句的翻译

第七章

7.1 运行存储分配概述

7.2 静态存储分配

7.3 栈式存储分配

7.4 调用序列和返回序列

7.5 非局部数据的访问

7.6 符号表

7.7 符号表建立

第八章

8.1 流图

8.2 常用代码优化方案一

8.3 常用代码优化方案二

8.4 基本块的优化

8.5 数据流分析

8.6 到达定值分析

8.7 到达定值方程的计算

8.8 活跃变量分析

8.9 可用表达式分析

8.10 支配节点和回边

8.11 自然循环及其识别

8.12 删除全局？？表达式和赋值语句

8.13 代码移动

8.14 作用于归纳变量的强度削弱

8.15 归纳变量的删除

第九章

9.1 代码生成器的主要任务

9.2 一个简单的目标机模型

9.3 指令选择

9.4 寄存器的选择

9.5 寄存器选择函数 getReg 的设计

9.6 窥孔优化

复习

LL(1),LR(0),SLR(1),LALR(1),LR(1)对比与分析

参考资料

Graph View