3章 习题 1、设有文法G[N]: N→D|ND D→0|1|2|…|9 (1)试写出021和4321的最右推导和 最左推导。 (2)试举出三个无最右推导的句型。
解:(1)021的最左推导： NNDNDDDDD0DD 02D 021 021的最右推导： NNDN1ND1N21 D21021
解:4321的最左推导： NNDNDDNDDDDDDD 4DDD43DD432D4321 4321的最右推导： NNDN1ND1N21 ND21N321D3214321 (2)无最右推导的句型 NNDN1ND1DD14D1
2、证明下列文法G[S] 是二义性文法： S→if E then S else S | if E then S 解：设有if E1 then if E2 then S1 else S2 ,则有两棵语法树:
S If E Then 第一种： E1 E2 S1 S2 If E Then S Else
第二种： If E Then S Else E1 E2 S1 S2 If E Then S
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 * i ) ( +
(2)语法树为： T * F i E ) ( - +
短语：第一个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)最右推导 ETT*FT*(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 A B S b 短语：bB,AB,ABb 简单短语：bB,AB 句柄：bB
(2)baabaab A B S a b
短语：第一个a,ba,baa, 第二个ba,baa,baab, 第三a,第四个a,baabaab 简单短语：第一个a，第三个a， 第四个a 句柄：第一个a