编译原理(清华大学 - 张素琴)复习例题(2)

构造简单优先关系表。该文法是否是简单优先文法? 解:简单优先关系矩阵如下: S a b P Q c S = a < > < = b = < < > > > P < = Q = < c > = = > 由于矩阵中有元素存在多种优先关系,故不是简单优先文法。

13.考虑文法 G: S → AS | b

A → SA | a

(1)构造文法的可归前缀图(活前缀的DFA); (2)判断文法是否是LR(0)文法,并说明理由。 解:(1)可归前缀图

I1:S’?S. A?S.A A?.SA A?.a S?.AS SSI5:A?S.A A?.SA A?.a S?.AS SAbAS?.b a S?.b aaI0:S’?.S S?.AS S?.b A?.SA A?.a I2:A?a. bbaI7:A?SA. S?A.S S?.AS S?.b A?.SA A?.a SAAI3:S?b. ababSbAI4:S?A.S S?.AS AI6:S?AS. A?S.A A?.SA A?.a S?.AS S?.b S?.b A?.SA A?.a S

(2)因为存在冲突,所以不是LR(0)文法。

14.文法G及其LR分析表如下,请给出对串dada#的分析过程。

G: S → VdB ①

V → e ② V → ε ③ B → a ④

- 6 -

B → Bda ⑤ B → ε ⑥

状态 0 1 2 3 4 5 6 7 8 ACTION d S4 r2 r6 r4 S7 r5 e a S8 # r4 r1 r5 S 1 r3 S3 GOTO B 6 V 2 acc S5 r6 解:对输入串dada#的分析过程 步骤 1 2 3 4 5 6 7 8 9 状态栈 0 02 024 0245 0246 02467 024678 0246 01 符号栈 剩余输入符号 # #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S dada# dada# ada# da# da# a# # # # 动作 用V →ε归约 移进 移进 用B →a归约 移进 移进 用B →Bda 归约 用S →VdB 归约 接受 15.对传值、传地址和传名3种参数传递方法分别写出下列

程序的输出:

void p(int x, int y, int z) {

y *= 3; z += x; }

void main() {

int a=5, b=2; p(a*b,a,a);

printf(“%d\\n”, a); }

这些参数传递机制如何实现? 解:(1)传值 5; (2)传地址 25; (3)传名 45 (参数传递机制,略)

16.将下面程序划分为基本块,并画出其程序流图。

- 7 -

b := 1 b := 2

if w <= x goto L2 e := b goto L2 L1:goto L3 L2:c := 3 b := 4 c := 6

L3:if y <= z goto L4 halt

L4:g := g + 1 h := 8 goto L1

解:(1)基本块: b := 1 b := 2 if w <= x goto L2 e := b goto L2 L1: goto L3 L2: c := 3 b := 4 c := 6 L3: if y <= z goto L4 halt L4: g := g + 1 h := 8 goto L1

(2)程序流图

1 5 6 7

(1) (2) (3)

2 4 (4) (5) (6)

3

(7)

- 8 -

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4