parsing - 解析的优先级

Question

我重新表述了我之前问过的一个问题。目的是了解优先级在解析中是如何工作的。

我想解析一个语句 a(3).value = 100 . parser.mly如下停止阅读. ，并返回错误。

但是，如果我移动专用于 argument_list 的部分(由 begin 和 end 全局化)到文件末尾(因此它在 l_expression 之后)，解析效果很好。

在语句被解析的情况下，它被简化为let_statement的 data_manipulation_statement ; a(3).value减少到 member_access_expression ; a(3)减少为 index_expression ;和 3减少到 argument_list .

在语句无法解析的情况下，它似乎试图将语句的开头减少为call_statement的 control_statement ...它以错误结束。

我一直认为，无论优先级如何，解析总是拒绝不能以成功结束的缩减。但在那里，它似乎尝试并失败了，并且拒绝尝试其他可能性......

有人可以帮忙澄清一下吗？

statement:
| control_statement { $1 }
| data_manipulation_statement  { BS_DMS $1 }

control_statement: | control_statement_except_multiline_if { BS_CSEMI $1 }
control_statement_except_multiline_if: | call_statement { $1 }
call_statement: | simple_name_expression argument_list { CSEMI_SNE_AL ($1, $2) }
data_manipulation_statement: | let_statement { $1 }
let_statement: | l_expression EQUAL expression { DMS_let (None, $1, $3) } 

simple_name_expression: | name { $1 } 
index_expression: | l_expression LPAREN argument_list RPAREN { IE_LE_AL ($1, $3) }
member_access_expression: | l_expression DOT unrestricted_name { MAE_LE_UN ($1, $3) }
literal_expression: | INTEGER { LIE_INT $1 }

unrestricted_name: | name { UN_N $1 }
name: | untyped_name { N_UN $1 }
untyped_name: | IDENTIFIER { UN_I $1 } 

expression: 
| l_expression { E_LE $1 }
| value_expression { E_VE $1 }

value_expression:
| literal_expression { VE_LIE $1 }
| parenthesized_expression { VE_PE $1 }

(***** begin argument_list *****)
argument_list: | positional_or_named_argument_list { AL_PONAL $1 }

positional_or_named_argument_list:
| positional_argument_COMMAs required_positional_argument { PONAL_PAs_RPA (List.rev $1, $2) }
positional_argument_COMMAs:
  /* empty */ { [] }
| positional_argument_COMMAs positional_argument COMMA { $2 :: $1 }

positional_argument: | argument_expression { $1 }
required_positional_argument: | argument_expression { $1 }
argument_expression: | expression { AE_expression (None, $1) }
(***** end argument_list *****)

l_expression:
| simple_name_expression { LE_SNE $1 } 
| index_expression { LE_IE $1 } 
| member_access_expression { LE_MAE $1 } 

Answer 1

关于解析如何进行没有绝对的规则。这取决于解析器。可以说，一个正确的解析器应该“总是拒绝不能以成功结束的减少”，但通常你不能用线性时间从左到右的解析器做到这一点。 GLR 解析器(野牛可以生成)可以做到这一点，可能在最多三次的时间内，具体取决于语法。回溯解析器——比如大多数解析组合器库——可以做到这一点，但估计算法的复杂性并不容易。但是，我认为您正在使用的 *LR(1) 解析器，根据您的标签，只能解析 *LR(1) 语法，而您的语法不是其中之一。

LR(1) 解析器从左到右 ( L ) 处理输入，一次一个标记。读取每个标记后，它会“减少”(即匹配产生式)所有以输入的最右侧标记 ( R ) 结尾的产生式。为此，它使用尽可能多的关于解析进度(“解析堆栈”)和下一个 的信息。 (1) token (“前瞻”)。它们与有限状态下推自动机一起工作，并且有多种构建这些自动机的方法，它们为理想的 PDA 提供了不同的近似值，但对于您的语法而言，这无关紧要。我相信 ocamlyacc 会生成 LALR(1) 解析器，就像原始的 yacc 一样，但是您的语法甚至不是 LR(1)，因此它肯定不能被简化的 LR(1) 解析器解析。

在上面的描述中，我没有使用“优先级”这个词，因为它不适用于LR解析。有诸如优先级解析器之类的东西——它们通常不如 LR 解析器强大，但也更容易构建——但除了手写解析器的形式之外，它们不再那么常见了。 (我不确定是否曾经有过优先语法解析器生成器；一旦发现 LALR(1) 解析器，它就迅速占领了解析器生成器市场，因为它比优先级或 LL(1) 解析器更强大。)但是，“优先级”被添加到 yacc在其发展的某个早期阶段，以应对模棱两可的语法；或者，通常情况下，语法可以明确地写出来，但在歧义形式时更紧凑。

当 LR 解析器决定要做什么时，可能有不止一种选择。这可能是因为存在不止一种可能的归约(“归约-归约”冲突)，或者因为尚不清楚可用归约是否正确(“移归归约”冲突)。冲突的产生是因为语法不明确，或者因为它不能仅使用指定的前瞻进行 LR 解析。

在任何一种情况下，迂腐的 LR 解析器生成器都会报告失败。但是实用的解析器生成器可能会尝试找出哪些替代方案是所需的，并相应地进行。这样做的一种简单方法是基于某些程序员提供的声明(“优先声明”)或基于某种启发式(“首选语法文件中的第一个” )。这种启发式方法是危险的，因为它们可能导致解析器实际上不解析您期望被解析的语言；恕我直言，任何解析器生成器都不应应用启发式，而至少不会警告您它已经这样做了。

现在，实际问题是:为什么您的语法不是 LR(1)。

让我们从以下摘录开始。

call_statement: simple_name_expression argument_list
let_statement: l_expression EQUAL expression
l_expression: index_expression
l_expression: simple_name_expression
index_expression: l_expression LPAREN argument_list RPAREN

现在考虑输入:a ( .也就是说，我们刚刚读取了 token a并且前瞻标记是 ( . a必须减少到 simple_name_expression (通过几个单元制作，但细节无关紧要)。现在，解析器状态将包括:( · 表示产品中的当前“点”):

call_statement:   simple_name_expression · argument_list
index_expression: l_expression · LPAREN argument_list RPAREN
l_expression:     simple_name_expression ·

也就是说，我们可以离开 simple_name_expression照原样继续收集 argument_list ，或者我们可以减少 simple_name_expression至 l_expression为了继续收集 index_expression 的其余部分.是哪一个？

不幸的是，至少在我们达到匹配的 RPAREN 之前，我们无法知道答案。 .即便如此，我们也可能不知道答案，因为下一个标记可能是扩展 l_expression 的东西。 (例如 . 或另一个 LPAREN )，在这种情况下，我们需要继续扫描。不知道我们什么时候会找到答案，所以没有有限的前瞻就足够了，这个语法——尽管可能是明确的——对于任何 k 都不是 LR(k)。 (并且优先启发式也不起作用。)

顺便说一句，我不清楚您对 call_statement 的语法。是你想要的。安 argument_list可以以 ( 开头，因为它必须以 expression 开头，而 expression 可以用括号括起来，但不必以括号开头。因此以下将是合法的 call_statement:

print a(3), value

如果这就是你想要的，那很好。