删除EBNF左递归的首选方式

Question

许多教科书提出了不同的去除左递归的技术。其中一些改变了关联性，这是我想避免的。

在以下(示例)语法中，删除左递归最直接的方法是什么？

logical_or_expression
= logical_and_expression
| logical_or_expression , "||" , logical_and_expression
;

该示例以扩展的backus-naur形式编写，取自C11标准中附录A的C语法。这样做是为了将语法转换为用于递归下降解析的EBNF。

我对这个问题的看法：

logical_or_expression
= logical_and_expression, { "||" , logical_and_expression }
;

但这是否保留了logical_or_expression的左结合性？

Answer 1

我想你指的是

logical_or_expression
= { logical_and_expression, "||" } , logical_and_expression
;

因为除此之外，您根本没有删除左递归。但这也不适合递归解析，因为您无法从logical_or_expression的第一个标记中判断是否应该预测重复子句。这就是为什么通常的风格是

logical_or_expression
= logical_and_expression, { "||" , logical_and_expression }
;

不幸的是，可以合理地说，上面的内容并没有保留左结合性。然而，也有一种意义上，{ ... }EBNF语法根本无法定义关联性。第一种解释(语法本质上是右联想的)来自于第一个logical_and_expression的特殊状态；第二种解释(语法未能指定关联性)来自于重复运算符缺乏定义的排序。[注1]

就我个人而言，我更喜欢添加一个"；插值"；(或"分隔重复")语法，这将允许对分隔列表进行更简单的表达：

logical_or_expression
= { logical_and_expression // "||" }
;

或者：

argument_list
= { expression // "," }
;

没有内在的理由不定义插值算子，而且一些增强的BNF确实有这样的东西。[注2和3]这仍然没有明确指定关联性，但它有两个优点：(1)它更短，(2)它不会人为地对列表的第一个元素赋予特权。

当(任何形式的)重复被翻译回BNF时，需要决定重复是左递归还是右递归，这也是关于重复是左联想还是右联想的决定。如果在构建递归下降解析器之前将重复运算符转换为BNF，那么除了使用正确的-{递归/关联}版本之外，别无选择。然而，递归下降解析器中的实际代码可以以任何一种方式工作：

# Recognize A_list == { A // sep }
# Iterative version, left associative
def parse_A_list():
x = parse_A()
while next() == sep:
accept(sep)
x = new_A_list(x, parse_A())
// Recursive version, right associative
def parse_A_list():
x = parse_A()
if next() == sep:
accept(sep)
x = new_A_list(x, parse_A_list())
return x

---

注释

1. 在《现代编程语言》第二版第3章第40页中，作者建议您可以：

   定义一个约定：例如，形式
   <exp> ::= <mulexp> { + <mulexp>}
   将仅用于左关联运算符

   尽管他也建议在英语文本的相关段落中明确描述联想性的策略。

   我不知道有什么常用的形式主义使用第一个约定(我觉得这很不自然)，但它至少说明了EBNF本身并不能充分定义重复的结合性。

2. 例如，语法定义格式(SDF)使用大括号表示分隔的重复；大括号内的最后一个元素必须是非端子，并且用作分隔符。您仍然需要一个重复运算符，*或+，所以我写为{ A // a }的内容将在SDF中写为{ A a }+，而我在那里写{ A a }*为[{ A // a }]。这些差异并不是特别相关。

3. 作为另一个例子，W3C使用(或在某个时候使用)ABNF(RFC 5234)形式的变体，其中#X表示用逗号分隔的X的列表。(还有用于指示最小和最大重复次数的数字n和m的n#mX。)