如何解析标准的if-else if-else语句？（带RPLY）

Question

我正在尝试用RPLY构建一个解析器，但在使if-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

这是从Bison的状态机转储中获取的相同语法。解析器状态是“项”的集合；每一个项目都是一个带有标记位置的产品。（标记是两个产品中的.。）该标记基本上显示了解析器在达到该状态时所取得的进展；如果.位于生产的末尾（如第一行所示），则可能执行缩减操作，因为解析器已到达生产的末尾。如果.有某个后续符号，那么如果下一个令牌可能是（或某个扩展中的第一个令牌）后续符号，则解析器可以移位下一个令牌。在上面的第二个产品的情况下，如果newline恰好是下一个令牌，则可以移动它。

状态中的生产也用一个前瞻集进行注释，尽管bison只显示了可能被减少的生产的前瞻集。第一个产品结尾处的注释[$end,NEWLINE,DEDENT]是该产品的前瞻集。换句话说，它是一组可能的下一个令牌，在其中生产可以减少。

此状态是移位/减少冲突，因为换行可能触发els_if_clause_seq:els_if_clause的减少，或者可以在假定将解析换行els_if_clause_seq的情况下进行移位。由于shift/reduce冲突的默认解决方案是更喜欢shift(bison、ply、rply和大多数其他LR解析器生成器中），因此将永远不会发生reduct，迫使解析器总是选择尝试扩展els_if_clause_seq。实际上，这意味着不在块末尾的else_if_clause必须始终跟在另一个else_if_clause后面，这使得无法解析else_if true 1 else1（其中else_if_clause后面跟有else子句）。

一个可以向前看两个令牌的解析器在这个语法上不会有任何问题。第二个next标记（位于换行之后）必须是else或else_if；在第一种情况下，需要减少，而在第二种情况下，移位是正确的动作。事实上，newline在这里实际上没有任何用处，因为else和else_if前面必须始终有newline标记。此外，由于else_if_clusa只能以block结尾，而block只能以dedent结尾，因此我们可以得出结论，换行前面必须有一个dedent。

您似乎选择在缩进之后发送换行,因为您的语法似乎指示您在缩进之前发送换行。这在理论上可能是可行的，但它肯定会导致你正在经历的转移/减少冲突。

空格感知词法扫描的更常见实现使用Python手册中概述的算法：当遇到换行时生成newline令牌，除非显式或隐式地连接周围的行，然后决定发出一个indent、一个或多个dedent，或者不发出。仔细检查Python语法就会发现这两者是如何结合在一起的。以下是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标记是严格冗余的，因为可以推断存在；将它们完全排除在外会减少解析器需要处理的令牌的数量。但如果这样做，就不能再使用简单语句总是以换行结尾的简单原则，因为块中的最后一条简单语句后面直接跟着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