《编译原理》复习题

46．将下图的DFA最小化。

1 a 3 a b 2 a b b a 4 a b b 0 答：初始划分：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 0 b 1 b a b 3

47．设有如下文法：P→D

D→D；D|id：T|proc id；D； T→real|integer

给出一个语法制导定义，打印该程序一共声明了多少个id。 答： 文法 P→D D→D1；D2 D→id：T D→proc id；D1； T→real T→integer 语法制导定义 Print（D.num） D.num=D1.num+D2.num D.num=1 D.num=D1.num+1

48．识别文法G的活前缀的DFA如下图所示，补充完成状态I2和I5，然后根据该图构造SLR（1）分析表。

G：(0) P'→P (1) P→aPb (2) P→Q (3) Q→bQc (4) Q→bSc (5) S→Sa (6) S→a

37

《编译原理》复习题

P I1 :P'→P. I2 : I4 :P→aP.b I0 :P'→.P a P P→.aPb b P→.Q I7 :P→aPb. a Q→.bQc b Q→.bSc I8 :Q→bQc. Q b Q I c 5 : I3 :P→Q. I9 :Q→bQ.c Q b I10 :Q→bS.c S I6 : S→a. S→S.a a c I11 :Q→bSc. a I12 : S→Sa.

答：I2，I5分别如下图所示：

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 b S5 S5 R2 S7 S5 R1 R3 R4 Action表 c R6 R3 S8 S11 R4 R5 $ Acc R2 R1 R3 R4 P 1 4 I2 :P→a.Pb P→.aPb P→.Q Q→.bQc Q→.bSc I5 :Q→b.Qc Q→b.Sc Q→.bQc Q→.bSc S→.Sa S→.a GOTO表 Q 3 3 9 S 10 49．给出表达式（a+b）*(c+d/e)的语法树和四元式序列。

38

《编译原理》复习题

答:语法树如下： 四元式序列：

* + + / a b c ①（+，a，b，T1） ②（/，d，e，T2） d e ③（+，c，T2，T3） ④（*，T1，T3，T4） ε B → ε 50．构造文法S→AaAb|BbBa A→ ，的预测分析表。

答：first（S）={a，b},First（AaAb）={a}，First（BbBa ）={b} Follow（A）={a，b} Follow（B）={a，b}

a b $ S S→AaAb S→BbBa A A→ε A→ε B B→ε B→ε

51．写出C语言标识符集（字母或下划线开头的由字母、数字、下划线构成的串）的正规式。 解答：用D表示数字0-9，用L表示字母a-z|A-Z，则C语言标识符的正规式为：

（L|_）（L|D|_）*

52．有一语法制导定义如下，其中+表示符号连接运算： S→B print B.vers B→a B.vers=a B→b B.vers=b

B→Ba B.vers=a+B.vers B→Bb B.vers=b+B.vers

若输入序列为abab，且采用自底向上的分析方法，则输出序列为（__________baba_________）。用分析树表示求解过程。

S Print baba B B.vers=baba B b B.vers=aba B a B.vers=ba B b B.vers=a a

53．假设第一个四元式的序号是100，写出布尔表达式ae的四元式序列。

39

《编译原理》复习题

100 （j<, a, b, 106） 101 （j, _, _ , 102） 102 （jnz, c, _ ,104） 103 （j，_ ,_ ,q） 104 （j>，d, e, 106） 105 （j，_ , _ , q ） T:106 …… F:q …….

54．设有如下文法： G[E]：E→EWT|T T→T/F|F

F→（E）|a|b|c W→+|-

证明符号串a/(b-c)是句子。

解答：有推导E?T?T/F?F/F?a/F?a/(E)?a/(EWT)? a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c)，即从文法开始符号E能够推导出a/(b-c)，所以a/(b-c)是文法G[E]的句子。 55．对于下列文法 G[S]： S→Sb|bA A→aA|a

（1）构造一个与G等价的LL（1）文法G′。 （2）对于文法G′,构造相应的LL（1）分析表。 解： （1）（5分）G′：S→bAS′ S′→b S′|ε

A→aA′

A′→A|ε

（2）（1分）FIRST（S）={ b } FIRST（S′）={ b，ε} FIRST（A）={a}

FIRST（A′）={a，ε} FOLLOW（S）={#} FOLLOW（S′）={#} FOLLOW（A）={b，#}

FOLLOW（A′）=（b，#）

LL（1）分析表：

S S′ A A′

a A→aA′ A′→A b S→bAS′ S′→b S′ A′→ε # S′→ε A′→ε 40