1、计算机编译原理模拟试卷A124start52othersothers/*/一、处于/* 和 */之间的串构成注解,注解中间没有*/,请根据词法分析基本方法,画出接受这种注解的DFA的状态转换图。二、根据自上而下的语法分析方法,构造下面文法的LL(1)分析表。D TLT int | realL id RR , id R | e答案:int realid,$DDTLDTLTTintTrealLLid RRR , id RR e三、根据自下而上的语法分析方法,为下面文法构造规范LR(1)分析表,画出状态转换图就可以了。然后说明它是否有动作冲突。S V = E | E V * E | id E V答案:(1)状态转换图如下:S S, $ S V = E, $S E, $V * E, =/$V id, =/$E V, $I0SEidV*S S , $I1=S V = E, $E V , $I2S E , $I3S V = E , $I9S V = E, $E V, $V * E, $V id, $I6EV id , =/$I5E V , =/$I8idV * E, =/$E V, =/$V *
2、E, =/$V id, =/$I4*VEV * E , =/$I7E V , $I10idV * E, $E V, $V * E, $V id, $I11*EV * E , $I13V id , $I12idVV(2)合并同心项目集(I4和I11,I5和I12,I7和I13,I8和I10)后没有动作冲突。四、何谓语法制导的定义?为下面文法写一个语法制导的定义,它完成一个句子的while-do最大嵌套层次的计算并输出这个计算结果。S EE while E do E | id := E | E + E | id | (E)答案:语法制导的定义如下:S Eprint(S.loop);E while E1 do E2E.loop := max(E1.loop, E2.loop) +1;E id := EE.loop := E1.loop;E E1 + E2E.loop := max(E1.loop, E2.loop);E idE.loop := 0;E (E1)E.loop := E1.loop;五、请根据数据流分析方法,对下面的程序片段作出其程序流图并计算: (1)各基本块的到达_定值集IN
3、B;(2)各基本块中各变量引用点的ud链; I := 1 J := 0 L1: J := J + I read I if I 100 goto L2 write J halt L2 : I := I * Igoto L1答案:程序流图(1)计算各基本块的到达-定值集INB。公式为:INB = OUTP PPB OUTB = GENB ( INB - KILLB ) GENB和KILLB由程序流图直接求出,显示在表9.6(1)中。基本块GENB位向量KILLB位向量B1 d1, d2 11000000 d3, d4, d6 00110100B2 d3, d4 00110000 d1, d2, d6 11000100B3 d6 00000100 d1, d4 10010000B4 00000000 00000000求各基本块到达-定值的初值及各遍的执行结果显示在表9.6(2)中基本块初值第一遍后第二遍后第三遍后INBOUTBINBOUTBINBOUTBINBOUTBB10000000011000000000000001100000000000000110000000000000011000
4、000B20000000000110000110001000011000011100100001100001110010000110000B30000000000000100001100000010010000110000001001000011000000100100B40000000000000000001100000011000000110000001100000011000000110000(2)求各基本块中各变量引用点的ud链: 假设在程序中某点u引用了变量a,则把能到达u的a的所有定值点,称为a在引用点u的引用-定值链(简称ud链)。可以利用到达-定值信息来计算各个变量在任何引用点的ud链。 由图9.6(1)的程序流图可知,I的引用点是d3、d5和d6,J的引用点是d3和d8。 B2中I和J的引用点d3前面没有对I和J的定值点,其ud链在INB2= d1, d2, d3, d6 中,所以I在引用点d3的ud链是 d1, d6 ;J在引用点d3的ud链是 d2, d3 。 在B2中I的引用点d5前面有I的定值点d4,且在d4定值后到达d5,所以I在引用点d5的ud链是 d4
5、。 B3中I的引用点d6前面没有I的定值点,其ud链是INB3中I的所有定值点,所以是 d4 。 B4中J的引用点d8前面没有对J的定值点,其ud链是INB4中J的所有定值点。已知INB4 = d3, d4 ,所以,J的引用点d8的ud链是 d3 。=2一、叙述下面的正规式描述的语言,并画出接受该语言的最简DFA的状态转换图。( 1 | 01 )* 0*答案:一、该正规式描述的语言是,所有不含子串001的0和1的串。start.二、(1)通过构造识别活前缀的DFA和构造分析表,来证明文法E E + id | id是SLR(1)文法。(2)下面左右两个文法都和(1)的文法等价E E + M id | idE M E + id | idM eM e请指出其中有几个文法不是LR(1)文法,并给出它们不是LR(1)文法的理由。答案:(1)先给出接受该文法活前缀的DFA如下:E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4id再构造SLR分析表如下:状态 动作转移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2
6、 3 s4 4 r1 r1 表中没有多重定义的条目,因此该文法是SLR(1)的。(2)只有文法E M E + id | idM e不是LR(1)文法。因为对于句子id+id+id来说,分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多,而此时句子中+id的个数是未知的。三、为下面的算术表达式文法写一个语法制导的翻译方案,它将每个子表达式E的符号(即值大于零还是小于零)记录在属性E.sign中(属性值分别用POS或NEG表示)。你可以假定所有的整数都不为零,这样就不用担心零的符号。E E *E | +E | -E | unsigned_integer答案:E E1 *E2if E1.sign= E2.sign then E.sign := POS else E.sign := NEG E +E1 E.sign := E1.sign E -E1 if E1.sign= POS then E.sign := NEG else E.sign := POSE unsigned_integer E.sign := POS四、一个C语言程序如下:func(i1,i2,i3)long
7、 i1,i2,i3;long j1,j2,j3; printf(Addresses of i1,i2,i3 = %o,%o,%on,&i1,&i2,&i3);printf(Addresses of j1,j2,j3 = %o,%o,%on,&j1,&j2,&j3);main()long i1,i2,i3;func(i1,i2,i3);该程序在某种机器的Linux上的运行结果如下:Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434从上面的结果可以看出,func 函数的3个形式参数的地址依次升高,而3个局部变量的地址依次降低。试说明为什么会有这个区别。答案:由于实参表达式是反序进入活动记录,而局部变量是顺序在活动记录中分配。五、考虑下面的三地址语句序列:b := 1b := 2if w = x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y = z goto L4goto L5L4:g := g + 1h := 8goto L1L5:h := 9(1)在该代码中用水平的横线将代码分成基本块,并给每个基本
《计算机编译原理模拟试卷A及答案》由会员jay****li分享,可在线阅读,更多相关《计算机编译原理模拟试卷A及答案》请在金锄头文库上搜索。