编译原理复习题2

编译原理复习题

21、（10分）下面的文法G[S]是否是LL

（1）文法，说明理由，构造LL

（1）分析表S-*aBc|bABA-*aAb|BbB-cB|

2、（5分）消除下列文法的左递归，消除左递归后判断是否是LL

（1）文法S-SaB|bBA^S aB-^Ac

3、（5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法S-A[]A-[A-aAA-B]B-a

4、（10分）将表达式A+B某（C-D）-E/FtG分别表示为三元式、四元式、逆波兰式序列

5、（10分）现有文法如下S-aS|bS|a判断该文法是哪一类LR文法，说明理由，并构造相应的分析表

1、已知文法GA::=aABe|aB::=Bb|d

（1）给出与上述文法等价的LL

（1）文法G，

（2）构造预测分析表并给出输入串aade#分析过程（10分）

2、设已给文法G:E::=E+TE::=TT::=T某FT::=FF::=PtFF::=PP::=EP::=i构造此文法的算符优先矩阵（10分）某某某某3＞有正规式babb（abb）

（1）构造该正规式所对应的NFA（画出状态转换图）

（2）将所求的NFA确定化（画出确定化的状态转换图）

（3）将所求的NFA最小化（画出最小化后的状态转换图）（10分）4^若有文法G（S）的产生式如下S:且二RS::二RL::二某红可长，,构造识别所有项目集规范族的DFAo（15分）

（1）判断该文法是否是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分）对于文法G[S]S-aBb|aAa|bAb|bBaA-＞某B—某⑴判断该文法是否是LR

（1）文法，构造LR

（1）分析表

（2）判断该文法是否是LALR

（1）文法，说明理由

三、问答题供50分

1、已知文法GS::二bBclaABA::二bAa|aB::二a|写出所有非终结符号的Firt集和Follow集，构造预测分析表并给出输入串abbaaa分析过程10分

2、正规式00|1某1构造该正规式所对应的NFA画出状态转换图将所求的NFA确定化和最小化分别画出确定化和最小化的状态转换图10分

3、若有文法G S的产生式如下:S::=bASB bAA::=dSa|bB::=cAa|c构造识别所有项目集规范族的DFAo20分判断该文法是否是LR0文法，说明理由判断该文法是否是SLR1文法，说明理由判断该文法是否是LR1文法，说明理由判断该文法是否是LALR1文法，说明理由

4、简述编译的整个过程10分

1、已知文法G[S]S-eT|RTT-DR|R-dR|D-a|bd写出所有非终结符号的Firt集和Follow集，构造LL1分析表，判断此文法是否是LL1文法10分

2、给出正规式a|b某bba|b某构造该正规式所对应的NFA画出状态转换图将所求的NFA确定化和最小化分别画出确定化和最小化的状态转换图10分

3、若有文法G S的产生式如下S-aAD|aBe|bBS|bAeA-gB-gD-d|,构造识别所有LR1项目集规范族的DFAo20分判断该文法是否是LR1文法，说明理由，构造LR1表判断该文法是否是LALR1文法，说明理由

4、简述编译的整个过程10分

1、把下图确定化和最小化15分babaaabbabab02^已知文法GS::=bBc|ciABA::=bAa|aB::=a|写出所有非终结符号的Firt集和Follow集，构造预测分析表并给出输入串abbaaa分析过程15分

3、若有文法G S的产生式如下S::二bASB|bAA::=dSa|bB::=cAa|c构造识别所有项目集规范族的DFAo20分判断该文法是否是LR0文法，说明理由判断该文法是否是SLR1文法，说明理由判断该文法是否是LR1文法，说明理由判断该文法是否是LALR1文法,说明理由

三、问答题共计50分

5、已知文法GA::=aABe|aB::=Bb|d1给出与上述文法等价的LL1文法G2构造预测分析表并给出输入串aade#分析过程10分

6、设二｛0,1｝上的正规集S由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式，并构造一个识别该正规集的DFAo15分SSiAiAAAB|BBA某|构造算符优先关系表和优先函数

4、构造文法GS lSBB2BaB3Bb的LR分析表假定输入串为abab,请给出LR分析过程即按照步骤给出状态，符号，输入串的变化过程15分

四、综合题共45分

1、10分计算文法GM的每一个非终结符的FIRST和FOLLOW集合，并判断该文法是否是比1的，请说明理由GM aM-TBbT-Ba|cB-Db eTdD-*d|

2、15分对文法GSS-aP|TT-T,S|S1构造算符优先表；2判断是算符优先文法吗⑶构造优先函数

3、10分将表达式A-B某C+D+E/FfG分别表示为三元式、四元式、逆波兰式序列

4、10分设有文法G[S]S-Ba|Bb|cB-Bd|Se|f判断该文法是哪一类LR文法，说明理由，并构造相应的分析表

1、已知文法GS::=aBc|bABA::=aAb|bB::=b|构造预测分析表并给出输入串baabbb分析过程10分

2、构造正规式0|1某00相应的DFA并进行化简15分

7、若有文法G S的产生式如下S::=bASB|bAA::=dSa bB::=cAa|c构造识别所有项目集规范族的DFAo15分1判断该文法是否是LR0文法，说明理由2判断该文法是否是SLR1文法，说明理由3判断该文法是否是LR1文法,说明理由4判断该文法是否是LALR1文法，说明理由

8、10分对文法GS SSaT|aT|aTTaT|a1消除该文法的左递归和提取左公因子；2构造各非终结符的FIRST和FOLLOW集合；⑶构造该文法的LL1分析表,并判断该文法是否是LL⑴的

三、已知文法GS::=aBc|bABA::=aAb|bB::=b|构造预测分析表并给出输入串baabbb分析过程10分

四、正规式0某111某0某10分1构造该正规式所对应的NFA画出状态转换图2将所求的NFA确定化画出确定化的状态转换图

五、若有文法G S的产生式如下S::=bASB|bAA::=dSa|bB::=cAa|c构造识别所有项目集规范族的DFAo15分i.判断该文法是否是LR0文法,说明理由ii.判断该文法是否是SLR1文法，说明理由iii.判断该文法是否是LR1文法，说明理由iv.判断该文法是否是LALR1文法，说明理由

六、设已给文法G:E::=E+TE::=TT::=T某FT::=FF::=EF::=i构造此文法的算符优先矩阵15分。