形如A→Aα的产生式称为左递归的，类似地称B一βB的产生式为右递归的。证明如果一个非终极符既有 左递归式，又有右递归式，则文法一定是二义性的。

设该文法中有一个非终极符为A，它有一个左递归式A → Aα和一个右递归式A → βA。

考虑字符串Aαβ，它可以有两种不同的推导方式：

1. A → Aα （左递归式）→ Aαβ （右递归式）→ βAαβ

2. A → βA （右递归式）→ βAαβ

因此，字符串Aαβ可以被这个文法推导出两种不同的结果，即存在二义性。因此，如果一个非终极符既有左递归式，又有右递归式，则文法一定是二义性的。

相关问题

消除文法G： S→a|b|(T) T→TcS|S 的左递归；

消除文法的左递归是为了让文法满足LL(1)文法的要求，方便语法分析器进行处理。对于文法G：S→a|b|(T) T→TcS|S，我们可以按照以下步骤进行左递归的消除：

1. 将所有的直接左递归都消除，即将T→TcS转化为T→SU，其中U→cSU|ε；
2. 对于每一个非终结符号A，找到其所有能够推导出ε的直接或间接子孙非终结符号B1,B2,...Bn，并将其从A的产生式中删除；
3. 将删除ε后的产生式中的右部替换为其所有可能的组合，例如T→SU可以替换为T→cST|S；
4. 将新产生的文法规则加入原有文法中。

经过消除左递归后，G的新文法为：

S → a | b | '(' T ')'
T → SU
U → cSU | ε

但是C -> dBa 中B不是产生式右侧的第一个符号

非常抱歉，我的回答有误。你是正确的，C -> dBa 不是左递归文法。因为B不是产生式右侧的第一个符号，因此不存在左递归问题。请允许我进行更正和澄清。左递归产生式的定义是，产生式右侧的第一个符号是产生式左侧的非终结符。如果一个产生式没有这样的形式，就不是左递归产生式。在 C -> dBa 中，B 不是产生式右侧的第一个符号，因此该产生式不是左递归产生式。然而，在文法中仍然可能存在左递归问题。如果存在形如 A -> Aα | β 的产生式，其中α的第一个符号是A，则该文法是左递归的。