编译原理重点学习点

编译原理学习重点
1． 必须要会画分析树，内部节点可以找到子树，一次推导出来的是直接短语，最左直接短语是句柄。
文法开始符可以推导出来的就是句型。☆
2． 由正规式求解minDFA：
按三个拆分规则 求得 NFA
确定的初始状态集（一般为初始状态或经过空字边形成的状态集）求DFA
将 DFA的初态和终态进行细化，看能否合并或分组，从而求minDFA
最后用正规式表示的语言来检测一下结果是否正确。 ☆
3． First集和Follow集与FIRSTVT和LASTVT的区别：☆☆
从求解的过程和定义入手：
First集：所有可能推导的开头终结符或可能的ε；求解有3条规则
Follow（A）集：跟在A后面的终结符及＄ 求解有3条规则☆
FIRSTVT： 首先遇到的终结符集 求解有2条规则☆
LASTVT： 最后遇到的终结符集 求解有2条规则☆
4． 判断文法是否为算符优先文法：☆☆
算符文法看有没有相连的终结符；
判断优先需求FIRSTVT和LASTVT；
按照先判断终结符和非终结符相隔的，再判断一对终结符相连或相隔的顺序
填写优先关系表
关于优先关系表，左部终结符小于非终结符的FIRSTVT
非终结符的LASTVT大于右边的非终结符
5． 判断文法是否为LR文法：☆☆☆☆
首先必须求得FOLLOW元素
接着要写SLR分析表，增加文法开始符，将文法拓广
了解项目规范组的所谓等价指什么，有原因才能引出来
在状态转换时，如果非终结符涉及的产生式有几个，小点后面规约前就应该写几个
（小点后面有L，即能识别L的产生式都要列出来）
规约即对产生式的Follow元素规约
对文法开始符规约，必在 处ACCEPT
goto下面是非终结符，action下面是 和终结符
6． 判断文法是否为LL（1）文法（凡是有左递归的，有公共左因子的不是LL（1）文法）
即消除左递归，提取公共左因子以后的等价变换进行判别：
记住公式：非左递归部分的L`，L`定义为左递归的后缀部分L`然后加上|ε
根据定义，在后选式处判断☆☆
7． 根据翻译方案求解中间代码☆☆
关键了解目标代码结构，了解每一种语句的格式（如何生成三地址序列的）
赋值语句：一定要有临时变量接受表达式的值，临时变量再向左部赋值；
注意数元素的地址求法（按行或按列）；数组元素赋值表达式三地址语句如何生成的，记住变址取（CONSPART部分变址VARPART部分）
每个布尔变量都占有两个语句（若两个布尔表达式有相同的转向点可挂到一条链上）
语句翻译结束时，必须nextlist
8． 控制流图求解：☆☆
根据入口数量（第一个语句，goto语句的下一语句，条件语句的下一语句）划分基本块，几个入口即几个基本块
将流图画成结构型，求必经节点集，求回边，求循环
9． 画dag图进行代码优化 ☆☆☆
常量要合并
若节点已经存在不必再申请
添加附加标记时不能重复
尽量引用标记
恢复代码时严格按节点次序
对L定值主要看和谁相关