龙书 第四章课后作业答案

bexpr→bexpr or bterm|bterm

bterm→bterm and bfactor | bfactor

bfactor→not bfactor|(bexpr)|true |false

解1  非递归方法

1)消除左递归

bexpr→bterm A     

A→or bterm  A    

A→ε

bterm→bfactor B   

B→and bfactor B    

B→ε

bfactor→not bfactor

bfactor→(bexpr)

bfactor→true 

bfactor→false

2)求first集 与 follow集

针对以同一非总结符开头的产生式右部求first集  如果该非终结符能产生ε  则需要求其follow集   

bexpr→bterm Abterm  A)= {not,(,true,false}

A→or bterm  or bterm  A)={or}

A→ε                   follow(A）=follow(bexpr)= {$, )}

bterm→bfactor B         first(bfactor B)={not,(,true,false}               

B→and bfactor B  and bfactor B)={and}

B→ε                   follow(B）=follow(bterm)=first(A)

因为first(A)= {or , ε} 包含ε

 所以follow(B）=follow(bterm)

=first(A) ∪follow(A）-{ε}={or, $, )}

bfactor→not bfactor     first(not bfactor)={not}

bfactor→(bexpr)  (bexpr))={(}

bfactor→true            first(true)={true}

bfactor→false  false)={false}

3)根据步骤2）画预测分析表

4)根据步骤3）编写预测分析程序

下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。

repeat

    X=当前栈顶符号;a=当前输入符号；

    if X∈ＶT∪{#} then

        if X=a then

              if X≠# then {将X弹出,且前移输入指针}

        else error

    else 

        if M[X,a]=Y1Y2…Yk then

            {将X弹出;依次将Yk…Y2Y1压入栈；

             输出产生式X→Y1Y2…Yk }

        else error

until X=#

注：

如果考虑错误恢复，上面的预测分析表还显得简单，应该将每个非总结符的follow集作为同步(sync)记号，便于错误恢复。具体留给感兴趣的同学深入研究

解2：递归下降方法

①消除给定文法中的左递归，并提取公因子：

bexpr→bterm {or bterm }

    bterm→bfactor {and bfactor} 

    bfactor→not bfactor | (bexpr) | true |false 

② 用类Pascal语言写出其递归预测分析器

   PROCEDURE bexpr;

     BEGIN

       Bterm

       WHILE (lookahead =='or')

         BEGIN

           match ('or');

             bterm;

         END;

     END;

 PROCEDURE bterm;

     BEGIN

       bfactor;

       WHILE (lookahead =='and');

         BEGIN

           match ('and');

           bfactor;

         END;

     END;

   PROCEDURE bfactor;

     BEGIN

       if (llokahead=='not')

         then BEGIN

             match ('not');

             bfactor;

            END

        else if (lookahead=='(')

             then BEGIN

                 match ('(');

                 bexpr;

                 match(')');

               END

             else if (lookahead =='true')

                 then match ('true)

                 else if (lookahead=='false')

                     then match ('false');

                     else error;

     END;

P1784.24 图4-60给出了练习4.1中文法的算符优先关系，利用这些优先关系分析练习4.1(b)的句子。

S→(L)|a 

L→L,S|S

解：

对每个终结符或＄建立符号f与g，把f(和g)

分成一组。根据文法的算符优先关系表，画出如下的有向图。

优先函数如下：

用算符优先分析法分析句子(a,(a,a))   

另外2个句子的分析略。

(也可不必如上面先构造优先矩阵在分析，亦可直接分析)

P1794.35 考虑下面文法

E→E+T|T 

T→TF|F 

F→F*|a|b

a）试为该文法构造SLR语法分析表

解：

该文法的拓广文法G'为

(0) E' → E

(1) E → E+T

(2) E → T

(3) T → TF

(4) T → F

(5) F → F*

(6) F → a

(7) F → b

其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:

I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}

I1 ={E'→E·, E→E·+T}

I2 ={E→T·, T→T·F, F→·F*, F→·a, F→·b}

I3 ={T→F·, F→F·*}

I4 ={F→a·}

I5 ={F→b·}

I6 ={E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}

I7 ={T→TF·, F→F·*}

I8 ={F→F*·}

I9 ={E→E+T·, T→T·F, F→·F*, F→·a, F→·b}

求FOLLOW集：

    FOLLOW(E)={＋, ＄}

    FOLLOW(T)={＋, ＄, a, b}

    FOLLOW(F)={＋, ＄, a, b, *}

构造的SLR分析表如下：

显然，此分析表无多重定义入口，所以此文法是SLR文法。

P1794.37 a）证明下面的文法是LL(1)文法，但不是SLR(1)文法

S→AaAb|BbBa 

A→ε 

B→ε

解：

对于产生式S→AaAb|BbBa 来说

FIRST(AaAb)∩FIRST(BbBa)={a}∩{b}=Φ

而A，B∈VN仅有一条候选式。

因此，这个文法是LL(1)的。

下面构造这个文法的识别活前缀的DFA。

I0 = {S'→·S, S→·AaAb, S→·BbBa, A→·, B→·} 

I1 = {S'→S·}

I2 = {S→A·aAb}

I3 = {S→B·bBa}

I4 = {S→Aa·Ab, A→·}

I5 = {S→Bb·Ba, B→·}

I6 = {S→AaA·b}

I7 = {S→BbB·a}

I8 = {S→AaAb·}

I9 = {S→BbBa·}

由于FOLLOW(A)=FOLLOW(B)={a, b}

因此项目集I0中存在归约－归约冲突。在I0状态下，当输入符号是a或是b时，不知用A→ε还是B→ε进行归约。故此文法不是SLR(1)的。但是，此文法时LR(1)的。

P1794.40证明下面的文法是LR(1)文法

S→Aa| bAc| Bc| bBa 

A→d 

B→d

解

拓广文法为：

G' : (0) S'→S

          (1) S→Aa

         (2) S→bAc

         (3) S→Bc

         (4) S→bAa

         (5) A→d

         (6) B→d

有效项目集族为：

LR(1)项目集不存在冲突

该文法是LR(1)文法

LR(1)项目集不存在冲突

该文法是LR(1)文法