二 形式语言基础

语法树

短语：任意子树的树叶全体皆为短语，注意短语不能是树叶的空子树构成的

简单短语：任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语。

句柄：一个句型的最左简单短语称为该句型的句柄。

递归文法：

文法的等价性是指他们所定义的语言是一样的。

文法化简：

三 自动机基础

自动机开始节点标加号，终止节点标减号，可以有多个开始或终止节点，也可以开始就结束。但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。

注意第一操作数只能为寄存器。

注意跳转前需要保存变量的值。