博客

编译原理-消除左递归的方法

  • Post category:other

下面是关于“编译原理-消除左递归的方法”的完整攻略：

1. 什么是左递归

在编译原理中，左递归是指文法中存在形如 $A \rightarrow A\alpha$ 的产生式，其中 $A$ 是非终结符，$\alpha$ 是由终结符和非终结符组成的字符串。左递归会导致递归下降分析法无法正常工作，因此需要消除左递归。

2. 消除左递归的方法

消除左递归的方法有两种：直接左递归消除法和间接左递归消除法。

直接左递归消除法

直接左递归消除法是指将文法中的左递归产生式换为等价的右递归产生式。具体步骤如下：

  1. 对于形如 $A \rightarrow A\alpha_1|\cdots|A\alpha_n|\beta_1|\cdots|\beta_m$ 的产生式，将其拆分为两个产生式 $A \rightarrow \beta_1A’|\cdots|\beta_mA’$ 和 $A’ \rightarrow \alpha_1A’|\cdots|\alpha_nA’|\epsilon$。
  2. 对于新产生的 $A’$ 非终结符，将其加入到原有的非结符集合中。

下面是一个示例说明：

假设有以下文法：

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

其中，产生式 $E \rightarrow E + T$ 是左递归产生式。可以使用直接左递归消除法将其转换为等价的右递归产生式：

E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> ( E ) | id

间接左递归消除法

间接左递归消除法是指将法中的间接左递归转换为直接左递归，然后再使用直接左递归消除法进行消除。具体步骤如下：

  1. 对于形如 $A \rightarrow B\alpha_1|\cdots|B\alpha_n|\beta_1|\cdots|\beta_m$ 的产生式，其中 $B$ 是非终结符，将其分为两个产生式 $A \rightarrow \beta_1B’|\cdots|\beta_mB’$ 和 $B’ \rightarrow \alpha_1|\cdots|\alpha_n$。
  2. 对于新产生的 $B’$ 非终结符，检查其是否存在左递归，如果存在，则使用直接左递归消除法进行消除。

下面一个示例说明：

假设有以下文法：

S -> Aa | b
A -> | Sd | ε

其中，产生式A \rightarrow Ac$ 是间接左递归产生式。可以使用间接左递归消除法将其转换为等价的直接左递归产生式：

S -> Aa | b
A -> SdA' | ε
A' -> cA' ε

然后再使用直接左递归消除法进行消除，得到：

S -> Aa | b
A -> SdA | ε
A' -> cA' | ε
S -> bS' | aA'
S' -> dA' | ε

3. 结论

消除左递归是编译原理中的一个重要概念，可以使用直接左递归消除法和间接左递归消除法进行消除。以上是关于“编译原理-消除左递归的方法”的完攻略。

另外，以下是一个更加详细的示例，以便更好地理解直接左递归消除法的具体步骤：

假设有以下文法：

A -> Ab | c

该文法中存在左递归产生式 $A \rightarrow Ab$，需要使用直接左递归消除法进行消除。

  1. 将 $A \rightarrow Ab$ 拆分为 $A \rightarrow cA’$ 和 $A’ \rightarrow bA’|\epsilon$。
  2. 将新产生的 $A’$ 非终结符加入到原有的非终结符集合中。
  3. 将原有的产生式 $A \rightarrow Ab$ 替换为 $A \rightarrow cA’$ 和 $A’ \rightarrow bA’|\epsilon$。

最终得到的文法为：

A -> cA'
A' -> bA' | ε

以上是关于“编译原理-消除左递归的方法”的完整攻略。

Tags: