编译原理左递归方法

❶ 编译原理左递归消除

这些题很难啊！！！
都有间接左递归。要先变成直接左递归，然后消除掉。
--------------------
G3.1
S->SA|Ab|b|c
A->Bc|a
B->Sb|b
--------------------
间接左递归转直接左递归
B代入A：A ->(Sb|b)c|a -> Sbc|bc|a
A代入S：S -> S(Sbc|bc|a)|(Sbc|bc|a)b|b|c -> SSbc|Sbc|Sa|Sbcb|bcb|ab|b|c
消除直接左递归
S->bcbS'|abS'|bS'|cS'
S'->SbcS'|bcS'|aS'|bcbS'|ε
S'还是有直接左递归，继续消除
S'->bcS'T|aS'T|bcbS'T
T->bcS'T|ε
最后，这题答案就是S,S',T的产生式

--------------------
下面两题更难了，上一题反复代入还能把其他非终结符消掉，下面两个文法都是最后代入还剩下两个非终结符反复迭代，佛了！
G3.2
E->ET+|T

T->TF*|F

F->E|i
--------------------
F代入T: T->T(E|i)*|(E|i)->TE*|Ti*|E|i
T代入E：

--------------------
G3.3
S->V_1

V_1->V_2|V_1 2 V_2

V_2->V_3|V_2 + V_3
V_3->V_1 * |(
这些字母我都不认识了，换一下
S->A|SiA
A->B|A+B
B->S*|(
--------------------
B代入A：A->(S*|()|A+(S*|()->S*|(|A+S*|A+(
A代入S：

--------------------

❷ 【编译原理】自顶向下LL（1）分析中，消除左递归和提取左因子的目的是什么

提取左因子---避免程序回溯；
消除左递归---消除死循环。

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

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

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

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

❹ 递归下降和递归向上以及左递归

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

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

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

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

❺ 编译原理文法定型规则

编译原理中的文法定型规则是指将任意上下文无关文法（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. 重复执行上述步骤，直到文法不存在二义性为止。
以上是文法定型规则的具体步骤和实现方法。通过执行这些步骤，可以将任意上下文无关文法转化为某个特定形式的上下文无关文法，从而方便进行语法分析和编译。

❻ 编译原理A->A,(A)|a消除左递归

A::=aA'
A'::=,(A)A'|ε