4.3 节的练习

4.3.1

下面是一个只包含符号 a 和 b 的正则表达式文法。它使用 + 替代表示并运算的字符 | ，以避免和文法中作为元符号使用的竖线相混淆：

rexpr -> rexpr + rterm | rterm
rterm -> rterm rfactor | rfactor
rfactor -> rfactor * | rprimary
rprimary -> a | b

1. 对这个文法提取左公因子。
2. 提取左公因子的变换能使这个文法适用于自顶向下的语法分析技术吗？
3. 提取左公因子之后，从原文法中消除左递归。
4. 得到的文法适用于自顶向下的语法分析吗？

解答

1. 无左公因子

2. 不适合

3. 消除左递归

       rexpr -> rterm A
           A -> + rterm A | ε
       rterm -> rfactor B
           B -> rfactor B | ε
     rfactor -> rprimary C
           C -> * C | ε
    rprimary -> a | b

4. 适合？

4.3.2

对下面的文法重复练习 4.3.1

1. 练习 4.2.1 的文法
2. 练习 4.2.2-1 的文法
3. 练习 4.2.2-3 的文法
4. 练习 4.2.2-5 的文法
5. 练习 4.2.2-7 的文法

解答

1. S -> S S + | S S * | a

   1. 提取左公因子

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

   2. 不适合

   3. 消除左递归

       // initial status
       1）S -> S S A | a
       2) A -> + | *
      
       // i = 1
       1) S -> a B
       2) B -> S A B | ε
       3) A -> + | *
      
       // i = 2, j = 1
       1) S -> a B
       2) B -> a B A B | ε
       3) A -> + | *
      
       // i = 3, j = 1 ~ 2
       // nothing changed

   4. 适合

2. S -> 0 S 1 | 0 1

   1. 提取左公因子

       S -> 0 A
       A -> S 1 | 1

   2. 不适合，有间接左递归

   3. 消除左递归

       // initial status
       1) S -> 0 A
       2) A -> S 1 | 1
      
       // i = 1
       // nothing changed
      
       // i = 2, j = 1
       1) S -> 0 A
       2) A -> 0 A 1 | 1

   4. 合适

3. S -> S (S) S | ε

   1. 无左公因子

   2. 不合适

   3. 消除左递归

       // initial status
       1) S -> S (S) S | ε
      
       // i = 1
       1) S -> A
       2) A -> (S) S A | ε
      
       // i = 2, j = 1
       // nothing changed

   4. 合适

4. S -> (L) | a 以及 L -> L, S | S

   1. 无左公因子

   2. 不合适

   3. 消除左递归

       // initial status
       1) S -> (L) | a
       2) L -> L, S | S
      
       // i = 1
       // nothing changed
      
       // i = 2, j = 1
       1) S -> (L) | a
       2) L -> (L) A | a A
       3) A -> , S A | ε
      
       // i = 3, j = 1~2
       // nothing changed

   4. 合适

4.3.3 ！

下面文法的目的是消除 4.3.2 节中讨论的 “悬空-else 二义性”：

stmt -> if expr then stmt
      | matchedStmt
matchedStmt -> if expr then matchedStmt else stmt
             | other

说明这个文法仍然是二义性的。

解答

看一段示范代码，我们通过缩进来表示代码解析的层次结构

if expr 
then 
    if expr 
    then matchedStmt 
    else
        if expr
        then matchedStmt
else stmt

这段代码还可以被解析成

if expr 
then 
    if expr 
    then matchedStmt 
    else
        if expr
        then matchedStmt
        else stmt

所以这仍然是一个二义性的文法。原因在于 matchedStmt -> if expr then matchedStmt else stmt 中的最后一个 stmt，如果包含 else 语句的话，既可以认为是属于这个 stmt 的，也可以认为是属于包含这个 matchedStmt 的语句的。