parsing - 将 EBNF 转换为 BNF 以用于 LALR 解析器

Question

我知道有几个帖子具有相似的标题。大多数链接到一个死网站 - 无论如何我有一个更具体的问题。

我正在尝试转换 EBNF in the XPath spec直接转换为 BNF，以便我可以轻松创建与 Bison 兼容的语法文件。

自从我这样做以来已经有一段时间了，我不记得递归属于产生式的哪一边。我以为是左边 - 但当通过 Bison 生成的解析器运行时，我的“直接”翻译给了我简单的 XPath 表达式语法错误。

所以，如果有人能迁就我并参与进来——这样我就不会在追鬼了:

在下面的 Expr 规则中:

Expr::=     
    ExprSingle ("," ExprSingle)*

这是正确的翻译吗？ (将递归放在左侧):

Expr::= 
    Expr "," ExprSingle
    | ExprSingle

Answer 1

没关系...

您可以将递归放在右侧，它应该可以工作，但是您将使解析器“做更多工作”，因为它必须跟踪递归的主干，并且为此必须使用更多堆栈位置。