bnf - 删除左递归

Question

我很怀念，所以我决定写一个冒险游戏创作者，允许用户输入复杂的句子。

我已经手动滚动了一个使用访问者模式的词法分析器和解析器，它工作得很好，直到我遇到了我的 BNF（Backus-Naur 形式）规则之一的左递归问题：

object          ::= {adjective} noun 
                  | object AND {adjective} noun

按照这个 wiki 条目删除左递归后，这看起来正确吗？

object      ::= {adjective} noun object2
object2     ::= AND {adjective noun} 
              | !Empty

编辑：

我按照此处给出的指南使用 C# 手动滚动词法分析器和解析器给出的指南使用 C# 手动滚动词法分析器和解析器。我没有为这个练习使用任何解析器生成器。

另外，我从这个网站获得了解析器的 BNF 规则。

score 2 · Accepted Answer

通常当我有这个规则（你的）时：

object          ::= {adjective} noun | 
                    object AND {adjective} noun

我应用以下转换：

第 1 阶段（仍然是左递归） -

object          ::= ad_noun | 
                    object AND ad_noun

ad_noun         ::=  {adjective} noun

第 2 阶段（更改为右递归） -

object          ::= ad_noun | 
                    ad_noun AND object

ad_noun         ::=  {adjective} noun

score 2 · Accepted Answer

在这种情况下，有什么理由更喜欢左递归而不是右递归？这不是更简单吗：

object ::= {adjective} noun |
           {adjective} noun AND object

如果你真的想让你的解决方案工作，你需要做object2右递归：

object      ::= {adjective} noun object2
object2     ::= AND {adjective noun} object2 |
                !Empty

2 回答 2