第5章 1.文法 S->a|^|(T) T->T, SIS (1)对(a,(a,a)的最左推导为: S=>(T) =>(a,S) >(a,(T,S) =>(a,(S,S)) =>(a,(a,S) >(a,(a,a)) 对((a,a),,(a)),a)的最左推导为: S=>(T) =>(T,S) =>(S,S) =>(T),S) =>(T,S),S) (T,S,S),S) =>(S,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) 改写文法为 0)S->a 2)S->(T) 4)N2>,SN2
第5章 1.文法 S->a|^|(T) T->T,S|S (1) 对(a,(a,a)的最左推导为： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a)) 对(((a,a),^,(a)),a) 的最左推导为： S=>(T) =>(T,S) =>(S,S) =>((T),S) =>((T,S),S) =>((T,S,S),S) =>((S,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) (3) 改写文法为： 0) S->a 1) S->^ 2) S->( T ) 3) T->S N2 4) N2->, S N2 5) N2->ε
FIRST FOLLOW {a,,(} {#,)} {a,,(} 对左部为N2的产生式可知 FIRST(→>,SN2)={, FIRST(→>E)={ε} FOLLOW (N2)=0K 所以文法是LL(1)的。 Predicting Analysis Table # -+++-— T|->SN2|->SN2|->SN2 也可由预测分析表中无多重入口判定文法是LL(1)的 对输入串(a,a)#的分析过程为 STATE STACK CUR CHAR INOUT STRING OPERATION a,a)# #)T S->(T) #)T a a)# #)N2S T->SN2 S->a #)N2 a)# #)N2S a)# N2->,SN2 #)N2S #)N2a #)N2 ## 可见输入串(a,a)#是文法的句子
=================================================== | | FIRST | FOLLOW | +-------+--------------------+--------------------+ | S | {a,^,(} | {#,,,)} | +-------+--------------------+--------------------+ | T | {a,^,(} | {)} | +-------+--------------------+--------------------+ | N2 | {,,ε} | {)} | =================================================== 对左部为 N2 的产生式可知： FIRST （->, S N2）={，} FIRST （->ε）={ε} FOLLOW （N2）={)} {，}∩ {)}=( 所以文法是 LL(1)的。 Predicting Analysis Table =========================================================================== | | a | ^ | ( | ) | , | # | +-------+----------+----------+----------+----------+----------+----------+ | S |->a |->^ |->( T ) | | | | +-------+----------+----------+----------+----------+----------+----------+ | T |->S N2 |->S N2 |->S N2 | | | | +-------+----------+----------+----------+----------+----------+----------+ | N2 | | | |->ε |->, S N2 | | =========================================================================== 也可由预测分析表中无多重入口判定文法是 LL(1)的。 (4) 对输入串（a,a）#的分析过程为： STATE STACK CUR_CHAR INOUT_STRING OPERATION #S ( a,a)# #)T( ( a,a)# S->(T) #)T a ,a)# #)N2S a ,a)# T->SN2 #)N2a a ,a)# S->a #)N2 , a)# #)N2S, , a)# N2->,SN2 #)N2S a )# #)N2a a )# S->a #)N2 ) # #) ) # N2->ε # # 可见输入串（a,a）#是文法的句子
2.文法 H->LSoe K->dML e L->eHf M->K bLM 展开为 0 S->M H 3)H 4) K->d M L 6) L->e H f 7)M->K 8) M->bL M FIRST FOLLOW S la, d, b, e, el #,o} M Id, e, b] e,#,o H Le, eh {#,f,o} L la, d, b, e, 0, #h {d,e} Predicting Analysis Table d f b # ++ s | ->a |->M|>M H1-MH 1->MH 1->M H >K 一 H 1->L l->E l->e f 由预测分析表中无多重入口判定文法是LL(1)的
2．文法： S->MH|a H->LSo|ε K->dML|ε L->eHf M->K|bLM 展开为： 0） S->M H 1） S->a 2） H->L S o 3） H->ε 4） K->d M L 5） K->ε 6） L->e H f 7） M->K 8） M->b L M =================================================== | | FIRST | FOLLOW | +-------+--------------------+--------------------+ | S | {a,d,b, ε,e} | {#,o} | +-------+--------------------+--------------------+ | M | {d, ε,b} | {e,#,o} | +-------+--------------------+--------------------+ | H | {ε,e} | {#,f,o} | +-------+--------------------+--------------------+ | L | {e} | {a,d,b,e,o,#} | +-------+--------------------+--------------------+ | K | {d, ε} | {e,#,o} | =================================================== Predicting Analysis Table ====================================================================== | | a | o | d | e | f | b | # | +------+--------+--------+--------+--------+--------+--------+--------+ | S |->a |->M H |->M H |->M H | |->M H |->M H | +------+--------+--------+--------+--------+--------+--------+--------+ | M | |->K |->K |->K | |->b L M |->K | +------+--------+--------+--------+--------+--------+--------+--------+ | H | |->ε | |->L S o |->ε | |->ε | +------+--------+--------+--------+--------+--------+--------+--------+ | L | | | |->e H f | | | | +------+--------+--------+--------+--------+--------+--------+--------+ | K | |->ε |->d M L |->ε | | |->ε | ======================================================================= 由预测分析表中无多重入口判定文法是 LL(1)的
(1)文法 A->aABela B->Bbd 改写文法为 0)A->aN3 1)N3->A B e 2)N3->E )B->d 4)N2->b FIRST FOLLOW {#,d} B Id -+ [e, al {#,d} Predicting Analysis table A| ->a N3 B ->dN2 ->bN2 N3 ->AB e ->e 由预测分析表中无多重入口判定文法是LL(1)的。 S->Aa b A->SB B->ab 第1种改写: S->SBab B->ab
3． （1） 文法： A->aABe|a B->Bb|d 改写文法为： 0) A->a N3 1) N3->A B e 2) N3->ε 3) B->d N2 4) N2->b N2 5) N2->ε =================================================== | | FIRST | FOLLOW | +-------+--------------------+--------------------+ | A | {a} | {#,d} | +-------+--------------------+--------------------+ | B | {d} | {e} | +-------+--------------------+--------------------+ | N2 | {b,ε} | {e} | +-------+--------------------+--------------------+ | N3 | {ε,a} | {#,d} | =================================================== Predicting Analysis Table ================================================================ | | a | e | b | d | # | +-------+----------+----------+----------+----------+----------+ | A |->a N3 | | | | | +-------+----------+----------+----------+----------+----------+ | B | | | |->d N2 | | +-------+----------+----------+----------+----------+----------+ | N2 | |->ε |->b N2 | | | +-------+----------+----------+----------+----------+----------+ | N3 |->A B e | | |->ε |->ε | ================================================================ 由预测分析表中无多重入口判定文法是 LL(1)的。 （3）文法： S->Aa|b A->SB B->ab 第 1 种改写： S->SBa|b B->ab
1)N2->BaN2 2)N2-> 3) B->a b FIRST FOLLOW +-+ B lah Predicting Analysis Table b # >b n2 1->a b 由预测分析表中无多重入口判定文法是LL(1)的 第2种改写 S->Aa b A->AaB bB B->ab 0) S->Aa 1)S->b 2) A->bB N3 5)B->a b FIRST FOLLOW SA-B
0) S->b N2 1) N2->B a N2 2) N2->ε 3) B->a b =================================================== | | FIRST | FOLLOW | +-------+--------------------+--------------------+ | S | {b} | {#} | +-------+--------------------+--------------------+ | B | {a} | {a} | +-------+--------------------+--------------------+ | N2 | {ε,a} | {#} | =================================================== Predicting Analysis Table ========================================== | | a | b | # | +-------+----------+----------+----------+ | S | |->b N2 | | +-------+----------+----------+----------+ | B |->a b | | | +-------+----------+----------+----------+ | N2 |->B a N2 | |->ε | ========================================== 由预测分析表中无多重入口判定文法是 LL(1)的。 第 2 种改写： S->Aa|b A->AaB|bB B->ab 0) S->A a 1) S->b 2) A->b B N3 3) N3->a B N3 4) N3->ε 5) B->a b =================================================== | | FIRST | FOLLOW | +-------+--------------------+--------------------+ | S | {b} | {#} | +-------+--------------------+--------------------+ | A | {b} | {a} | +-------+--------------------+--------------------+ | B | {a} | {a} |
Predicting Analysis Table 巴二二二二二二二二二二二二二二二二二二二二 1-Aa 1->b B N3 1->a b I N3 ->a B N3 由预测分析表中含有多重入口判定文法不是LL(1)的
+-------+--------------------+--------------------+ | N3 | {a, ε} | {a} | =================================================== Predicting Analysis Table ========================================== | | a | b | # | +-------+----------+----------+----------+ | S | |->A a | | +-------+----------+----------+----------+ | | |->b | | +-------+----------+----------+----------+ | A | |->b B N3 | | +-------+----------+----------+----------+ | B |->a b | | | +-------+----------+----------+----------+ | N3 |->a B N3 | | | +-------+----------+----------+----------+ | |->ε | | | ========================================== 由预测分析表中含有多重入口判定文法不是 LL(1)的