代码之家 › 专栏 › 技术社区 › heroxav

如何解析标准if-else if-else语句?(带着)

ply programming-languages parsing python

heroxav · 技术社区 · 5 年前

我正试图用 RPLY 而且我没能让if-else-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))

我的规则有什么问题吗?你将如何实现这样一种(常见的)语法?

1 回复 | 直到 5 年前

rici 5 年前

问题在于你处理 NEWLINE 令牌。这就产生了转移/减少冲突,这些冲突有利于转移行动的解决。其结果是,冲突减少的行为永远不会被采取,这使得某些语法结构不可能被解析。

以下是一个例子:

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

这是从Bison的状态机转储中获取的,语法相同。解析器状态是“项”的集合;每个项都是带有标记位置的产品。(标记是 . 在这两个结果中。)标记基本上显示了当解析器达到该状态时,解析器得到的距离;如果 . 是在生产的末尾(如第一行),然后可以执行缩减操作,因为解析器已到达生产的末尾。如果 . 如果下一个令牌可能是(或在某些扩展中是第一个)以下符号,那么解析器可以移动下一个令牌。在上述第二次生产的情况下,a 换行符 如果它恰好是下一个令牌,则可以进行移位。

虽然bison只显示可以减少的产品的lookahead集,但状态中的产品也会用lookahead集进行注释。注释 [$end, NEWLINE, DEDENT] 在第一次生产的最后,是生产的前瞻性设置。换句话说,它是一组可能的下一个令牌,在这种上下文中,可以减少生产。

这种状态是一种转换/减少冲突,因为 换行符 可以触发减少 else_if_clause_seq: else_if_clause 或者它可以在假设 NEWLINE else_if_clause_seq 将被分析。由于shift/reduce冲突的默认解决方案是首选shift(在bison、ply、rply和大多数其他lr解析器生成器中),因此不会进行缩减,这迫使解析器始终选择尝试扩展 else_if_clause_seq . 实际上,这意味着 else_if_clause 不是在一个块的末尾,后面必须跟另一个 ELSIFIFIFY子句 else_if true 1 else 1 ELSIFIFIFY子句 后面跟着一个 else 条款。

一个可以向前看两个标记的解析器对于这种语法不会有任何问题。第二个下一个标记,在 换行符 ,必须是 其他的 或 else_if ;在第一种情况下,需要减少,而在第二种情况下,轮班是正确的操作。事实上, 换行符 这两个都没有用 其他的 和 埃尔西亚夫 前面必须始终有 换行符 令牌。此外,由于 ELSIFIFIFY子句 只能以结尾 block 和 块 只能以结尾 DEDENT 我们可以得出结论 换行符 前面必须是 齿根的 .

似乎您选择发送 换行符 后 齿根的 ,因为您的语法似乎表明您发送了 换行符 之前安 INDENT .这在理论上可能是可行的,但它肯定会导致你正在经历的转变/减少冲突。

更常见的白空间感知词汇扫描的实现使用算法 outlined in the Python manual 答: 换行符 遇到换行时生成标记,除非周围的行显式或隐式联接,然后决定发布其中一行 缩进 一个或多个 齿根的 S,或者什么也没有。仔细检查 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 或多或少与你的 块 但允许在同一行上使用未插入的单个语句,但请注意,它以 换行符 . 简单(非复合)语句以 换行符 ;复合语句被视为自定界。

另一种方法是只解决问题 换行符 如果两个连续的行具有完全相同的缩进,则使用标记。如上所述, 换行符 缩进或取消缩进的行中的标记是严格冗余的,因为可以推导出存在的情况;将它们完全去掉会减少解析器需要处理的标记的数量。但是,如果这样做,就不能再使用简单的原则,即简单语句总是以 换行符 自上一个简单语句 块 后面紧跟 齿根的 . 这就需要使用稍微复杂一点的(右递归)定义 expression_seq :

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