野牛减少了与前瞻性令牌集的冲突

Question

我该如何修复这个LR(2)(我认为(语法部分？我想在这个规则中解析type[]和type，但我得到了一个减少冲突：

expression:
... other expressions
| expression LSQUARE expression RSQUARE
| expression KW_IS type
| expression KW_AS type
... other expressions
;

type
: fqtypename LSQUARE RSQUARE
| live_types LSQUARE RSQUARE
| fqtypename
| live_types
;
fqtypename
: identifier
| fqtypename DOT identifier
;
live_types
: KW_INT | KW_DOUBLE | KW_BOOL | KW_STRING
;

我得到的错误是：

State 113
56 type: fqtypename • LSQUARE RSQUARE
58     | fqtypename •
63 fqtypename: fqtypename • DOT identifier
LSQUARE  shift, and go to state 123
DOT      shift, and go to state 21
LSQUARE   [reduce using rule 58 (type)]
DOT       [reduce using rule 58 (type)]
$default  reduce using rule 58 (type)

State 114
57 type: live_types • LSQUARE RSQUARE
59     | live_types •
LSQUARE  shift, and go to state 124
LSQUARE   [reduce using rule 59 (type)]
$default  reduce using rule 59 (type)

我试图将其重新创建为最小可复制的示例：

%require "3.0"
%defines
%define api.pure full
%define parse.trace
%token LSQUARE '['
%token RSQUARE ']'
%token DOT '.'
%token IS "is"
%%
example
:expression
;

expression
: expression LSQUARE expression RSQUARE
| expression IS type
| identifier
;

type
: fqtypename LSQUARE RSQUARE
| fqtypename
;
fqtypename
: identifier
| fqtypename DOT identifier
;
identifier: 
"blah"
;
%%

有错误：

State 10
5 type: fqtypename • LSQUARE RSQUARE
6     | fqtypename •
8 fqtypename: fqtypename • DOT identifier
LSQUARE  shift, and go to state 13
DOT      shift, and go to state 14
LSQUARE   [reduce using rule 6 (type)]
$default  reduce using rule 6 (type)

Answer 1

你是对的，这是LR(2(语法。在解析器读取expression IS identifier之后，以[作为先行标记，它需要查看[之后的内容，以知道是立即将identifier缩减为type，还是将[]包括在type中。

尽管总是可以将LALR(2(语法转换为等效的LALR(1(语法，但该算法产生了大量语法。(不过，它可以重新创建原始的解析树。(有时可以为特定语法想出一个更精简的解决方案，但在这种情况下，我看不到明显的解决方案。

一个常见的解决方案是将延迟逻辑放入词法分析器中。例如，在找到[时，词法分析器可以读取下一个(非空白标记(；如果该令牌是]，则它可以返回制造的LRSQUARE("[]"(令牌；否则，它为下一个调用保留新的先行令牌，并立即返回LSQUARE。这基本上就是Bison本身处理可选分号的LR(2(方面的方式。(如果您使用推送解析器，这会稍微容易实现，因为单个词法分析器操作可以一次发送两个令牌。(

另一种解决方案是使用GLR解析器，它允许在必要时通过并行探索多种可能性进行任意前瞻。在LR(2(的情况下，额外的开销是最小的，但它仍然存在。