《编译原理》期中及期末习题(8)

请设计其目标结构，并给出相应的语义分析过程。 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}

/*V·OFFSET为null表示V为简单变量*/ ⑦elist→elist(1),E {T：=NEWTEMP；k：=elist(1).DIM+1；/*下标记数，初值elist(l).DIM=1*/ dK：=LIMIT(elist(l).ARRAY,K)；/*给出数组第K维的长度*/ GEN (*,elist(l).PLACE,dK,T)； GEN(+,E·PLACE,T,T)； elist·ARRAY：=elist(l).ARRAY； elist·PLACE：=T； elist·DIM：=K} ⑧elist→i[E {elist·PLACE：=E·PLACE；elist·DIM：=1；elist·ARRAY：=ENTRY(i) /*ENTRY(i)为数组i的入口地址(即首地址a)*/}

己知A是一个10X20的数组且按行存放,求： (1)赋值语句X：=A[I,J]的四元式序列； (2)赋值语句A[I+2, J+1]： =M+N的四元式序列。

5.6.7 改写例题5.12文法G描述布尔表达式的语义子程序,使得i(1)rop i(2)不按通常方式翻译为下面的相继两个四元式：

(jrop, i(1), i(2), 0) (j_,_,0) 而是翻译成如下的一个四元式： (jnrop, i(1), i(2), 0)

使得当iMrop i(2)为假时发生转移，而为真时并不发生转移(即顺序执行下一个四元式),从而 产生效率较高的四元式代码。

5.6.8 (上海交大2000年研究生试题) 给出文法G[S]：S→-SaA|A A→AbB|B B→cSd|e

（1)请证实AacAbcBaAdbed是文法G[S]的一个句型。 (2)请写出该句型的所有短语、素短语以及句柄。

(3)为文法G[S]每个产生式写出相应的翻译子程序，使句型AacAbcBaAdbed经该翻译 方案后，输出131042521430。

(4)文法G[S]是不是SLR文法？请构造分析表证实之。

5.6.9 (上海交大2000年研究生试题) 语句While AD then x:=F[i,j] else x:=x+l经翻译后的三地址语句或四元式是 什么？（设三地址语句或四元式自100开始存放，数组F的内情向量自300开始存放，数组首地址500,每个数组元素占四字节。）

5.7.0 (上海交大1997年研究生试题) 文法G及相应的翻译方案如下 S→bts{printf:\

S→a {print: \ T→R {print: \ R→R/S {print: \ R→S {print: \ (1）文法G属于Chomsky哪一型文法？

(2)符号串bR/bTc/bSc/ac是不是该文法的一个句型，请证实。 （3)若是句型，写出该句型的所有短语、素短语以及句柄。 (4)文法G是不是算符优先文法，请予证实。

（5)文法G经消除左递归后得到的等价文法G’是不是LL(1)文法，请予证实。 (6)文法G是不是SLR(1)文法，请予以证实。

(7)对于题2的输入符号串，该翻译方案的输出是什么？

5.7.1 下面是用筛选法求素数的程序段，试将其翻译为四元式序列。 for i：=2 to N do B [i]：=true； i：=1；

while i≤N do begin

i：=i+l； if B[i]then begin

j：=2；

while i*j≤N do begin

B[i*j]：=false j：=j+1

end end end； 5.7.2 使用中间语言有什么好处？

5.7.3 将下面的语句翻译成四元式序列： while A

5.7.4 （陕西省1999年自考）

已知源程序如下：

prod:=0; i=1；

WHILE i≤20 do begin

prod:=prod+a[i]*b[i]； i=i+l end；

试按语法制导翻译法将上述源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。 5.7.5 (中科元计算所1999年研究生试题) 己知表达式为A+B*(C-D）**N（**为幂乘） （1)给出该表达式的逆波兰式表示（后缀式）。 (2）给出上述表达式的四元式和三元式序列。 5.7.6 (中科元计算所1999年研究生试题) 文法G的产生式如下：

S→(L)|α L→L，S|S

（1)试写出一个语法制导定义，它输出配对括号个数。

(2）写一个翻译方案，打印每个a的嵌套深度。如((a), a),打印2,1。

5.7.7 (中科元计算所2000年研究生试题) 程序的文法如下：

p→D

D→D；D|id:T|proc id；D；S

（1)写一个语法制导定义，打印该程序一共声明了多少个id? (2）写一个翻译方案，打印该程序每个变量id的嵌套深度。

5.7.8 (南开大学1998年研究生试题) 写出语句

X:=(a+b)*c Y=d↑（a+b) 的间接三元式。

5.7.9 (国防科大1999年研究生试题) 把语句if a>b then while x>0 do x:=x-2 else y:=y+1； 翻译为四元式序列。

5.8.0 (国防科大1999年研究生试题) 把下面的语句

while (A>B) do

if (C

5.8.1举例说明什么是语法制导的翻译。

5.8.2 对下面的程序段，产生相应的四元式，并给出填符号表、返填、拉链等过程的执行情况。

GOTO L1； S1；

GOTO L1； S2；

COTO L1； L1： S3；

GOTO Ll； L2： S4；

GOTO L2； S5；

文法G[P]↑及相应翻译方案为

p→bQb {print：”1”} Q→cR {print：“2”} Q→a {print： \ R→Qad {print： \

(1)该文法是不是算符优先文法，请构造算符优先关系表证实之。 (2)输入串为bcccaadadadb时，该翻译方案的输出是什么？

5

※<习题六>

第六章 程序运行时存储空间组织

单项选择题：

6.1.1．过程的DISPLAY表中记录了______＿。 a.过程的连接数据 b.过程的嵌套层次 c.过程的返回地址 d.过程的入口地址 6.1.2．过程Pi调用P2时，连接数据不包含______。

a.嵌套层次显示表 b.老SP c.返回地址 d.全局DISPLAY地址 6.1.3．程序所需的数据空间在程序运行前就可确定，称为_____＿管理技术。

（陕西省1997年自考题） a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 6.1.4.堆式动态分配申请和释放存储空间遵守_______＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 6.1.5．静态分配允许程序出现_______。

a.递归过程 b.可变体积的数据项目 c.静态变量 d.待定性质的名字 6.1.6.活动记录中的连接数据不包含____。

a.老SP b.返回地址 c.全局DISPLAY地址 d.形式单元

6.1.7. Fortran语言采用静态分配策略时，任一活动的活动记录中不包括____＿。

（西安电子科大2000年研究生试题） a.控制链 b.机器状态 c.返回地址 d.访问链 6.1.8．在编译方法中，动态存储分配的含义是_______。

a.在运行阶段对源程序中的数组、变量、参数等进行分配 b.在编译阶段对源程序中的数组、变量、参数等进行分配

c.在编译阶段对源程序中的数组、变量、参数等进行分配，在运行时这些数组、变 量、参数的地址可根据需要改变 d.以上都不正确

6.1.9.在编译时有传名功能的高级程序语言是______。 a. Fortran b. Basic c. Pascal d. ALGOL

6.1.10.栈式动态分配与管理在过程返回时应做的工作有____＿。 a.保护SP b.恢复SP c.保护TOP d.恢复TOP

多项选择题：

6.2.1. 如果活动记录中没有DISPLAY表，则说明_____＿。（陕西省1998年自考题） a.程序中不允许有递归定义的过程 b.程序中不允许有嵌套定义的过程

c.程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程 d．程序中允许有递归定义的过程，也允许有嵌套定义的过程 e.程序中不允许有嵌套定义的过程，但可以有递归定义的过程 6.2.2. 动态存储分配可采用的分配方案有____＿。 a.队式存储分配 b.栈式存储分配 c.链式存储分配 d.堆式存储分配 e.线性存储分配

6.2.3．下面___＿需要在运行阶段分配存储空间。 a.数组 b.指针变量 c.动态数组· d.静态变量 e.动态变量