句柄%……
1. 已知文法G(S)：
S —>a|(T) T —>T,S|S
①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。
解：（1）最左推导：S ⇒(T)⇒(T,S)⇒(S,S) ⇒(a,S)⇒(a,(T))⇒(a,(T,S))⇒(a,(S,S))⇒(a,(a, S))⇒(a,(a,a))
语法树：如图A-16所示。
图A-16 (a,(a,a))的语法树
（2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。
短语：a || T,a || (T) || T , a , (T) || (T , a , (T)) 直接短语：a || (T) 素短语：a || (T) 最左素短语：a 句柄：a
活前缀：ε || ( || (T || (T , || (T , a
S ( T )a
( T )
图A-17 (T,a,(T))的语法树
四、对于文法G(E): (8分)
E →T|E+T T →F|T*
F F →(E)|i
1.
写出句型(T*F+i)的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语、句柄和素短语。
答： 1. (4分)
E ⇒T ⇒
F ⇒(E) ⇒(E+T) ⇒(E+F) ⇒(E+i) ⇒(T+i) ⇒(T*F+i)
2. (4分)
短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i 句柄：T*F 素短语：T*F, i 2．对于文法G[S]：S →AB ，A →Aa|bB ，B →a|Sb 求句型baSb 的全部短语、直接短语和句柄？
句型baSb 的语法树如图五(2)所示。
解：baSb 为句型baSb 的相对于S 的短语，ba 为句型baSb 的相对于A 的短语，Sb 为句型baSb 的相对于B 的短语，且为直接短语，a 为句型baSb 的相对于B 的短语，且为直接短语和句柄。
7.已知文法G(S) S→a | ^ | (T) T→T,S | S
(1) 给出句子(a,(a,a))的最左推导；
(2) 给出句型((T,S),a)的短语, 直接短语，句柄。
最左推导
S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 短语
((T,S),a) (T,S),a (T,S) T,S a
直接短语 T,S a 句柄 T,S
12.已知文法G(S) E →E+T | T T →T*F| F F →(E)| i
(1) 给出句型 (i+i)*i+i 的最左推导及画出语法树；
A S
B
b B S
a b
(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。
(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T
=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T =>(i+i)*i+F=>(i+i)*i+i
(2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F
素短语 i, E+T
最左素短语 E+T
9.已知文法G(S)
S→aAcBe
A→Ab| b
B→d
(1)给出句子abbcde的最左推导及画出语法树；
(2)给出句型aAbcde的短语、素短语。
(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde
(2) 短语: aAbcde, Ab, d
素短语: Ab, d
7、文法G：E→E+T|T
T→T*P|P
P→(E)|I
则句型P+T+i的句柄和最左素短语为。
a.P+T和i
b. P和P+T
c. i和P+T+i
d.P和T
由图2-8-1的语法树和优先关系可以看出应选b。
4、有文法G：S→aAcB|Bd
A→AaB|c
B→bScA|b
（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；
（2）写出句子acabcbbdcc的最左推导过程。
【解答】（1）分别画出对应两句型的语法树，如图2-8-2所示
句柄:AaB Bd
语法树
（2）句子acabcbbdcc 的最左推导如下：
S ⇒aAcB ⇒aAaBcB ⇒acaBcB ⇒acabcB ⇒acabcbScA ⇒acabcbBdcA
⇒acabcbbdcA ⇒acabcbbdcc 5、对于文法G[S]：
S →（L ）|aS|a L →L, S|S （1）画出句型（S,（a ））的语法树。
（2）写出上述句型的所有短语、直接短语、句柄和素短语。
【解答】 （1）句型（S,（a ）
（2）由图2-8-3可知：
①短语：S 、a 、(a)、S,(a)、(S,(a))②直接短语：a 、S ；
③句柄：S ；
④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；
因此素短语为a 。
6、考虑文法G[T]： T →T*F|F F →F ↑P|P P →（T ）|i
证明T*P ↑（T*F 【解答】 首先构造T*P ↑（T*F ）的语法树如图2-8-4 由图2-8-4可知，T*P ↑（T*F ）是文法G[T]直接短语有两个，即P 和T*F ；句柄为P 。
设有文法G[S]为： S →a|b|(A)
A →SdA|S
（1） 完成下列算符优先关系表，见表5-7-1，并判断
G[S]是否为算符优先文法。
表5-7-1 算符优先关系表
（2）给出句型（SdSdS ）的短语、简单短语、句柄、素短语和最左素短语。
（3）给出输入串（adb ）#的分析过程。
解答：
（1）先求文法G[S]的FIRSTVT 集和LASTVT 集：
由S →a|b|(A)得：FIRSTVT(S)={a,b,( );
由A →Sd …得：FIRSTVT(A)={d};又由A →S …得：FIRSTVT(S) ⊂ FIRSTVT(A)，即FIRSTVT(A)={d,a,b,(};
由S →a|b|(A)得；LASTVT(S)={a,b,}};
由A →…dA 得：LASTVT(A)={d},又由A →S 得：LASTVT(S) ⊂ LASTVT(A)，即LASTVT(A)={d,a,b,)}。
构造优先关系表方法如下：
① 对P →…ab …，或P →…aQb …，有a ≖b; ② 对P →…aR …，而b ∈FIRSTVT(R)，有a ⋖b; ③ 对P →…Rb …，而a ∈FIRSTVT(R)，有a ⋗b 。
由此得到：
① 由S →(A)得：(≖);
② 由S →(A …得：(⋖FIRSTVT(A)，即：(⋖d,(⋖a ,(⋖b,(⋖(;由A →…dA 得：d ⋖FIRSTVT(A)， 即：d ⋖d,d ⋖a,d ⋖b,d ⋖(;
③ 由S →A)得，LASTVT(A)⋗)，即：d ⋗),a ⋗),b ⋗),)⋗);由A →Sd …得：LASTVT(S)⋗d ，即：a ⋗d,b ⋗d,)⋗d;
此外，由#S#得：#≖#；
由#⋖FIRSTVT(S)得：#⋖a,#⋖b,#⋖(；脂由LASTVT(S)⋗#得：d ⋗#,a ⋗#,b ⋗#,)⋗#。
最后得到算符优先关系表，见表5-7-2。
表5-7-2 算符优先关系表
由表5-7-2可以看出，任何两个终结符之间至少只满足≖、⋖、⋗三种优先关系之一，故G[S]为算符优先文法。
（2）为求出句型（SdSdS ）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图5-7-3所示。
由图5-7-3得到： 短语：S ，SdS ，SdSdS ，（SdSdS ）
简单短语（即直接短语）：S 句柄（即最左直接短语）：S
素短语：SdS ，它同时也是该句型的最左素短语。
（3）输入串（adb）#的分析过程见表5-7-4 表5-7-4 输入串（adb）#的分析过程。