《编译原理》期中及期末习题 下载本文

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):begin end. (2)→var (3),id: (4)→id: (5)→int (6)→bool (7)

(8) (9) and (10)* (11)→id (12)→num (13)→true (14)→false 要求:(1) 中的id必须在中先声明。

(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}