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

Question

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

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

但是如果我有以下示例语法（带有 "regex repitition"）怎么办：

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

如何使用 LR(k)（或其他一些解析算法）解析此类语法并构建树？

Answer 1

那是

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

或

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

在你的第一个片段中，你说你 "know how to parse"，你的语法有歧义。我假设您正在使用某种外部 precedence/associativity 声明来解析它，因为除了简单识别之外，如果不指定如何构建解析树，就无法将解析有意义地应用于文本。

我在这里提供的语法没有歧义，因此体现了列表的关联性。在许多情况下，列表的关联性是无关紧要的，因为所需的结果只是一个列表；在这种情况下，（从语法上）您选择上述哪个选项并不重要。

通常在使用 LR 解析器生成器时，我们会选择左关联的，也就是上面的第一个。那是因为右结合性要求将单个元素保留在解析器堆栈上，直到最终可以从后到前构造列表，当您到达末尾时。因此，解析一个长列表会耗尽大量的解析器堆栈；如果您的解析器生成器限制了堆栈的大小，那么这最终会成为一个问题。

从后到前的列表构造也可能让新手感到困惑。一个常见的混淆（从关于 SO 的问题判断）来自以下 "debugging" 代码（在 yacc/bison 语法中）：（为简单起见，我实现 (E ';')* 而不是 (E ';')+；大多数无论如何，这就是你想要的。）

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

这将导致列表中的元素从右到左打印出来，如果这是您希望代码执行的操作，这很好。但往往会导致混乱，这对调试代码有些适得其反。（这只是为什么我总是建议使用解析器生成器中内置的调试工具的原因之一 - 并且总是选择具有内置调试工具的解析器生成器 - 而不是尝试使用一组即席 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 { .set_scope(new Scope());
                               .prepend(.initialiser()); }
     | statement ';' block   { .prepend(); }

顺便说一下：转换有众所周知的成语

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 没有错（或者创建一个中间非终结符来表示它，如果它真的很复杂或有复杂的动作），但避免这个问题更简单。

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

Repetitions Grammar parsing S -> ( E ';' )+

parsing

grammar

parser-generator

lr