编译原理样题3

*编译原理 样题

一 选择题

【 】1．____型文法也称为正规文法。

[A] 0 [B] 1 [C] 2 [D] 3 【 】2．____文法不是LL(1)的。

[A] 递归 [B] 右递归 [C] 2型 [D] 含有公共左因子的

【 】3． 文法E→E+E|E*E|i的句子i*i+i*i的不同语法分析树的总数为______。 [A]1 [B]3 [C]5 [D]7 【 】4．四元式之间的联系是通过 实现。

[A]临时变量 [B]指示器 [C]符号表 [D]程序变量 【 】5．同心集合并可能会产生的新冲突为 。

[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约 【 】6．代码优化时所依据的是 。

[A]语法规则 [B]词法规则 [C]等价变换规则 [D]语义规则

【 】7．表达式a-(-b)*c的逆波兰表示为 。

[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* （注：@为单目减运算符）

【 】8．过程的DISPLAY表记录了 。

[A]过程的连接数据 [B]过程的嵌套层次 [C]过程的返回地址 [D]过程的入口地址

二 填空题

1．编译过程的六个阶段为：词法分析、 、语义分析、 代码优化和目标代码生成。 2．词法分析阶段的任务式从左到右扫描 ，从而逐个识别 。 3．对于文法G1和G2，若有 ，则称文法G1和G2是等价的。

4．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是 ，最左素短语是 。

所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。所谓最左素短语是指处于句型最左边的那个素短语。如，P*P和i是句型P*P+i的素短语，而P*P是它的最左素短语。

- 1 -

5．最右推导的逆过程称为 ，也称为 。

6．规范规约中的可规约串是 ，算符优先分析中的可规约串是 。 7．（A∨ B）∧（C∨ ?D∧ E） 的逆波兰式是 。

8．在属性文法中文法符号的两种属性分别称为 和 。

9．符号表的每一项是由名字栏和 两个栏目组成。在目标代码生成阶段，符号表

是 的依据。 10．一个过程的DISPLAY表的内容是它的 的DISPLAY表的内容加上 。

三 有穷自动机M接受字母表?＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右

边。构造一个最小的DFA M及和M等价的正规式。 四 证明正规式(ab)*a 与正规式a(ba)*等价 （用构造他们的最小的DFA方法）。 五 写一个文法，使其语言是：

L ＝ { 1n0m1m0n | m,n≥0 }

六 对文法G[S]

S → aSb | P

P → bPc | bQc Q → Qa | a

(1) 它是否是算符优先文法？请构造算符优先关系表

(2) 文法G[S]消除左递归、提取左公因子后是否是LL（1）文法？请证实。 七 已知文法G为:

（0） S′→ S （1） S → aAd （2） S → bAc （3） S → aec （4） S → bed （5） A → e

试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。 八 已知源程序如下： prod:=0; i:=1;

while i≤20 do begin

prod:=prod+a[i]*b[i]; i:=i+1

end;

试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。

- 2 -

九 设有以下程序段

procedure P(x,y,z) begin

Y:=y*3; Z:=X+z; end; begin

a:=5; b:=2; p(a*b,a,a); print(a); end

若参数传递的方法分别为（1）传值、（2）传地址、（3）传名，试问结果分别什么？ 十 对以下文法，请写出关于括号嵌套层数的属性文法。(为S,L引入属性h,用来记录输出配对的括号个数)

文法规则 S→(T) S→i T→T,S T→S 语 义 规 则 十一 对PL/0语言的while语句 while 条件B DO 语句S 的编译程序，

请在空缺处填空，完成该语句的编译算法： switch (SYM) { ……

case WHILESYM:

;

GetSym();

CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX); ;

GEN(JPC,0,0); if (SYM==DOSYM) ; else Error(18);

STATEMENT(FSYS,LEV,TX); GEN(JMP,0,CX1);

； break;

…… }

- 3 -

编译原理样题参考答案

一 选择题（12分）

1. D 2. D 3. B 4. A 5. D 6. C 7. B 8. B

二 填空题（8分）

1. 语法分析 中间代码生成 2. 源程序 单词

3. L(G1)=L(G2) （或 G1和G2的语言相同） 4. T T*F 5. 规范归约 最左归约 6. 句柄 最左素短语 7. ＡＢ∨ＣＤ?Ｅ∧∨∧

8. 继承属性 综合属性（次序可换） 9. 信息栏 地址分配

10. 直接外层 本过程的SP的地址 三 最小的DFA M如下图所示：

*

0 1 S 0 **

S1 与M等价的正规式为：(0 | (10) )

四 正规式（ab）* a对应的NFA如图：

2

b a

X ε 1 a Y

a b

ε a X Y 1

这两个正规式最终都可得到最简的DFA如图所示：

b

1 0

a - 4 -

正规式a(ba)* 对应的NFA如图： 2

所以这两个正规式等价。 五 文法G：S → 1S0 | A

A → 0A1 | ε

六 1.求出G[S]的FIRSTVT集和LASTVT集：

FIERSTVT（S）={a,b} LASTBVT（S）={b,c} FIERSTVT(P)={b} FIERSTVT(Q)={a}

LASTBVT（P）={c} LASTBVT（Q）={a}

构造优先关系表为：

a b c a < > < > b < > c > > 由于在优先关系中同时出现了aa以及bb，所以该文法不是算符优先文法。

2. 消除左递归和提取左公因子后的文法为：

S → aSb | P P → bP’ P’→ Pc |Qc Q → aQ’ Q’→ aQ’|ε

求具有相同左部的两个产生式的Select集的交集：

Select(S→aSb)∩Select(S→P) = {a}∩First(P) = {a}∩{b} = Ф Select(P’→Pc)∩Select(P’→Qc) = First(P)∩First(Q)={b}∩{a}= Ф Select(Q’→aQ’)∩Select(Q’→ε) = {a}∩Follow(Q) = {a}∩{c} = Ф 所以修改后的文法是LL（1）文法。

七 LR(1)项目集和可归前缀图如下:

S I0: S′→· S , # S→· aAd , # S→ · bAc , # S→ ·aec , # S→ · bed , # I1：S′→S · , # A e a d I4：S→aA· d , # I5：S→ae· c , #I8：S→aAd · , # I2： S→a · Ad , # S→a · ec , # A→· e , d c A→e · , d I9：S→aec · , # b I3: S→b · Ac , # S→b · ed , # A e I10： I6: S→bA·c,# , # c S→bAc · A→· e , c I7：S→be · d , # A→e · , c d I11： S→bed · , # - 5 -

构造LR(1)分析表 如下：

0 1 2 3 4 5 6 7 8

9

状态

action a S2

b S3

S9 S10 r5

S11

c

S8 r5 d

e S5 S7

r1 r3# acc

goto S

A

1

10

11

r2 r4

八 四元式序列

100 prode:=0 101 i:=1

102 If i≤20 goto 104 103 goto 114 104 T1:=4*I 105 T2:=A-4 106 T3:=T2[T1] 107 T4:=4*I 108 T5:=B-4 109 T6:=T5[T4] 110 T7:=T3*T6

111 prod:=prod+T7 112 i:=i+1 113 goto 102 114

- 6 -

十 （1）传值 5； （2）传地址 25； （3）传名 45

十一

文法规则 S→(T) S→i T→T,S T→S 十一 CX1=CX CX2=CX GetSym() CODE[CX2].A=CX

语 义 规 则 {S.h:=T.h+1; } {s.h:=0} {T.h:=T.h+S.h;} T.h:= S.h;} - 7 -

本文来源：https://www.bwwdw.com/article/jjjv.html