Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
236 lines (154 sloc) 7.48 KB

4.2 节的练习

4.2.1

考虑上下文无关文法:

S -> S S + | S S * | a

以及串 aa+a* 。

  1. 给出这个串的一个最左推导
  2. 给出这个串的一个最右推导
  3. 给出这个串的一个语法分析树
  4. ! 这个文法是否为二义性的?证明你的回答。
  5. ! 描述这个语法生成的语言。

解答

  1. S =lm=> SS* => SS+S* => aS+S* => aa+S* => aa+a*
  2. S =rm=> SS* => Sa* => SS+a* => Sa+a* => aa+a*
![4 2 1](https://f.cloud.github.com/assets/340282/469058/c08b4f9c-b6af-11e2-8236-f79c6a56215a.gif)
  1. 非二义
  2. 包含加法和乘法的后缀表达式

4.2.2

对下列的每一对文法和串重复练习 4.2.1 。

  1. S -> 0 S 1 | 0 1 和串 000111

  2. S -> + S S | * S S | a 和串 +*aaa

  3. ! S -> S (S) S | ε 和串 (()())

  4. ! S -> S + S | S S | (S) | S * | a 和串 (a+a)*a

  5. ! S -> (L) | a 以及 L -> L, S | S 和串 ((a,a),a,(a))

  6. !! S -> a S b S | b S a S | ε 和串 aabbab

  7. 下面的布尔表达式对应的文法:

     bexpr -> bexpr or bterm | bterm
     bterm -> bterm and bfactor | bfactor
     bfactor -> not bfactor | (bexpr) | true | false

解答

1、

  1. S =lm=> 0S1 => 00S11 => 000111
  2. S =rm=> 0S1 => 00S11 => 000111
  3. 非二义
  4. 前导n个连续0,后跟n个连续1的串

2、

  1. S =lm=> +SS => +*SSS => +*aSS => +*aaS => +*aaa
  2. S =rm=> +SS => +Sa => +*SSa => +*Saa => +*aaa
  3. 非二义
  4. 包含加法和惩罚的前缀表达式

3、

  1. S =lm=> S(S)S => (S)S => (S(S)S)S => ((S)S)S => (()S)S => (()S(S)S)S => (()(S)S)S => (()()S)S => (()())S => (()())
  2. S =rm=> S(S)S => S(S) => S(S(S)S) => S(S(S)) => S(S()) => S(S(S)S()) => S(S(S)()) => S(S()()) => S(()()) => (()())
  3. 二义
  4. 所有对称的括号串

4、

  1. S =lm=> SS => S*S => (S)*S => (S+S)*S => (a+S)*S => (a+a)*S => (a+a)*a
  2. S =rm=> SS => Sa => S*a => (S)*a => (S+S)*a => (S+a)*a => (a+a)*a
  3. 二义
  4. 由加号、乘号和字符a和对称的括号组成的串,且加号不在开头和结尾位置,乘号不在开头位置

5、

  1. S =lm=> (L) => (L, S) => (L, S, S) => ((S), S, S) => ((L), S, S) => ((L, S), S, S) => ((S, S), S, S) => ((a, S), S, S) => ((a, a), S, S) => ((a, a), a, S) => ((a, a), a, (L)) => ((a, a), a, (S)) => ((a, a), a, (a))
  2. S =rm=> (L) => (L, S) => (L, (L)) => (L, (a)) => (L, S, (a)) => (L, a, (a)) => (S, a, (a)) => ((L), a, (a)) => ((L, S), a, (a)) => ((S, S), a, (a)) => ((S, a), a, (a)) => ((a, a), a, (a))
  3. 非二义
  4. 类似于python中的元组

6、

  1. S =lm=> aSbS => aaSbSbS => aabSbS => aabbS => aabbaSbS => aabbabS => aabbab

  2. S =rm=> aSbS => aSbaSbS => aSbaSb => aSbab => aaSbSbab => aaSbbab => aabbab

  3. 二义

  4. 数量相同的a和b组成的串

  5. 非二义,该文法生成布尔表达式

4.2.3

为下面的语言设计文法

  1. 所有由 0 和 1 组成的并且每个 0 之后至少跟着一个 1 的串的集合。
  2. ! 所有由 0 和 1 组成的回文集合。
  3. ! 所有由 0 和 1 组成的具有相同多个 0 和 1 的串的集合。
  4. !! 所有由 0 和 1 组成的并且 0 的个数和 1 的个数不同的串的集合。
  5. ! 所有由 0 和 1 组成的且不包含子串 011 的串的集合。
  6. !! 所有由 0 和 1 组成的形如 xy 的串的集合,其中 x<>y 且 x 和 y 等长。

解答

1、

S -> (0*1)*

2、

S -> 0S0 | 1S1 | ε

3、

S -> 0S1S | 1S0S | ε

5、

S -> 1*(0+1?)*

4.2.4

有一个常用的扩展的文法表示方法。在这个表示方法中,产生式体中的方括号和花括号是元符号,且具有如下含义:

  1. 一个或多个文法符号两边的方括号表示这些构造是可选的。因此,产生式 A -> X[Y]Z 和两个产生式 A -> XYZ 及 A -> XZ 具有相同的效果。
  2. 一个或多个文法符号两边的花括号表示这些符号可以重复任意多次(包括零次)。因此, A -> X{YZ} 和如下的无穷产生式序列具有相同的效果: A -> X, A -> XYZ, A -> XYZYZ, ... 等等。

正明这两个扩展并没有增加文法功能。也就是说,由带有这些扩展表示的文法生成的任何语言都可以由一个不带扩展表示的文法生成。

证明

扩展文法表示 不带扩展的文法表示
A -> X[Y]Z A -> XZ | XYZ
A -> X{YZ} A -> XB
B -> YZB | ε

4.2.5

使用练习 4.2.4 中描述的括号表示法来简化如下的语句块和条件语句的文法。

stmt -> if expr then stmt else stmt
      | if stmt them stmt
      | begin stmtList end
stmtList -> stmt; stmtList | stmt

解答

stmt -> if expr then stmt [else stmt]
      | begin stmtList end
stmtList -> stmt[; stmtList]

4.2.6

扩展练习 4.2.4 的思想,使得产生式体中可以出现文法符号的任意正则表达式。证明这个扩展没有使得文法可以定义任何新的语言。

证明

只要证明所有的正则文法均有等价的无扩展文法即可

4.2.7 !

如果不存在形如 S =*=> wXy =*=> wxy 的推导,那么文法符号 X 就被称为无用的。也就是说 X 不可能出现在任何句子的推导过程当中。

  1. 给出一个算法,从一个文法中消除所有包含无用符号的产生式。

  2. 将你的算法应用于以下文法:

     S -> 0 | A
     A -> AB
     B -> 1

4.2.8

图 4-7 中的文法可以生成单个数值标识符的声明,这些声明包含四种不同的、相互独立的数字性质。

stmt -> declare id optionList
optionList -> optionList option | ε
option -> mode | scale | precision | base
mode -> real | complex
scale -> fixed | floating
precision -> single | double
base -> binary | decimal
  1. 扩展图 4-7 中的文法,使得它可以允许 n 种选项 A_i,其中 n 是一个固定的数, i = 1, 2 , ..., n。选项 A_i 的取值可以是 a_i 或 b_i。你的文法发只能使用 O(n) 个文法符号,并且产生式的总长度页必须是 O(n) 的。

  2. ! 图 4-7 中的文法和它在 1 中的扩展支持相互矛盾或冗余的声明,比如:

    declare foo real fixed real floating

    我们可以要求这个语言的语法禁止这种声明。也就是说,由这个文法生成的每个声明中,n 种选项中的每一项都只有一个取值。如果我们这样做,那么对于任意给定的 n 值,合法声明的个数是有穷的。因此和任何有穷语法一样,合法声明组成的语言有一个文法(同时也有一个正则表达式)。最显而易见的文法是这样的:文法的开始符号对每个合法声明都是一个产生式,这样共有 n! 个产生式。该文法的产生式的总长度是 O(n*n!)。你必须做得更好:给出一个产生式总长度为 O(n2^n) 的文法。

  3. !! 说明对于任何满足 2 中的要求的文法,其产生式的总长度至少是 2^n 。

  4. 我们可以通过程序设计语言的语法来保证声明中的选项无冗余性、无矛盾。对于这个文法的可行性,本题 3 的结论说明了什么问题?

解答

1、

stmt -> declare id optionList
optionList -> optionList option | ε
option -> A_1 | A_2 | … | A_n
A_1 -> a_1 | b_1
A_2 -> a_2 | b_2
…
A_n -> a_n | b_n

显然这个文法符号的个数是 O(n) 的