编译原理复习
2021-01-29 19:43:16 1 举报AI智能生成
编译原理，龙书知识点总结！
作者其他创作
大纲/内容
词法分析
分类
自动构造：正则表达式-有限状态机图
手工构造
正则表达式（RE）
选择
连接
闭包
空串
字符集中任意一个字符
FA
NFA
DFA
RE->NFA
Thompson算法
NFA->DFA
子集构造法
DFA最小化
Hopcroft算法
语法分析
目标：给定一个上下文无关文法CFG，能否推导出某个具体的句子
自顶向下
递归下降：每个非终结符都是一个函数——需要回溯
LL（1）表驱动算法，线性时间复杂度
求非终结符的First集
一般情况的First集，需要求出Nullable集
然后求出Follow集
最后求出First_S集，即可构建出LL(1)分析表
LL(1)分析表：某个非终结符看到一个记号应该使用哪条产生式
遇到的问题
提取左公因子
消除左递归
自底向上
LR（0）
加一个点记号画出DFA
非终结符变转移
终结符变移进
某个状态集已经吃完记号规约，遇到$接受
缺点：延误发现错误时机，无脑规约
SLR
求一个Follow集，规约时，看到Follow集中的记号才选择规约
缺点：仍然不够精确
LR(1)
求.Ab,c，后面跟一个符号集位First_S(bc)
LALR
仅仅后面符号集不同的项目集合并
语法制导翻译
目标：在语法分析过程生成抽象语法树
语法制导定义SDD
本质：上下文无关文法，每个记号具有属性，每个产生式具有一个语义动作，操作记号属性，可能会产生副作用
S属性SDD
只有自底向上依赖关系
L属性SDD
有自底向上依赖关系
有自定向下依赖关系
有自左向右依赖关系
语法分析过程搞定SDD翻译
S属性：使用产生式规约时执行翻译动作
L属性：
N的继承属性是子函数的函数参数
N的综合属性是子函数返回值
左边的子函数先执行
语义分析
目标：根据抽象语法树检查一些上下文相关的属性
通过符号表的构建和查询
代码生成
目标：选择合适的机器指令作为目标代码生成
栈是计算机
寄存器计算机
中间表示
图IR
有向无环图：把抽象语法树中的相同的子树合并
生成方法：生成抽象语法树节点时，查询是否已经生成
子主题
线性IR
三地址码：一条指令最多有三个地址（操作数），一个操作符。
基本思想
给每个中间结果命名
只有最基本的控制流，goto,call等
三地址码可以看出抽象的指令集
混合IR
代码优化
前期优化
常量折叠：x=3+5直接算
代数化简
死代码删除，根据CFG
中期优化
到达定义分析
哪些定义可以到达
gen集合表示该条语句是否新生成定义
def表示某变量全局定义，kill=def-i
前向数据流方程
in[s]=out[p]，所用指向s的并集
out[s]=gen+(in[s]-kill)
活性分析
在程序某个点之后一个变量仍然在之后的语句中被使用，则活跃
use集表示某一句中被使用的变量
def集合表示新定义的变量
后向数据流方程
out[s]=U in[p]，所用s指向p
in[s] = use[s] + (out[s]-def[s])
后期优化
根据活性分析画出冲突图，图着色算法分配寄存器
职业：本科
0 条评论
下一页
