4

许多编程语言都有以行尾结尾的语句。但是，通常，如果解析器无法理解该行，则允许在语句中间使用行结尾。例如，

a = 3 +
4

...将在 Ruby 和 Python* 中解析为 statement a = 3+4，因为a = 3+没有任何意义。换句话说，换行符会被忽略，因为它会导致解析错误。

我的问题是：如何使用标记器和解析器简单/优雅地完成相同的行为？我使用 Lemon 作为解析器生成器，如果它有任何区别（尽管我也将此问题标记为 yacc，因为我确信该解决方案同样适用于两个程序）。

这就是我现在的做法：允许在不存在语法歧义的任何情况下可选地出现语句终止符。换句话说，像

expression ::= identifier PLUS identifier statement_terminator.
expression ::= identifier PLUS statement_terminator identifier statement_terminator.

...换句话说，可以在加号之后使用换行符，因为这不会对语法的歧义产生任何影响。我担心这会增加语法的大小，我有很多机会错过案例或在语法中引入细微的错误。有没有更简单的方法来做到这一点？

编辑*：实际上，该代码示例不适用于 Python。但是，如果您传入这样的内容，Python 实际上会忽略换行符：

print (1, 2,
3)
4

1 回答 1

5

您可能可以让解析器生成器做到这一点，但它可能需要修改解析器生成器的骨架。

我知道三种可能的算法；没有一个是完美的。

  1. 在以下情况下，在行尾插入显式语句终止符：

    一个。前一个标记不是语句终止符，并且

    湾。可以移动语句终止符。

  2. 在以下情况下，在不可移位的标记（在 Ecmascript 中称为“违规标记”）之前插入显式语句终止符：

    一个。违规标记位于行首，或者是一个}或是输入结束标记，并且

    湾。移动语句终止符不会导致空语句产生式的减少。[1]

  3. 制作所有令牌对的清单。对于每个标记对，决定是否适合用语句终止符替换行尾。您可能可以使用上述算法之一来计算此表。

算法 3 最容易实现，但最难解决。而且可能每次修改语法都需要调整表格，这会大大增加修改语法的难度。如果您可以计算标记对表，则插入语句终止符可以由词法分析器处理。（如果您的语法是运算符优先语法，那么您可以在任何没有优先关系的标记之间插入语句终止符。但是，即使这样，您也可能希望对受限上下文进行一些调整。）

如果您可以在不破坏上下文的情况下向解析器查询令牌的可移动性，则可以在解析器中实现算法 1 和 2。最近版本的野牛允许您指定他们所谓的“LAC”（LookAhead Correction），这涉及到这样做。从概念上讲，解析器堆栈被复制并且解析器尝试处理令牌；如果令牌最终被移动，可能在一些减少之后，没有触发错误产生，那么令牌是有效前瞻的一部分。我还没有查看实现，但很明显实际上不需要复制堆栈来计算可移动性。无论如何，如果你想使用它，你必须将该设施逆向工程成 Lemon，这将是一个有趣的练习，可能不会太难。（你' d 还需要修改野牛骨架来执行此操作，但从 LAC 实现开始可能更容易。LAC 目前仅由 bison 用于生成更好的错误消息，但它确实涉及测试每个令牌的可移动性。）

在所有上述算法中，需要注意的一件事是可能以括号表达式开头的语句。特别是 Ecmascript 弄错了（恕我直言）。Ecmascript 示例，直接来自报告：

a = b + c
(d + e).print()

Ecmascript 会将其解析为单个语句，因为c(d + e)它是一个语法上有效的函数调用。因此，(不是一个冒犯性的标记，因为它可以被转移。但是，程序员不太可能打算这样做，并且在执行代码之前不会产生错误，如果它被执行的话。

请注意，算法 1 会在第一行的末尾插入一个语句终止符，但同样不会标记歧义。这更有可能是程序员的意图，但未标记的歧义仍然令人讨厌。

Lua 5.1 会将上面的示例视为错误，因为它不允许在函数对象和(调用表达式中插入新行。但是，Lua 5.2 的行为类似于 Ecmascript。

另一个经典的歧义是return（以及可能的其他语句）具有可选表达式。在 Ecmascript 中，return <expr>是受限制的生产；关键字和表达式之间不允许有换行符，因此return在行尾自动插入分号。在 Lua 中，它不是模棱两可的，因为一个return语句后面不能跟另一个语句。

笔记：

  1. Ecmascript 还要求将语句终止符标记解析为语句终止符，尽管它并没有这么说；它不允许for自动插入语句的迭代器子句中的分号。它的算法还包括在两个上下文中的强制分号插入：在return/throw/continue/break出现在行尾的标记之后，以及在++/--出现在行首的标记之前。
于 2013-07-16T04:06:54.100 回答