编译原理考试试卷答案A卷

1、编译原理期末试卷1给出LL(1)分析方法的总控流程图。（5分）2按指定类型给出下列语言的文法。（10分）(1) L1= canbm| n0,m>0 用正规文法。 ScA AaA|aB|a BbB|b (2) L2= 0na 1nbm| n>0，m 0 用二型文法。 S0S1B|0a1 BbB|c3文法GS为：（10分）SSdT | T TT<G | G G(S) | a试给出句型adT<(S)的短语、简单(直接)短语、句柄和最左素短语。 短语：a, T, (S), T<(S), adT<(S) 直接短语：a, (S) 句柄：a 最左素短语：a4将文法GS 改

2、写为等价的G'S，使G'S不含左递归和左公共因子。（5分）SA AB|AS BaB|+a SA ABA A SA| BaB|+a5判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表，并写出aabbb的分析过程。（10分）SaD DSTe| TbM MbH HM|abe#SSaDDDSTeDDTTbMMMbHHHMH步骤栈输入串动作(规则右部逆序入栈)0#Saabbb#Push SaD1#Daabbb#Pop a2#Dabbb#Push DSTe3#eTSabbb#Push SaD4#eTDaabbb#Pop a5#eTDbbb#Push D6#eTbbb#Pu

3、sh TbM7#eMbbbb#Pop b8#eMbb#Push MbH9#eHbbb#Pop b10#eHb#Push HM11#eMb#Push MbH12#eHbb#Pop b13#eH#出错，故句子不合法 6简述编译程序概念及构成。（10分）编译程序是现代计算机系统的基本组成部分.从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序. 7设G=（VN，VT，P，<S>）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？（10分）2型（上下文无关）：规则形式 ： A

4、74;b A ÎVN，b Î (VTÈVN)* 3型（右线性）：A®aB或A®a（右线性） A®Ba或A®a （左线性） a ÎVTÈe8为文法GE：（10分） V N | NE E V | V+E N i 构造递归下降识别程序E( ) V( ); if symbol = + E( ); V( ) N(); if symbol = E(); if symbol != error(); N( ) if symbol != i error(); /* 这样的写法很简化，当文法提取左公因子后，需要计算相关非终结

5、符的Follow集，才能确定什么时候用空串规则推导。*/9对给定正则表达式(d|ad)(b|ab)+ 构造其DFA M（10分）10将下图的NFA确定化为DFA。（10分） 2 b a b X 0 1 3 Y a babSABAACBDCEDNFA: DFA:IaIbX,0,1,30,2,1,33,Y0,2,1,30,2,1,31,3,Y3,YY1,3,Y2Y含有Y的状态子集为DFA的终态11简答题（10分）(1) 什么是文法，给出DFA的定义一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；3.f是转换函数，是在K×K上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki