野牛变换/减少冲突

Question

当我试图编译以下语法时，我会得到2个移位/减少错误，这是一个较大语法的一部分：

%token NAMESPACE IDENTIFIER
%start statement
%%
post_expression
: IDENTIFIER
| post_expression '[' expression ']'
| post_expression '.' IDENTIFIER '(' ')'
| post_expression '.' IDENTIFIER
;
expression
: post_expression
| expression '<' post_expression
| expression '>' post_expression
;
data_type
: IDENTIFIER
| IDENTIFIER '<' data_type_list '>'
| IDENTIFIER '<'  '>'
| IDENTIFIER '['  ']'
;
statement
: expression ';'
| data_type initializer ';'
;
initializer
: IDENTIFIER
| IDENTIFIER '=' expression
;
data_type_list
: data_type
| data_type_list ',' data_type
;
%%

冲突状态如下：

State 1
1 post_expression: IDENTIFIER .
8 data_type: IDENTIFIER .
9          | IDENTIFIER . '<' data_type_list '>'
10          | IDENTIFIER . '<' '>'
11          | IDENTIFIER . '[' ']'
'['  shift, and go to state 6
'<'  shift, and go to state 7
IDENTIFIER  reduce using rule 8 (data_type)
'['         [reduce using rule 1 (post_expression)]
'<'         [reduce using rule 1 (post_expression)]
$default    reduce using rule 1 (post_expression)

有人能解释一下如何纠正这个错误吗？有可能使用优先级来解决问题吗？

Answer 1

这两个冲突是解析器被限制为单个前瞻性令牌的结果。

考虑两条规则：

post_expression  : post_expression '[' expression ']'
data_type        : IDENTIFIER '[' ']'

并思考当解析器看到CCD_ 1后面跟着CCD_ 2时会发生什么。由于IDENTIFIER将与post_expression匹配，所以这两个规则都是活动的。但是，解析器不能在不决定是否将IDENTIFIER缩减为post_expression的情况下继续，因为在shift-reduce解析器中，缩减操作必须在生产结束时进行，而不是在以后。如果解析器可以在剩余的输入中查找两个令牌，就不会有问题；第二个next标记要么是]，要么不是(尽管在实际语法中，决策可能更复杂)。

也出现了类似的问题

expression
: expression '<' post_expression
data_type
: IDENTIFIER '<' data_type_list '>'
: IDENTIFIER '<'  '>'

同样，在解析器有足够的信息做出决定之前，需要做出是否将IDENTIFIER减少到expression的决定。

使用优先级规则无法解决这些问题，因为优先级规则不会扩展解析器的前瞻性。无论有没有优先级规则，解析器都无法在不看到(至少)第二个下一个令牌的情况下做出正确的决定。

这不是一个可以忽略的冲突。Bison会以某种方式解决冲突(默认情况下，它会选择shift操作，这意味着它永远不会进行归约)，但对于许多输入来说，这种解决方案都是不正确的，这些将产生语法错误，因为解析器已被逼入死胡同。

那么，该怎么办呢？

• 第一种可能性：无需做出选择。您可以接受更通用的语法(例如IDENTIFIER1的post_expression '[' ']')，然后使用语义规则来拒绝post_expression不是IDENTIFIER的解析。或者，您可以将expression分为两类：IDENTIFIER和complex_expression，从而使post_expression与IDENTIFIER不匹配。

  这两种选择都很丑陋；第一个需要验证post_expression的AST，这将解析器与AST的细节联系得比您想要的更紧密；第二个需要对语法进行大量修改，从而降低语法的可读性并使语法维护更加困难。但这两者都有一个优点：您可以生成更好的错误消息。

• 第二种可能性：也许[0不能以任何IDENTIFIER开头，也许data_type中的IDENTIFIERs不可能真的是expressions。在一些流行的编程语言中，类型和表达式在同一名称空间中，但不响应相同的语法。如果是这样的话，您可能能够调整您的词法扫描器，为值标识符和类型标识符生成不同的令牌。(例如，这在C解析器中是一种非常常见的策略。)但这也有点难看，因为这可能意味着lexer需要访问符号表，甚至可能访问名称解析函数，而解析器可能根本不需要这些函数。因此，这将需要名称解析、解析和词汇扫描之间的耦合，这比好的程序设计可能建议的要紧密得多。

  尽管如此，如果它是实用的，我基本上会接受它"良好的设计"；并不意味着排除合理的解决方案。只要注意保持各种组件之间的接口尽可能简单，而不必在不透明的数据结构中添加新的后门。

• 有了Bison，您有了第三种选择：您可以要求Bison创建一个GLR解析器，它不受前瞻性的限制。GLR解析器可以通过简单地并行维护所有可能性来处理任意长的前瞻，直到接收到足够的信息来解决它

  Bison的GLR算法不喜欢真正的模糊性，但这通常不是问题，因为编程语言不应该是模糊的。尽管如此，有时还是有必要允许不明确的解析，因为如果没有后续传递的语义信息，就无法真正解析。在这种情况下，可以使用自定义合并过程来创建具有替代分支的AST。

  即使您要求Bison生成GLR解析器，Bison也会生成冲突警告，因为您可能想了解这些警告。然而，如果你的语法不含糊，你就不必担心它们。如果你的语法不明确，并且你试图用多种可能的解析来解析输入，那么解析器会在运行时识别出问题，并发出错误消息。良好的测试将有助于识别可能的歧义，但它并不能提供明确性的证据。