第 3 章 文法和语言

第 1 题 文法 G＝({A,B,S},{a,b,c},P,S)其中 P 为： S→Ac|a A→ab B→bc

写出 L(G[S])的全部元素。 答案：L(G[S])={abc}

第 2 题 文法 G[N]为： N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？

答案: G[N]的语言是 V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D 或者：允许 0 开头的非负整数

第３题 为只包含数字、加号和减号的表达式，例如 9-2＋5，3-1，７等构造一个文法。 答案： G[S]:

S->S+D|S-D|D

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

第 4 题 已知文法 G[Z]：Z→aZb|ab 写出 L(G[Z])的全部元素。 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb

L(G[Z])={a b |n>=1}

第 5 题

写一文法，使其语言是偶正整数的集合。 要求： (1) 允许 0 打头； (2)不允许 0 打头。 答案：

(1)允许 0 开头的偶正整数集合的文法

E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许 0 开头的偶正整数集合的文法

E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第 6 题 已知文法 G：

<表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i

试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i

答案：

(5) <表达式>

=><表达式>＋<项> =><表达式>＋<因子>

=><表达式>＋（<表达式>）

=><表达式>＋（<表达式>＋<项>） =><表达式>＋（<表达式>＋<因子>） =><表达式>＋（<表达式>＋i） =><表达式>＋（<项>＋i） =><表达式>＋（<因子>＋i） =><表达式>＋（i＋i） =><项>＋（i＋i） =><因子>＋（i＋i） =>i＋（i＋i）

(6) <表达式>

=><表达式>＋<项>

=><表达式>＋<项>*<因子> =><表达式>＋<项>*i =><表达式>＋<因子>*i =><表达式>＋i*i =><项>＋i*i =><因子>＋i*i =>i＋i*i 第 7 题

证明下述文法 G[〈表达式〉]是二义的。 〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/

答案：可为句子 a+a*a 构造两个不同的最右推导:

最右推导 1 〈表达式〉 〈表达式〉〈运算符〉〈表达式〉

〈表达式〉〈运算符〉a 〈表达式〉* a 〈表达式〉〈运算符〉〈表达式〉* a 〈表达式〉〈运算符〉a * a 〈表达式〉+ a * a a + a * a 〈表达式〉最右推导 2 〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉 a 〈表达式〉〈运算符〉〈表达式〉 * a 〈表达式〉〈运算符〉a * a 〈表达式〉+ a * a a + a * a

第 8 题文法 G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 答案：对于串 abc

(1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。

或者：对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。

S S

a

B

A

c

a

b

c

b

第 9 题

考虑下面上下文无关文法： S→SS*|SS+|a

(1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。 (2)G[S]的语言是什么？

答案：

(1)此文法生成串 aa+a*的最右推导如下

S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 第 10 题 文法 S→S(S)S|ε

(1) 生成的语言是什么？

(2) 该文法是二义的吗？说明理由。 答案：（１） 嵌套的括号

（２） 是二义的，因为对于（）（）可以构造两棵不同的语法树。 第 11 题

令文法 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*F 句型 此句型相对于 E 的短语有:E+T*F；相对于 T 的短语 有 T*F 直接短语为：T*F 句柄为：T*F

第 13 题 一个上下文无关文法生成句子 abbaa 的推导树如下：

(1)给出串 abbaa 最左推导、最右推导。

S (2)该文法的产生式集合 P 可能有哪些元素？

(3)找出该句子的所有短语、直接短语、句柄。

A B S

a

S ε B b B A b a a

答案：

(1)串 abbaa 最左推导:

S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导：

S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa

(2)产生式有：S→ABS |Aa|ε A→a B→SBB|b 可能元素有：ε aa ab abbaa aaabbaa ……

(3)该句子的短语有： a 是相对 A 的短语； ε 是相对 S 的短语； b 是相对 B 的短语；εbb 是相对 B 的短语；aa 是相对 S 的短语；aεbbaa 是相对 S 的短语 直接短语有：a ε b 句柄是：a

第 14 题 给出生成下述语言的上下文无关文法：

（1）{ anbnambm| n，m>=0} （2）{ 1n0m 1m0n| n，m>=0}

（3）{WaWr|W 属于{0|a}*，Wr 表示 W 的逆} 答案：

（１）S→AA A→aAb|ε （２）S→1S0|A A→0A1|ε （３）S→0S0|1S1|ε

第 16 题 给出生成下述语言的三型文法：

(1){an|n >=0 }

(2) { anbm|n,m>=1 } (3){anbmck|n,m,k>=0 } 答案：

(1) S→aS|ε

(2) S→aA A→aA|B B→bB|b (3) A→aA|B B→bB|C C→cC|ε

第 17 题 习题７和习题 11 中的文法等价吗？ 答案：等价。 第 18 题 解释下列术语和概念：

（１） 字母表

（２） 串、字和句子 （３） 语言、语法和语义 答案：

（１）字母表：是一个非空有穷集合。

（２）串：符号的有穷序列。 字：字母表中的元素。

句子：如果

则称 x 是文法 G 的一个句子。

（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所

有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合。

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。

附加题

问题 1：给出下述文法所对应的正规式：

S→0A|1B A→1S|1 B→0S|0 答案：R = (01 | 10) ( 01 | 10 )*

问题 2：已知文法 G[A]，写出它定义的语言描述

G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC

答案: G[A]定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同. 问题 3： 给出语言描述，构造文法.

构造一文法,其定义的语言是由算符+, *, (,)和运算对象 a 构成的算术表达式的集合.

答案一：

G[E] E→E+T|T T→T* F|F F→(E)|a 答案二：

G[E] E→E+E|E* E|(E)|a

问题 4：已知文法 G[S]: S→dAB

A→aA|a B→ε|bB

相应的正规式是什么？G[S]能否改写成为等价的正规文法？ 答案：正规式是 daa*b*； 相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε 问题 5：已知文法 G： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i

试给出下述表达式的推导及语法树 (1) i; (2) i*i+i (3) i+i*i (4) i+(i+i)

答案：

(1)E=>T=>F=>i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)

问题 6：已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a

试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.

答案： 该句型对应的语法树如

下：

该句型相对于 E 的短语有 FF^^* 相对于 T 的短语有 FF^^*,F 相对于 F 的短语有 F^;F^^ 简单短语有 F;F^ 句柄为 F.

问题 7： 适当变换文法，找到下列文法所定义语言的一个无二义的文法：

S → SaS |SbS |ScS |d 答案：该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。

设 a、b 和 c 的优先级别依次增高，根据优先级联规则将文法变换为：

S → SaS | A A → AbA | C C → CcC | d 规定结合性为左结合，进一步将文法变换为： S → SaA| A A → AbC |C C → CcF | F F → d

该文法为非二义的。 问题 8：

构造产生如下语言的上下文无关文法：

（1） {abc| n，m ≥ 0} （2） {abc

nm2m mn

n2nm

| n，m ≥ 0}

（3） { ab| m ≥ n }

（4）{ a b c d | m+n = p+q }

（5）{ uawb | u,w ∈{a, b}* ∧ | u | = | w | }

答案：（1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如 anb2n 和 形如 cm 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是 特别指明，通常可以忽略这一点。

m

n

p

q