P; F’; End ; Procedure F’ b + * ( ) a ^ E E?T E’ Begin E?T E’ E?T E’ E?T E’ ? E’ E’?+E E’ξ If sym = ‘ * ’ T T ?FT’ T’Then begin ?FT’ T?FT’ T?FT’ ?ξ T’ T’ T’?ξ T’ ? T T’?T Advance ; T’?T T’ ?T F F ?PF’ F? PF’ F ’P ?PF’ F?PF’ End F’ F’ ? ξ F’ F’ ? ξ F’?ξ F’?ξ F’?ξ F’?ξ End; ?*F’ Procedure P P P ?(E) P?a P?b P? ^ Begin
If sym = ‘ a ’ or sym = （4） 构造其递归下降分析程序：
‘ b ‘ or sym = ‘ ^ Procedure E;
Then acvance Begin
Else if sym = ‘ ( ‘ T ; E’
Then begin End ;
Advance ;
E ; Procedure E’ ;
If sym = Begin
‘ ) ‘ If sym = ‘ + ’
Then Then begin
advance Acvance ;
Else E
error End
End End ;
Else error
End; Procedure T ;
3 解： Begin
（1） 该文法不含左递归，计算每个 F ; T’
非终结符的FIRST集合和FOLLOW集合如下： End ;
FIRST（S）={a，b，c}
FIRST（A）={a，ε} Procedure T’ ;
FIRST（B）={b，ε} Begin
FOLLOW（S）={#} If sym ∈first ( T )
FOLLOW（A）={b，c} Then T
Else if sym = ‘*’ then FOLLOW（B）={c}
可见该文法满足LL(1)文法的三个条error
件，是LL(1)文法。 End ;
（2） 该文法不含左递归，计算每个
非终结符的FIRST集合和FOLLOW集合如下： Procedure F ;
FIRST（S）={a，b} Begin
FIRST（A）={a，b，ε} If sym ∈first ( P )
11
预测
分析表 # E’ ->ξ T’?ξ F’?ξ
FIRST（B）={b，ε} FOLLOW（S）={#} FOLLOW（A）={b} FOLLOW（B）={b}
考虑A→a∣B∣ε，因为FIRST（B）∩FOLLOW（A）={b}≠?，所以该文法不是LL(1)文法。
（3） 该文法不含左递归，计算每个
非终结符的FIRST集合和FOLLOW集合如下： FIRST（S）={a，b，ε} FIRST（A）={a，ε} FIRST（B）={b，ε} FOLLOW（S）={#}
FOLLOW（A）={a，b，#} FOLLOW（B）={a，b，#} 考虑A→a∣ε和B→b∣ε，
因为 FIRST（a）∩FOLLOW（A）={a}
≠? FIRST（b）∩FOLLOW（B）={b}
≠?
所以该文法不是LL(1)文法。
（4） 该文法不含左递归，计算每个
非终结符的FIRST集合和FOLLOW集合如下： FIRST（S）={a，b，c，d} FIRST（B）={b，c，d} FIRST（C）={c，d} FOLLOW（S）={e，#} FOLLOW（B）={e，#} FOLLOW（C）={e，#}
可见该文法满足LL(1)文法的三个条件，是LL(1)文法。
1解：因为E=>E+T=>E+T*F，所以E+T*F是该文法的一个句型。 短语：E+T*F，T*F 直接短语：T*F 句柄：T*F 2解： 步骤 （1）最左推导： 0 S=>(T)=>(T，S)=>(S，S)=>(a，S)=>(a，1 (T))=>(a，(T，S))=>(a，(S，S))=> (a2 ，(a，S))=>(a，(a，a)) 3 S=>(T)=>(T，S)=>(S，S)=>((T)4 ，S)=>((T，S)，S)=>((T，S，S)，S)=>((S5 ，
S，S)，S)=>(((T)，S，S)，S)=>(((T，S)，
S，S)，S)=>(((S，S)，S，S)，S)=>(((a，S)，S，S)，S)=>(((a，a)，S，S)，S)=>(((a，a)，∧，S)，S)=>(((a，a)，∧，(T))，S)=>(((a，a)，∧，(S))，S)=>(((a，a)，∧，(a))，S)=>(((a，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))
S=>(T，S)=>(T，a)=>(S，a)=>((T)，a)=>((T，S)，a)=>((T，(T))，a)=>((T，(S))，a)=>((T，(a))，a)=>((T，S，(a))，a)=>((T，∧，(a))，a)=>((S，∧，(a))，a)=>(((T)，∧，(a))，a)=>(((T，S)，∧，(a))，a)=>(((T，a)，∧，(a))，a)=>(((S，a)，∧，(a))，a)=> (((a，a)，∧，(a))，a)
（2）(((a，a)，^，(a))，a)的规范归约如下：
(((a，a)，∧，(a))，a) (((S，a)，∧，(a))，a) (((T，a)，∧，(a))，a) (((T，S)，∧，(a))，a) (((T)，∧，(a))，a) ((S，∧，(a))，a) ((T，∧，(a))，a) ((T，S，(a))，a) ((T，(a))，a) ((T，(S))，a) ((T，(T))，a) ((T，S)，a) ((T)，a) (S，a) (T，S) (T)
“移进—归约”过程： 栈 # #( #(( #((( #(((a #(((S 输入串 (((a，a)，∧，(a))，a)# ((a，a)，∧，(a))，a)# (a，a)，∧，(a))，a)# a，a)，∧，(a))，a)# ，a)，∧，(a))，a)# ，a)，∧，(a))，a)# 12
动作 预备 进 进 进 进 归
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #(((T #(((T， #(((T，a #(((T，S #(((T #(((T) #((S #((T #((T， #((T，∧ #((T，S #((T #((T， #((T，( #((T，(a #((T，(S #((T，(T #((T，(T) #((T，S #((T #((T) #(S #(T #(T， #(T，a #(T，S #(T #(T) #S ，a)，∧，(a))，a)# a)，∧，(a))，a)# )，∧，(a))，a)# )，∧，(a))，a)# )，∧，(a))，a)# ，∧，(a))，a)# ，∧，(a))，a)# ，∧，(a))，a)# ∧，(a))，a)# ，(a))，a)# ，(a))，a)# ，(a))，a)# (a))，a)# a))，a)# ))，a)# ))，a)# ))，a)# )，a)# )，a)# )，a)# ，a)# ，a)# ，a)# a)# )# )# )# # # 归 进 进 归 归 进 归 归 进 进 归 归 进 进 进 归 归 进 归 归 进 确定化的结果见转换矩阵表： 归 S 归 {0，2，5，7，10} {1，2，5，7，8，10} 进 {1，2，5，7，8，10} {2，5，7，8，10} 进 {2，3，5，7，10} {2，4，5，7，8，10} 归 {2，5，7，8，10} {2，5，7，8，10} 归 {2，3，5，7，9，10} {2，4，5，7，8，10} 进 {2，4，5，7，8，10} {2，5，7，8，10} 归 {11} ? {6} ? （3）、不是SLR文法。
I3、I6、I7有“移进—归约”冲突。 I3：FOLLOW(S’)={#}不包含a，b。 I6：FOLLOW(S)={#，a，b}包含a，b；“移进—归约”冲突无法消解。
I7：FOLLOW(A)={a，b}包含a，b；“移进—归约”冲突消解。 所以不是SLR文法。
编译原理G卷
1．构造正规表达式a(aa)*bb(bb)*a(aa)* 的NFA。
13
1 S S 7 ε ε 10 ε 2 ε A 3 8 ε ε A 0 a S ε ε ε d 5 6 A {2，3，5，7{2，3，5，7{，3，5，7，{2，3，5，7{2，3，5，7? ? {2，3，5，7 4解： （1）、0.S’→·S 1.S’ →S· 2.S→·AS 3.S→A·S 4.S→AS·
5.S→·b 6.S→b· 7.A→·SA 8.A→S·A 9.A→SA· 10.A→·a 11.A→a· （2）、构造识别活前缀的NFA如下图所示：
2．构造正规表达式((a|b)*|aa)*b的NFA。 （13分）
2．令文法G[N]为 G[N]: N→D|ND D→0|1|2|3|4|5|6|7|8|9
给出句子568的最左、最右推导。 3．给出字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；
5. 表达式a*b-c-d$e$f-g-h*i中，运算符的优先级由高到低依次为-、*、$，且均为右结合，请写出相应的后缀式。 6．判断文法G[S]: S → BA
A → BS | d B → aA| bS | c 是否为LL(1)文法.
7．对于文法G[E]: E→E+T | T
T→T+P | P P→(E) | i
写出句型P+T+(E+i)的所有短语、直接短语、句柄。
8．已知文法G[A]: A→aABl|a
B→Bb|d
试给出消除左递归和回溯与G[A]等价的LL(1)文法G[A′]；
9．将下面的语句翻译成四元式序列： if (x＞y) m= 1; else m=0;
10．将以下DFA 最小化。（8分）
2baXa1?Y 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分） 12．试构造下述文法的SLR(1)分析表。
G[A]: A→aABl|a
B→Bb|d
13．将下面的语句翻译成四元式序列：（7分）
if (x＞y) m= 1; else m=x+y;
14. 试构造下述文法的LL(1)分析表。（15分）
G[S]: S→（L）|a
L→L，S|S
17．已知文法G[S]: S→aSbS|bSaS|ε 试证明G[S]是二义文法
18．将下面的语句翻译成四元式序列： while(a if (c＞d) x=y+z 19．构造正规表达式a(aa)*bb(bb)*a 的最小化的确定有限自动机M′。 21．画出编译程序的总体结构图，简述各部分的主要功能。 22．对于文法G(S)： S → (L) | aS | a L → L, S | S (1) 画出句型(S, (a))的语法树。 (2) 写出上述句型的所有短语、直接短语和句柄。 23．构造一文法，使其描述的语言L = {ω|ω ∈ (a, b)* ，且ω中含有相同个数的a 和b}。 24．分别给出表达式 –(a*(b-c))+d 的逆波兰表示和四元式表示。 25．把下列语句翻译为四元式序列： while (A > B) if (C > D) X = Y * Z else X = Y + Z 26．构造一个DFA，它接受Σ = {0, 1}上所有满足如下条件的字符串：每个1后面都有0直接跟在右边。 27．已知文法G(S)： 14 S→S*aP| aP| *aP P→+aP| +a (1) 将文法G(S)改写为LL(1)文法G’(S)； (2) 写出文法G’(S)的预测分析表。 28．已知文法G(S)： S→aS | bS | a (1) 构造识别该文法所产生的活前缀的DFA； (2) 判断该文法是LR(0)还是SLR(1)， A ? d 36． 将下图所示的确定有限自动机(DFA)最小化。其中，X为初态，Y为终态。 aaXb21bab3aYb并构造所属文法的LR分析表。 29．将下图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。其中，X为初态，Y为终态。 ba2?a1baXaYbb34b?a? 30． 对正规式(a|b)*abb构造其等价的NFA。 31． 下面的文法产生0和1的串，即二进制的正整数，请给出决定每个二进制数的值（十进制形式）的语法制导定义。 32．把算术表达式?(a + b) ? (c + d) + (e+ f) 翻译成等价的四元式序列（序号从0开始）。 33．设有文法G[S]: S→a|（T）|? T→T,S|S 试给出句子(a,a,a)的最左推导。 34．已知文法Ｇ： S → ( L | a L → S , L | ) 判断是不是LL（1）文法，如果是请构造文法 Ｇ 的预测分析表，如果不是请说明理由。 35．文法 S ? A a | b A c | d c | b d a 37．请画出识别无符号十进制整数的状态转换图 38．设有文法G[S]: S→S*S|S+S|(S)|i 该文法是否为二义文法,并说明理由？ 40．把下列语句翻译为四元式序列（四元式序号从1开始）： while (A > B) if (C > D) X = Y * Z else X = Y + Z 41.构造下面文法的LL（1）分析表。 G[D]: D ? TL T ? int | real L ? id 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所示。 15