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

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

2、5 分）得分精选优质文档-倾情为你奉上专心-专注-专业二、二、 （2020 分）分）设文法 GS如下：Si（B）SASaAeSABb1 （5 分）求出各非终结符的 first 集合和 follow 集合，填入下表：非终结符firstfollowSAB2 （10 分）构造预测分析表，填入下表： 终结符非终结符abei#SAB3 （5 分）该文法是 LL（1）文法吗？请说明理由。三三 、 （2020 分）分）设文法 GS： SaSSbS Sa1. 文法 GS属于乔姆斯基哪一型文法？（2 分）2. 符号串 abbaa 是不是该文法的一个句型？请证实。 （方法不限） （3 分）得分得分规则精选优质文档

3、-倾情为你奉上专心-专注-专业I0：S SSaABe I1I2I3I4I5I6I7I9I83. 若是句型，写出该句型的所有短语、直接短语、素短语、最左素短语以及句柄（5分）4. 求出该文法的 firstvt集和lastvt集，构造算符优先 关系表填入下表。（10分）四、四、 （2525 分）设分）设 CFGCFG 文法文法 GSGS如下：如下：SaABeAAbcAbBd1 （4 分）写出该文法的拓广文法：2 （9 分）构造识别全部活前缀的 DFA，填入下表： S e a B A b c b dfirstvtlastvtSSab#ab#精选优质文档-倾情为你奉上专心-专注-专业3 （5 分）构造

4、该文法的 LR（0）分析表，填入下表：actiongotoIabcde#SAB01234567894 （7 分）将 abbc 的分析过程填入下表：状态栈符号栈步骤S0S1S2S3S4R0R1R2R3R4余留符号串actiongoto说明1234567五、五、 （5 5 分）分）对于下面的程序 program test (input，output)； var a ：integerprocedure cala（x：integer); temp：integer；精选优质文档-倾情为你奉上专心-专注-专业 begin x:=a+1; temp:=a+2; x:=temp; end; begin a=2

5、;cala ( a )；writeln（a） end.若参数传递的办法分别为传名，传地址，传结果，传值，则最终打印的 a 值分别是多少？六、六、 （5 5 分）分）设基本块如下：A：=B*CD：=B/CE：=A+DF：=2*EG：=B*CH：=G*GF：=H*GL：=FM：=L构造相应的 DAG，并写出利用 DAG 优化后的语句序列；（5 分）得 分精选优质文档-倾情为你奉上专心-专注-专业七、七、 （1010 分）分）设程序段如下：r e a d Ar e a d BF ： = 1C ： = A * AD ： = B * Bi f C D g o t o L 1E ： = A * AF ： = F + 1E ： = E + Fw r i t e Eh a l t L 1 ： E ： = B * BF ： = F + 2w r i t e Ei f E 1 0 0 g o t o L 2h a l t L 2 ： F ： = F - 1g o t o L 1 利用基本块划分方法构造该代码段的程序流图（3 分） ；精选优质文