Shift/reduce Happy 语法冲突

Question

我得到了以下（大量精简）快乐语法

%token
   '{'   { Langle }
   '}'   { Rangle }
   '..'  { DotDot }
   '::'  { ColonColon }
   '@'   { At }
   mut   { Mut }
   ident { Ident }

 %%

 pattern
   : binding_mode ident at_pat  { error "identifier pattern" }
   | expr_path                  { error "constant expression" }
   | expr_path '{' '..' '}'     { error "struct pattern" }

 binding_mode
   : mut                        { }
   |                            { }

 at_pat
   : '@' pat                    { }
   |                            { }

 expr_path
   : expr_path '::' ident       { }
   | ident                      { }

模式中的标识符存在 shift/reduce 冲突。默认情况下，Happy 选择移动，但在这种情况下这不是我想要的：它试图将所有内容都塞进 constant expression，即使它可能是 identifier pattern.

我读到 precedence/associativity 是解决这类问题的方法，但我添加的任何内容都无法使语法朝着正确的方向发展（公平地说，我已经大部分时间都是在黑暗中拍摄的）。

使用一些明显的标记化，我想要：

x 产生 identifier pattern
mut x 产生 identifier pattern
std::pi 产生 constant expression
point{..} 产生 struct pattern
std::point{..} 产生 struct pattern

基本上，除非有 { 或 :: 令牌等待被消费，否则标识符应该转到 identifier pattern 案例。

如果我的问题不清楚，我深表歉意 - 部分问题是我很难确定问题所在。 :(

Answer 1

首先，了解什么是转变很重要。移位是接受下一个输入标记并将其放入解析器堆栈的结果（它最终将成为产生式的一部分，但还没有必要知道是哪一个。）减少是采用零个或多个标记从堆栈顶部匹配某些生产的 right-hand 侧，并用 left-hand 侧替换它们。

当解析器决定从 binding_mode ident at_pat 中创建一个 identifier pattern 时，其中 at_pat 为空，它不会移动；它正在减少。实际上，它减少了两次：首先它将零个堆叠符号减少为空 at_pat，然后将前三个堆叠符号减少为 identifier pattern。如果没有 binding_mode，它可以将 ident 减少为 expr_path，然后将 expr_path 减少为 constant_expression。所以这将是一个 reduce/reduce 冲突。

但是还有一个问题，正是因为 binding_mode 可以为空。当解析器看到 ident 时，它不知道 binding_mode 是否可能，因此它不知道是减少空 binding_mode 还是移动 ident。那是一个 shift/reduce 冲突。由于它更喜欢shift而不是reduce，所以它选择shift ident，这意味着不能产生一个空的binding_mode，这反过来又排除了reduce/reduce冲突（并防止ident @ pat 完全不被认出来。）

因此，要理清所有这些问题，我们需要从避免减少空 binding_mode 的必要性开始。我们通过通常的 nullable-production 消除算法来做到这一点，该算法涉及制作 right-hand 端的两份副本，一份带有可空非终结符，另一份没有；然后我们删除可为空的产生式。一旦我们这样做，就会出现 reduce/reduce 冲突。

为避免 reduce/reduce 冲突，我们需要明确说明首选哪个产品。 Reduce/reduce 冲突不能通过优先声明来解决，因为优先算法总是涉及生产（可以减少）和终端（可以移位）之间的比较。所以解析必须是明确的，这意味着我们需要说一个裸 ident 是一个模式，而一个 expr_path 而不是 ident 是一个常量表达式。这给我们留下了以下内容：

（请注意，我使用 non-terminals 来标记 pattern 的三个不同作品，而不是依赖动作。对我来说，这更容易思考和阅读。）

pattern: identifier_pattern | constant_expression | struct_pattern

这里是空生产消除：

identifier_pattern:   ident at_pat 
                  |   binding_mode ident at_pat

这里是对身份的明确禁止：

constant_expression:  complex_expr_path 

struct_pattern:       expr_path '{' '..' '}'

binding_mode 不再可以为空：

binding_mode: mut

at_pat
   : '@' pat
   | %empty

这里我们创建两个不同的expr_paths:

complex_expr_path
   : complex_expr_path '::' ident
   | ident '::' ident

expr_path: ident | complex_expr_path

我希望这个解决方案与您原来的语法有一些关系。

Shift/reduce Happy 语法冲突

Shift/reduce conflict in Happy grammar

grammar

haskell

parser-generator

happy

ambiguous-grammar