《编译原理》复习题
35．文法
S ? A a | b A c | d c | b d a A ? d
造识别活前缀的DFA。请根据这个DFA来判断该文法是不是SLR(1)文法并说明理由。 【解】 S’ S S’
? ? .
S A S a S S ? ? ? .
A a c S A S b S S ? ? ? b . d S A c a S d ? S ? S b ? c S d .d .?
c Follow(S)={#} Follow(A)={a,c}
I4存在冲突且Follow(A)∩{c}={ c} I7存在冲突且Follow(A)∩{a}={ a} 所以不是SLR(1)文法
36．将下图所示的确定有限自动机(DFA)最小化。其中，X为初态，Y为终态。
【解】 １-９ ０-９ ?(其它) 2 3 1 0 38．设有文法G[S]:
S→S*S|S+S|(S)|i
该文法是否为二义文法,并说明理由？
【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。
S S i (1) S S S i + S i S i S * + S i (2) *
aaXb21ba3abYb 【解】 先划分为终态集{Y}和非终态集I={X,1,2,3}
X面对输入符号b时下一状态属于I，而1,2,3面对输入符号b时下一状态属于{Y}，故划分为{X}、{1,2,3}
非终态2和非终态3面对输入符号a的下一状态相同，而1不同，即最简状态{X}、{1}、{2，3}、{Y}。按顺序重新命名为0、1、2、3，则得到最简DFA，
a0ab21abb339．程序的文法如下：
P → D
D → D;D | id : T | proc id; D; S
写一语法制导定义，打印该程序一共声明了多少个id
【解】 属性num表示id个数 P → D print(D.num) D → D(1)；D(2) D.num = D(1).num + D(2).num D → id : T D.num = 1 D → proc id; D(1); S D.num = D(1).num + 1
例：proc id; proc id; id : T; S; S（从语法树分析入手）
（注意：本例只是帮助学生理解题意，不是答案部分）
P D procid ; D ; S procid ; D ; S
37．请画出识别无符号十进制整数的状态转换图
21
id : T 《编译原理》复习题
40．把下列语句翻译为四元式序列（四元式序号 int real id , # D D ? D ? 从1开始）：
while (A > B) if (C > D)
X = Y * Z
else
X = Y + Z 【解】(1) (j>, A, B, 3) (2) (j, _, _, 11) (3) (j>, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X) (7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11)
41.构造下面文法的LL（1）分析表。 G[D]: D ? TL
T ? int | real L ? id R
R ? , id R | ?
【解】FIRST(T)={ int realFOLLOW(T)={ id } FIRST(L)={ id FOLLOW(L)={ #}
FIRST(R)={ , FOLLOW(R)={ #}
FIRST(D)={ int real FOLLOW(D)={#}
因为FIRST(int)∩FIRST(real)=Φ
FIRST(, id R)∩FOLLOW(R)=Φ
所以是LL（1）文法，LL（1）分析表如下：
TL TL T T ? T ? int real L L ? id R R R ? , R ? ? id R 42．给定文法S→aS|bS|a，下面是拓广文法和识别该文法所产生的活前缀的DFA。判断该文法是否是SLR(1)文法：如果是构造其SLR(1)分析表，如果不是请说明理由。
(1)将文法G(S)拓广为G(S’)：
(0)S’→S (1)S→aS (2)S→bS (3)S→a
(2)识别该文法所产生的活前缀的DFA如图1所示。
} } ?}
图1
}
【解】注意到状态I1存在“移进-归纳”冲突，计
算S的FOLLOW集合：
FOLLOW(S)={#}
{a}∩{b}∩FOLLOW(R)=Φ
可以采用SLR冲突消解法，得到如下的SLR分析表。
从分析表可以看出，表中没有冲突项，所以该文法
是SLR(1)文法。
22
《编译原理》复习题
表1 SLR分析表 状态 0 1 2 3 a S1 S1 S1 ACTION b S2 S2 S2 # r3 acc GOTO S 3 4 5 B→.
但该项目中有两个可归约项目：A→. B→.，产生归约-归约冲突，而follow（A）={a，b}，follow（B）={a，b}，有follow（A）∩follow（B）≠Φ，所以使用向前看一个终结符的方法不能解决此冲突，所以该文法不是SLR（1）文法。（3分）
45．现有文法G[S]
S→a|ε|(T) T→T,S|S
4 r1 请给出句子（a,(a,a)）的最左、最右推导，并
指出最右推导中每一个句型的句柄。 5 r2 答：最左推导：S=〉（T）=〉（T，S）=〉（S，
S）=〉（a，S）=〉（a，（T））=〉（a，（T，S））=〉
43．给出表达式-a*b+b*c+d/e的语法树和三元式序
（a，（S，S））=〉（a，（a，S））=〉（a，（a，a））
列。
最右推导：
答：语法树
S=〉（T）=〉（T，S）=〉（T，（T））=〉（T，（T，三元式
S））=〉（T，（T，a））=〉（T，（S，a））=〉（T，（a，
+ a））=〉（S，（a，a））=〉（a，（a，a））
句型的句柄是为加下划线的部分
+ 46．将下图的DFA最小化。
/ * * - a b b c d 0 b 1 a 3 a 2 a b b a 4 e a b b
①（-，a，-） ②（*，①，b） ③（*，b，c） ④（+，②，③） ⑤（/，d，e） ⑥（+，④，⑤） 44．证明下面文法S→AaAb|BbBa A→ε B→ε，是LL（1）文法，但不是SLR（1）文法。
证明：
（1）first（AaAb）={a} first（BbBb）={b} ，
0 1 有first（AaAb）∩first（BbBb）=Φ
b b 所以根据LL（1）文法的定义，该文法是LL（1）a 文法。（2分）
（2）为了构造识别活前缀的DFA，初态集包含如
47．设有如下文法：P→D
下四个项目：S→.AaAb S→.BbBa A→.
23
答：初始划分：II={{0，1，2}，{3，4}}（1分）
（1）考查{0，1，2}，1和2接受a，b后都转向相同的状态，且接受b后转向终态，而0接受b后转向非终态2，所以0与1，2可分，IInew={{0}，{1，2}，{3，4}}(1分)
（2）考查{3，4}，接受a，b后都转向相同的状态，所以3，4不可分。IInew={{0}，{1，2}，{3，4}}（1分）
将1，2合并用1代表，3，4合并用3代表，最终的最小化DFA如下：
a 3 b
《编译原理》复习题
D→D；D|id：T|proc id；D； T→real|integer
给出一个语法制导定义，打印该程序一共声明了多少个id。 答：
48．识别文法G的活前缀的DFA如下图所示，补 文法 语法制导定义 充P→D Print（D.num） 完D→D1；D2 D.num=D1.num+ 成D2.num 状D→id：T D.num=1 态D→proc D.num=D1.num+ Iid；D1； 1 2 和T→real → IT5integer ，然后根据
49．该图构造SLR（1）分析表。 G：(0) P'→P (1) P→aPb (2) P→Q (3) Q→bQc
(4) Q→bSc (5) S→Sa (6) S→a
Follow（P）={b，$} 1分 Follow（Q）={ b，c，$} 1分 Follow（S）={c，a} 1分 SLR（1）分析表： 0 1 2 3 4 5 6 7 8 9 10 11 12 a S2 S2 S6 R6 S12 R5 Action表 b S5 S5 R2 S7 S5 R1 R3 R4 c R6 R3 S8 S11 R4 R5 $ Acc R2 R1 R3 R4 P 1 4 GOTO表 Q 3 3 9 S 10 I0 :P'→.P P→.aPb P→.Q P I1 :P'→P. I2 : :P→a.Pb a P → .aPb P I4 :P→aP.b 49．给出表达式（a+b）*(c+d/e)的语法树和四元式序列。
答:语法树如下： 四元式序列：
* + + / a d e b c P → .Q b I7 :P→aPb. Q → .bQc a Q→.bQc b Q→.bSc Q→.bSc I8 :Q→bQc. Q b Q I 5 : Q → b.Qc c I3 :P→Q. I9 :Q→bQ.c Q → b.Sc Q b Q→.bQc I10 :Q→bS.c Q → .bSc S I6 : S→a. S→S.a a S → .Sa S → .a c I11 :Q→bSc. a I12 : S→Sa.
答：I2，I5分别如下图所示：
S A
a S→AaAb A→ε b S→BbBa A→ε $ 24
50．构造文法S→AaAb|BbBa A→ε B→ε，的预测分析表。
答：first（S）={a，b},First（AaAb）={a}，First（BbBa ）={b}
Follow（A）={a，b} Follow（B）={a，b}
①（+，a，b，T1） ②（/，d，e，T2） ③（+，c，T2，T3） ④（*，T1，T3，T4） B B→ε B→ε