第03章 文法和语言 下载本文

第 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 开头的非负整数

第3题 为只包含数字、加号和减号的表达式,例如 9-2+5,3-1,7等构造一个文法。 答案: 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

试给出下述表达式的推导及语法树。 (5)i+(i+i) (6)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) 该文法是二义的吗?说明理由。 答案:(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 的逆} 答案:

(1)S→AA A→aAb|ε (2)S→1S0|A A→0A1|ε (3)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 题 习题7和习题 11 中的文法等价吗? 答案:等价。 第 18 题 解释下列术语和概念:

(1) 字母表

(2) 串、字和句子 (3) 语言、语法和语义 答案:

(1)字母表:是一个非空有穷集合。

(2)串:符号的有穷序列。 字:字母表中的元素。

句子:如果

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

(3)语言:它是由句子组成的集合,是由一组记号所构成的集合。程序设计的语言就是所

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

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

附加题

问题 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