编译原理期末复习（自用）
VLSMB二 形式语言基础
语法树
短语：任意子树的树叶全体皆为短语，注意短语不能是树叶的空子树构成的
简单短语：任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语。
句柄：一个句型的最左简单短语称为该句型的句柄。
递归文法：
文法的等价性是指他们所定义的语言是一样的。
文法化简：
三 自动机基础
自动机开始节点标加号，终止节点标减号，可以有多个开始或终止节点，也可以开始就结束。但DFA开始状态唯一、且无幺元边、状态确定。
有限自动机确定化：
幺回路上的节点是等效节点。
四 词法分析
五 语法分析
递归子程序，自顶向下法：
递归子程序法的要求为（LL1文法）：
消除左递归：
LL1分析法：
LL1文法判定：
firsta为a能够推到出的句子的终极符开头，followA为从开始Z触发推到的句型A后会出现的字符是什么。
判定定理：
LL1分析器设计：
LR（）分析法：
点指向的下一个字符为自动机上临边的字符，并且下一个状态点后移。如果点后为非终极符则展开。如果点到最后则规约或者结束。
扩展句柄，SLR1：
SLR1对冲突的状态节点进行下一个读取进来的数据进行判断。
LR1分析表：
LR1需要看每一个状态的下一个字符，只有下一个字符为follow的才进行规约，与LR0和SLR1有点区别。
简单优先分析法：
优先关系：他俩能同时出现则是平级，层数越深的字符越大。
优先表xy表示xy字符的关系，不可以反过来
算符优先文法：
六 符号表
七 中间代码及其翻译
gt i lb i
if t1 el ie
wh do t3 we
if需要先计算bool值，while在wh和do里计算bool值
翻译文法就是加了一个动作符号？
符号运算的动作是GEQ
八 优化
局部优化算法是以基本块为单位进行的，基本块也是目标代码生成的基本单位。
两个运算数为子节点，然后建立一个父节点运算符节点，同时写上结果标记。
九 目标代码及其生成
活跃信息：之后这个变量会不会被使用
活跃信息求法：首先临时变量为n，外部变量为y，之后逆序扫描每一个四元组，首先用当前符号表状态给四元组赋值，然后A更新为y，BC更新为n。
注意第一操作数只能为寄存器。
注意跳转前需要保存变量的值。
