编译原理整理资料Word文件下载.docx
《编译原理整理资料Word文件下载.docx》由会员分享，可在线阅读，更多相关《编译原理整理资料Word文件下载.docx（20页珍藏版）》请在冰点文库上搜索。
语法树：
设G=（VN,VT,P,S）为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树。
最左/最右推导：
在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换。
自上而下分析：
从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。
自下而上分析：
从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。
短语：
存在文法G[s],S=>
*αAδ且A=>
+β，则称β是句型αβδ相对于非终结符A的短语。
句柄：
一个句型的最左直接短语称为该句型的句柄
项目：
在右端某一位置有圆点的G的产生式
语法制导翻译：
在语法分析的同时，执行语义规则描述的动作：
回填：
一旦真假出口确定下来之后,用顺着真链和假链把真假出口补上.
拉链：
为了记录需回填地址的四元式,把需要回填的真出口的四元式拉成链,把需要回填家出口的四元式拉成一链,分别称作真链假链.
目标程序运行时存储区划分图：
简答题：
一．给出一个句子的最左，最右推导，语法树。
例:
G[S]:
S→aAS
A→SbA
A→SS
S→a
A→ba
最右推导：
SaASaAaaSbAaaSbbaaaabbaa
最左推导：
SaASaSbASaabASaabbaSaabbaa
任意推导：
SaASaSbASaSbAaaabAaaabbaa
二.判定文法的类型（0，1，2，3型）：
运用知识：
文法的类型：
通过对产生式施加不同的限制，Chomsky将文法分为四种类型：
0型文法：
对任一产生式α→β，都有α∈（VN∪VT）+，β∈（VN∪VT）*
1型文法：
对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外
2型文法：
对任一产生式α→β，都有α∈VN
3型文法：
任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT*
1型文法
例：
1型（上下文有关）文法
文法G[S]：
S→CDAb→bA
C→aCABa→aB
C→bCBBb→bB
AD→aDC→a
BD→bDD→b
Aa→bD
2型文法
2型（上下文无关）文法
S→AB
A→BS|0
B→SA|1
3型文法
例子G[S]：
S→0A|1B|0
A→0A|1B|0S
B→1B|1|0
三．正规式，正规文法，自动机之间的转换
正规式到正规文法的转换
对上的正规式r,存在一个RG=（VN,VT,P,S）：
L（G）=L（r）
（R.0）VT=,SVN,生成正规产生式：
Sr
（R.1）对形如Ar1r2的正规产生式：
Ar1BBr2BVN
（R.2）对形如Arr1的正规产生式：
ArAAr1
（R.3）对形如Ar1r2的正规产生式:
Ar1Ar2
不断应用（R.x）做变换，直到每个产生式右端至多有一个VN
例子r=a（ad）
解：
（1）Sa（ad）（Sr）
（2）SaAA（ad）（Ar1B,Br2）
（3）A（ad）A（ArA,Ar1）
A
G[s]:
SaA
AVT={a,d}
AaBVN={S,A}
AdB
正规文法到正规式的转换
对G=（VN,VT,P,S）,存在一个=VT上的正规式r:
L（r）=L（G）
AxB,By形成正规式A=xy
AxAy形成正规式A=xy
Axy形成正规式A=xy
例子：
由NFAM构造正规式r
从Σ上的一个NFAM，构造Σ上的,一个正规式r，使得L（M）=L（r）的方法。
由NAM构造正规式r步骤如下：
（1）在NFAM的状态图中增加2个新节点：
X和Y。
从X节点到NFAM的所有初态引标记的弧，从NFAM的所有终态到Y节点引标记的弧，形成一个新的NFAM’，这个M’只有一个初态X和一个终态Y。
显然M与M’等价。
（2）逐步消去M’的节，直至剩下X和Y节，消节的过程中，根据消节规则，逐步用正规式标记弧。
消结规则：
NFA到正规式的例子：
由正规式r构造NFAM
从Σ上的一个正规式r，构造Σ上的一个NFAM，使得L（M）=L（r）的方法。
“语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下：
（1）R=,构造任一具有空终态集的NFAM
（2）R=，构造的NFAM=（{k0},∑,f,k0,{k0}）;
f（k0,a）对于所有a∑都没定义。
（3）R=a,构造的NFAM=（{k0,,k1},∑,f,k0,{k1}）:
f（k0,a）=k1
（4）R=R1|R2,将步骤
（1）
（2）（3）分别应用到R1,R2；
产生M1=（K1,∑,f1,k1,F1）,M2=（K2,∑,f2,k2,F2）,其中K1,K2不相交.
构造的NFAM=（K1K2{k},∑,f,k,F）:
k是新增加的状态符号，f包含f1和f2,且f（k,a）=f1（k1,a）f2（k2,a）.
若k1F1且k2F2，则F=F1F2；
否则F=F1F2{k}
（5）R=R1.R2
将步骤
（1）
（2）（3）分别应用到R1,R2；
产生M1==（K1,∑,f1,k1,F1）,M2=（K2,∑,f2,k2,F2）,其中K1,K2不相交.
构造的NFAM=（K1K2,∑,f,k1,F2）:
f包含f1和f2,且
f（k,a）=f1（k,a）,当kF1时;
f（k,a）=f2（k,a）,当k∈K2时;
f（k1,）=k2,
（6）R=R1*
将步骤
（1）
（2）（3）分别应用到R1,
产生M1==（K1,∑,f1,k1,F1）,
构造的NFAM=（K1{k0,F0},∑,f,k0,F0）,其中k0,F0是新增加的两个状态,
f（k0,）=f（F1,）={k1,F0},
从正规表达式构造等价的–NFA
由正规文法G构造NFAM
定理：
设G=（VN,VT,P,S）为一个正规文法，则存在一个有穷自动机NFAM=（K,∑,f,S,Z），使得L（M）=L（G）。
M的构造方法：
•∑=VT;
S=S
•为G中每一个非终结符生成M的一个状态（不妨取成相同的名字），G的开始符号M的开始状态S；
•增加一个新状态Z，作为NFA的终态；
K=VN+{Z}
•若G中有形如A->
tB的产生式，则令f（A,t）=B;
t的产生式，则令f（A,t）=Z;
求与文法G[S]等价的NFA
由NFAM构造正规文法G
已知一个有穷自动机NFAM=（K,∑,f,S,Z），则存在一个正规文法G=（VN,VT,P,S），使得L（M）=L（G）。
G的构造方法：
•VN=K;
VT=∑;
•P:
若f（A,t）=B,则A->
tB在P中；
•对于可接受状态Z，增加产生式Z->
ε;
求与NFA等价的文法G[S]
四.NFA->
DFA既NFA的确定化
NFA的确定化例子：
等价的DFA
五．DFA的最小化
DFA的最小化算法
DFAM=（K,∑,f,k0,kt）,最小状态DFAM’
1.构造状态的一初始划分；
终态kt和非终态K-kt两组（group）
2.对∏施用过程PP构造新划分∏new
3.如∏new=∏,则令∏final:
=∏并继续步骤4，否则∏:
=∏new重复2.
4.为∏final中的每一组选一代表，这些代表构成M’的状态。
若k是一代表且f（k,a）=t,令r是t组的代表，则M’中有一转换f’（k,a）=r
M’的开始状态是含有S0的那组的代表
M’的终态是含有F的那组的代表
5.去掉M’中的死状态.
1、初始划分：
（终态集和非终态集）P0={{1,2,3,4},{5,6,7}}
2、观察第一个子集{1,2,3,4}，读入符号a后情形，得出{1,2}和{3,4}是可区别的重新划分：
P1={{1,2},{3,4},{5,6,7}}
3、在P1中寻找一个子集和一个输入符号，使得这个子集中的状态可区别重新划分：
P2={{1,2},{3},{4},{5,6,7}}
4、P2中的{5,6,7}可由输入符号a或b而分割重新划分：
P3={{1,2},{3},{4},{5},{6,7}}
5、经观察P3不能再划分了。
令1代表{1,2}消去2,令6代表{6,7}消去2，得到DFAM’
六.文法二义性的判定
若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。
判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件
文法的二义性和语言的二义性是两个不同的概念。
因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L（G）=L（G′），也就是说，这两个文法所产生的语言是相同的。
二义文法改造为无二义文法
G‘[E]:
E→iG[E]：
E→T|E+T
E→E+ET→F|T*F
E→E*EF→（E）|i
E→（E）规定算符优先性和结合性
如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。
对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
七.找短语，直接短语，句柄
用语法树找短语，直接短语，句柄
子树：
语法树中的某个非叶结点连同它所有子孙所组成的树。
•短语：
一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。
•直接短语：
仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。
•句柄：
一个句型的语法树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。
例子
八.LL
（1）的判定以及预测分析表的构造，对指定符号串的分析过程
1．LL
（1）的判定：
文法G[S]：
S->
aA|dA->
bAS|ε是否是LL
（1）文法？
（文法中含有ε，比较麻烦）
判断第一个非终结符S
SELECT（S->
aA）=First（aA）={a}；
d）=First（d）={d}；
SELECT（S->
aA）∩SELECT（S->
d）=Ø
满足LL
（1）文法要求，判断下一个非终结符A
SELECT（A->
bAS）=First（bAS）={b}；
ε）=（First（ε）-{ε}）∪Follow（A）
求Follow（A）：
Follow（A）=First（S）+follow（S）;
Follow（S）={#}+follow（A）
其中First（S）={a,d};
解得Follow（A）={a,d,#}
bAS）∩SELECT（A->
ε）=Ø
满足LL
（1）文法要求，
所有的非终结符都已经判断完毕，所以这个文法是LL
（1）文法。
九.LR（0）的判定以及分析表的构造，对指定符号串的分析过程
LR（0）分析的完整例子
例G[S]为:
SaAcBe
Ab
AAb
Bd
1）构造识别活前缀的DFA
2）构造它的LR（0）分析表
3）分别给出对输入符号串abbcde和abbce#的LR（0）分析步骤。
LR（0）项目集及DFA:
十.写出表达式的中间代码形式（逆波兰，三元式，四元式）
逆波兰式（后缀式）
将运算对象写在前面，把运算符号写在后面
逆波兰式的计算：
自左向右扫描逆波兰式，遇到运算对象则入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。
例:
A+B*（C-D）+E/（C-D）^N
逆波兰:
ABCD-*+ECD–N^/+
逆波兰记号的扩充用途
-（a+（b-c））+d
（注：
单目算符-用@代替）
逆波兰:
abc-+@d+
（b+c）*e+（b+c）/f
bc+e*bc+f/+
三元式
格式：
（算符,第一运算对象,第二运算对象）
四元式
（算符,第一运算对象,第二运算对象,结果）
优点:
类似于三地址指令（汇编语言，机器指令）
利于优化和代码生成
十一.给定属性文法，对某个句子进行分析
采用语法制导翻译思想表达式E的“值”的描述如下：
产生式语义动作
（0）S’—>
E{printE.VAL}
（1）E—>
E1+E2{E.VAL:
=E1.VAL+E2.VAL}
（2）E—>
E1*E2{E.VAL:
=E1.VAL*E2.VAL}
（3）E—>
（E1）{E.VAL:
=E1.VAL}
n{E.VAL:
=n.LEXVAL}
如采用LR分析方法，给出表达式（5*4+8）*2的语法树并在各节点注明语义值VAL
十二.画出栈式存储分配示意图（静态链，display表）
用静态链解决对非局部量的引用（存取）
用Display表解决对非局部量的引用（存取）
另外一种存取非局部变量的办法，也是常用的有效办法。
即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表Display。
这里所提到的“嵌套层次”，是指过程定义的层数，始终假定主程序的层数为0，因此主程序称为0层过程。
如某过程p是在层次为i的过程q内定义的，并且q是包围p的直接外层，那么p的过程层数为i+1。
一般编译程序处理过程说明时，将把过程层数作为重要的属性登记在符号表中。
计数过程的层数很容易实现，用一个计数器Level，初值为0，每遇到过程说明则增1，过程说明结束则减1.
Display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，……直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址。
也即，嵌套层次i的过程的局部变量a是在由Display元素d[i]所指的那个活动记录中存放的。
也就是说，嵌套层次i+1过程中的非局部变量可能在i,i-1,…,0层，对它的存取是通过display元素d[i],d[i-],…,d[0]而获得的。
例子2
假定现在进入的过程的层数为i，则它的display表含有i+1个元素，依次指向现行层、直接外层……直至最外层（0层）等每一层过程的最新活动记录的地址。
假定有如下四种调用情况：
（a）sort→quicksort…;
（b）sort→quicksort→quicksort…;
（c）sort→quicksort→quicksort→partition…;
（d）sort→quicksort→quicksort→partition→exchange…
升级会员 