语义分析与中间代码产生
优化
目标代码生成
文法3型文法：正则文法，用于描述程序设计语言词法的有效工具
2型文法：上下型无关文法，描述程序语法的有效工具
产生式 A -> B B -> BC|C C -> 0|1|2|3|4|5|6|7|8|9 推导与规约 A -> aBc B -> b ================== aBc是abc的归约 abc是aBc的推导 规范推导/规约规范推导：最右推导
规范规约：最左规约
无符号串 =》数字串 =》数字串+数字 =》数字串6 =》数字6 =》56 句型由产生式到最终状态之间的中间串
例如<数字>9
句子产生式最终匹配的终态
例如56是文法无符号整数的一个句子
词法分析 有限自动机 DFA确定有限自动机：每个状态在接收下一个输入，只会转移到唯一一个下一个状态
L(M)：代表由FA能够识别的所有字符串的总体 NFA
非确定有限自动机，自动机中含有某些状态，在接收下一个输入后，会转移到多于一个的状态
每个NFA都存在一个DFA，使得L(NFA) = L(DFA)，也就是说等价
NFA的确定化就是，从NFA转变为DFA的过程
c-closure(state)：c-闭包，从一个状态转移不需要通过输入可以直接转移到下一个状态的集合
move(state, action)：从状态state，通过action，转换到的下一个状态的集合
a弧转换的闭包：I = c-closure(move(state, action))
子集构造法
然后把I列表标记为状态，并画出DFA
在NFA->DFA后，得到的DFA并不是最简的，必须通过DFA最简化处理，来提高分析的效率
DFA最简化多余状态：从开始状态出发无法到达的状态
死状态：从此状态出发无法到达最终状态的状态
无关状态：多余状态+死状态
等价状态（不可区别状态）：当两个状态，输入任意action，都转移到相同的状态时，代表这两个状态是等价的。
简化步骤为：
消除无关状态
合并等价状态
正则与NFA的转换 R->NFA
例子
逆过程
语法分析 自顶向下语法分析 消除左递归 直接左递归 P->Pa|b => ba+ P ->bM M -> aM|空 间接左递归 A -> Bc|d B -> aA|Ab => A -> aAc|Abc|d => A -> (aAc|d)M M -> bcM|空 First集若X->a....则a加入X的First集中，如果X->空，则空加入到X的First集中
X->amm|bk|空 => First(X) = {a,b,空} X->Ym|b Y->a|d|空 => First(X) = {a, d, m, b} Follow集若A->aBC，则First(C)加入Follow(B)
若A->aB，则Follow(A)加入Follow(B)
LL(1)语法分析
L：从左向由扫描
L：最左推导
1：向前看1个字符
对文法G的句子进行确定的自顶向下语法分析的充要条件是
产生式A->B|C满足
如果B和C都不能推导出空，则FIrst(B)交First(C)为空集
B和C最多只有一个可以推导出空
如果B可以推导出空，则First(C)交Follow(A为空
LL(1)文法不能由二义性，也不能含有左递归，对LL(1)文法的所有句子都可以进行自顶向下的语法分析
并不是所有语言都可以用LL(1)来描述
自下而上的语法分析 FirstVT(T)非终结符T的最左终结符集合
If T->a or T->Ra => a属于FirstVt(T)
if b belongs to FirstVt(R) => b and T->R... 属于FirstVt(T)
LastVt(T)非终结符T的最右终结符集合
if T->....a or T->....aR => a属于LastVt(T)
if b belongs to LastVt(R) and T->...R => b属于LastVt(T)
最左素语
建立一个栈
从左到右扫描表达式
通过出栈比较相邻两个个操作符的优先级
如果如果两个操作符优先级相等或者前一个后一个优先级高则规约前一个操作符
出栈比较相邻两个操作符
如果第一个操作符比第二个操作符低，则再取一个操作符，如果第二个操作符等于或者高于第三个操作符，则规约第二个操作符，否则继续入栈
产生式->NFA E->aA|bB A->cA|d B->cB|d
NFA->DFA
通过子集构造法
移进项目：圆点之后为终结符的项目,A->a.bc
待约项目：圆点之后为非终结符，A->a.Bb
归约项目：圆点之后没有远点，A->a.
接受项目：对于文法G(S)，有S->Q.