编译原理归纳学习——除去晦涩
NFA
1. (a|b)*ab的NFA
DFA
1. (a|b)*ab的DFA ？
NFA到DFA的变换
从NFA构造等价的DFA的一般思想是让新构造的DFA的每个状态代表NFA的一个状态集，这个DFA用它的状态去记住该NFA在读入符号后能到达的所有状态。
写一个文法，使其语言是奇数集，且每个奇数不以0开头。
解：文法G(N)：
N→AB|B
A→AC|D
B→1|3|5|7|9
D→B|2|4|6|8
C→0|D
First集合的求法：
First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。
1. 直接收取：对形如U－a„的产生式（其中a是终结符），把a收入到First(U)中。
2. 反复传送：对形入U－P„的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。
3. 见下面给出的例1。
Follow集合的求法：
Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。
1. 直接收取：注意产生式右部的每一个形如“„Ua„”的组合，把a直接收入到Follow(U)中。
2. 直接收取：对形如“„UP„”(P是非终结符)的组合，把First(P)除ε直接收入到Follow(U)中。
3. 反复传送：对形如P－„U的产生式（其中U是非终结符），应把Follow(P)中的全部内容传送到Follow(U)中。(或 P－„UB且First(B)包含ε，则把First(B)除ε直接收入到Follow(U)中，并把Follow(P)中的全部内容传送到Follow(U)中)
例1：判断该文法是不是LL(1)文法，说明理由 S→ABc A→a|ε B→b|ε？
First集合求法就是：能由非终结符号推出的所有的开头符号或可能的ε，但要求这个开头符号是终结符号。如此题A可以推导出a和ε，所以FIRST（A）=｛a，ε｝；同理FIRST（B）={b,ε};S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=｛a，b，c｝。
Follow集合的求法是：紧跟随其后面的终结符号或＃。但文法的识别符号包含＃，在求的时候还要考虑到ε。具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow（S）=｛＃｝ 如求A的，产生式：S→ABc A→a|ε ，但只有S→ABc 有用。跟随在A后年的终结符号是FIRST（B）=｛b，ε｝，当FIRST（B）的元素为ε时，跟随在A后的符号就是c，所以 Follow（A）=｛b，c｝ 同理Follow（B）=｛c｝
消除左递归的例子：
提取公共左因子：
LL(1)文法：
LL(1)文法预测分析法：
文法（4 1）'
1
E→TE′
2 E′→ATE′|ε
3 T→FT′
4 T′→MFT′|ε
5 F→(E)|i
6 A→+|-
7 M→*|/
再考虑文法(4 1)′，首先分别求出各个FIRST集和FOLLOW集如表41所示，再构造相应的LL(1)分析表如表42所示。现以输入符号串i+i*i为例，列出识别此符号串的过程如表43所示。
上面的算法对应课本上的晦涩讲解为：
(1) 若a∈FIRST(γi)，则置M［A,a］=“A→γi”；
(2) 若ε∈FIRST(γj)，且a∈FOLLOW(A)，则置M［A,a］=“A→γj”；
(3) 除上述两种情况外，其余的一切表元素均置为“出错”。
注：M为LL(1)分析表
再来一个例子加深印象：
文法：
各个非终结符的first集合：
关于follow集合我们只要考虑有可能变成空转换的非终结符：
根据FIRST集和FOLLOW集可以生成一张LL(1)文法的预测分析表：
预测分析表法的分析过程:
要以表格的形式，列出分析栈的变化，输入，和输出动作：
以下是上面的文法对于id+id*id串的分析过程
（注：比如上表的第5行，T'本来可以表示成两种之一，但因为此时输入最左端是+，根据分析表T'应该取ε）
DAG图：
[例]试对以下基本块B1应用DAG进行优化。
B1: A:=B*C
D:=B/C
E:=A+D
F:=E*2
G:=B*C
H:=G*G
F:=H*G
L:=F
M:=L
并就以下两种情况分别写出优化后的四元式序列：
（1）假设G、L、M在基本块后面背引用；
（2）假设只有L在基本块后被引用。
解：对于B1其DAG图：
(1)若只有G、L、M在基本块后被引用，则优化为：
G :=B*C
H := G*G
L := H*G
M := L
(2) 若只有L在基本块后被引用，则优化为：
G:= B*C
H :=G*G
L := H*G
[例]
T1 := A+B
T2 := A- B
F := T1 * T2
T1 := A- B
T2 := A – C
T3 := B - C
T1 := T1 * T2
G := T1 * T3
（注意T1和T2的位置变化）
三地址：
表达式x+y*z的三地址代码为：
t1:=y*z
t2:=x+t1
其中t1和t2是编译时需要的临时变量
三地址代码是语法树或dag的一种线性表示
a:= (-b + c*d ) + c*d
语法树的代码 dag的代码
t1:= -b t1 := -b
t2:= c*d t2:= c*d
t3:= t1+ t2 t3:= t1+ t2
t4:= c*d t4:= t3 + t2
t5:= t3 + t4 a:= t4
a:= t5
间接三元式
三元式，四元式的运算次序即为其代码表中语句的次序，在三元式代码表的基础上另设一张表，按运算次序列出相应三元式在三元式表的位置，这张表称为间接码表。因此三元式表只记录不同的三元式语句，而间接码表则表示由这些语句组成的运算次序逆波兰：
也称后缀表达式，用它可以很轻松的计算表达式，对于开发一个简易的计算器是很重要的方法，给出表达式，转换为中缀表达式，再转换为逆波兰，再通过栈操作：
如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
三地址总结:
活动记录：
参数传递：？
值调用