将EBNF转换为用于LALR解析器的BNF

Question

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

我正在尝试将XPath规范中的EBNF转换为直接的BNF，这样我就可以轻松地创建一个与Bison兼容的语法文件。

我已经有一段时间没有这样做了，我不记得递归属于生成的哪一边。我原以为是左边的，但当通过Bison生成的解析器运行纯janeXPath表达式时，我的"直接"翻译会给我带来语法错误。

所以，如果有人能幽默我并参与进来——这样我就不会追鬼了：

在下面的Expr规则中：

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

这是正确的翻译吗？（将递归放在左边）：

Expr::= 
    Expr "," ExprSingle
    | ExprSingle

Answer 1

没关系。。。。

你可以把递归放在右边，它应该可以工作，但你会让解析器"做更多的工作"，因为它必须跟踪递归的主干，而且要做到这一点，它必须使用更多的堆栈位置。

Answer 2

您的翻译在规则Expr上是递归的，它接受其他Expr生成。

正确的翻译是：

Expr::=
    ExprSingle Expr1
Expr1::=
    Expr1 "," ExprSingle | ε