2011-2012安徽大学编译原理补考试卷(共7页).doc

《2011-2012安徽大学编译原理补考试卷(共7页).doc》由会员分享，可在线阅读，更多相关《2011-2012安徽大学编译原理补考试卷(共7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上安徽大学20 11 20 12 学年第 一 学期 编译原理 考试试卷（B卷）（闭卷 时间120分钟）院/系 年级 专业 姓名 学号 题 号一二三四五六七总分得 分得分一、（15分）设字母表=a，b，1. 写出不是以a开头，但以aa结尾的字符串集合的正规表达式r（5分）。 2. 构造NFA M，使得 L（M）=L（r）；（5分）3. 将NFA M 确定化、最小化，得到DFA M1，使得L（M1）=L（M）。（5分）得分二、（20分）设文法GS如下：Si（B）SASaAeSABb1（5分）求出各非终结符的first集合和follow集合，填入下表：非终结符firstfol

2、lowSAB2（10分）构造预测分析表，填入下表：则规 终结符非终结符abei#SAB3（5分）该文法是LL（1）文法吗？请说明理由。得分三 、（20分）设文法GS： SaSSbS Sa1. 文法GS属于乔姆斯基哪一型文法？（2分）2. 符号串abbaa 是不是该文法的一个句型？请证实。（方法不限）（3分）3. 若是句型，写出该句型的所有短语、直接短语、素短语、最左素短语以及句柄（5分）4. 求出该文法的firstvt集和lastvt集，构造算符优先关系表填入下表。（10分）firstvtlastvtSSab#ab#四、（25分）设CFG文法GS如下：SaABeAAbcAbBd1（4分）写出该

3、文法的拓广文法：2（9分）构造识别全部活前缀的DFA，填入下表：I0：S SSaABe I1I2I3I4I5I6I7I9I8 S e a B A b c b d3（5分）构造该文法的LR（0）分析表，填入下表：Iactiongotoabcde#SAB01234567894（7分）将abbc的分析过程填入下表：步骤状态栈符号栈余留符号串actiongoto说明S0S1S2S3S4R0R1R2R3R41234567五、（5分）对于下面的程序 program test (input，output)； var a ：integerprocedure cala（x：integer); temp：inte

4、ger； begin x:=a+1; temp:=a+2; x:=temp; end; begin a=2;cala ( a )；writeln（a） end.若参数传递的办法分别为传名，传地址，传结果，传值，则最终打印的a值分别是多少？六、（5分）设基本块如下：得 分A：=B*CD：=B/CE：=A+DF：=2*EG：=B*CH：=G*GF：=H*GL：=FM：=L构造相应的DAG，并写出利用DAG优化后的语句序列；（5分）七、（10分）设程序段如下：read Aread BF：=1C： =A*AD： =B*Bif CD goto L1E： =A*AF： =F+1E： =E+Fwrite Ehalt L1：E：=B*BF：=F+2write Eif E100 goto L2halt L2：F：=F-1goto L1 利用基本块划分方法构造该代码段的程序流图（3分）； 将基本块依次编号为B1，B2，求出各结点Bi的必经结点集D（Bi）；（3分） 求出流图中的回边；（2分） 求出流图中的循环。（2分）专心-专注-专业