第二章：习题2-4 Table表var x,y;procedure p;var a;procedure q;var b;beginb:=10;end;procedure s;var c,d;procedure r;var e,f;begincall q;end;begincall r;end;begincall s;end;begincall p;end根据：Page289，变量table:array[0..txmax] of record 结构体以及block函数得到下表，而表中各部分的含义，见教材Page18,Page19第三章文法和语言1.文法Ｇ＝({A,B,S},{a,b,c},P,S)S->Ac|aBA->abB->bc写出Ｌ(G)的全部元素5. 写一文法，使其语言是偶正整数的集合要求：(1)允许0打头(2)不允许0打头解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:S→AD|DA->AN|ND→0|2|4|6|8N->0|1|2|3|4|5|6|7|8|9(2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)P:S→PD|P0|DP->NR|NR->QR|QD→2|4|6|8N->1|2|3|4|5|6|7|8|9Q->0|1|2|3|4|5|6|7|8|9或：G[S]:S->D|BSB->1|2|3…|9|B0D->0|2|4|6|86. 已知文法G：<表达式>::=<项>|<表达式>+<项>|<表达式>-<项><项>::=<因子>|<项>*<因子>|<项>/<因子><因子>::=(<表达式>)|i。
试给出下述表达式的推导及语法树。
(1)i; (2)(i) (3)i*i;(4)i*i+i; (5)i+(i+i); (6)i+i*i。
解：(1)<表达式>=><项>=><因子>=>i(2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)(3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*<因子=>i*i(4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子>+<因子>=>i*i+i(5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)(6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i语法树见下图:7. 为句子i+i*i 构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。
<表达式>::=i|(<表达式>)|<表达式><运算符><表达式> <运算符>::=+|-|*|/解：为句子i+i*i 构造的两棵语法树如下：<表达式> <项> <因子> i<表达式> <项> <因子> ( <表达式> )<项> <因子> i<表达式> <项><项> * <因子> <因子> ii<表达式><表达式> + <项> <项> <项> * <因子> <因子> ii<因子> i<表达式><表达式> + <项> <项> <因子> i<因子> ( <表达式> ) <表达式> + <项> <项> <因子> i<因子> i<表达式><表达式> + <项> <项> <因子>i<项> * <因子> <因子> ii(1)i (2)(i) (3)i*i (4) i*i+i (5) i+(i+i) (6) i+i*i<表达式> <表达式> + <表达式> i <表达式> * <表达式> i i<表达式><表达式> * <表达式><表达式> + <表达式> i ii所以，该文法是二义的。
8. 习题1中的文法G[S]是二义的吗？为什么？答：是二义的。
因为对于句子abc 可以有两种不同的生成树，即：S=>Ac=>abc 和S=>aB=>abc 11. 令文法G[E]为： E →T|E+T|E-T T →F|T*F|T/F F →(E)|i证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
解：可为E+T*F 构造一棵语法树（见下图），所以它是句型。
从语法树中容易看出，E+T*F 的短语有：T*F 是句型E+T*F 的相对于T 的短语，也是相对于规则T →T*F 的直接短语。
E+T*F 是句型E+T*F 的相对于E 的短语。
句型E+T*F 的句柄（最左直接短语）是T*F 。
12. 下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。
证明：<E><T><F><MOP><POP>是G[<E>]的句型，并指出该句型的所有短语、直接短语和句柄。
<E>→<E><T><POP>|<T> <T>→<T><F><MOP>|<F> <F>→a|b|c <POP>→+|- <MOP>→*|/ 解：(1)计算文法G[E]的语言：由于L(T)={(a|b|c)((a|b|c)(*|/))n|n>=0}所以L(E)={L(T)(L(T)(+|-))n |n>=0}(2)该文法的一个句子是aab*+,它的语法树是：(3) 证明：<E><T><F><MOP><POP>是G[<E>]的句型，并指出该句型的所有短语、直接短语和句柄。
由于下面的语法树可以生成<E><T><F><MOP><POP>，所以它是G[<E>]的句型。
EE + T T *F <E><E> <T> <POP><T> <F> <MOP> <T> <F> a <F> ab *+<E><E> <T> <POP><T> <F> <MOP>由于<E> => <E><T><POP>,且<T> => <T><F><MOP>,所以<T><F><MOP>是句型<E><T><F><MOP><POP>相对于<T>的短语，也是相对于规则<T> → <T><F><MOP>的直接短语。
由于<E> => <E> 且<E> => <E><T><F><MOP><POP>,所以<E><T><F><MOP><POP>是句型<E><T><F><MOP><POP>相对于<E>的短语。
显然，句型<E><T><F><MOP><POP>的句柄是<T><F><MOP>。
14. 给出生成下述语言的上下文无关文法：（1）{a n b n a m b m|n,m>=0}（2）{1n0m1m0n|n,m>=0}（3）{WaW t|W属于{0|a}*,W表示W t的逆}解：（1）所求文法为G[S]=({S,A},{a,b},P,S),其中P为：S→ABA→aAb|εB→aBb|ε（2）所求文法为G[S]=({S,A},{0,1},P,S),其中P为：S→1S0|AA→0A1|ε（3）W属于{0|a}*是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}如果W=aa0a00,则W t=00a0aa。