发布时间 : 星期三 文章编译原理复习题-给学生(2014)更新完毕开始阅读
《编译原理》复习题
{X, 0, 1, 3, Y} {0, 1, 3, Y} {2} {1, 3, Y} 重新命名状态，即得：
S 1 2 3 4 ③ 最小化
{0, 1, 3, Y} {0, 1, 3, Y} {1, 3, Y} {1, 3, Y} {2} {2} - {2} 0 2 2 4 4 1 3 3 - 3 首先分为终态集和非终态集 {3} {1, 2, 4} 因为10 = 2 20 = 2 40 = 4 状态均属于集合{1, 2, 4}，所以对于输入符号0不能区分开1，2，4三个状态；11 = 3 21 = 3 41 = 3状态均属于集合{3}，所以对于输入符号1也不能区分开1，2，4三个状态；因此最终的状态划分即为: {3} {1, 2, 4}，其对应的DFA如下图所示：
0 1 0 0
1
5．写出C语言标识符集（字母或下划线开头的由字母、数字、下划线构成的串）的正规式。 解答：用D表示数字0-9，用L表示字母a-z|A-Z，则C语言标识符的正规式为： （L|_）（L|D|_）*
语法分析部分：
6．构造一文法，使其描述的语言L = {ω |ω ∈ (a, b)*，且ω中含有相同个数的a和b}。 解：
S→ ε| aA|bB A→ b| bS| aAA B→ a| aS| bBB 7．对于文法G(S)：
S → (L) | aS | a L → L, S | S
(1) 画出句型(S, (a))的语法树。
13
《编译原理》复习题
(2) 写出上述句型的所有短语、直接短语和句柄。 解：
(1) 句型(S, (a))的语法树如下图所示：
S ( L ) L , S S ( L ) S a
(2) 从语法树中可以找到（3分）短语：a; (a); S; S,(a); (S, (a)) 直接短语： a; S 句柄： S
8．令文法G[N]为 G[N]: N→D|ND
D→0|1|2|3|4|5|6|7|8|9
给出句子568的最左、最右推导。
解：最左推导：N ? ND ? NDD ? DDD ? 5DD ? 56D ? 568
最右推导：N ? ND ? N8 ? ND8? N68 ? D68 ? 568 8．已知文法G[A]: A→aABl|a
B→Bb|d
试给出与G[A]等价的LL(1)文法G[A′]； 解：G[A′]：A→aA′
A′→ABl | ε B→dB′
B′→bB′| ε
9．试构造下述文法的SLR(1)分析表。
G[A]: A→aABl|a
B→Bb|d
解：拓广文法 （0）S→A
（1）A→aABl （2）A→a （3）B→Bb （4）B→d
14
《编译原理》复习题
I0：S→．A I1：S→A． A→．aABl A→．a a I2：A→a．ABl I3： A→a． A A→aA．Bl d I4：B→d． A→．aABl B→．Bb A→．a B→．d B a I5： l I6： A→aAB．l A→aABl． B→B．b b I7： B→Bb． First（A）={a}follow（A）={#，d} First（B）={d}follow（B）={l} SLR（1）分析表如下： a b d l # A B 0 S2 1 1 ACC 2 S2 R2 R2 3 3 S4 5 4 R4 5 S7 S6 6 R1 R1 7 R3 10. 试构造下述文法的LL(1)分析表。 G[S]: S→（L）|a
L→L，S|S
解：消除左递归：
G(S): S ? (L) | a L ? SL’ L’ ? , SL’| ε
构造FIRST集，如下： （1）FIRST(S) = {(, a} （2）FIRST(L) = {(, a}
（3）FIRST(L’) = {,, ε}
构造FOLLOW集如下： （1）FOLLOW(S) = {#, ,, )} （2）FOLLOW(L) = {)} （3）FOLLOW(L’) = {)}
15
《编译原理》复习题
LL(1)分析表 S L L’ ( S ? (L) L ? SL’ ) L’ ? ε a S ? a L ? SL’ , L’ ? ,SL’ #
11．已知文法G[S]: S→aSbS|bSaS|ε 试证明G[S]是二义文法
证明： 该文法产生的语言是a的个数和b的个数相等的串的集合。该文法二义，例如句子abab有两种不同的最左推导。
S?aSbS?abS?abaSbS?ababS?abab S?aSbS?abSaSbS?abaSbS?ababS?abab
12．已知文法Ｇ： S → ( L | a L → S , L | )
判断是不是LL（1）文法，如果是请构造文法 Ｇ 的预测分析表，如果不是请说明理由。 【解】
1）求各非终结符的 FISRT 集和 FOLLOW 集： First（S）= { (, a } FIRST(L) = { ） }? FIRST(S) = { (, ), a } FOLLOW(S) = {, # } FOLLOW(L) = FOLLOW(S) ={ , # }
FIRST(( L)∩{a}=Φ FIRST(S , L)∩{)}=Φ 所以是LL（1）文法 2）预测分析表： ( a , } # S S→ ( L S→ a L L→ S , L L→ S , L L → )
13．文法 S ? A a | b A c | d c | b d a
A ? d
16