编译原理CH4-3

问题：

对于以下正则表达式文法（其中 + 表示并运算而非加法）：

1
2
3
4
rexpr    -> rexpr + rterm | rterm  
rterm    -> rterm rfactor | rfactor  
rfactor  -> rfactor * | rprimary  
rprimary -> a | b

请完成以下任务：

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

答案：

  1. 是否有左公因子？
    无左公因子。

    解释：
    左公因子是指两个产生式右部具有相同前缀，例如 A -> αβ1 | αβ2。在该文法中，每一对产生式虽然有左递归，但右部之间并无公共前缀可提取，因此无需进行左公因子提取。

  2. 提取左公因子的变换能否使该文法适用于自顶向下语法分析？
    不能。

    解释：
    适用于自顶向下语法分析的关键是：文法不能有左递归。虽然提取左公因子有助于解决回溯问题，但本例中并无左公因子，而且问题在于存在直接左递归，例如 rexpr -> rexpr + rterm，这会导致递归下降分析器陷入无限递归。因此仅仅考虑左公因子并不能解决问题。

  3. 消除左递归：

    消除左递归后得到的文法如下：

    1
    2
    3
    4
    5
    6
    7
    rexpr    -> rterm A  
    A        -> + rterm A | ε  
    rterm    -> rfactor B  
    B        -> rfactor B | ε  
    rfactor  -> rprimary C  
    C        -> * C | ε  
    rprimary -> a | b

    解释：
    使用标准的消除直接左递归方法。例如，rexpr -> rexpr + rterm | rterm 改写为：

    1
    2
    rexpr -> rterm A  
    A     -> + rterm A | ε

    类似地处理 rterm 和 rfactor。

  4. 新文法是否适用于自顶向下的语法分析？
    适合。

    解释：
    消除了所有的左递归，且文法不再存在二义性或左公因子，因此适合用于递归下降分析器或LL(1)语法分析。

🌟问题：

对以下各个文法，完成如下任务：

  1. 提取左公因子（如有）。
  2. 判断是否适用于自顶向下语法分析（如 LL(1)）。
  3. 消除左递归（如有左递归）。
  4. 判断处理后的文法是否适用于自顶向下语法分析。

🧩文法一：

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

✅答案：

  1. 提取左公因子：

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

  2. 适用于自顶向下分析？
    ❌不适合（仍有左递归）

  3. 消除左递归过程：

    1
    2
    3
    S -> a B  
    B -> S A B | ε  
    A -> + | *

  4. 是否适合？
    ✅适合。消除左递归后，结构清晰，适合递归下降等自顶向下分析。

🧩文法二：

S -> 0 S 1 | 0 1

✅答案：

  1. 提取左公因子：

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

  2. 适用于自顶向下分析？
    ❌不适合（A -> S 1 | 1 有间接左递归）

  3. 消除左递归过程：

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

  4. 是否适合？
    ✅适合，左递归已消除，文法可以递归下降。

🧩文法三：

S -> S (S) S | ε

✅答案：

  1. 左公因子：
    ❌无左公因子

  2. 适用于自顶向下分析？
    ❌不适合（存在左递归）

  3. 消除左递归过程：

    1
    2
    S -> A  
    A -> (S) S A | ε

  4. 是否适合？
    ✅适合，左递归消除后适合自顶向下分析。

🧩文法四：

S -> (L) | a
L -> L, S | S

✅答案：

  1. 左公因子：
    ❌无左公因子

  2. 适用于自顶向下分析？
    ❌不适合（L 有左递归）

  3. 消除左递归过程：

    1
    2
    3
    S -> (L) | a  
    L -> S A  
    A -> , S A | ε

  4. 是否适合？
    ✅适合，已消除左递归并规范化结构。

🌟问题：

考虑如下文法，其目的是为了消除 if-then-else 的“悬空 else（dangling else）”二义性问题：

1
2
3
4
5
stmt        -> if expr then stmt  
             | matchedStmt  

matchedStmt -> if expr then matchedStmt else stmt  
             | other

请回答以下问题：

说明该文法是否仍然是二义性的？请解释。

✅答案：

该文法仍然是二义性的。

🔍解释：

我们用一段嵌套的 if-then-else 代码来说明问题。考虑下面的代码示例（使用缩进表示语法层次）：

1
2
3
4
5
6
7
8
if expr
then
    if expr
    then matchedStmt
    else
        if expr
        then matchedStmt
else stmt

这个程序片段可以有两种不同的解析方式：

⛓️ 解析方式一（else 匹配最近的 if）：

1
2
3
4
5
6
7
8
if expr
then
    if expr
    then matchedStmt
    else
        if expr
        then matchedStmt
else stmt

在这种解析中，最后一个 else stmt 被绑定到了最内层的 if。

🔗 解析方式二（else 匹配最外层的 if）：

1
2
3
4
5
6
7
8
if expr
then
    if expr
    then matchedStmt
    else
        if expr
        then matchedStmt
        else stmt

在这种解析中，else stmt 被绑定到了最外层的 if，即使中间的 if expr then matchedStmt 看起来也能接受 else。

🎯关键问题：

文法中：

1
matchedStmt -> if expr then matchedStmt else stmt

其中的 最后一个 stmt 可以是：

  • 一个含有 else 的 stmt（从而将 else 绑定到这里），
  • 或者是一个包含在外层的 stmt 中的部分（将 else 绑定到外层）。

这就产生了两种可能的解析树结构，因此文法是二义性的。