编译原理(模拟试卷-更新中)1

编译原理（模拟试卷更新中）1/9四川理工学院试卷(2015至2016学年第2学期)课程名称：编译原理（模拟试卷更新中）命题教师：黎远松适用班级：软件2013级1-5班考试2016年5月17日（12周二下午3:00-5:00）共6页注意事项：1、满分100分。要求卷面整洁、字迹工整、无错别字。2、考生必须将姓名、班级、学号完整、准确、清楚地填写在试卷规定的地方，否则视为废卷。3、考生必须在签到单上签到，若出现遗漏，后果自负。4、如有答题纸，答案请全部写在答题纸上，否则不给分；考完请将试卷和答题卷分别一同交回，否则不给分。试题（模拟更新中）一、选择题（共10个小题，每个小题2分，共20分）1．词法分析器的输入是________。A．符号串B．源程序C．语法单位D．目标程序2．语言是________。A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合3．一个句型中称为句柄的是该句型的最左________。A．非终结符号B．短语C．句子D．直接短语题号一二三四五六七八评阅(统分)教师得分202018868128黎远松得分评阅教师系专业级班学号姓名密封线密封线内不要答题编译原理（模拟试卷更新中）2/94．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即________。A．字符B．单词C．句子D．句型5．构造编译程序应掌握________。A．源程序B．目标语言C．编译方法D．以上三项都是6．正规式M1和M2等价是指________。A．M1和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等7．代码优化的目的是________。A．节省时间B．节省空间C．节省时间和空间D．把编译程序进行等价交换8．生成中间代码时所依据的是________。A．语法规则B．词法规则C．语义规则D．等价变换规则9．下推自动机识别的语言是________。A．0型语言B．1型语言C．2型语言D．3型语言10．对应Chomsky四种文法的四种语言之间的关系是________。A．L0L1L2L3B．L3L2L1L0C．L3=L2L1L0D．L0L1L2=L3二、是非题（共10个小题，每个小题2分，共20分。下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”)1.一个上下文无关文法的开始符，可以是终结符或非终结符。(×)2.一个句型的直接短语是唯一的。(×)3.已经证明文法的二义性是可判定的。（×）得分评阅教师编译原理（模拟试卷更新中）3/94.每个基本块可用一个DAG表示。（√）5.每个过程的活动记录的体积在编译时可静态确定。（√）6.2型文法一定是3型文法。（×）7.一个句型一定句子。(√)8.算符优先分析法每次都是对句柄进行归约。(×)9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。(√)三、回答下列问题：（共3个小题，每个小题6分，共18分）1.对于下面程序段programtest(input,output)vari,j:integer;procedureCAL(x,y:integer);beginy:=y*y;x:=x-y;y:=y-xend;begini:=2;j:=3;CAL(i,j)writeln(j)end.若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出程序执行的输出结果。答：(1)3(2)16(3)16(每个值2分)2.计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。G(M)：M→TBT→Ba|B→Db|eT|D→d|解答：计算文法的FIRST和FOLLOW集合：(4分)FIRST(M)={a，b，e，d，}FIRST(T)={a，b，e，d，}FIRST(B)={b，e，d，}FIRST(D)={d，}FOLLOW(M)={#}FOLLOW(T)={a，b，e，d，#}FOLLOW(B)={a，#}FOLLOW(D)={b}得分评阅教师编译原理（模拟试卷更新中）4/9检查文法的所有产生式，我们可以得到：1.该文法不含左递归，2.该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。3.该文法的非终结符T、B和D，它们都有候选式，而且FIRST(T)∩FOLLOW(T)={a，b，e，d}≠所以该文法不是LL(1)文法。(2分)编译原理（模拟试卷更新中）5/93.考虑下面的属性文法产生式语义规则S→ABCA→aB→bC→cB.u:=S.uA.u:=B.v+C.vS.v:=A.vA.v:=3*A.uB.v:=B.uC.v:=1(1)画出字符串abc的语法树;(2)对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少?答：(1)(2分)（2）S.v的值为18(2分)四、(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符串。答案：(2分)构造相应的正规式：(a|b)*ab(a|b)*(3分)aaabbb(3分)确定化：I0I1I{0,1,2}{1,2,3}{1,2}得分评阅教师SABCabc0123645编译原理（模拟试卷更新中）6/9{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}bbbaaaaaabbb最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}五、(6分)写一个文法使其语言为L(G)={anbncm|m,n≥1，n为奇数，m为偶数}。文法G(S):ccCcc|ccCbaaAbb|aAACS六、(8分)对于文法G(S):得分评阅教师得分评阅教师012345baa01b3ba编译原理（模拟试卷更新中）7/9）MaLa|(LMbMbS1.写出句型b(Ma)b的最右推导并画出语法树。2.写出上述句型的短语，直接短语和句柄。答：1.(4分)bMabLbbbMbS)((2.(4分)短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)SbM(TMabL)编译原理（模拟试卷更新中）8/9七、(12分)对文法G(S)：S→a|^|(T)T→T，S|S(1)构造各非终结符的FIRSTVT和LASTVT集合;(2)构造算符优先表;(3)是算符优先文法吗?(4)构造优先函数。答：(1)(4分))},^,,{,)()},^,{)((},^,,{,)((},^,{)(aTLASTVTaSLASTVTaTFIRSTVTaSFIRSTVT(2)(4分)a^(),a^(=),(3)是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。(1分)(4)优先函数(3分)a^(),F44244G55523得分评阅教师编译原理（模拟试卷更新中）9/9八、(8分)文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1)S→DbB(2)D→d(3)D→ε(4)B→a(5)B→Bba(6)B→εLR分析表ACTIONGOTObda#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5注：答案格式为：步骤状态栈符号栈输入串动作，产生式00#baba#初始化步骤状态符号输入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc得分评阅教师