haskell - 转移/减少 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                      { }

它可以转移/减少模式中标识符的冲突。默认情况下，Happy 选择转移，但在这种情况下，这不是我想要的:它试图将所有内容硬塞到 constant expression 中。即使它可能是 identifier pattern .

我读到优先级/关联性是解决此类问题的方法，但我添加的任何内容都无法使语法朝正确的方向移动(公平地说，我大部分时间都在拍摄在黑暗中)。

使用一些明显的标记化，我希望:

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

基本上，除非有 {或::等待消耗的 token ，标识符应转到 identifier pattern案例。

---

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

Answer 1

首先，了解什么是转变非常重要。移位是接受下一个输入标记并将其放在解析器堆栈上的结果(它最终将成为产生式的一部分，但还没有必要知道是哪一个。)减少是采用零个或多个标记离开堆栈顶部，与某些产生式的右侧相匹配，并将其替换为左侧。

当解析器决定从 binding_mode ident at_pat 创建一个标识符模式(其中 at_pat 为空)时，它不会移位；它正在减少。事实上，它减少了两次:首先，它将零堆栈符号减少为空 at_pat，然后将前三个堆栈符号减少为 标识符模式。如果没有 binding_mode，它可能会将 ident 简化为 expr_path，然后将 expr_path 简化为 >常量表达式。所以这将是一个减少/减少冲突。

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

因此，为了解决所有这些问题，我们需要首先避免减少空 binding_mode 的必要性。我们通过通常的可为空产生消除算法来做到这一点，该算法涉及制作右侧的两个副本，一个带有可为空非终结符，另一个没有；然后我们删除可为空的产生式。一旦我们这样做了，就会出现归约/归约冲突。

为了避免归约/归约冲突，我们需要明确首选哪种生产方式。归约/归约冲突无法通过优先级声明来解决，因为优先级算法总是涉及产生式(可以归约)和终结符(可以移动)之间的比较。因此解析必须是显式的，这意味着我们需要说一个裸ident是一个模式，而一个expr_path不是一个ident 是一个常量表达式。这给我们留下了以下内容:

(请注意，我使用非终结符来标记 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_path:

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

expr_path: ident | complex_expr_path

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