《编译原理》复习题
A → BS | d B → aA| bS | c 是否为LL(1)文法.
解：对于该文法求其FIRST集如下：
FIRST(S) = {a, b, c}; FIRST(A) = {a, b, c, d}; FIRST(B) = {a, b, c}。 求其FOLLOW集如下：
FOLLOW(S) = {a, b, c, d, #}; FOLLOW(A) = {a, b, c, d, #}; FOLLOW(B) = {a, b, c, d, #}。 由A → BS | d 得：
FIRST(BS) ∩ FIRST(‘d’) = {a, b, c} ∩ {d} = Φ
由B → aA| bS | c 得
FIRST(aA) ∩ FIRST(bS) ∩ FIRST(c) = {a} ∩{b}∩ {c} =Φ
由于文法G[S]不存在形如β→ε的产生式，故无需求解形如FIRST(α) ∩ FOLLOW(A)的值，也即文法G[S]是一个LL(1)文法。
7．对于文法G[E]: E→E+T | T
T→T+P | P P→(E) | i
写出句型P+T+(E+i)的所有短语、直接短语、句柄。
解：短语：P、P+T、i、E+i、(E+i )、P+T+(E+i )； 直接短语：P、i； 句柄：P；
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．将下面的语句翻译成四元式序列： if (x＞y) m= 1; else m=0;
解：1 (j＞,x,y,3)
2 (j,_,_,5) 3 (=,1,_,m) 4 (j,_,_,6) 5 (=,0,_,m)
13
6:
10．将以下DFA 最小化。（8分）
2bXa1a?Y 解：
a0b1
11．设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f定义如下：
f(x,a)={x,y} f{x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M′。（12分）
解：对照自动机的定义M=(S,Σ,f,So,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。 先画出NFA M相应的状态图，如下图所示。
aabbXYb
用子集法构造状态转换矩阵，如下表所示。
I {x} {y} {x,y} Ia {x,y} — {x,y} Ib {y} {x,y} {x,y} 将转换矩阵中的所有子集重新命名，形成下表所示的状态转换矩阵，即得到
f 字符 状态 0 1 2 a 2 — 2 b 1 2 2
《编译原理》复习题
M′=({0,1,2},{a,b},f,0,{1,2})， M′状态转换图如下图所示。 a
02a, b
b b1
（注意：本题由于集合的命名和先后顺序不同，可能最终结果不同。）
12．试构造下述文法的SLR(1)分析表。（13分）
G[A]: A→aABl|a
B→Bb|d
解：拓广文法 （0）S→A
（1）A→aABl （2）A→a （3）B→Bb （4）B→d
I0：S→．A A→．aABl a A→．a I1：S→A． I2：A→a．ABl A A→a． A→．aABl A→．a I3： A→aA．Bl d B→．Bb B→．d B I4：B→d． a I5： A→aAB．l B→B．b b I7： B→Bb． l I6： A→aABl． if (x＞y) m= 1; else m=x+y;
解：1 (j＞,x,y,3)
2 (j,_,_,5) 3 (=,1,_,m) 4 (j,_,_,7) 5 (+,x,y,T1) 6 (=, T1,_,m) 7:
14. 试构造下述文法的LL(1)分析表。（15分）
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’) = {)}
LL(1)分析表 S L ( S ? (L) L ? SL’ ) L’ ? ε a S ? a L ? SL’ , L’ ? ,SL’ #
First（A）={a}follow（A）={#，d} First（B）={d}follow（B）={l} SLR（1）分析表如下： 0 1 2 3 4 5 6 7
L’ a S2 S2 b S7 d R2 S4 R1 l R4 S6 R3 # ACC R2 R1 A 1 3 B 5 14
13．将下面的语句翻译成四元式序列：（7分）
15．判断文法G[S]: S → BA
A → BS | d B → aA| bS | c 是否为LL(1)文法.
解：对于该文法求其FIRST集如下：
FIRST(S) = {a, b, c}; FIRST(A) = {a, b, c, d}; FIRST(B) = {a, b, c}。 求其FOLLOW集如下：
FOLLOW(S) = {a, b, c, d, #}; FOLLOW(A) = {a, b, c, d, #}; FOLLOW(B) = {a, b, c, d, #}。 由A → BS | d 得：
《编译原理》复习题
FIRST(BS) ∩ FIRST(‘d’) = {a, b, c} ∩ {d} = Φ
由B → aA| bS | c 得
FIRST(aA) ∩ FIRST(bS) ∩ FIRST(c) = {a} ∩{b}∩ {c} =Φ
由于文法G[S]不存在形如β→ε的产生式，故无需求解形如FIRST(α) ∩ FOLLOW(A)的值，也即文法G[S]是一个LL(1)文法。 16．对于文法G[E]: E→E+T | T
T→T+P | P P→(E) | i
写出句型P+T+(E+i)的所有短语、直接短语、句柄。 解：短语：P、i、E+i、(E+i )、T+(E+i )、P+T+(E+i )； 直接短语：P、i； 句柄：P；
17．已知文法G[S]: S→aSbS|bSaS|ε 试证明G[S]是二义文法
证明： 该文法产生的语言是a的个数和b的个数相等的串的集合。该文法二义，例如句子abab有两种不同的最左推导。
S?aSbS?abS?abaSbS?ababS?abab S?aSbS?abSaSbS?abaSbS?ababS?abab 18．将下面的语句翻译成四元式序列： while(a if (c＞d) x=y+z 解：100 (j<,a,b,102) 101 (j,_,_,107) 102 (j>,c,d,104) 103 (j,_,_,106) 104 (+,y ,z ,t) 105 (=,t ,_ ,x) 106 (j,_,_,100) 107: 19．构造正规表达式a(aa)*bb(bb)*a 的最小化的确定有限自动机M′。 解：先画出正规式相应的NFA M状态图，如下图所示。 2 5 a a b b a b b a X 1 3 4 Y 15 用子集法构造状态转换矩阵，如下表所示。 I {x} {1} {2} {3} {4} {5} {Y} Ia {1} {2} {1} - {Y} - - Ib - {3} - {4} {5} {4} - 将状态分为终态集{Y}和非终态集{X,1,2,3,4,5} 因为｛X,1,2,3,4,5｝a={1,2,1,_,Y,_} 所以非终态集分为{X,1,2},{3,5},{4} 因为{X,1,2}b={_,3,_},所以分为 最后得到集合{X,2},{1},{3,5},{4},{Y}重新命名为1，2，3，4，5得到最小化的DFA M′状态转换矩阵和状态转换图如下图所示。 I 1 2 3 4 5 Ia 2 1 - 5 - Ib _ 3 4 3 _ a b b a 3 4 1 2 5 a b （注意：本题由于集合的命名和先后顺序不同，可能最终结果不同。） 20．试构造下述文法的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 《编译原理》复习题 I0：S→．A A A→．aABl A→．a a I1：S→A． （1）词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个单 I2：A→a．ABl A→a． A→．aABl A→．a A I3：A→aA．Bl B→．Bb B→．d B d 词符号，其输出结果是二元式(单词种别，单词自身 I4：B→d． 的值)流。 （2）语法分析器，对单词符号串进行语法分析 l I6： A→aABl． a I5： A→aAB．l B→B．b b I7： B→Bb． （根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的句子。 （3）语义分析及中间代码生成器，按照语义规 则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而 First（A）={a}follow（A）={#，d} First（B）={d}follow（B）={l} SLR（1）分析表如下： a 0 1 2 3 4 5 6 7 S2 S2 b S7 ACTION d R2 S4 R1 l R4 S6 R3 # ACC R2 R1 GOTO A 1 3 B 5 直接生成目标代码。 （4）优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。 （5）目标代码生成器，把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能在机器上运行。 （6）表格管理模块保持一系列的表格，登记源 21．画出编译程序的总体结构图，简述各部分的主要功能。 解：编译程序的总体框图如下所示： 表词法分析器单词符号语法分析器语法单位语义分析与中间代码生成器出程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都 格错管四元式优化段四元式目标代码生成器目标代码处在不断和表格打交道。 （7）出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现 16 理理错误，把有关错误信息报告给用户。编译程序的各