《语法树和推导过程》由会员分享，可在线阅读，更多相关《语法树和推导过程（3页珍藏版）》请在金锄头文库上搜索。
1、依据文法给出句子的语法树和推导过程，并计算短语、句柄7.已知文法 G(S)Sa | | (T)TT,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,Sa直接短语T,Sa句柄T,S9.已知文法 G(S)SaAcBeAAb| bBd(1)给出句子 abbcde的最左推导及画出语法树；(2)给出句型 aAbcde的短语、素短语。(1) S=aAcBe=
2、AAbcBe=abbcBe=abbcde(2) 短语: aAbcde, Ab, d素短语: Ab, d12.已知文法 G(S)EE+T | TTT*F| FF(E)| i(1) 给出句型 (i+i)*i+i 的最左推导及画出语法树；(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), (
3、E+T)*i, (E+T)*i+F素短语 i, E+T最左素短语 E+T3、对于文法 G(S): ）Ma L|(bS答：1） bMaLbS)(2） 短语: Ma)， (Ma)， b(Ma)b直接短语: Ma) 句柄: Ma)四、对于文法 G(E): (8 分)ET|E+TTF|T*FF(E)|i1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。答：1. (4 分 )ETF(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素
4、短语：T*F, iSb M( TM abL)ETF( E )E + TFiTT * F五 : 已知文法 G(S)：Sa|(T)TT,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 所示。S( T )T , SSa( T )SaaT , S图 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 , aS( T )T , ST , Sa( T )图 A-17 (T,a,(T)的语法树
