python - 如果-else if-else语句，您将如何解析标准？ (使用RPLY)

Question

我正在尝试使用RPLY构建解析器，但无法使if-else -else语句正常工作。

在我看来，解析器拼命尝试遵循一条路径，当它失败时，它只是停止而不是寻找另一条路径。

这是我目前的作品/规则：

@self.pg.production('file : ')
@self.pg.production('file : expression_seq')

@self.pg.production('block : INDENT expression_seq DEDENT')

@self.pg.production('expression_seq : expression')
@self.pg.production('expression_seq : expression NEWLINE expression_seq')

@self.pg.production('else_clause : else NEWLINE block')

@self.pg.production('else_if_clause : else_if expression NEWLINE block')

@self.pg.production('else_if_clause_seq : else_if_clause')
@self.pg.production('else_if_clause_seq : else_if_clause NEWLINE else_if_clause_seq')

@self.pg.production('expression : if expression NEWLINE block')
@self.pg.production('expression : if expression NEWLINE block NEWLINE else_if_clause_seq')
@self.pg.production('expression : if expression NEWLINE block NEWLINE else_clause')
@self.pg.production('expression : if expression NEWLINE block NEWLINE else_if_clause_seq NEWLINE else_clause')

@self.pg.production('expression : INTEGER')

@self.pg.production('expression : false')
@self.pg.production('expression : true')

这是EBNF中的语法：

file = [ expression_seq ] ;
expression_seq = expression , { NEWLINE , expression } ;
block = INDENT , expression_seq , DEDENT ;
expression = if | INTEGER | 'false' | 'true' ;
if = 'if' , expression , NEWLINE , block , { NEWLINE , else_if_clause_seq } , [ NEWLINE , else_clause ] ;
else_clause = 'else' , block ;
else_if_clause = 'else if' , expression , NEWLINE , block ;
else_if_clause_seq = else_if_clause , { NEWLINE , else_if_clause } ;

因此，到目前为止，解析器解析：

if true
  1
else
  1

true

但不是：

if true
  1

true
=> rply.errors.ParsingError: (None, SourcePosition(idx=13, lineno=4, colno=1))

要么

if true
  1
else if true
  1
else
  1

true
=> rply.errors.ParsingError: (None, SourcePosition(idx=29, lineno=5, colno=1))

我的规则有问题吗？您将如何实现这种（通用）语法？

Answer 1

问题在于您对NEWLINE令牌的处理。这会产生换档/减少冲突，这些冲突可以通过换档动作解决。结果是，永远不可能采取减少冲突的措施，这使得某些语法结构无法解析。

这是一个例子：

else_if_clause_seq: else_if_clause .  [$end, NEWLINE, DEDENT]
                  | else_if_clause . NEWLINE else_if_clause_seq

这是从野牛的状态机转储中提取的，用于相同的语法。解析器状态是“项目”的集合；每个项目都是带有明显位置的产品。 （标记是两个产品中的 .。）标记基本上显示了解析器到达该状态时已到达的距离；如果 .在生产的末尾（如第一行），则可以执行缩减操作，因为解析器已到达生产的末尾。如果 .具有后跟符号，则如果下一个标记可能是（或在后一个扩展中的第一个标记），则解析器可以移动下一个标记。在上面的第二个生产中，如果 NEWLINE恰好是下一个标记，则可以将其移位。

该州的作品还带有前瞻集，尽管野牛只显示了可以减少的作品的前瞻集。第一个生产的结尾处的注释 [$end, NEWLINE, DEDENT]是该生产的前瞻集。换句话说，它是可以减少生产的上下文中一组可能的下一个标记。

此状态是移位/减少冲突，因为 NEWLINE可能会触发 else_if_clause_seq: else_if_clause的减少，也可能是在假定将解析 NEWLINE else_if_clause_seq的情况下进行转移的。由于平移/减少冲突的默认解决方案是偏向于平移（在野牛，叠层，rply和大多数其他LR解析器生成器中），因此减少永远不会发生，从而迫使解析器始终选择尝试扩展 else_if_clause_seq 。实际上，这意味着不在块末尾的 else_if_clause必须始终跟在另一个 else_if_clause之后，从而无法解析 else_if true 1 else 1，其中 else_if_clause后跟 else子句。

可以预见两个标记的解析器对此语法没有任何问题。第二个下一个标记（在 NEWLINE之后）必须是 else或 else_if。在第一种情况下，需要减少，而在第二种情况下，变速是正确的动作。实际上， NEWLINE确实没有任何用途，因为 else和 else_if必须始终在 NEWLINE标记之前。另外，由于 else_if_clause只能以 block结尾，而 block只能以 DEDENT结尾，因此我们可以得出结论，在 NEWLINE之前必须加上 DEDENT。

您似乎选择在 NEWLINE之后发送 DEDENT，因为语法似乎表明您在 NEWLINE之前发送了 INDENT。从理论上讲，这可能是可行的，但肯定会导致您转移/减少冲突。

感知空白的词法扫描的更常见实现是使用算法 outlined in the Python manual：遇到换行符时会生成一个 NEWLINE令牌，除非周围的行被显式或隐式连接，然后决定发布一个 INDENT，一个或多个 DEDENT或什么都没有。对 Python grammar的仔细检查显示了它们如何组合在一起。这是EBNF中的简化摘录：

stmt: simple_stmt | compound_stmt
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
small_stmt: expr_stmt …
compound_stmt: if_stmt …
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

suite或多或少与您的 block相对应，但允许同一行中不缩进的单个语句，但请注意，它以 NEWLINE开头。简单（非复合）语句以 NEWLINE结尾；复合语句被视为是自定界的。

另一种方法是仅在两行连续的缩进完全相同的情况下发出 NEWLINE令牌。如上所述，缩进或缩进的行中的 NEWLINE标记严格多余，因为可以推断出存在。完全不使用它们可以减少解析器需要处理的令牌数量。但是，如果这样做，您将无法再继续使用简单原则，即简单语句始终以 NEWLINE终止，因为 block中的最后一个简单语句直接跟在 DEDENT之后。这使得必须使用 expression_seq的稍微复杂一点（和右递归）的定义：

block              : INDENT statement_sequence DEDENT
statement          : simple_statement | compound_statement
statement_sequence : statement
                   | simple_statement NEWLINE statement_sequence
                   | compound_statement statement_sequence