删除 EBNF 左递归的首选方法

Question

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

在以下（示例）文法中删除左递归的最直接方法是什么？

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

例子是用扩展的backus-naur形式写的，取自C11标准中Annex 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
    ;

否则，您根本没有删除 left-recursion。但这也不太适合递归解析，因为您无法从 logical_or_expression 的第一个标记判断是否应该预测重复的子句。这就是为什么通常的样式是

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

遗憾的是，按理说上面没有保留left-associativity。但是，从某种意义上说，{ ... } EBNF 语法根本无法定义关联性。第一种解释（语法本质上是right-associative）来自第一个logical_and_expression的特殊地位；第二种解释（语法未能指定结合性）来自重复运算符缺乏定义的顺序。 [注1]

就个人而言，我更喜欢添加“插值”（或“分隔重复”）语法，这样可以更简单地表达分隔列表：

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

或者：

argument_list
    = { expression // "," }
    ;

没有不定义插值运算符的内在原因，一些增强 BNF 变体确实有这样的东西。 [注释 2&3] 这仍然没有明确指定关联性，但它有两个优点：(1) 它更短，以及 (2) 它不会人为地优先于列表的第一个元素。

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

# 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

备注

在 Modern Programming Languages, 2d Edition 第 3 章第 40 页中，作者建议您可以：

Define a convention: for example, that the form
<exp> ::= <mulexp> { + <mulexp>}
will be used only for left-associative operators

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

我不知道使用第一个约定的任何 commonly-used 形式主义（我发现它不自然）但它至少说明了 EBNF 本身没有充分定义重复的结合性。
例如Syntax Definition Format (SDF)用大括号表示分隔重复；大括号内的最后一个元素必须是 non-terminal 并用作分隔符。您仍然需要一个重复运算符，* 或 +，因此我写为 { A // a } 的内容将在 SDF 中写为 { A a }+，而我会写为 [=23] =] 为 [{ A // a }]。这些差异不是特别相关。
作为另一个例子，W3C 使用（或有时使用）ABNF (RFC 5234) 形式的变体，其中 #X 表示 X 的列表以逗号分隔。（还有 n#mX 数字 n 和 m 表示最小和最大重复次数。）

删除 EBNF 左递归的首选方法

Preferred way of removing left recursion of EBNF

ebnf

context-free-grammar

left-recursion

备注