重复语法分析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的问题判断)来自以下“调试”代码(在yacc/bison语法中)：(为了简单起见，我实现了(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 (或者创建一个中间的非终端来表示它，如果它真的很复杂或者有一个复杂的操作)没有什么错，但是避免这个问题更简单。