本文主要为编译原理的题目做法解答，基于mooc题目。人人都是做题家！

编译原理做题版

第二章 文法与语言

写出语言

文法对应的所有句子的集合，也就是文法所能推导出来的所有句子的集合。写出即可。

构造语法树

根为产生式左部，下面从左到右组合成为产生式右部，构建即可。

如何生成目标串

产生式推导，使用=>连接即可。

二义性

对于同一句子，是否存在两棵不同的语法树，可判断二义性。

给出语言的上下文无关文法

上下文无关文法： 左侧必须为非终结符 且满足1型文法|β|>=|α|
无特定技巧，注意递归思想，注意数据范围，使用独特方法规范数据范围即可。

给出语言的三型文法

三型文法： 右侧为左线性或者右线性，即只能aA与a，或只能Aa与a。
也无特定技巧，注意三型文法规范。

第三章 词法分析

画DFA

DFA状态是确定的，每一个输入对应确定的下一个状态，没有ε边。注意该点。进行绘画即可。

构造DFA

首先需要NFA，这时候需要观察题干，得到NFA的所有字母，所有状态，转换关系，开始状态，结束状态。

然后将转换关系，绘制成NFA表格。

得到NFA表格后，扩充状态，如x状态在输入1后能进入x或y状态，则将xy状态加入表格，继续执行该过程，直至结束。

得到该表格后，将终止结点与非终止结点分为两个集合，在根据输入的不同，继续划分集合，直到无法再分。得到最简DFA。

画出图，即可。

写正规式

注意星号，或号用法。

第四章 自顶向下语法分析

first集求法

first集合含义便是该非终结符所能产生的第一个字符，按照此规则去找。A->a则只有a，A->Ba则观察B是否成产生ε，如果能则将First(B)与a加入集合，不能则只加入First(B)，没有a。多个非终结符推出ε则以此类推。注意，epsilon本身也可以进入first集合。

follow集求法

follow集合意义是该非终结符后面所有能接的第一个字符。那么观察产生式右边。比如A，如果只有S->Aa则follow只有a，如果只有S->A并且最后到了结束则加入#，如果S->AB，则将first(B)放入follow(A)，如果B能推出ε或者A为右部，则将follow(S)放入follow(A)。

select集合构建

select集合是针对产生式的，注意。S->AB如果产生式右部不是空串，则为first(S)，AB可以推出空串，则first(S)∪follow(S)-ε

LL(1)文法判断

对于相同左部的产生式而言，产生式的select集合不相交。

预测分析表

纵轴为产生式左部，横轴为输入符号，中间为对应产生式。

消除左递归

对于A->Aα|β而言，为直接左递归，可以改写为A->βA’ A’->αA’的等价形式。
存在间接左递归，可以先带入化成直接左递归后处理。

提取左公因子

对于A->aB1|aB2|……|aBn|y 可以提取左公因子后，得到A->aB|y B->B1|B2|……|Bn

注意，消除左递归并且提取左公因子后不一定为LL(1)文法。

第五章 自底向上语法分析

firstvt求法

注意区别于first集合，firstvt求法：T->a…则加入a，T->R…则加入firstvt(R),T->Ra…则加入firstvt(R)与a。如此递归。

lastvt求法

与firstvt类似，T->…a则加入a，T->…R则加入lastvt(R)，T->…aR则加入a和lastvt(R)，如此递归。

算符优先级判断

对于ab而言，a=b。对于aAb而言，a=b，a小于firstvt(A)，lastvt(A)大于b，如此扫描。
对于画表而言，横纵都是终结符，大小比较注意横纵关系。
没有冲突则为算符优先级文法。

短语，句柄，素短语，最左素短语

短语：子树的叶子从左到右
句柄：最左的只有两层的子树的叶子从左到右
素短语：至少包含一个非终结符的，与其他素短语不相交的短语
最左素短语：语法树内最左的一个。

分析过程

画表，观察栈顶和输入字符，比较关系，当遇到大于号和小于号配对时候则规约，不然移进。

第六章 LR分析法

FSM构建

首先增加拓广文法：增加个开头。
将点放在拓广文法右部开头，如果是非终结符，则在方框内增加该非终结符的产生式，并将点放在右部开头。
将点后续相同符号的，引出一条线指向新方框，方框内移动点到该符号后面，并和上面处理点后非终结符一样。
迭代此过程，直到所有状态结束。

分析表构建

注意ACTION表和GOTO表，如果点后为终结符则action(k,a) = Sj，k为当前表的标号，a为该中介符号j为后续表的标号。
如果点后为非终结符A，则goto(k,A) = j
如果项目为规约项目，则对于任何终结符a,Action(k,a)=rj，rj为目标产生式。注意这个a是任意a。
如果结束了，则放入acc
其他为error

分析表使用

如果右边为si，则单纯地改变状态。
如果右边为ri，则先将栈内符号可规约的符号弹出，状态置为剩余的栈顶部符号所存在的状态，根据此状态和规约出来的非终结符进行跳转。
如此循环，直到结束。

LR(0)判断

点后为终结符，则为移进项目。
点后为非终结符，则为待约项目。
点后为结束，则为规约项目。
移进，规约同时存在会冲突。规约，规约存在也会冲突。

SLR(1)判断

对于移进项目的非终结符b，规约项目的不同产生式左部B，C，如果b和Follow(B) Follow(C) 互不相交，则为SLR(1)文法，判断时候根据输入字符在这三者哪个里面决定移进还是规约。

第七章 语法制导的翻译

标出属性值

根据语义，带入语法树即可。

翻译成三地址码

TAC三地址码 OP A1 A2 A3 类似汇编 注意操作变量个数

第八章 代码优化

分基本块

程序的第一个语句；goto的目标语句；跟在条件转移语句后面的语句 按照此切分

流图

有向边：能到达则画有向边 根据go 语句执行顺序来确定

找循环

D(N) 必经结点集合，指从开始到这个点，绕不开的结点的集合 当存在a->b的边，而且a的必经结点有b，则为回边
回边a->b 循环入口为a 出口为b 先放入入口 再放入出口，直到栈顶的前驱都是a为止，找到循环（类似BFS）

DAG优化

将所有右边的，意义相同的变量放在DAG一个结点中，以操作符的方法增加边或结点，构造DAG，然后根据图，重新命名变量，重新构造式子，最后根据需要引用什么来赋值

第九章 目标代码生成

根据TAC序列生成目标代码

先翻译代码，然后尽量使用寄存器。