编译原理知识点复习笔记

马上要期末考试了，临考前紧急自救一下，嘻嘻嘻

有穷自动机

转换图：

初始状态（开始状态）：只有一个，用start箭头指向

终止状态（接受状态）：可以有多个，用双圈表示

最长子串匹配原则：当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配

确定的有穷自动机（DFA）：

根据转换表画出转换图

不确定的有穷自动机（NFA）：

存在进入一个状态集合的情况，NFA可存在空边

DFA与NFA存在等价性

NFA转换为DFA：

课本P50-P52

有穷自动机的化简：没有多于状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除无用状态和合并等价状态而转换为一个与之等价的最小状态的有穷自动机。

无用状态：从该自动机的开始状态出发，任何输入状态也不能到达的那个状态，或者从这个状态没有通路到达终态。

等价状态：

（1）状态s和t必须同时为可接受状态或不可接受状态。

（2）对于所有的输入符号，状态s和状态t必须转换到等价的状态里

https://www.jianshu.com/p/c779953434ac

文法转换

S->aAd|aBe
A->c
B->b

输出abc就会出错，无法判断

同一非终结符的多个候选式存在共同前缀，将导致回溯现象

回溯解决：

提取左公因子

S->aS'
S'->Ad|Be
A->c
B->b

含有A->Aa形式的产生式的文法成为是直接左递归的，经过两步或两步以上推导产生的左递归成为是间接左递归的

消除直接左递归

将左递归转换为右递归：A->Aa A’->aA’

方法：

A->Aa|b
A->bA'
A'->aA'|空

消除间接左递归

思路：将间接左递归转换为直接左递归

FIRST集与FOLLOW集的计算

FIRST(X)：

（1）可以从X推导出的所有串首终结符构成的集合

（2）如果X可以推导出空，那么空也属于FIRST(X)

（3）若产生式的右部开头的是非终结符，那么该非终结符能推导出的FIRST集中的终结符就是该产生式的FIRST集

（4）X->Y1Y2Y3Y4…..YK，如果空属于Y1，那么Y2FIRST集中的终结符就成为X的FIRST集的一部分，如果空也属于Y2，则Y3FIRST集中的终结符就成为X的FIRST集的一部分,依次递推，如果产生式右侧每个都能推导出空，那么空属于FIRST(X)

FOLLOW(A)：

可能在某个句型中紧跟在A后边的终结符a的集合

（1）若是最开始的符号，讲“#”加入FOLLOW

（2）E->TE’，FIRST(E’)中的终结符属于FOLLOW(T)

（3）在（2）的情况下，如果E’可以推出空，那么FOLLOW(E)属于FOLLOW(T)

（4）在（2）的情况下， E‘为产生式的最右侧符号，那么FOLLOW(E)属于FOLLOW(E’)

（5）循环前4条，直到不出现各FOLLOW集不出现新的符号

LL(1)文法

如果产生式具有相同的左部，而SELECT互不相交，则是LL(1)文法

（1）若产生式 右部开始为非终结符，则SELECT集为该非终结符的FIRST集中的终结符，不含空

（2）若产生式右部开始符号为终结符，则SELECT集就是该终结符

（3）若产生式的右部为空，则SELECT集为左侧符号的FOLLOW集

LR(0)分析

LR(0)项目：右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）

空产生式只生成A-> .

首先要转换为增广文法。即添加新的产生式

LR(0)自动机：

自动机的每个状态都是项目集闭包。

规约状态下无后继状态

LR分析表：
ACTION对应终结符和#，GOTO对应非终结符

sn：将符号a、状态n压入栈

rn：用第n个产生式进行规约

LR(0)分析过程中的冲突：
移进/归约冲突和规约/规约冲突

如果分析表中没有动作冲突，那么给定的文法就被称为LR(0)文法

SLR分析

消解冲突：

仅对FOLOOW集的元素进行规约动作

LR(1)分析