编译原理复习习题2

1、1、 （10分）下面的文法GS是否是LL（1）文法，说明理由，构造LL（1）分析表SaBc|bAB AaAb|Bb BcB|e2、 （5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。 SSaB|bB AS|a BAc3、 （5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法SA A AaA AB Ba4、 （10分）将表达式A+B*(C-D)-E/FG分别表示为三元式、四元式、逆波兰式序列5、 （10分）现有文法如下：SaS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。1、 已知文法G A:=aABe|a B:=Bb|d（1） 给出与上述文法等价

2、的LL（1）文法G。（2） 构造预测分析表并给出输入串aade#分析过程。（10分）2、 设已给文法G: E:=E+T E:=T T:=T*F T:=F F:=PF F:=P P:=(E) P:=i构造此文法的算符优先矩阵。（10分）3、 有正规式b*abb*(abb*)*（1） 构造该正规式所对应的NFA（画出状态转换图）。（2） 将所求的NFA确定化。（画出确定化的状态转换图）。（3） 将所求的NFA最小化。（画出最小化后的状态转换图）。（10分）4、 若有文法G（S）的产生式如下：S:=L=R S:=R L:=*R L:=i R:=L,构造识别所有项目集规范族的DFA。（15分）（1）

3、判断该文法是否是LR（0）文法，说明理由。（2） 判断该文法是否是SLR（1）文法，说明理由。（3） 判断该文法是否是LR（1）文法，说明理由。（4） 判断该文法是否是LALR（1）文法，说明理由1、（10分）将表达式（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列2、（10分）对基本块P画出DAG图B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在基本块出口之后活跃，写出优化后的四元式序列。3、（10分）对于文法GS：SaBb | aAa |bAb|bBa Ax Bx （1）判断该文法

4、是否是LR（1）文法，构造LR（1）分析表（2）判断该文法是否是LALR（1）文法，说明理由三、问答题：(共50分)1、已知文法G S:=bBc|aAB A:=bAa|a B:=a|e写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（10分） 2、正规式0（0|1）*1构造该正规式所对应的NFA（画出状态转换图）。将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）3、若有文法G（S）的产生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c构造识别所有项目集规范族的DFA。（20分）判断该文法是否是LR

5、（0）文法，说明理由。判断该文法是否是SLR（1）文法，说明理由。判断该文法是否是LR（1）文法，说明理由。判断该文法是否是LALR（1）文法，说明理由。4、简述编译的整个过程（10分）。1、已知文法GS SeT|RT TDR| e RdR|e Da|bd写出所有非终结符号的First集和Follow集，构造LL(1)分析表，判断此文法是否是LL（1）文法。（10分） 2、给出正规式 (a|b)*bb(a|b)*构造该正规式所对应的NFA（画出状态转换图）。将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）3、若有文法G（S）的产生式如下：SaAD|aBe|bBS

6、|bAe Ag Bg Dd|e，构造识别所有LR(1)项目集规范族的DFA。（20分）判断该文法是否是LR（1）文法，说明理由，构造LR（1）表。判断该文法是否是LALR（1）文法，说明理由。4、简述编译的整个过程（10分）。1、 把下图确定化和最小化：（15分）0baaabbbbbaaa2、 已知文法G S:=bBc|aAB A:=bAa|a B:=a|e写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（15分）3、 若有文法G（S）的产生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c构造识别所有项目集规范族的DFA。（20

7、分）判断该文法是否是LR（0）文法，说明理由。判断该文法是否是SLR（1）文法，说明理由。判断该文法是否是LR（1）文法，说明理由。判断该文法是否是LALR（1）文法，说明理由。三、问答题：（共计50分）5、 已知文法G A:=aABe|a B:=Bb|d（1） 给出与上述文法等价的LL（1）文法G。（2） 构造预测分析表并给出输入串aade#分析过程。（10分）6、 设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(15分)3、设文法G(S)：(10分)构造算符优先关系表和优先函数。4、构造文法G(S)：(1) S &#

8、174; BB(2) B ® aB(3) B® b的LR分析表。假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)（15分）。四、综合题（共45分）1、(10分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。G(M)：a) M TBb) T Ba | ec) B Db | eT | ed) D d | e2、(15分)对文法G(S)：S a | | (T)T T，S | S(1) 构造算符优先表;(2) 判断是算符优先文法吗(3) 构造优先函数。3、（10分）将表达式A-B*(C

9、+D)+E/FG分别表示为三元式、四元式、逆波兰式序列4、（10分）设有文法GS SBa|Bb|c BBd|Se|f判断该文法是哪一类LR文法，说明理由，并构造相应的分析表1、已知文法G S:=aBc|bAB A:=aAb|b B:=b|e构造预测分析表并给出输入串baabbb分析过程。（10分）2、构造正规式 (0|1)*00 相应的DFA并进行化简。(15分) 7、 若有文法G（S）的产生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c构造识别所有项目集规范族的DFA。（15分）（1） 判断该文法是否是LR（0）文法，说明理由。（2） 判断该文法是否是SLR（1）文法，说明

10、理由。（3） 判断该文法是否是LR（1）文法，说明理由。（4） 判断该文法是否是LALR（1）文法，说明理由。8、 （10分）对文法G(S)：S ® S Ú a T | a T | Ú a TT ® Ù a T | Ù a(1) 消除该文法的左递归和提取左公因子；(2) 构造各非终结符的FIRST和FOLLOW集合；(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。三、已知文法G S:=aBc|bAB A:=aAb|b B:=b|e构造预测分析表并给出输入串baabbb分析过程。（10分） 四、正规式（0*|1）（1*0）*（10分）（1） 构造该正规式所对应的NFA（画出状态转换图）。（2） 将所求的NFA确定化。（画出确定化的状态转换图）。五、若有文法G（S）的产生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c构造识别所有项目集规范族的DFA。（15分）i.