清华大学：编译原理：chpt5练习答案

第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 |
+-------+--------------------+--------------------+
| 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．文法：
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)的。
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
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} |
+-------+--------------------+--------------------+
| 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)的。