您将如何解析标准的 if - else if - else 语句？ （与回复）
How would you parse a standard if - else if - else statement? (with RPLY)
我正在尝试使用 RPLY 构建解析器，但未能使 if - else if -else 语句起作用。
在我看来，解析器似乎拼命地尝试遵循一条路径，当它失败时，它没有寻找另一条路径，而是停止了。
这是我现在的 productions/rules:
@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))
我的规则有问题吗？您将如何实现这样的（通用）语法？
问题在于您对 NEWLINE 令牌的处理。这会产生 shift/reduce 冲突，解决后有利于 shift 操作。结果是永远无法采取冲突减少操作，这使得某些语法结构无法解析。
这是一个例子：
else_if_clause_seq: else_if_clause . [$end, NEWLINE, DEDENT]
| else_if_clause . NEWLINE else_if_clause_seq
这是从 bison 的状态机转储中获取的相同语法。解析器状态是 "items" 的集合；每个项目都是一个带有标记位置的产品。 （标记是两个产生式中的 .。）标记基本上显示解析器到达该状态时已经走了多远；如果 . 位于产生式的末尾（如第一行），则可以进行缩减操作，因为解析器已到达产生式的末尾。如果 . 有一些后续符号，那么如果下一个标记可能是（或者是某些扩展中的第一个标记）以下符号，那么解析器可以移动下一个标记。在上面的第二个生产的情况下，如果碰巧是下一个令牌，则可以移动 NEWLINE。
该州的作品也用前瞻集进行了注释，尽管野牛只显示了可以减少的作品的前瞻集。第一个产品末尾的注释 [$end, NEWLINE, DEDENT] 是该产品的前瞻集。换句话说，它是在可以减少生产的上下文中可能的下一个标记集。
此状态是 shift/reduce 冲突，因为 NEWLINE 可能会触发 else_if_clause_seq: else_if_clause 的减少，或者它可能会在 NEWLINE else_if_clause_seq 将被解析的假设下转移.由于 shift/reduce 冲突的默认解决方案是更喜欢移位（在 bison、ply、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。
您似乎选择在 DEDENT 之后发送 NEWLINE，因为您的语法似乎表明您在 NEWLINE 之前发送 ]一个INDENT。这在理论上可能是可行的，但它肯定会导致您遇到的 shift/reduce 冲突。
空白感知词法扫描的更常见实现使用算法 outlined in the Python manual: a NEWLINE token is generated when the newline is encountered, unless the surrounding lines are explicitly or implicitly joined, and then the decision is made to issue either one INDENT, one or more DEDENTs, or nothing. Careful examination of the 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
我正在尝试使用 RPLY 构建解析器，但未能使 if - else if -else 语句起作用。
在我看来，解析器似乎拼命地尝试遵循一条路径，当它失败时，它没有寻找另一条路径，而是停止了。
这是我现在的 productions/rules:
@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))
我的规则有问题吗？您将如何实现这样的（通用）语法？
问题在于您对 NEWLINE 令牌的处理。这会产生 shift/reduce 冲突，解决后有利于 shift 操作。结果是永远无法采取冲突减少操作，这使得某些语法结构无法解析。
这是一个例子：
else_if_clause_seq: else_if_clause . [$end, NEWLINE, DEDENT]
| else_if_clause . NEWLINE else_if_clause_seq
这是从 bison 的状态机转储中获取的相同语法。解析器状态是 "items" 的集合；每个项目都是一个带有标记位置的产品。 （标记是两个产生式中的 .。）标记基本上显示解析器到达该状态时已经走了多远；如果 . 位于产生式的末尾（如第一行），则可以进行缩减操作，因为解析器已到达产生式的末尾。如果 . 有一些后续符号，那么如果下一个标记可能是（或者是某些扩展中的第一个标记）以下符号，那么解析器可以移动下一个标记。在上面的第二个生产的情况下，如果碰巧是下一个令牌，则可以移动 NEWLINE。
该州的作品也用前瞻集进行了注释，尽管野牛只显示了可以减少的作品的前瞻集。第一个产品末尾的注释 [$end, NEWLINE, DEDENT] 是该产品的前瞻集。换句话说，它是在可以减少生产的上下文中可能的下一个标记集。
此状态是 shift/reduce 冲突，因为 NEWLINE 可能会触发 else_if_clause_seq: else_if_clause 的减少，或者它可能会在 NEWLINE else_if_clause_seq 将被解析的假设下转移.由于 shift/reduce 冲突的默认解决方案是更喜欢移位（在 bison、ply、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。
您似乎选择在 DEDENT 之后发送 NEWLINE，因为您的语法似乎表明您在 NEWLINE 之前发送 ]一个INDENT。这在理论上可能是可行的，但它肯定会导致您遇到的 shift/reduce 冲突。
空白感知词法扫描的更常见实现使用算法 outlined in the Python manual: a NEWLINE token is generated when the newline is encountered, unless the surrounding lines are explicitly or implicitly joined, and then the decision is made to issue either one INDENT, one or more DEDENTs, or nothing. Careful examination of the 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