西理工编译原理试题集1-7(3)

stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other

则上面给出的if-then-else文法仍是二义性的。 2. 考虑文法G[bexpr]：

bexpr→bexpr or bterm | bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor| ( bexpr ) | true | false

(a) 请指出此文法的终结符号、非终结符号和开始符号。 (b) 试对于句子not(true or false)构造一棵分析树。 (c) 试说明此文法所产生的语言是全体布尔表达式。 答：

(a) 终结符号为：{or, and, not, (, ), true, false} 非终结符号为：{bexpr, bterm, bfactor} 开始符号为：bexpr

(b) 句子not(true or false)的分析树为： (c) 用归纳法说明如下：

(1) 不含运算的布尔表达式，常数true和false由此文法产生：

bexpr => bterm => bfactor => true bexpr => bterm => bfactor => false

(2) 设结论对于少于n(n≥1)个运算的布尔表达式成立，即若be1和be2是含有少于n个运算的布尔表达式，则有：bexpr=>+be1,bexpr=>+be2。

(3) 对于含有n个运算的布尔表达式，可表示成下面三种形式：

(a) (be1) or (be2) (b) (be1) and (be2) (c) not (be1)

对于(a)：bexpr => bexpr or bterm => bterm or bterm => bfactor or bterm => (bexpr) or bterm =>+(be1) or bterm => (be1) or bfactor => (be1) or (bexpr) =>+ (be1) or (be2) 同理，有：

Bexpr=>+ (be1) and (be2) Bexpr=>+ not (be1)

综上所述，此文法所产生的语言是全体布尔表达式。 3. 已知文法G[S],其产生式为：S→(S)| ?

（a）L(G)是什么？

（b）对于(a)的结果，请给出证明。 答：

(a) 解：L(G)?{()|n?0} (b)证明：

首先证明L(G)?{()|n?0} 对推导次数进行归纳

1):当推导次数为1时，使用产生式S→?，此时左括号与右括号个数为0 2):假设推导次数为n时(a)成立,即: S?(((...S...)))?(((......)))

n?1n?1n?1n?1?nnnn则推导次数为n+1次时，多使用一次产生式S→(S)即:

S?(((...S...)))?(((...S...)))?(((......)))

n?1n?1nnnn?推导次数为n+1次时(a)成立。

根据(1)(2)可得：L(G)?{()|n?0}

nn其次证明{(n)n|n?0}?L(G) 对n进行归纳

1):当n=0时,使用产生式S→? 即可；

2):假设当n=k时,结论成立，即(k)k?L(G)，下面证n=k+1时结论成立。 由(k)k?L(G)，其推导过程如下：

S?(((...S...)))?(((......)))

kkkk?当n=k+1时，推导过程如下：

S?(((...S...)))?(((...S...)))?(((......)))

kkk?1k?1k?1k?1?故(k?1)k?1?L(G)

根据(1)(2)可得：{(n)n|n?0}?L(G) 根据1，2可知：L(G)?{(n)n|?0} 4. 试构造生成下列语言的上下文无关文法： (1) { anbnci | n≥1, i≥0 -

(2) { w | w∈{a,b}+，且w中a的个数恰好比b多1 } (3) { w | w∈{a,b}+，且|a|≤|b|≤2|a| - 答：

（1）把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为： S → AB A → aAb|ab B → cB|ε

（2）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下： S → aE|Ea|bSS|SbS|SSb

E → aEbE|bEaE|ε

(3) 设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）： S → aSBS|BSaS|ε B → b|bb

5. 已知文法G[S]:

S→AB A→aA|a B→bB|b

求该文法所定义的语言。 答：

从规则2可推出: a,aa,aaa,?? 从规则3可推出: b,bb,bbb,?? 再从规则1可推出句子：

ab, aab, aabb, aaab, abbb,……

即，从S出发可推出多个a后跟多个b的字符串，且a的个数与b的个数不尽相同。 故： L(G)={ambn| m,n≥1}

6. 考虑下面上下文无关文法G[S]：

S→SS*|SS+|a

(1) 对于符号串aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。 (2)G[S]的语言是什么？ 答：

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

S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* 此文法生成串 aa+a*的最左推导：

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

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

7 令文法G为 N→ D | ND

D→ 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9 (1) G的语言L（G）是什么？

(2) 给出句子0127、34和568的最左推导和最右推导。 答： （1）

∵N N?ND?NDD?NDDD?NDDDD……?DD……D ∴L(G)=｛d(n+1)|n≥0, d∈{0, 1, …, 9}｝

允许以0开头的自然数（十进制无符号整数）； （2）

0127最左推导：N?ND?NDD?NDDD?DDDD?0DDD?01DD?012D?0127 0127最右推导：N?ND?N7?ND7?N27?ND27?N127?D127?0127 8 写一个文法，使其语言是奇数集，且每个奇数不以0开头。

答：（首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。

引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。）