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

Question

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

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

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

因此，如果有人可以取笑我并参与进来-所以我不是在追鬼：

在以下Expr规则中：

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

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

Expr::= 
    Expr "," ExprSingle
    | ExprSingle

score 4 · Accepted Answer

没关系....

你可以把递归放在右边，它应该可以工作，但是你会让解析器“做更多的工作”，因为它必须跟踪递归的脊椎，为此它必须使用更多的堆栈位置。

score 0 · Accepted Answer

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

正确的翻译应该是：

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

2 回答 2