编译原理期末考试试卷A卷.doc

TJUT编译原理 试卷答题时限： 120 分钟 考试形式：闭卷笔试得分统计表：大题号总分 一二三四一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分,共20分)得分注意：须将本题答案写在下面的表格中，写在其它地方无效12345678910DCBDDBCBDC1. 编译程序是对（ ）A。 汇编程序的翻译 B。 高级语言程序的解释执行 C. 机器语言的执行 D. 高级语言的翻译 2. 词法分析器的输出结果是( ）A单词的种别编码B单词在符号表中的位置C单词的种别编码和自身值D单词自身值3. 在规范规约中,用（ ）来刻画可规约串。A直接短语 B句柄 C最左素短语 D素短语4。 与正规式（a | b） * （c | d）等价的正规式是( ）Aa* (c | d) b(c | d） Ba* (c | d） * b（c | d) *Ca* （c | d） b （c | d）D(a b） c (a b) * d5。 若项目集IK含有A,则在状态K时,仅当面临输入符号aFOLLOW(A）时，才采取A动作的一定是( ）ALALR文法 BLR（0） 文法 CLR（1）文法 DSLR(1）文法6。 四元式之间的联系是通过（ )实现的.A。 指示器 B。 临时变量 C. 符号表 D. 程序变量7文法G：S x Sx y所识别的语言是( ）Axyx B（xyx） * Cxnyxn（n0) Dxyx*8。 有一语法制导翻译如下所示：S b Ab print “1A（B print “2Aa print “3”BAa） print “4若输入序列为b（(aa)a)a)b，且采用自下而上的分析方法，则输出序列为( ）A32224441 B. 34242421 C12424243 D。 34442212 9关于必经结点的二元关系，下列叙述不正确的是（ ）A满足自反性 B满足传递性 C满足反对称型 D满足对称性10错误的局部化是指（ ）. A把错误理解成局部的错误 B对错误在局部范围内进行纠正C当发现错误时,跳过错误所在的语法单位继续分析下去D当发现错误时立即停止编译，待用户改正错误后再继续编译 二、判断题（每小题1分，共5分)得分1。 文法G的一个句子对应于多个推导，则G是二义性的。（ ）2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（ ）3。 算符优先文法采用“移进规约”技术，其规约过程是规范的。（ ）4。 删除归纳变量是在强度削弱以后进行.（ ）5. 在目标代码生成阶段，符号表用于目标代码生成。（ ）三、简答题（每小题5分，共15分）得分1。 构造正规式（01)*00相应的正规式并化简.(共5分）（1)根据正规式，画出相应的NFA M（2分）0e40031e21X(2）用子集法将NFA确定化（2分）II0I1x，1，21,2，31，21，2,31,2,3,41,21,21,2，31，2 1,2,3,4 1,2，3，41，2 将所有子集重命名，得到转换矩阵：S01012132212332(3）化简,并画出DFA M（1分）划分为状态：0，2 1 3 将这三个状态命名为0，1，2三个状态S010101202201200100112. 设文法GS： （共5分)S S + aT | aT | +aTT *aT | *a (1）写出句型 aT + a *a a的最右推导并画出语法树(2分）SSSaTSaaTS+aa*aaT+a*aaTS a a T * a T* a（2）写出该句型中所有的短语、直接短语、句柄和最左素短语。（3分）短语：aT、*aa、a、aT+a*a*a直接短语:aT、*a句柄：aT最左素短语：aT3。 将下列语句翻译为逆波兰表示，三元式、间接三元式和四元式表示：（共5分）a = （b + c） e + (b + c) / f（1） 逆波兰表示（1分）abc + e bc + f / + =（2） 三元式(1分） （+，b， c） (*,e) (+，b, c） (/,f) （+， ） (=，a， )(3) 间接三元式（1分） (+， b, c） (, , e) (/,，f) (+, , ） (=, a， ）间接码表：(4) 四元式(2分） （+， b, c, T1） （, T1, e，T2） （+, b, c, T3) (/, T3, f， T4） (+, T2, T4， T5) (=， T5,， a）四、综合题（共60分)得分1.已知文法G（S）：(共15分）S * AA 0A1 | （1)求文法G的各非终结符号的FIRSTVT和LASTVT集合。(5分）FIRSTVT（S）= * LASTVT(S）= 1, *FIRSTVT（A)= 0, * LASTVT(S）= 1, *(2)构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法。(5分）01* 0 =1 文法G中的任何终结符对至多只存在一种优先关系，所以文法G是一个算符优先文法。（3)分析句子*0*1，并写出分析过程。(5分）0#*0*1#1#*0*12#0*13*0*140A15#0A1#6A7#S分析正确步骤 符号栈 输入串 输出2。已知文法G(S）：（共15分）S aS | bS | a(1) 构造该文法的拓广文法。（1分)（0）SS(1） SaS（2)AbS（3）Aa(2） 构造其LR（0)项目集规范族，并给出识别活前缀的DFA。（7分）SaI4 : SaS.I1 : Sa.SS.aSS.bSS.aSa.I0 : S.SS.aSS.bSS.aI2 : Sb.SS.aSS.bSS.aI3 : SS.I5 : SbS.aaSbbSb(3）构造其SLR分析表，并判断该文法是否是SLR(1）文法。（7分）状态I1移进规约冲突，计算S的Follow集合:Follow(S），可以采用SLR冲突消解法,得到如下SLR分析表：状态ACTIONGOTOab#S0S1S231S1S2r342S1S253acc4r15r2该文法是SLR（1）文法.3.设有如下基本块：（共10分） T1 = A + BT2 = 5M = T2 4T3 = C - DT4 = M + T3L = T1 T3T4 = A + Bn10n1n2n3n4n5n6n8n77AT1,T4,NB5T4LT2MC+*N = T4(1) 画出该基本块的DAG图.（5分）n9T320D(2) 假设变量L,M，N在基本块出口之后是活跃的，给出优化后的四元式序列。(5分）NABM=20T3=CDL=NT34.以下程序段是最内循环(共13分）A = 0I = 1L1： B = J + 1C = B + IA = C + Aif I = 100 GOTO L2I = I + 1GOTO L1L2:(1) 画出程序流图,并找出回边与循环。（3分）A=0I=1L1：B=J+1C=B+IA=C+Aif I=100 goto L2I=I+1GOTO L1L2：B1B2B3B4流图中有一条回边B3B2，且B2DOMB3,所以,有一个循环B2， B3,B2是循环入口结点，也是出口结点.(2) 对循环优化（8分)1. 代码外提:对于B2中的赋值四元式B=J+1，由于循环中没有对J的定值操作，所有对J的定值都在循环外，所以，它是循环中的不变运算，可以进行代码外提。2. 删除归纳变量：循环中I是基本归纳变量,C是与I同族的归纳变量，两者有如下线性关系：C=B+I,则I=100可以用C=B+100替代，相应的I=I+1可用C=C+1替代，再将新的不变运算提到循环外。(3) 画出优化后的程序流图（2分)A=0I=1B=J+1C=B+IR=B+100L1：A=C+Aif C=R goto L2C=C+1GOTO L1L2：B1B2B3B45。 有一程序如下：program ex；a： integer;procedure PP(x: integer）;begin：x:=5； x:=a+1end；begina:=2;PP(a)；write（a）end试用图表示ex调用PP（a）前后活动记录的过程。（共7分)DISPLAY表PP_SPex_SP形式参数x参数个数:1全局DISPLAY地址返回地址ex_SP局部变量:aDISPLAY表ex_SP参数个数：0全局DISPLAY地址返回地址ex_SPPP_TOP PP的活动记录（调用PP（a）之后） PP_SP ex_TOP ex的活动记录（调用PP（a）之前） ex_SP 试卷编号： 1-A 第 7 页 共 7 页