编译原理_消除左递归

Question

简单的消除直接左递归和间接左递归都可以做出来。但是不理解各个非终结符怎么分配排序。
不理解为什么要讲S->AB换成S->BA'，为啥要把A放后面。是需要求一下A的SELECT再去把AB换成BA'吗

Answer 1

消除左递归是在文法设计时的一个优化，目的是使文法更简洁，更易于处理。为了消除左递归，需要了解每个非终结符的 SELECT 集，以确定它们的相对顺序。

SELECT 集是指每个非终结符所生成的所有第一符号。为了消除左递归，我们需要确保每个非终结符的 SELECT 集不包含其自身，因为这样的递归将会导致死循环。

设计消除左递归的策略就是要避免把非终结符的 SELECT 集向其自身递归。如果我们在把 S->AB 换成 S->BA' 的过程中，把 A 放到了后面，那么这个规则的 SELECT 集将不会包含 S，因此 S 就不会再递归到自身。

需要注意的是，上述转换过程可能不适用于所有文法，可能需要根据每个特定的文法来确定如何进行转换。