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

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

1. 什么是左递归

在编译原理中，左递归是指文法中存在形如 $ \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：直接左递归消除法

假设有以下文法：

``S -> S a | b

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

1. 将 $S \rightarrow Sa$ 拆分为 $S \rightarrow bS'$ 和 $S' \rightarrow aS'| \epsilon$。
2. 将新产生的 $S'$ 非终结符加入原有的非终结符集合中。
3. 将原有的产生式 $S \rightarrow Sa$ 替换为 $S \rightarrow bS'$ 和 $S' \rightarrow aS'| \epsilon$。

最终得到的文法为：

S -> bS'
S' -> aS' |

### 间接左递归消除法

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

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

下面一个示例说明：

假设有以下文法：

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

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

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

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

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

3. 结论

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