编译原理期末考试试卷以及答案.pdf

《编译原理期末考试试卷以及答案.pdf》由会员分享，可在线阅读，更多相关《编译原理期末考试试卷以及答案.pdf（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一.填 空 题（每 空 2 分，共 20分）1.不 同 的 编 译 程 序 关 于 数 据 空 间 的 存 储 分 配 策 略 可 能 不 同，但 大 部 分 编 译 中 采 用 的 方 案 有 两 种：静 态 存 储 分 配 方 案 和 动 态 存 储 分 配 方 案，而 后 者 又 分 为（1）和（2）o2.规 范 规 约 是 最（3）规 约。3.编 译 程 序 的 工 作 过 程 一 般 划 分 为 5 个 阶 段：词 法 分 析、（4）、语 义 分 析 与 中 间 代 码 生 成，代 码 优 化 及（5）o 另 外 还 有（6）和 出 错 处 理。4.表 达 式 x+y*z/（a+b）

2、的 后 缀 式 为（7）。5.文 法 符 号 的 属 性 有 综 合 属 性 和（8）o6.假 设 二 位 数 组 按 行 存 放,而 且 每 个 元 素 占 用 一 个 存 储 单 元，则 数 组 a1.15,1.20J某 个 元 素 ai,j的 地 址 计 算 公 式 为 包。7.局 部 优 化 是 局 限 于 一 个 工 皿 范 围 内 的 一 种 优 化。得 分 二.选 择 题（1-6为 单 选 题，7-8为 多 选 题，每 问 2 分，共 20分）1.一 个 上 下 文 无 关 文 法 G 包 括 四 个 组 成 部 分：一 组 终 结 符，一 组 非 终 结 符，一 个（），以 及

3、 一 组（）。A.字 符 串 B.产 生 式 C.开 始 符 号 D.文 法 2.程 序 的 基 本 块 是 指（)oA.一 个 子 程 序 B.一 个 仅 有 一 个 入 口 和 一 个 出 口 的 语 句C.一 个 没 有 嵌 套 的 程 序 段 D.一 组 顺 序 执 行 的 程 序 段，仅 有 一 个 入 口 和 一 个 出 口 3.高 级 语 言 编 译 程 序 常 用 的 语 法 分 析 方 法 中，递 归 下 降 分 析 法 属 于（）分 析 方 法。A.自 左 向 右 B.自 顶 向 下 C.自 底 向 上 D.自 右 向 左 4.在 通 常 的 语 法 分 析 方 法 中，（

4、）特 别 适 用 于 表 达 式 的 分 析。A.算 符 优 先 分 析 法 B.LR分 析 法 C.递 归 下 降 分 析 法 D.L L（1）分 析 法 5.经 过 编 译 所 得 到 的 目 标 程 序 是（）。A.四 元 式 序 列 B.间 接 三 元 式 序 列 C.二 元 式 序 列 D.机 器 语 言 程 序 或 汇 编 语 言 程 序 6.一 个 文 法 所 描 述 的 语 言 是（）；描 述 一 个 语 言 的 文 法 是（）（,A.唯 一 的 B.不 唯 一 的 C.可 能 唯 一，也 可 能 不 唯 一 7.如 果 在 文 法 G 中 存 在 一 个 句 子，当 其 满

5、足 下 列 条 件（）之 一 时，则 称 该 文 法 是 二 义 文 法。A.其 最 左 推 导 和 最 右 推 导 相 同 B.该 句 子 有 两 个 不 同 的 最 左 推 导 C.该 句 子 有 两 个 不 同 的 最 右 推 导 D.该 句 子 有 两 棵 不 同 的 语 法 树E.该 句 子 对 应 的 语 法 树 唯 一 8.下 面()语 法 制 导 翻 译 中，采 用 拉 链 一 回 填 技 术。A.赋 值 语 句 B.布 尔 表 达 式 的 计 算 C.条 件 语 句 D.循 环 语 句 得 分 三.解 答 题(共 60分)1.(共 15分)已 知 文 法 GE:E-*ETE|

6、(E)|iT-*|+(1)将 文 法 G 改 造 成 LL(1)文 法；(5分)(2)构 造 文 法 G 中 每 个 非 终 结 符 的 FIRST集 合 及 FOLLOW集 合；(5分)(3)构 造 LL(1)分 析 表。(5分)2.(共 12 分)给 定 文 法 GS：S-S(S)|(1)给 出 句 子()()()()的 规 范 推 导 过 程；(4分)(2)指 出 每 步 推 导 所 得 句 型 的 句 柄；(4分)(3)画 出 该 句 子 的 语 法 推 导 树。(4分)3.(共 8 分)在 一 个 移 入-规 约 分 析 过 程 中 采 用 以 下 的 语 法 制 导 翻 译 模 式

7、，在 按 一 个 产 生 式 规 约 时，立 即 执 行 括 号 中 的 动 作。A-*aB print“0”；A*c print“1”；BAb print“2”；(1)当 分 析 器 的 输 入 为 a a c b b时-，打 印 的 字 符 串 是 什 么？(3 分)(2)写 出 分 析 过 程。(5 分)4.(10 分)翻 译 循 环 语 句 while(ad)then x:=y+z。要 求：给 出 加 注 释 的 分 析 树 及 四 元 式 序 列。参 考 以 下 部 分 翻 译 模 式：(1)S f if E then M Si backpatch(E.truelist,M.quad

8、);S.nextlist:=merge(E.falselist,Si.nextlist)(2)S-*while M i E do M 2 sl backpatch(Si.nextlist,Mi,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit(j,-,-,Mi.quad)(3)S f A S.nextlist:=makelist()(4)L-S L.nextlist:=S.nextlistemit(4jrelop.op,4,5id.place,id2.place,O);(5)M-*M.quad:=nextquad

9、(6)E-id i relop id2 E.truelist:=makelist(nextquad);e.falselistmakelist(nextquad+1);emitCj,-,-。)(7)S-L:二 E emit(:=,E.place,-,L-place)(8)E-E1+E2 E.place:=newtemp;emit(+,Ei.place,E2.place,E.place,)5.（共 15分）设 有 表 格 构 造 文 法 GS：S-a|A|（T）T-*T,S|S（1）计 算 文 法 GS的 FIRSTVT集 和 LASTVT集。（5 分）构 造 GS的 优 先 关 系 表，并 判

10、断 GS是 否 为 算 符 优 先 文 法。（5 分）计 算 GS的 优 先 函 数。（5 分）得 分 二.单 项 选 择 题（每 题 2 分，共 10分）1.设 有 文 法 GI：I-Il|I0|Ia|Ic|a|b|c下 列 符 号 串 中 是 该 文 法 句 子 的 有（)0 abO aOcOl aaa bclO可 选 项 有:A.B.C.D.2.程 序 的 基 本 块 是 指（）。A.一 个 子 程 序 B.一 个 仅 有 一 个 入 口 和 一 个 出 口 的 语 句 C.一 个 没 有 嵌 套 的 程 序 段 D.一 组 顺 序 执 行 的 程 序 段，仅 有 一 个 入 口 和 一

11、 个 出 口 3.高 级 语 言 编 译 程 序 常 用 的 语 法 分 析 方 法 中，递 归 下 降 分 析 法 属 于（）分 析 方 法。A.自 左 向 右 B.自 顶 向 下 C.自 底 向 上 D.自 右 向 左 4.经 过 编 译 所 得 到 的 目 标 程 序 是（）oA.四 元 式 序 列 B.间 接 三 元 式 序 列 C.二 元 式 序 列 D.机 器 语 言 程 序 或 汇 编 语 言 程 序5.运 行 阶 段 的 存 储 组 织 与 管 理 的 目 的 是（）0 提 高 编 译 程 序 的 运 行 速 度 节 省 编 译 程 序 的 存 储 空 间 提 高 目 标 程

12、序 的 运 行 速 度 为 运 行 阶 段 的 存 储 分 配 做 准 备 可 选 项 有：A.B.C.D.得 分 2.（10分）已 知 文 法 GS:S-*aBc|bABA f aAb|bB-b|E（4）构 造 其 LL（1）分 析 表;（5）判 断 符 号 串 baabbb是 否 为 该 文 法 的 句 子（写 出 含 有 符 号 栈、输 入 串 和 规 则 的 分 析 过 程）。3.（10分）已 知 文 法 G 为：E f E+T|TTT*P|PP-i(1)构 造 该 文 法 的 优 先 关 系 表(不 考 虑 语 句 括 号#),并 指 出 此 文 法 是 否 为 算 符 优 先 文

13、法。(2)构 造 文 法 G 的 优 先 函 数 表。4.(8 分)在 一 个 移 入-规 约 分 析 过 程 中 采 用 以 下 的 语 法 制 导 翻 译 模 式，在 按 一 个 产 生 式 规 约 时，立 即 执 行 括 号 中 的 动 作。S-bAb print T A-(B print“2”A-*a print 3”B-*Aa)print 4(3)当 输 入 序 列 为 b(aa)a)a)b时，打 印 的 字 符 串 是 什 么？(4)写 出 移 入-规 约 分 析 过 程。5.(12 分)翻 译 循 环 语 句 while(xy)do if(a=b)then x:=2*y+a。要

14、求：给 出 加 注 释 的 分 析 树、三 地 址 码 序 列 及 相 应 的 四 元 式 序 列。参 考 以 下 部 分 翻 译 模 式：(1)S-*if E then M S)backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,Si.nextlist)(2)while M i E do M 2 Si backpatch(S 1.nextlist,Mi,.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselistemit Mi.quad)S f A S.nextlis

15、t:=makelist()(4)L f S L.nextlist:=S.nextlist)M f e M.quad:=nextquad)(6)E-*idi relop idi E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+l);emitCj,relop.op,idi.place,id2.place,0);(7)S f L:=E emit(:=,E.place,-,L.place)(8)EEI+E2 E.place:=newtemp;emit(+,Ei.place,E2.place,E-place,)6.(8 分)Ge

16、nerate assembly code for the following sequence assuming that x,yand z are in m e m o r y locations(noticing only two registers RI and R2).S=01=0LI:if xy goto L2Z=s+aiI=i+1Goto LIL2:7.(6 分)Give out the all basic blocks of the following program fragment andconstruct the relevant flow graph(DAG).read

17、CA=0B=1L4:A=A+BifBC goto L2B=B+1goto L4L2:write A8.（8 分）Translate the assignment statement bi=b*c-b*d into（1）A syntax tree.（2）Three address instructions.答 案：栈 式 动 态 存 储 分 配 堆 式 动 态 存 储 分 配(3)左(4)语 法 分 析 目 标 代 码 生 成(6)表 格 管 理 xyz*ab+/+(8)继 承 属 性(9)a+(i-l)*20+j-l(10)基 本 块 一、选 择 题(每 问 2 分，共 2 0分)l.C B

18、2.D 3.B 4.A 5.D 6.A,C7.BCD,选 对 一 个 得 1分 且 不 超 过 满 分，选 错 一 个 扣 一 分，扣 完 为 止。8.B C D,选 对 一 个 得 1分 且 不 超 过 满 分，选 错 一 个 扣 一 分，扣 完 为 止。二、解 答 题 1.(1)文 法 存 在 左 递 归，消 除 左 递 归 后 的 文 法 为：E f(E)E E(2 分)E TEE|(2 分)T-*|+(1 分)(2)(5分)没 考 虑#扣 0.5分，其 它 错 或 少 写 一 个 扣 0.5分 FIRST(E)=(,i FIRST(E,)=*,+,FIRST(T)=*,+FOLLOW(

19、E)=),*,+,#FOWLLOW(E,尸),*,+,#FOLLOW(T)=(,i(3)每 错 一 个 扣 0.5分，全 错 或 不 写 不 得 分，扣 完 为 止，共 5 分 2.(1)规 范 推 导 过 程 如 下。写 错 推 导 符 号 扣 0.5分，错 写 或 少 写 一 步 推 导 扣 0.5分，扣 完 为 止，最 左 推 导 扣 2分，共 4 分。S n 咨 n S()n S(S)()n S(g)()=S(S)()()=S(S(S)()()n S(S()()()n S(S 0)()()=S(S()()()()n S(3)()()()=()()()()()i*+#E E 一(E)EE

20、-iE，E，E fE T E E E，-eE 一 TEEE,一 E ET*T-+(2)(1)中 加 下 划 线 的 部 分 是 句 柄，标 识 如(D o 每 少 写 一 个 句 柄 扣 0.5分,扣 完 为 止，共 4 分。(3)每 少 写 步 扣 0.5分，扣 完 为 止，共 4 分。d Iq r q、/I3.(1)打 印 的 字 符 串 是：12020(错 一 个 扣 0.5分，共 3分)(2)归 约 过 程 中 错 一 步 扣 0.5分，扣 完 为 止。(共 5分)4.(1)每 少 写 一 步 扣 0.5分，扣 完 为 止，共 5分。(2)少 写 一 个 四 元 式 扣 0.5分，全

21、错 或 不 写 不 得 分，回 填 错 误 扣 0.5分，共 5分。四 元 式 序 列 为:100(j,c,J,104)103(；,1 0 6)104(+,y,z,n)1O5(：=,T1,_,X)106(j,_,100)5.(1)少 写 一 个 扣 1分，全 错 或 不 写 不 得 分，共 5分。FIRSTVT(S)=a,八,(FIRSTVT(T)=,a,A,(LASTVT(S)=a,A,)LASTVT(T)=a,A,),)优 先 表 如 下。每 错 一 个 扣 0.5分，全 错 或 不 写 不 得 分，扣 完 为 止，共 3分 文 法 GS没 有 两 个 非 终 结 符 相 邻 的 情 况，

22、且 其 优 先 表 中 任 一 对 终 结 符 之 间 最 多 满 足、三 种 关 系 中 的 一 种，因 此 是 GS算 符 优 先 文 法。(2 分)可 以 不 考 虑 终 结 符 或 者 a A()#A A(z#z(3)优 先 函 数。可 以 不 考 虑 终 结 符 每 错 一 个 扣 0.5分，全 错 或 不 写 不 得 分，扣 完 为 止，共 5 分。a A()#f 6 6 2 6 6 2manager)2 继 承 属 性(inherited attribute)3 局 部 优 化(local optimization)4 四 元 式(quatriple)5E+*()id四、单 项

23、选 择 题(每 题 2分，共 10分)l.B 2.D 3.B 4.D 5.C五、解 答 题(共 70分)1.(1)L(G)=0mlm|M l 共 2 分，2 写 成 扣 1 分(2)S=0Sl=00Sll=000111,共 3 分，=写 成-扣 1 分(3)共 3分，错 处 扣 0.5分，扣 完 为 止 2.(1)空 白 表 格 也 可 以 填 写“错 误”字 样，共 4 分，错 一 个 扣 0.5分，扣 完 为 止(2)共 6分，其 中 判 断“baabbb是 该 文 法 句 子”为 2 分，其 他 错 一 个 扣 0.5a b c$(#)S S-aB c S-bA BA A f aAb A

24、-*bB B-b B f E B f 分，扣 完 为 止 符 号 栈 输 入 串 规 则$s baabbb$BAb baabbb$SbAB$BA aabbb$A f aAb$BbAa aabbb$BbA abbb$A f aAb$BbbAa abbb$BbbA bbb$Ab$Bbbb bbb$Bbb bb$B-E$Bb b$b$success$3.(1)共 6 分，其 中 判 断“该 文 法 为 算 符 优 先 文 法”为 2 分，其 他 错 一 个 扣 0.5分，扣 完 为 止+*i+(2)共 4 分，错 一 个 扣 0.5分，扣 完 为 止+*if 2 4 4g1 3 54.(1)3424

25、2421,共 4 分，错 一 个 扣 0.5 分(2)共 4 分，错 一 个 扣 0.5分，扣 完 为 止stack Input string action$b(aa)a)a)b$b(aa)a)a)b$shift$b(aa)a)a)b$abbb$shift$b(aa)a)a)b$bbb$shift$b(aa)a)a)b$bb$shift$b(a a)a)a)b$shift$b(A a)a)a)b$reduce,A a$b(Aa)a)a)b$shift$b(Aa)a)a)b$shift$b(B a)a)b$reduce,B-*Aa)$b(A a)a)b$reduce,A-*(B$b(Aa)a)b

26、$shift$b(Aa)a)b$shift$b(B a)b$reduce,B f Aa)$b(A a)b$reduce,(B$b(Aa)b$shift$b(Aa)b$shift$b(B b$reduce,B-*Aa)$bA b$reduce,A f(B$bAb$shift$S$reduce,S b A b$s$accept5.共 1 2分，其 中 带 注 释 的 分 析 树、三 地 址 码 序 列 和 四 元 式 序 列 分 别 为 4 分,错 一 个 序 列 扣 0.5分，而 错 某 点（某 项）少 于 或 等 于 5 个 扣 0.5分 带 注 释 语 法 树（略）三 地 址 码 序 列 M

27、 l:if(xy)goto M2四 元 式 序 列 100(j,x,y,102)goto M4 101(j-J 0 8)M2:if(a=b)goto M3 102(j=,a,b,104)goto M l 103 0,-,-,100)M3:tl=2*y 104(*,2,y,tl)t2=tl+a 105(+,tl,a,t2)x=t2 106(=,t2,-,x)goto M l 107(j,-,-,100)M4:1086.共 8分，错 一 个 扣 0.5分，扣 完 为 止 LDR1,OSTS,RIST I,RILI:LDR1,XSUB R1,R1,Y(OR SUB R 1,Y)BGTZR1,L2LD

28、 R2,a(Rl)ADD R2,R2,S(OR ADD R2,S)ST Z,R2LDR1,I(从 这 开 始，下 面 的 语 句 中 的 R I也 可 以 全 部 变 成 R2)ADDR1,R1,1(OR INC RI)ST I,RIBRL1L2:7.共 6分，基 本 块 划 分 和 流 图 各 为 3分，错 一 处 扣 1分，扣 完 为 止 8.(1)共 4 分，错 一 项 扣 1分，扣 完 为 止(2)共 4 分，错 一 项 扣 1分，扣 完 为 止 tl=b*ct2=b*dt3=tl-t2t4=i+l(or t4=i)bt4=t3一、判 断 题：1.一 个 上 下 文 无 关 文 法 的

29、 开 始 符，可 以 是 终 结 符 或 非 终 结 符。()2.一 个 句 型 的 直 接 短 语 是 唯 一 的。()3.已 经 证 明 文 法 的 二 义 性 是 可 判 定 的。()4.每 个 基 本 块 可 用 个 DAG 表 示 0()5.每 个 过 程 的 活 动 记 录 的 体 积 在 编 译 时 可 静 态 确 定。()6.2 型 文 法 一 定 是()7.一 个 句 型 一 3 型 文 法 定 句 子)8.算 符 优 先 分 析 法 每 次 都 是 对 句 柄 进 行 归 约。()9.采 用 三 元 式 实 现 三 地 址 代 码 时,不 利 于 对 中 间 代 码 进 行

30、 优 化。()10.编 译 过 程 中，语 法 分 析 器 的 任 务 是 分 析 单 词 是 怎 样 构 成 的。()11.一 个 优 先 表 一 定 存 在 相 应 的 优 先 函 数。()12.目 标 代 码 生 成 时，应 考 虑 如 何 充 分 利 用 计 算 机 的 寄 存 器 的 问 题。()13.递 归 下 降 分 析 法 是 一 种 自 下 而 上 分 析 法。()14.并 不()15.每 个 是 每 个 基 本 块 文 法 都 能 改 写 成 LL 文 法 只 有 一 个 入 口 和 一 个 出 口 O()16.个 LL 文 法 一 定 是 无 二 义 的。()17.逆 波

31、 兰 法 表 示 的 表 达 试 亦 称 前 缀 式 O18.目 标 代 码 生 成 时，应 考 虑 如 何 充 分 利 用 计 算 机 的 寄 存 器 的 问 题。()19.正 规 文 法 产 生 的 语 言 都 可 以 用 上 下 文 无 关 文 法 来 描 述。()20.一 个 优 先 表 一 定 存 在 相 应 的 优 先 函 数。()21.3 型 文 法 一 定 是 2 型 文 法。()22.如 果 一 个 文 法 存 在 某 个 句 子 对 应 两 棵 不 同 的 语 法 树，则 文 法 是 二 义 性 的。()二、填 空 题：1.()称 为 规 范 推 导。2.编 译 过 程 可

32、 分 为()，(),(),()和()五 个 阶 段。3.如 果 一 个 文 法 存 在 某 个 句 子 对 应 两 棵 不 同 的 语 法 树，则 称 这 个 文 法 是()o4.从 功 能 上 说，程 序 语 言 的 语 句 大 体 可 分 为()语 句 和()语 句 两 大 类。5.语 法 分 析 器 的 输 入 是(),其 输 出 是()。6.扫 描 器 的 任 务 是 从()中 识 别 出 一 个 个()。7.符 号 表 中 的 信 息 栏 中 登 记 了 每 个 名 字 的 有 关 的 性 质，如()等 等。8.一 个 过 程 相 应 的 DISPLAY 表 的 内 容 为)o9.一

33、 个 句 型 的 最 左 直 接 短 语 称 为 句 型 的()10.常 用 的 两 种 动 态 存 贮 分 配 办 法 是（）动 态 分 配 和）动 态 分 配。11.一 个 名 字 的 属 性 包 括（）和（）o12.常 用 的 参 数 传 递 方 式 有（），（）和（）o13.根 据 优 化 所 涉 及 的 程 序 范 围，可 将 优 化 分 成 为（）三 个 级 别。14.语 法 分 析 的 方 法 大 致 可 分 为 两 类，一 类 是（）,（）和）分 析 法，另 一 类 是（）分 析 法。15.预 测 分 析 程 序 是 使 用 一 张（的。16.常 用 的 参 数 传 递 方 式

34、 有（）和 一 个（）进 行 联 合 控 制),()和()o17.一 张 转 换 图 只 包 含 有 限 个 状 态,其 中 有 一 个 被 认 为 是（）态;而 且 实 际 上 至 少 要 有 一 个（）态。18.根 据 优 化 所 涉 及 的 程 序 范 围，可 将 优 化 分 成 为（），（）和（）三 个 级 别。19.语 法 分 析 是 依 据 语 言 的（）规 则 进 行。中 间 代 码 产 生 是 依 据 语 言 的（）规 则 进 行 的。20.一 个 句 型 的 最 左 直 接 短 语 称 为 句 型 的（）。21.一 个 文 法 G,若 它 的 预 测 分 析 表 M 不 含

35、多 重 定 义，则 该 文 法 是（）文 法。22.对 于 数 据 空 间 的 存 贮 分 配，FORTRAN采 用（）策 略，PASCAL采 用（）策 略。23.如 果 一 个 文 法 存 在 某 个 句 子 对 应 两 棵 不 同 的 语 法 树，则 称 这 个 文 法 是（）。24.最 右 推 导 亦 称 为（），由 此 得 到 的 句 型 称 为（）句 型。25.语 法 分 析 的 方 法 大 致 可 分 为 两 类，一 类 是（）分 析 法，另 一 类 是（）分 析 法。26.对 于 文 法 G,仅 含 终 结 符 号 的 句 型 称 为（)27.所 谓 自 上（28.语 法 分 析

36、 器 的 输 入 是（29.局 限 于 基 本 块 范 围 的 优 化 称 30.预 测 分 析 程 序 是 使 用 一 张（的。31.2型 文 法 又 称 为（32.每 条 指 令 的 执 行 代 价 定 义 为 33.算 符 优 先 分 析 法 每 次 都 是 对 而 下 分 析 以）o）,其 输 出 是（）。（）。）和 一 个（）文 法；3 型 文 法 又 称 为（）进 行 归 约。;是 指 进 行 联 合 控 制）文 法。）。三、名 词 解 释 题:1.局 部 优 化 2.二 义 性 文 法 3.DISPLAY 表 4.词 法 分 析 器 5.最 左 推 导 6.语 法 7.文 法 8

37、.基 本 块 9.语 法 制 导 翻 译 10.短 语 11.待 用 信 息 12.规 范 句 型 13.扫 描 器 14.超 前 搜 索 15.句 柄16.语 法 制 导 翻 译 17.规 范 句 型 18.素 短 语 19.语 法 2 C L待 用 信 息 21.语 义 四、简 答 题：1.写 一 个 文 法 G,使 其 语 言 为 不 以。开 头 的 偶 数 集。2.已 知 文 法 G(S)及 相 应 翻 译 方 案 S-aA b print“1”S-a print“2”A-A S print“3”A-c print“4”输 入 acab,输 出 是 什 么？3.已 知 文 法 G(S)

38、S-bA aA f(B|aB f Aa)写 出 句 子 b(aa)b的 规 范 归 约 过 程。4.考 虑 下 面 的 程 序：procedure p(x,y,z)；beginy:=x+y;z:=z*z;endbeginA-2;B:=A*2;P(A,A,B);Print A,Bend.试 问，若 参 数 传 递 的 方 式 分 别 采 用 传 地 址 和 传 值 时，程 序 执 行 后 输 出 A,B的 值 是 什 么？5.文 法 G(S)S-dA BA f aA|aB fB b|描 述 的 语 言 是 什 么？6.证 明 文 法 G(S)S-*SaS|是 二 义 性 的。7.已 知 文 法

39、G(S)SBAA f BS|dB-*aA|bS|c的 预 测 分 析 表 如 下 a b c d#s S-B A S-B A S-B AA A-B S A-B S A fB S A-dB B-*aA B-b S B-*c给 出 句 子 adccd的 分 析 过 程。8.写 一 个 文 法 G,使 其 语 言 为 L(G)=a1bmcanbn|1=0,m=l,n=29 已 知 文 法 G(S):S-*a|(T)T-*T,S|S的 优 先 关 系 表 如 下：关 系 a()9a.(.二.请 计 算 出 该 优 先 关 系 表 所 对 应 的 优 先 函 数 表。10.何 谓 优 化？按 所 涉 及

40、 的 程 序 范 围 可 分 为 哪 几 级 优 化？11.目 标 代 码 有 哪 几 种 形 式？生 成 目 标 代 码 时 通 常 应 考 虑 哪 几 个 问 题？12.一 字 母 表 2=a,b,试 写 出 2 上 所 有 以 a 为 首 的 字 组 成 的 正 规 集 相 对 应 的 正 规 式。13.基 本 的 优 化 方 法 有 哪 几 种？14.写 一 个 文 法 G,使 其 语 言 为 L(G)=abncn|n 0 15.考 虑 下 面 的 程 序：procedure p(x,y,z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b,b

41、,a);print aend.试 问，若 参 数 传 递 的 方 式 分 别 采 用 传 地 址 和 传 值 时，程 序 执 行 后 输 出 a 的 值 是 什 么？16.写 出 表 达 式 a+b*(c-d)/e的 逆 波 兰 式 和 三 元 序 列。17.证 明 文 法 G(A)A-*AA|(A)|E是 二 义 性 的。18.令 2=a,b,则 正 规 式 a*b|b*a表 示 的 正 规 集 是 什 么？19.何 谓 DISPLAY表？其 作 用 是 什 么？20.考 虑 下 面 的 程 序：procedure p(x,y,z)；beginy:=y+2;z:=z+x;endbegina:

42、=5;b:=2;p(a+b,a-b,a);print aend.试 问，若 参 数 传 递 的 方 式 分 别 采 用 传 地 址 和 传 值 时，程 序 执 行 后 输 出 a 的 值 是 什 么？21.写 一 个 文 法 G,使 其 语 言 为 L(G尸 值 叼 的 n0为 奇 数，m0为 偶 数 22.写 出 表 达 式 a:=(b+c)*e+(b+c)/f的 逆 波 兰 式 和 三 元 序 列。23.一 个 文 法 G 别 是 LL(1)文 法 的 充 要 条 件 是 什 么？24.已 知 文 法 GSS f S*aF|aF|*aFFf+aF|+a消 除 文 法 左 递 归 和 提 公

43、 共 左 因 子。25.符 号 表 的 作 用 是 什 么？符 号 表 查 找 和 整 理 技 术 有 哪 几 种？五、计 算 题：1.设 文 法 G(S):S一 人 I a|T-*T,S|S 消 除 左 递 归；(2)构 造 相 应 的 FIRST和 F O L L O W 集 合；构 造 预 测 分 析 表 2.语 句 if E then S(1)改 写 文 法，使 之 适 合 语 法 制 导 翻 译；(2)写 出 改 写 后 产 生 式 的 语 义 动 作。3.设 文 法 G(S)：S-(T)|aT f T+S|S(1)计 算 FIRSTVT 和 LASTVT；(2)构 造 优 先 关

44、系 表。4.设 某 语 言 的 for语 句 的 形 式 为for i:=E()to E do S其 语 义 解 释 为 i:=E(1)LIMIT:=E(2)again:if i=LIMIT thenBeginS;i:=i+1goto againEnd;(1)写 出 适 合 语 法 制 导 翻 译 的 产 生 式;(2)写 出 每 个 产 生 式 对 应 的 语 义 动 作。5.把 语 句 while a0 then a:=a+lelse a:=a*3-l;翻 译 成 四 元 式 序 列。6.设 有 基 本 块 D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ

45、:=T*QK:=G*5L:=K+JM:=L假 设 基 本 块 出 口 时 只 有 M 还 被 引 用，请 写 出 优 化 后 的 四 元 序 列。7.已 知 文 法 G(S)S f a|八|T f T,S|S(1)给 出 句 子(a,(a,a)的 最 左 推 导；给 出 句 型(T,S),a)的 短 语，直 接 短 语，句 柄。8.对 于 C 语 言 do S while E 语 句(1)改 写 文 法，使 之 适 合 语 法 制 导 翻 译；(2)写 出 改 写 后 产 生 式 的 语 义 动 作。9.已 知 文 法 G(S)S-*aAcBeA-Ab|bBd(1)给 出 句 子 abbcde

46、的 最 左 推 导 及 画 出 语 法 树；(2)给 出 句 型 aAbcde的 短 语、素 短 语。10.设 文 法 G(S):S-(T)|aS|aT-*T,S|S 消 除 左 递 归 和 提 公 共 左 因 子；构 造 相 应 的 FIRST和 FOLLOW集 合；构 造 预 测 分 析 表。11.把 语 句 ifX0 V Y0then while X0 do X:=A*3else Y:=B+3;翻 译 成 四 元 式 序 列。12.已 知 文 法 G(S)E-E+T|TTT*F|FF-(E)|i(1)给 出 句 型(i+i)*i+i的 最 左 推 导 及 画 出 语 法 树；(2)给 出

47、 句 型(E+T)*i+F的 短 语，素 短 语 和 最 左 素 短 语。13.设 文 法 G(S)：S-*T|SV TT f U|TAUU f i|-U(1)计 算 FIRSTVT 和 LASTVT；(2)构 造 优 先 关 系 表。参 考 答 案 一、是 非 题：l.X 2.x 3.X 4.V 5.V 6.x 7.X 8.X 9.V 10.X 11.X12.V 13.X 14.V 15.V 16.V 17.X 18.V 19.V 20.X 21.J 22.V二、填 空 题：1.（最 右 推 导）2.（词 法 分 析），（语 法 分 析），（中 间 代 码 生 成），（代 码 优 化），（目

48、 标 代 码 生 成）3.（二 义 性 的）4.（执 行 性），（说 明 性）5.（单 词 符 号），（语 法 单 位）。6.（源 程 序），（单 词 符 号）7.（类 型、种 属、所 占 单 元 大 小、地 址）8.（现 行 活 动 记 录 地 址 和 所 有 外 层 最 新 活 动 记 录 的 地 址）9.（句 柄）10.（栈 式），（堆 式）11.（类 型），（作 用 域）12.（传 地 址），（传 值），（传 名）13.（局 部 优 化），（循 环 优 化），（全 局 优 化）14.（自 上 而 下），（自 下 而 上）15.（分 析 表），（符 号 栈）16.（传 地 址），（传 值

49、），（传 名）17.（初），（终）18.（局 部 优 化），（循 环 优 化），（全 局 优 化）19.（语 法），（语 义）20.（句 柄）第。页 共 4 3 页21.（LL（1）文 法）22.（静 态），（动 态）23.（二 义 性 文 法）24.（规 范 推 导），（规 范）25.（自 上 而 下），（自 下 而 上）26.（句 子）27.（从 开 始 符 号 出 发，向 下 推 导，推 出 句 子）28.（单 词 符 号），（语 法 单 位）29.（局 部 优 化）30.（分 析 表），（符 号 栈）31.（上 下 文 无 关 文 法），（正 规）32.（指 令 访 问 主 存 次 数

50、 加 1）33.（最 左 素 短 语）三、名 词 解 释 题：1.局 部 优 化 局 限 于 基 本 块 范 围 的 优 化 称。2.二 义 性 文 法 一 如 果 一 个 文 法 存 在 某 个 句 子 对 应 两 棵 不 同 的 语 法 树，则 称 这 个 文 法 是 二 义 性 文 法。3.DISPLAY表 一 过 程 的 嵌 套 层 次 显 示 表，记 录 该 过 程 的 各 外 层 过 程 的 最 新 活 动 记 录 的 起 始 地 址。4.词 法 分 析 器-执 行 词 法 分 析 的 程 序。5.最 左 推 导 任 何 一 步 a=B都 是 对 a 中 的 最 右 非 终 结 符