编译原理课后答案_第三版

三 12 将图a确定化 最小化 a,b a a 图a 解：引入新的初态结点X和终态结点Y(X,Y不属于源非确定集)得图如下： a εε ε ε a,b a 列出状态转换矩阵如下所示： a b A {X,0,Y} {0,1,Y} {1} B {0,1,Y} {0,1,Y} {1} C {1} {0,Y} ø D {0,Y} {0,1,Y} {1} DFA如下： a a b b b b a 最少化：终态{A,B,D}a={A,B}∈{A,B,D} {A,B,D}b={B,}∈{A,B,D} ∴ 最少化为： a b a (b)将图b最少化 b b a b a a a b b a a b 图b 解：终态{0,1} a∈{0,1} {0,1} b={2,4}∈{2,3,4,5} ∴{0,1}不能再分 非终态{2,3,4,5} a ={0,1,3,5} {2,4} a ={0,1} {2,4} b ={3,5} {3,5} a ={3,5} {3,5} b ={2,4} 0代{0,1},2代表{2,4},3代表{3,5}得最少化为： a b a b b a 14.构造一个DFA，它接收∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。 解：构造正规式为：（0|10）* 则可构造如下NFA： ε 0 ε ε ε ε ε 1 0 ε ε 列出状态转换矩阵如下： 0 1 A { q0,F,A,C, qf } {B,G,F,A,C, qf} {D} B {B,G,F,A,C, qf} {B,G,F,A,C, qf} {D} C {D} {E,G,F,A,B,C, qf } ø D {E,G,F,A,B,C, qf } {B,G,F,A,C, qf} {D} 则得DFA 如下： 0 0 0 1 1 0 1 最少化得 {A,B,D}0={B} {A,B,D}1={C} 0 1 0 15.给定右线性文法G： S->0S|1S|1A|0B A->1C|1 B->0C|0 C->0C|1C|0|1 求出一个与G等价的左线性文法。 解：由G得NFA=<{S,A,B,C}∪{f},{0,1},δ,S,{f}> 1 0,1 1 1 0,1 0,1 0 0 0 由NFA得左线性文法：GL=<{0,1},{A,B,C,f},f, ρ’> ρ’:A->1 B->0 C->A1|B0|C0|C1 f->A1|B0|C0|C1 四 1.考虑下面文法G：S->a|^|(T) T->T,S|S (1)消除G的左递归 (2)改写后的文法是否是LL(1)的？给出预分析表。 解：(1) S->a|^|(T) T->ST’ T’->,ST’|ε (2) FIRST FOLLOW S a,^,( #, , , ) T a,^,( ) T’ , , ε ) 预分析表： a ^ ( ) ， # S S->a S->^ S->(T) T T->ST’ T->ST’ T->ST’ T’ T’->ε T->,ST’ 是LL(1)的。 五 5．文法 S->AS|b A->SA|a (1) 列出所有LR(0)项目 (2) 构造LR(0)项目集族及识别活前缀的DFA (3) 该文法是SLR的么？若是构造它的SLR分析表。 解：扩展文法：S’->S S S->AS|b A->SA|a b A a S A a S b A b b S a a S A b A a a S b A (3) 　　　　　　　　　　Follow First S’ # a,b S #,a,b a,b A a,b a,b 冲突项目I１中：有接受项目和移进冲突，可解决.　　　　　 ＃ a,b I5 , I7 存在移进，归约冲突，不可解决． ∵Follow(S) ∩a ∩b≠○ 所以，该文法不是SLR的 ８.证明下面的文法 S->AaAb|BbBa A->ε B->ε 是LL(1)文法。 ①不含左递归； ②First(α1) ∩First(α2) ∩…=○ ③First(A) ∩Follow(A) =○ ∴该文法是LL(1)文法 七 1． 给出下面表达式的逆波兰表示（后缀式）： a*(-b+c) a+b*(c+d/e) not A or not(C or not D) (A and B)or (not C or D) 后缀式分别为： ab-c+* abcde/+*+ A not CD not or not or AB and C not D or or 3. 请将表达式-（a+b）*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 三元式： (0)（+，a, b） (1) ( -, (0), _) (2) (+, c, d) (3) (*,(1),(2)) (4)（+，a, b） (5) (+, (4), c) (6) (-,(3),(5)) 间接三元式： (1)（+，a, b） (2) ( -, (1), _) (3) (+, c, d) (4) (*,(2),(3)) (5) (+, (1), c) (6) (-,(4),(5)) 间接代码： （1） （2） （3） （4） （1） （5） （6） 四元式： （0）（+，a, b, T1） （1）（-，T1, _, T2） （2）（+， c, d, T3） （3）（*, T2, T3, T4） （4）（+，a, b, T5） （5）（+，T5, c, T6） （6）（-，T4,T6,T7） 7.用7.5.1节的方法，把下面语句翻译成四元式序列： While AS·A A->SA· A->·a S->·AS S->·b I1: S’->S· A->S·A A->·a S->·AS S->·b I0 : S’->·S S->·AS 　S->·b A->·SA A->·a I5: A->SA· S->A·S S->·AS S->·b A->·SA A->·a I2 : S->A·S 　S->·AS S->·b A->·SA A->·a I3 : S->b· I4 : A->a· I7 : S->AS· A->S·A A->·SA 　A->·a S->·AS S->·b