2

我有以下（严重剥离）快乐语法

%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

基本上，除非有一个{或::令牌等待被消费，否则一个标识符应该去identifier patterncase。

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

4

1 回答 1

5

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

当解析器决定创建一个identifier patternout of binding_mode ident at_patwhereat_pat为空时，它并没有移动；它正在减少。实际上，它减少了两次：首先将零堆叠符号减少为空at_pat，然后将顶部三个堆叠符号减少为identifier pattern. 如果没有binding_mode，它可能会减少ident到expr_path，然后再减少expr_path到constant_expression。所以这将是一个减少/减少冲突。

但是还有另一个问题，正是因为binding_mode它可以为空。当解析器看到 aident时，它不知道 a 是否binding_mode可能，所以它不知道是减少一个空binding_mode还是移动ident。那是一个转变/减少冲突。由于它更喜欢 shift 而不是 reduce，所以它选择 shift ident，这意味着binding_mode不能产生空，这反过来又排除了 reduce/reduce 冲突（并且ident @ pat根本无法识别。）

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

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

（请注意，我使用非终结符来标记 的三种不同产生式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

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

于 2017-02-02T01:38:56.733 回答