编译原理什么叫左递归

1. 递归下降和递归向上以及左递归

递归下降、递归向上以及左递归是编译原理与语法解析中关键概念。递归下降是一种自顶向下的语法解析方法，每个非终结符对应解析函数，通过递归调用处理特定文法规则。此方法直观易懂，适用于上下文无关文法，但可能受到左递归影响，需进行特殊处理避免无限递归。

递归向上则为自底向上的语法解析方法，从最低级终结符开始解析，逐步构建语法树，直至最高级非终结符。递归向上常用于LR分析器，如LR(1)与LALR(1)，这类分析器通过自底向上推导树解析输入文本，相比递归下降，通常能处理更复杂语法，解析效率更高。

左递归指的是非终结符规则中以自身开头的特性，如A->Aα。此结构可能使递归下降解析器陷入无限递归，导致解析失败。处理左递归是编写递归下降解析器时的重要步骤，常见解决方式为消除左递归，将左递归规则转换为非左递归规则。例如，对于左递归规则A->Aα|β，可通过引入新非终结符A'进行转换，如A->βA'，A'->αA'|ε。

递归下降与递归向上是不同语法解析方法，适用于不同文法类型。处理左递归在编写递归下降解析器时至关重要。根据语言特性与需求，选择合适的解析方法极为重要。

2. 编译原理语法分析中消除左递归的问题。比如A→Ab|c中为什么说它是左递归呢，明明是A定义为Ab或者

A->Ab|c为什么是左递归，和为什么要消除左递归：

定义，就无需争辩了。至于为什么自顶向下文法不能处理左递归,解释如下：

c∈FIRST(A)，所以当预测分析的栈顶出现非终结符A，而输入字符串最左边为c时，就不知道用产生式A->Ab还是A->c了。无法构造预测分析表。比如输入字符串为cbb，我们人当然容易知道是A->Ab->Abb->cbb了，但是电脑没那么聪明，如果不消除左递归，只有回溯了。

3. 编译原理文法定型规则

编译原理中的文法定型规则是指将任意上下文无关文法（Context-Free Grammar, CFG）转化为某个特定形式的上下文无关文法的规则。这个特定形式的上下文无关文法通常是Chomsky范式或Greibach范式。
以下是文法定型规则的具体步骤：
1. 消除文法中的ε产生式（epsilon-proction），即产生空串的产生式。
2. 消除文法中的单一产生式（unit-proction），即右侧只有一个非终结符的产生式。
3. 消除文法中的左递归产生式（left-recursive proction）。
4. 将文法转化为无二义性的文法。
上述步骤的具体实现方法如下：
1. 消除文法中的ε产生式：
1. 对于所有含有ε产生式的非终结符，将其ε产生式删除。
2. 对于所有产生式右侧含有已删除非终结符的产生式，将其右侧的已删除非终结符替换为ε。
3. 重复执行上述步骤，直到所有含有ε的产生式都被消除为止。
2. 消除文法中的单一产生式：
1. 对于所有单一产生式A → B，将其删除。
2. 对于所有产生式右侧含有被删除产生式的非终结符的产生式，将其替换为被删除产生式的右侧符号B。
3. 重复执行上述步骤，直到所有单一产生式都被消除为止。
3. 消除文法中的左递归产生式：
1. 对于每个非终结符A，将所有形如A → Aα的产生式改为A → β1A'、A' → β2A' | ε的形式。
2. 其中，β1是所有右侧不含有A的A产生式的右侧符号串，β2是所有右侧含有A的A产生式的右侧符号串，α是所有产生式右侧不含有A的符号串。
3. 重复执行上述步骤，直到所有左递归产生式都被消除为止。
4. 将文法转化为无二义性的文法：
1. 消除文法中的二义性产生式，即产生式右侧存在两个或以上的不同符号串。
2. 引入新的非终结符，将二义性产生式拆分为多个不同的产生式。
3. 对于所有产生式右侧含有多个符号的产生式，使用括号或其他符号进行明确区分。
4. 重复执行上述步骤，直到文法不存在二义性为止。
以上是文法定型规则的具体步骤和实现方法。通过执行这些步骤，可以将任意上下文无关文法转化为某个特定形式的上下文无关文法，从而方便进行语法分析和编译。