玩具语言的无歧义BNF语法、CFG属性及递归问题咨询

1. 该文法是否为上下文无关文法(CFG)？判断依据是什么？ #

只要你的BNF满足所有产生式的左部都是单个非终结符，那它就是上下文无关文法。

CFG的定义核心就是这一点——不管文法是否有歧义、是否包含递归，只要产生式左部仅由单个非终结符构成，就属于CFG范畴。歧义性是CFG的一种属性，而非排除它成为CFG的条件。

2. 当前BNF文法是否包含左递归、右递归或两者兼具？能否调整避免其一，调整后的性能影响如何？ #

递归判断方式 #

• 左递归：若存在非终结符A，能通过产生式直接（形如A → Aα）或间接推导得到以A开头的符号串，则文法含左递归。
• 右递归：若存在非终结符A，能通过产生式直接（形如A → αA）或间接推导得到以A结尾的符号串，则文法含右递归；两者都满足即为兼具。

调整方法 #

• 左递归可通过改写产生式消除：例如将A → Aα | β改写为A → βA'，A' → αA' | ε（ε表示空串）。
• 右递归可通过类似的结构改写消除：例如将A → αA | β改写为A → A'β，A' → A'α | ε；也可直接调整产生式结构规避。

性能影响 #

• 对自顶向下解析器（如递归下降）：左递归必须消除，否则会导致无限递归栈溢出；消除后解析可正常执行，改写后的文法虽增加了非终结符数量，但对现代解析器的性能影响可忽略。右递归不消除会导致长序列解析时栈深度线性增长，消除后可转为迭代处理，降低栈资源消耗。
• 对自底向上解析器（如LR/LALR系列）：左/右递归本身可直接处理，消除与否对解析性能影响极小，主要变化是文法结构的可读性。

内容的提问来源于stack exchange，提问作者user228852