递归如何实现编译原理

A. 编译原理-句型、句子、短语、直接短语、句柄、素短语、最左素短语

在进行语法分析的时候，有时候会对这些词语的概念不清晰，这里我们就详细归纳总结一下。

可以看出这个里面，最需要理解的概念就是短语，其他大部分概念都是在短语基础上延伸的，从概念上可以看出：

假设有一个文法

针对文法的一个特定句型 (Sd(T)db) , 其推导过程如下:

这个句型 (Sd(T)db) 对应的 CFG 分析树如下：

那个这个句型 (Sd(T)db) 有多少个短语呢？

还记得短语的定义么， S ⇒* αβδ ， αβδ 代表句型就是这里的 (Sd(T)db) 。

因此这个句型 (Sd(T)db) :

算法非常简单，就是通过分析树的后序遍历，先将子树的叶节点从左到右排合并成字符串(即一个短语)，然后用它代表子树的根节点的值，再和与子树根节点同一层节点值合并，得到新的短语。就这样从分析树的最底层，一路合并到分析树的根节点，就能得到所有的短语了。

通过递归的方法，获取短语列表 phraseList , 直接短语列表 directPhraseList 和 素短语列表 plainPhraseList 。

运行结果:

B. 编译原理左递归消除

这些题很难啊！！！
都有间接左递归。要先变成直接左递归，然后消除掉。
--------------------
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：

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

C. 编译原理为什么存在递归文法

编译原理中存在递归文法是因为编程语言的语法和结构往往具有递归性质。递归文法是一种用来描述编程语言语法的形式化表示方法，其中规则可以包含对同一语法结构的递归引用。这种递归性质反映了编程语言中常见的嵌套和递归结构。
以下是一些原因，说明为什么编译原理中存在递归文法：
1. 语法结构的嵌套：编程语言中的语法结构通常可以嵌套在其他语法结构中，例如，一个函数可以包含其他函数，一个条件语句可以包含另一个条件语句，等等。递归文法可以很自然地表示这种嵌套结构。
2. 语法的可扩展性：编程语言通常需要具有可扩展性，允许程序员定义新的语法结构或数据类型。递归文法可以轻松地扩展以包括新的语法规则。
3. 函数调用和表达式求值：编程语言中的函数调用和表达式求值通常是递归的过程。递归文法可以用于清晰地描述这些递归计算过程。
4. 简洁性和可读性：递归文法可以帮助编译器设计者更简洁地表示语言的语法，这有助于提高编译器的可读性和维护性。
5. 符合语言设计的自然表示：递归文法使得语法规则的表示更符合编程语言设计的自然结构，因为它们允许对语法结构进行递归定义，而不需要多次重复相似的规则。
虽然递归文法在编译原理中非常有用，但它们也需要谨慎使用，以避免无限递归或歧义性。编译器设计者需要确保递归文法能够被正确解析和处理，通常需要使用递归下降解析器或其他技术来处理递归文法。

D. 编译原理中 左递归具体解释是什么

定义：
"一个文法是左递归的，若我们可以找出其中存在某非终端符号A，最终会推导出来的句型(sentential form)里面包含以自己为最左符号(left-symbol)的句型"
即
A -> Aa 或
A -> Ba
B -> A
两种形式的文法.

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

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

F. 编译原理：消除文法中的左递归

总得有个规则吧。如果不能提供，可以自己看看bison源代码分析--gcc源代码分析语法分析部分。