PPT《3章 习题》

3章 习题

1、设有文法G[N]N→D|ND D→0|1|2|…|9 (1)试写出021和4321的最右推导和 最左推导.

(2)试举出三个无最右推导的句型. 解:(1)021的最左推导: N?ND?NDD?DDD?0DD ?02D?

021 021的最右推导: N?ND?N1?ND1?N21 ?D21?021 解:4321的最左推导: N?ND?NDD?NDDD?DDDD ?4DDD?43DD?432D?4321 4321的最右推导: N?ND?N1?ND1?N21 ?ND21?N321?D321?4321 (2)无最右推导的句型N?ND?N1?ND1?DD1?4D1

2、证明下列文法G[S] 是二义性文法: S→if E then S else S | if E then S解:设有if E1 then if E2 then S1 else S2 ,则有两棵语法树: If E Then S Else S S If E Then S 第一种: E1 E2 S1 S2 第二种: If E Then S Else S S If E Then S E1 E2 S1 S2

3、设有文法G[E]: E→T|E+T|E-T T→F|T*F|T/F F→i|(E)(1)试写出i*i/(i+i*i)的语法树. (2)试写出句型(F+i)-T*(F*i)的短语、最简单短语、和句柄. (3)试写出句型T*F*(T+i)的最右推导. 解:(1)??i*i/(i+i*i)的语法树 E T / F T * F T F i E ) ( + T E * F T F i T F i i i (2)语法树为: T * F T F i F E ) ( T * T E - E T F + T E T E ) ( F i F 短语:第一个F,F+i,i, 第二个F,i, F*i(F+i),(F*i), T*(F*i),(F+ i)-T*(F*i)简单短语:第一个F,i, 第二个Fi句柄:第一个F (3)最右推导 E?T?T*F?T*(E)?T*(E+T) ?T*(E+F)?T*(E+i)?T*(T+i) ? T*F*(T+i)

4、设有文法:S→AB A→Aa A→bB B→a B→Sb求bBABb和baabaab的全部短语、简单短语、句柄 解:(1)bBABb 短语:bB,AB,ABb简单短语:bB,AB句柄:bB A B S b B S b A B (2)baabaab A B S A a S b A B b B a b B a a 短语:第一个a,ba,baa, 第二个ba,baa,baab, 第三a,第四个a,baabaab简单短语:第一个a,第三个a,第四个a 句柄:第一个a