在快乐语法中转换/减少冲突

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

基本上,除非有等待消耗的令牌{或::令牌,否则应该使用标识符identifier pattern.

---

如果我的问题不清楚,我会道歉 - 部分问题是我很难确定问题甚至是什么.:(

Answer 1

首先,了解转变是很重要的.移位是接受下一个输入令牌并将其放在解析器堆栈上的结果(最终它将成为生产的一部分,但是没有必要知道哪一个.)减少需要零个或多个令牌在堆栈顶部与一些生产的右侧相匹配,并用左侧替换它们.

当解析器决定创建一个空identifier pattern的binding_mode ident at_patwhere时at_pat,它不会移位; 它正在减少.事实上,它减少了两次:首先它将零堆叠符号减少为空at_pat,然后将前三个堆栈符号减少为一个identifier pattern.如果没有binding_mode,它可以减少ident到expr_path然后减少expr_path到一个constant_expression.这样可以减少/减少冲突.

但还有另一个问题,正是因为可以binding_mode为空.当解析器看到一个时ident,它不知道是否binding_mode可能,因此它不知道是减少空binding_mode还是移位ident.这是一个转变/减少冲突.由于它更倾向于减少,它选择移动ident,这意味着binding_mode不能产生空,这反过来排除减少/减少冲突(并且防止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_paths:

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

expr_path: ident | complex_expr_path

我希望解决方案与你的原始语法有一些关系.