重复语法解析 S ->( E ';' )+。

Question

我知道如何解析这样的语法。

E -> E '*' E
E -> E '+' E
E -> N
N -> '0'
N -> '1'

但是，如果我有以下的例子语法(有一个 "regex重复")。

E -> 'e'
S -> ( E ';' )+ // '+' used like in regexes

我如何用LR(k)(或其他解析算法)解析这样的语法并建立一棵树?

Answer 1

那就是

S → E ';'
S → S E ';'

或

S → E ';'
S → E ';' S

在你的第一个片段中，你说你 "知道如何解析"，但你的语法却含糊不清。我推测你是用某种外在的先例关联性声明来解析的，因为如果不说明解析树如何构建，就不能有意义地将解析应用于文本，而不是简单的识别。

我在这里提供的语法并不含糊，因此体现了列表的关联性。在许多情况下，列表的关联性是不相关的，因为所需的结果只是一个列表；在这样的情况下，（从语法上看）你选择上述备选方案中的哪一个并不重要。

通常在使用LR解析器生成器的时候，我们会选择左联想型的，也就是上面第一个。这是因为右关联性需要将各个元素保留在解析器堆栈上，直到最后可以构造出列表，背对背，当你到了最后。因此，解析一个长的列表会耗费大量的解析器栈；如果你的解析器生成器限制了栈的大小，那么这最终会成为一个问题。

背靠背列表构造也会让新手感到困惑。一个常见的困惑（从SO上的问题来看）来自于下面的 "调试 "代码（用yaccbison语法）：（为了简单起见，我实现的是 (E ';')* 而不是 (E ';')+大多数情况下，这就是你想要的）。)

list: %empty
    | element ';' list { printf("Adding %s\n", $1); }

这将导致列表中的元素被从右到左打印出来，如果这是你期望代码做的事情，这是很好的。但往往会导致混乱，这对于调试代码来说是有些适得其反的。(这就是为什么我总是建议使用你的解析器生成器中内置的调试工具的原因之一--并且总是选择一个内置调试工具的解析器生成器--而不是试图用一组临时的 print 语句）。)

例如，如果解析器是即时计算器的一部分，那么背对背的评估显然会是一个巨大的错误。你想从左到右，一次一个地评估然后丢弃表达式，左关联性将是强制性的。

但情况并非总是如此。假设我们解析的目的是为了构造AST（或其他一些将导致代码生成的中间产物）。而假设这里的元素是声明，而列表代表一个块（减去块定界符，它将在一些外部产品中附加）。在语言中，块中的声明是块的局部，并且范围从声明到块的末尾，程序的语义强烈地暗示了右关联性。考虑下面这个有点愚蠢的例子。

1    function example(i: integer)
2       var tmp: integer = i;
3       var i: integer = tmp - 1;
4       return tmp * i;
5    end

这里, 范围是 tmp 从报表2一直延伸到报表4的末尾。的范围。i 的范围从语句1一直延伸到语句5，但在语句3中，它被另一个同名变量的声明所掩盖，其范围从语句3延伸到语句4的末尾。

为了有意义地解析这种语言，我们将希望在每次看到声明时创建一个新的子范围，并将这个子范围附加到声明之后开始的程序部分。这将建议使用类似这样的语法。

block: %empty
     | declaration ';' block { $3.set_scope(new Scope($1));
                               $3.prepend($1.initialiser()); }
     | statement ';' block   { $3.prepend($1); }

---

我想说明的是： 有一些著名的成语用于转换... ...

S → A B*

和

S → B* A

到无语境语法。第一个是

S: A
 | S B

第二个是

S: A
 | B S

如果 A 是 B (换句话说，如果你想 S → B+，它表示的是相同的文本，既可以是 S → B B* 或 S → B* B您可以使用 S: B | S B 或 S: B | B S. 我没有做上面的，因为它涉及到重复的 B 以及与之对应的任何动作，这是很烦人的，如果 B 不是一个单一的符号。重复使用 B (如果真的很复杂或者动作复杂的话，也可以创建一个中间的非终端来表示)，但是为了避免这个问题，还是比较简单的。