第3章 文法和语言.doc

第三章 文法和语言（习题参考答案）
1、文法G=({A,B,S},{a,b,c},P,S),其中P为：
S->Ac|aB A->ab B->bc
写出L（G [S]）的全部元素。
【解】S=>Ac=>abc
或S=>aB=>abc
所以L(G[S])={abc}
2、文法G[N]为：
N->D|ND
D->0|1|2|3|4|5|6|7|8|9
G[N]的语言是什么？
【解】
N=>ND=>NDD.... =>NDDDD...D=>D......D
G[N]的语言是V+,其中V={0,1,2,3,4,5,6,7,8,9}
或：
解: N NDn-1
Dn
{0,1,3,4,5,6,7,8,9}+
∴L(G[N])= {0,1,3,4,5,6,7,8,9}+

5. 写一文法，使其语言是偶正整数的集合
要求：(1) 允许0打头; (2) 不允许0打头
解：
(1) G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
S->PD|D
P->NP|N
D->0|2|4|6|8
N->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|D
P->NR|N
R->QR|Q
D->2|4|6|8
N->1|2|3|4|5|6|7|8|9
Q->0|1|2|3|4|5|6|7|8|9
6. 已知文法G：
<表达式>::=<项>|<表达式>+<项>|<表达式>-<项>
<项>::=<因子>|<项>*<因子>|<项>/<因子>
<因子>::=(<表达式>)|i。
试给出下述表达式的推导及语法树。
(1)i; (2)(i) (3)i*i;
(4)i*i+i; (5)i+(i+i); (6)i+i*i。
解：
(1) v=<表达式>=><项>=><因子>=>i
(2) v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)
(3) v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i
(4) v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项> =><因子>*<因子>+<因子>=>i*i+i
(5) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)=> i+(<表达式>+<项>)
=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)
(6) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i
语法树见下图（略）

7. 为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。
<表达式>::=i|(<表达式>)|<表达式><运算符><表达式>
<运算符>::=+|-|*|/
解：
为句子i+i*i构造的两棵语法树如下：（略）

所以，该文法是二义的。

8. 习题1中的文法G[S]是二义的吗？为什么？
答：
是二义的。因为对于句子abc可以有两种不同的生成树，即：S=>Ac=>abc和S=>aB=>abc
两棵语法树如下：（略）

9.考虑下面上下文无关文法：
S→SS*|SS+|a
(1) 表明通过此文法如何生成串aa+a*，并为该串构造推导树。
(2) 该文法生成的语言是什么？
【解】
(1) S=>SS*
=>SS+S*
aa+a*
该串的推导树如下：

(2) 该文法生成的语言是只含+、*的算术表达式的逆波兰表示。

11. 令文法G[E]为：
ET|E+T|E-T
TF|T*F|T/F
F(E)|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
解：可为E+T*F构造一棵语法树（见下图），所以它是句型。

从语法树中容易看出，E+T*F的短语有：
T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*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*+,它的语法树是：

证明：<E><T><F><MOP><POP>是G[<E>]的句型，并指出该句型的所有短语、直接短语和句柄。
由于下面的语法树可以生成<E><T><F><MOP><POP>，所以它是G[<E>]的句型。

由于<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>。

13.一个上下文无关文法生成句子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)为方便叙述将句型abbaa写作a1b1b2a2a3
该句子的短语有：a1, ε, b1, b2, a2, b1b2, a2 a3, a1b1b2a2a3
该句子的直接短语有：a1, ε, b1, b2, a2
该句子的句柄为：a1

14. 给出生成下述语言的上下文无关文法：
（1）{anbnambm|n,m>=0}
（2）{1n0m1m0n|n,m>=0}
（3）{WaWt|W属于{0|a}*,W表示Wt的逆}
解：
（1）所求文法为G[S]=({S,A},{a,b},P,S),
其中P为：
S->AA
A->aAb|ε

（2）所求文法为G[S]=({S,A},{0,1},P,S),
其中P为：
S->1S0|A
A->0A1|ε
（3）W属于{0|a}*是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}
如果W=aa0a00,则Wt=00a0aa。
所求文法为G[S]=({S,P,Q},{0,a},P,S),
其中P为：
S->0S0|aSa|a

15. 语言{WaW}和{anbmcndm}是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？
答：生成语言{WaW}的文法非常简单，如
G[S]: S->WaW
W->aW|bW|ε
可见G[S]是上下文无关的。
生成语言{ anbmcndm }的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关文法。这是因为要在ancn的中间插入bm,而同时要在其后面插入dm。即a,c相关联，b,d相关联。
这说明对语言的限定越多（特别是语言中的符号前后关联越多），生成它的文法越复杂，甚至于很难找到一个上下文法无关文法。

16．给出生成下述语言的三型文法：
(1){an|n>=0}
(2){anbm|n,m>=1}
(3){anbmck|n,m,k>=0}
解：
(1) 生成的3型文法是：
G[S]：S->aS|ε
(2) 生成的2型文法是：
G[S]: S->AB
A->aA|a
B->bB|b
生成的3型文法是：
G[S]： S->aP
P->aP|bD
D->bD|ε
(3) 生成的2型文法是：
G[S]: S->ABC
A->aA|ε
B->bB|ε
C->cC|ε
生成的3型方法是：
G[S]： A->aA|bB|cC|ε
B->bB|cC|ε
C->cC|ε