编译原理总结

知识点总结

杂乱

消除左递归的方法

句柄

句柄：句型的最左直接短语

LL文法判断

当且仅当G的任意两个具有相同左部的产生式A → α | β 满足下面的条件：
不存在终结符a使得α 和β都能够推导出以a开头的串
α 和β至多有一个能推导出ε 
如果 β ->* ε，则FIRST (α)∩FOLLOW(A) =Φ；
如果 α ->* ε，则FIRST (β)∩FOLLOW(A) =Φ；

LR四种文法的判断

关系：LR(0)<SLR(1)<LALR(1)<LR(1)

1.判断LR(0)文法：
看项目中是否有归约-归约和移进-归约冲突。
如果无冲突则是LR(0)文法（如果是LR(0)文法则四种都是）；如果有冲突则不是LR(0)文法。（就要向下判断）

2.判断SLR(1)文法：
a:DFA中存在冲突项目（归约-归约，归约-移进）
b:{a1,a2,…,an},FOLLOW(B1),FOLLOW(B2)两两互不相交，（交集=空集）时是SLR(1)项目。
【也就是说，同时满足两个条件才是SLR（1）文法】

若不是再向下判断。

3.判断LR(1)文法：
构造带向前搜索符的DFA，无归约-归约冲突则是LR(1)文法。

【此处意思是如果有向前搜索符还有冲突的话就不是LR（1）文法，就要再向下判断】

4.判断LALR(1)文法：
合并同心集后无（归约-归约）冲突（在之前的基础上）
（核相同，向前搜索符不同）

（B->a,a
B->a,a|b
同心集）

LR即指LR(1)

四元式知识点

一些函数

赋值语句的翻译

newtemp( )：生成一个新的临时变量t，返回t的地址
gen(code)：生成三地址指令code
lookup(name)：查询符号表返回name 对应的记录

数组引用的翻译

L的综合属性
L.type：L生成的数组元素的类型
L.offset：指示一个临时变量，该临时变量用于累加公式中的ij × wj项，从而计算数组元素的偏移量
L.array：数组名在符号表的入口地址

控制语句的翻译

继承属性
B.true：是一个地址，该地址用来存放当B为真时控制流转向的指令的标号
B.false：是一个地址，该地址用来存放当B为假时控制流转向的指令的标号
S.next：是一个地址，该地址用来存放紧跟在S代码之后执行的指令(S的后继指令)的标号

回填

非终结符B的综合属性

B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

函数

makelist( i )
创建一个只包含i的列表，i是跳转指令的标号，函数返回指向新创建的列表的指针
merge( p1, p2 )
将 p1 和 p2 指向的列表进行合并，返回指向合并后的列表的指针
backpatch( p, i )
将 i 作为目标标号插入到 p所指列表中的各指令中

nextquad：即将生成的下一条指令的标号

优化方法

NFA到DFA的转换

词法分析

词法分析阶段可检测错误的类型：

单词拼写错误
非法字符

语法分析

最左规约称为规范规约，而最右推导相应的称为规范推导。

LL错误恢复：恐慌模式

LR错误恢复：恐慌模式错误恢复；短语层次错误恢复

语法制导翻译

这两种情况下，SDT可在语法分析过程中实现

基本文法可以使用LR分析技术，且SDD是S属性的
基本文法可以使用LL分析技术，且SDD是L属性的

给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD

给定一个以LL文法为基础的L-属性定义，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD
首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性， 并在产生式后端放置语义动作计算综合属性
对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生式M→ε
如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a' ，并且将a'关联到M→ε 上。动作a'
(a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
(b) 按照a中的方法计算各个属性，但是将计算得到的这些属性作为M的综合属性

中间代码生成

类型表达式

控制流语句SDT编写要点

分析每一个非终结符之前
先计算继承属性
再观察代码结构图中该非终结符对应的方框顶部是否有导入箭头。如果有，调用label( )函数
上一个代码框执行完不顺序执行下一个代码框时，生成一条显式跳转指令
有自下而上的箭头时，设置begin属性。且定义后直接调用label( )函数绑定地址

运行存储分配

活动记录的一般形式

静态存储分配

顺序分配法

层次分配法

栈式存储分配

活动树

调用序列与返回序列

代码优化

如果表达式x op y先前已被计算过，并且从先前的计算到现在，x op y中变量的值没有改变，那么x op y的这次出现就称为公共子表达式

复制传播：在复制语句x = y之后尽可能地用y代替x

对于一个变量x ，如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c ，那么x就称为归纳变量

DAG

数组元素赋值

数据流分析

到达定值分析

正常

作用：

循环不变计算的检测

如果循环中含有赋值x=y+z ，而y和z所有可能的定值都在循环外面(包括y或z是常数的特殊情况) ，那么y+z就是循环不变计算

常量合并

如果对变量x的某次使用只有一个定值可以到达，并且该定值把一个常量赋给x ，那么可以简单地把x替换为该常量

ud链

活跃变量分析

活跃变量：对于变量x和程序点p，如果在流图中沿着从p开始的某条路径会引用变量x在p点的值，则称变量x在点p是活跃(live)的，否则称变量x在点p不活跃(dead)

逆向分析

用途：

删除无用赋值

无用赋值：如果x在点p的定值在基本块内所有后继点都不被引用，且x在基本块出口之后又是不活跃的，那么x在点p的定值就是无用的

为基本块分配寄存器

如果所有寄存器都被占用，并且还需要申请一个寄存器，则应该考虑使用已经存放了死亡值的寄存器，因为这个值不需要保存到内存
 如果一个值在基本块结尾处是死的就不必在结尾处保存这个值

du链

可用表达式分析

概念：如果从流图的首节点到达程序点 p的每条路径都对表达式x op y进行计算，并且从最后一个这样的计算到点p之间没有再次对x或y定值，那么表达式x op y在点 p是可用的

初始化时出enter外每个out都是全集

用途：

消除全局公共子表达式

进行复制传播

代码生成

主要任务

指令选择
寄存器分配（allocation）和指派（assignment）
指令排序

题目总结

词素分析

符号表

递归的预测分析

非递归的预测分析

设计SDD

改写SDT

递归的翻译

非递归的翻译

活动记录

嵌套深度

找自然循坏

全局优化

句柄

注释语法分析树

翻译赋值语句

控制流翻译

四元式序列

翻译方案

13.5 难

13.6

14.4

求trulist

活动树

DAG

数值分析