编译原理作业集-第二章

七、应用题：

1. 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(else悬挂)文法的二义性：

stmt → if expr then stmt | matched-stmt

matched-stmt→ if expr then matched-stmt else stmt | other expr→e

考虑句子if e then if e then other else if e then other else other，试说明此文法仍然是二义性的。 答：

1. 考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other 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)n|n?0} (b)证明：

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

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

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

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

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

根据(1)(2)可得：L(G)?{()|n?0} 其次证明{()|n?0}?L(G) 对n进行归纳

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

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

kkkknnnnS?(((...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