发布时间 : 星期一 文章编译原理（清华大学 - 张素琴）复习例题(2)更新完毕开始阅读ffcdbae8561252d380eb6ea3
L(G)={ ambnc2n | m>=0,n>0 } 并证明文法是LL(1)。 解：文法G（S）：S ? aS | E
E ? bE’
E’? Ecc | cc
Select(S ? aS)∩Select (S ? E)= Ф Select(E’? Ecc)∩Select (E’? cc) =Ф 故文法为LL(1)的
11．将文法G改写成等价的LL(1)文法，并构造预测分析表。
G：S→S*aT|aT|*aT T→+aT|+a （编写递归下降子程序）
解：消除左递归后的文法G’: S→aTS’|*aTS’
S’→*aTS’|ε T→+aT|+a
提取左公因子得文法G’’:S→aTS’|*aTS’
S’→*aTS’|ε T→+aT’ T’→T|ε
Select(S→aTS’)={a} Select(S→*aTS’)={*}
Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}
Select(S’→ε)=Follow(s’)={#}
Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}
Select(T’→T)=First(T) ={+}
Select(T’→ ε)=Follow(T’)={*,#} Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a # S S’Ta, N S’ S’Ta, N T T’ ε, P a #
12．对文法G[S]: S → aSb | P
P → bPc | bQc Q → Qa | a
- 5 -
T’a, N T, P TS’T, N ε, N ε, P ε, P OK （递归下降子程序，略）
构造简单优先关系表。该文法是否是简单优先文法？ 解：简单优先关系矩阵如下： 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 -