编译原理（第3版）第二章部分习题答案

1. 文法G=({A,B,C},{a,b,c},P,S)，其中P为

        S->Ac|aB

        A->ab

        B-bc

写出L(G[S])的全部元素。

解：L(G[S])的全部元素为{a,b,c}。

2. 文法G[N]为

        N->D|ND

        D->0|1|2|3|4|5|6|7|8|9|

G[N]的语言是什么？

解：G[N]的语言是以数字表示的数字串。

3.为只包含数字、加号和减号的表达式，例如9-2+5、3-1、7等构造一个文法。

解：A->ATA

        A->D|BD

        B->BD|C

        C->1|2|3|4|5|6|7|8|9

        T->+|-

        D->0|1|2|3|4|5|6|7|8|9

5.已知文法G[Z]:

        Z: := a Z b

        Z: :=a b

写出L(G[Z])的全部元素。

解：L(G[Z])的全部元素为{| n1}

6.已知文法G：

        <表达式>: := <项> | <表达式> + <项>

        <项>: := <因子> | <项> * <因子>

        <因子>: := (<表达式>) | i

试给出下列表达式的推导和语法树。

（4）i * i + i

（5）i + ( i+ i )

解：（4）i * i + i

最左推导：<表达式> => <表达式> + <项> => <项> + <项>

                                   => <项> * <因子> + <项> => <因子> * <因子> + <项>

                                   => i * <因子> + <项> => i * i + <项>

                                   => i * i + <因子> => i * i + i

最右推导：<表达式> => <表达式> + <项> => <表达式> + <因子> => <表达式> + i

                => <项> + i = > <项> * <因子> + i => <项> * i + i => <因子> * i + i => i * i + i

语法树：

 

 

（5）i + ( i+ i )

最左推导：<表达式> => <表达式> + <项> => <项> + <项> => <因子> + <项> => i + <项>

=> i + <因子> => i + (<表达式>) => i + (<表达式> + <项>) => i + (<项> + <项>)

=> i + (<因子> + <项>) => i + (i + <项>) => i + (i + <因子>) => i + (i + i)

最右推导：<表达式> => <表达式> + <项> => <表达式> + <因子> => <表达式> + (<表达式>)

=> <表达式> + (<表达式> + <项>) => <表达式> + （<表达式> + <因子>）

=> <表达式> + (<表达式> + i) => <表达式> + (<项> + i) => <表达式> + (<因子> + i)

=> <表达式> + (i + i) => <项> + (i + i) => <因子> + (i + i) => i + (i + i)

语法树：

 

 

 

 8.考虑下面的上下无关文法：

                                S->SS * | SS+ | a

（1）表明通过此文法如何生成串aa+a*,并为该串构造语法树。

（2）该文法生成的语言是什么？

解：（1）最左推导：S => SS* => SS+S* => aS+S* =>aa+S* =>aa+a*。

语法树：

 

 

 （2）该文法生成的语言是由+、*、a构成的表达式。

 9.已知文法S->S(S)S| 。

（1）该文法生成的语言是什么？

（2）该文法是二义的吗？说明理由。

解：（1）该文法生成的语言是嵌套的小括号。

（2）该文法是二义的，该文法有两棵不同的语法树。

 10.令文法G[E]为

E->T|E+T|E-T

T->F|T*F|T/F

F->(E)|i

证明E+T*F是它的一个右句型，指出这个句型的所有短语、直接短语和句柄。

解：最右推导：E => E+T => E+T*F => E+T*i => E+F*i => E+i*i => T+i*i =>F+i*i => i+i*i

短语：E+T*F，T*F

直接短语：T*F

句柄：T*F

11.一个上下无关文法生成句子abbaa的唯一语法树如下：

 

（1）给出该句子相应的最左推导和最右推导。

（2）该文法的产生式集合P可能有哪些元素？

（3）找出句子的所有短语、简单短语、句柄。

解：（1）最左推导：S => ABS => aBS => aSBBS => aBBS => abBS => abbS => abbAa => abbaa

最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => abbaa

（2）产生式集合P的元素有：S->ABS|Aa|，B->SBB|b，A->a。

（3）短语：a，，b，bb，aa，abbaa...

直接短语：a，，b

句柄：a

12.构造产生如下语言的上下文无关文法各一个：

（1）{ | n0}

（2）{ | mn0} 

 （3）{uab | u, {a,b}*  |u| = ||}

（4）{ | n2m0}

 解：（1）A->aAb|

（2）S-AB

          A->aA|

          B->aBb| 

（3）S->Ab

        A->aAb|aAa|bAa|bAb|a 

（4）S->aaSb|A

         A->aA| 

 13.构造产生如下语言的上下文无关文法各一个：

（1）{ | n,m0} 

（2）{ |  {a,b} *}

解：（1）S->AB

                A->aSbb|

                B-CB|

                C->c|   

（2）S->aSa|bSb|c

 15.分以下两种情形，各写一个文法，使其语言是十进制非负偶数的集合：

（1）允许0打头。

（2）不允许0打头。

解：（1）S->D|NT

                T->NT|D

                D->0|2|4|6|8

                N->1|2|3|4|5|6|7|8|9

（2）S->D|NT

        T->0|D|FT

        F->0|N

        D->0|2|4|6|8

        N->1|2|3|4|5|6|7|8|9

 18.给出生下述语言的一个3型文法：

（1）{ | n0}

（2）{ | n,m0}

（3）{ | n,m,k0}

解：（1）S->aS|

（2）S->aS|aB

        B->Bb|b

（3）A->aA|bB|cC|

        B->bB|cC|

        C->cC|