发布时间 : 星期一 文章《编译原理》期中及期末习题更新完毕开始阅读22792f0df12d2af90242e68e
7.在语法分析中，根据每个产生式对应的语义子程序进行____的办法叫做____。
（陕西省1998年自考题） 8.对＋、*采用左结合习惯，对乘幂↑个采用右结合习惯，则E1+E2+E3可解释成＿， 而E1↑E2↑E3可解释成＿。（陕西省1997年自考题）
9.在语法树中，一个结点的综合属性的值由其＿的属性值确定，而继承属性则由该 结点的＿的某些属性确定。
10.对某个压缩了的上下文无关文法，当把每个文法符号联系于，且让该文法的规 则附加以＿时，称该文法为属性文法。
11.语法制导的翻译程序能够同时进行_____和______。 5.4 判断题
1.一个语义子程序描述了一个文法所对应的翻译工作。（） 2.逆波兰表示法表示表达式时无须使用括号。 （）
3.树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。（） 4.三地址语句类似于汇编语言代码，可以看成中间代码的一种抽象形式。（） 5.非终结符可以有综合属性，但不能有继承属性。（） 6.程序中的表达式语句在语义翻译时不需要回填技术。（） 7.在编译阶段只对可执行语句进行翻译。（）
8.无论是三元式表示还是间接三元式表示的中间代码，其三元式在三元式表中的位置一
旦确定就很难改变。（陕西省1998年自考题）（）
9.对中间代码的产生而言，目前还没有一种公认的形式系统。（） 10.三元式出现的先后顺序和表达式各部分的计值顺序并不一致。（）
11.自上而下分析的一个优点是：在一个产生式的中间就可以调用语义子程序。（） 12.终结符只有继承属性，它们由词法分析器提供。（） 13.翻译算术表达式语句时需要用到回填技术。（）
14.程序中不允许标号先引用后定义。（） 5.5 综合题
5.5 .1 （哈工大2000年研究生试题） 叙述下列概念：
（1）语法制导翻译 (2)翻译文法 (3)语义子程序
5.5.2 （武汉大学1999年研究生试题）
何谓“语法制导翻译(SDTS)”？试给出用SDTS生成中间代码的要点，并用一简例予以说明。
5.5.3 给出下列表达式的逆波兰表示(后缀式)： ①a*(－b+c)
②(A∨)∧(C∨┐D∧E)
③if (x+y)*Z=5 then x：=(a+b)↑c else y：=a↑b↑ c 5.5.4 写出算术表达式：A+B*(C－D)+E/(C－D)↑N的
①四元式序列；②三元式序列；③间接三元式序列；④树形表示 5.5.5 （清华大学1999年研究生试题）
令S.val为文法G[S]生成的二进制数的值，例如对输入串101．101则S.val=5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则。 G[S]：S-L.L|L L→LB|B B→0|1
5.5.6 （清华大学2000年研究生试题）
现有文法G1、G2如下，欲将G1定义的expression转换成如、G2的E所描述的形式。给出其语法制导翻译的语义描述。（提示：可采用类似yacc源程序的形式，所涉及的语义函数须用自然语言给予说明，不用抄写产生式，用产生式编号表示）。 G1：(1)
（8）
(2)and和*分别是常规的布尔和算术运算符，要求其运算对象的相应类型匹配， G2：E→EE*|EE and|id|num|true|false 5.5.7 下面的文法生成变量的类型说明： D→id L L→,id L|:T T→integer|real
试构造一个翻译方案，仅使用综合属性，把每个标识符的类型填入符号表中（对所用到 的过程，仅说明功能即可，不必具体写出）。
5.5.8 已知文法G及每个产生式相应的语义子程序如下：
（1）E→i {E·TC: =NXQ; E·FC:=NXQ+1：GEN (jnz, ENTRY(i), ,0);
GEN (j,＿,＿,0)}/*NXQ指针总是指向下一个将要形成的四元式的地址（编号）； GEN过程把四元式（OP, ARG1，ARG2，RESULT）填入四元式表中*/
(2)E→i(1)ropi(2) {E·TC: =NXQ; E·FC:=NXQ+1：GEN(jrop, ENTRY(i(1)),ENTRY(i(2)),0);
GEN (j,＿,＿,0)}/*jrop是根据关系符rop而定义的一条件转移指令*/ (3）E→(E(1)) {E·TC:=E(1)·TC；E·FC:＝E(1)·FC} (4)E→┐E(1) {E·TC:=E(1)·FC；E·FC:＝E(1)·TC}
（5）EA→E(1)∧{BACKPATCH(E(1)·TC，NXQ)；EA·FC:=E(1)·FC}
/*BACKPATCH过程将NXQ的当前值填入E(1)·TC所指四元式的第四区段*/ （6）E→EAE(2) {E·TC:=E(2)·TC；E·FC: =MERG（EA·FC，E(2)·FC)}
/*MERG函数将EA·FC和E(2)·FC两条链合并，并以EA·FC作为链首*/ （7）E0→E(1)∨{BACKPATCH(E(1)·FC，NXQ)；E0·TC:=E(1)·TC} （8）E→E0E(2) {E·FC:=E(2)·FC；E·TC:=MERG(E0·TC, E(2)·TC} 5.5.9 赋值语句的文法及语义动作描述如下： (1)A→:=E {GEN(:=,E·PLACE,＿ ,ENTRY(i))}
(2)E→E(1)+E(2) {E·PLACE:=NEWTEMP：GEN(＋，E(1))·PLACE,E(2)·PLACE,E·PLACE)} (3)E→E(1)*E(2) {E·PLACE:=NEWTEMP：GEN(*，E(1)·PLACE,E(2)·PLACE,E·PLACE)} (4)E→-E(1) {E·PLACE:=NEWTEMP：GEN(＠，E(1)·PLACE,＿,E·PLACE)} (5)E→(E(1) {E·PLACE:= E(1)·PLACE} (6)E→i {E·PLACE:=ENTRY(i)}
写出赋值语句X:=-B*(C+D)+A的自下而上的语法制导翻译过程。 5.6.0 (1)写出Pascal语言的repeat语句； repeat
S1；S2；…；Sn until. E；
的文法及对应的语义子程序(注：E为条件表达式)； (2)按构造好的文法分析并翻译语句： repeat x：=x+l until x>5； 5.6.1 写出翻译过程调用语句的语义子程序。要求生成的四元式序列在转子指令之前的参
数四元式par按反序出现（与实在参数的顺序相反），问这种情况下在翻译过程调用语句时是否需要语义变量（队列）QUEUE呢？
5.6.2 （国防科大2001年研究生试题） 设某语言的while语句的语法形式为： S→while E do S(l) 其语义解释如图5.8所示。
(1)写出适合语法制导翻译的产生式。
(2)写出每个产生式对应的语义动作。
5.6.3 (国防科大1999年研究生试题)
条件式if E(l) then E(2) else E(3)的语义解释为：若布尔式E(l)为真，则条件表达式值取E(2)的值；否则条件表达式值取E(3)的值。
(1)写出if E(l) then E(2) else E(3)的适合语法制导翻译的产生式及相应语义子程序。 (2)按(1)中的语义子程序把
a:=if x>0 then x+1 else x+2; 翻译为四元式序列。
5.6.4 (哈工大2000年研究生试题) 设for语句的形式为：
for V=El step E2 until E3 do S
请设计其目标结构，并给出相应的语义分析过程。 5.6.5 某程序设计语言中有如下形式的选择语句 switch (E)
{case cl：sl；
case c2：s2； case ci：si； case cn：Sn； default： Sn+l } 其中n≥1。此选择语句的语义是：先计算整型表达式E的值，然后将表达式的值依次和case 后的常数Ci比较，当与某常数ci相等时就执行语句Si, 并结束该选择语句； 若与诸常数均不相等, 则执行语句Sn+1。
为了便于翻译, 上述选择语句可用下列产生式来定义： A→switch(E) B→A{case c D→B：S|F：S F→D；case c S→D；default：S}
使用自上而下的语法制导翻译方法,给出翻译此选择语句的翻译子程序(语义子程序)。 在翻译子程序中可以使用下列指示器、过程和函数，
·指示器NXQ：指向下一个将要形成但尚未生成的四元式的地址； ·过程GEN(OP,ARG1,ARG2,RESULT),该过程把四元式 (OP,ARG1,ARG2,RESULT) 填进四元式表中，且将NXQ增加1；
·过程BACKPATCH(P,t)：把P所链接的每个四元式的第四区段都填为t； ·函数MERG(P1, P2)：把P1和P2为链首的两条链合并,回送合并后的链首；
·函数ENTRY(i)：回送标识符i在符号表中的位置。 5.6.6 含有数组元素的赋值语句翻译规则如下：
①A→V：=E {IF V·OFFSET=null THEN GEN(：=,E·PLACE,_,V·PLACE) /*V为简单变量*/
ELSE GEN([]＝,E·PLACE,_V·PLACE[V·OFFSET]) /*V为数组变量*/}
②E→E(1)+E(2) {T：=NEWTEMP；GEN(+，E(1)·PLACE，E(2)·PLACE,T)；E·PLACE：=T)
③E→(E(1)) {E·PLACE：＝E(1)·PLACE)
④E→V {IF V·OFFSET=null THEN E·PLACE：=V·PLACE
/*V为简单变量*/ ELSE BEGIN T：=NEWTEMP； GEN(＝[],V·PLACE[V OFFSET],_,T)； E·PLACE：=T END /*V为数组变量*/}
⑤V→elist] {T：=NEWTEMP；GEN(-,elist·ARRAY,C,T)；
/*elist·ARRAY为数组的首地址a, C为常数：d2d3? dn+d3 ?dn+?+dn+1*/
V·PLACE：=T； V·OFFSET：=elist·PLACE} ⑥V→i {V·PLACE：=ENTRY(i)：V·OFFSET：=null}