2011-2012安徽大学编译原理补考试卷.doc

《2011-2012安徽大学编译原理补考试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、安徽大学2011—2012学年第一学期《编译原理》考试试卷（B卷）（闭卷时间120分钟）院/系年级专业姓名学号题号一二三四五六七总分得分得分一、（15分）设字母表∑={a，b}，1.写出不是以a开头，但以aa结尾的字符串集合的正规表达式r（5分）。2.构造NFAM，使得L（M）=L（r）；（5分）3.将NFAM确定化、最小化，得到DFAM1，使得L（M1）=L（M）。（5分）得分二、（20分）设文法G[S]如下：S→i（B）SAS→aA→eSA→εB→b1．（5分）求出各非终结符的first集合和follow集合，填入下表：非终结符firstfollowSAB2．（10分）构造预测分析

2、表，填入下表：则规终结符非终结符abei#SAB3．（5分）该文法是LL（1）文法吗？请说明理由。得分三、（20分）设文法G[S]：S→aSS→bSS→a1.文法G[S]属于乔姆斯基哪一型文法？（2分）2.符号串abbaa是不是该文法的一个句型？请证实。（方法不限）（3分）3.若是句型，写出该句型的所有短语、直接短语、素短语、最左素短语以及句柄（5分）4.求出该文法的firstvt集和lastvt集，构造算符优先关系表填入下表。（10分）firstvtlastvtS’Sab#ab#四、（25分）设CFG文法G[S]如下：S→aABeA→AbcA→bB→d1．（4分）写出该文法的拓广文法

3、：2．（9分）构造识别全部活前缀的DFA，填入下表：I0：S’→·SS→·aABeI1I2I3I4I5I6I7I9I8SeaBAbcbd3．（5分）构造该文法的LR（0）分析表，填入下表：Iactiongotoabcde#SAB01234567894．（7分）将abbc的分析过程填入下表：步骤状态栈符号栈余留符号串actiongoto说明S0S1S2S3S4R0R1R2R3R41234567五、（5分）对于下面的程序programtest(input，output)；vara：integerprocedurecala（x：integer);temp：integer；beginx:=a+

4、1;temp:=a+2;x:=temp;end;begina=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分）设程序段如下：readAreadBF：=1C：=A*AD：=B*BifC＜DgotoL1E：=A*AF：=F+1E：=E+FwriteEhaltL1：E：=B*BF：=F+2writeEifE＞100

5、gotoL2haltL2：F：=F-1gotoL1⒈利用基本块划分方法构造该代码段的程序流图（3分）；⒉将基本块依次编号为B1，B2，……求出各结点Bi的必经结点集D（Bi）；（3分）⒊求出流图中的回边；（2分）⒋求出流图中的循环。（2分）