在快乐中转移/减少冲突

Question

如何为解析if-then [-else]案例制定正确的规则？这是一些语法:

{
 module TestGram (tparse) where
}

%tokentype    { String  }
%token one    { "1"     } 
       if     { "if"    }
       then   { "then"  }
       else   { "else"  }

%name tparse  

%%

statement : if one then statement else statement {"if 1 then ("++$4++") else ("++$6++")"}
          | if one then statement                {"if 1 then ("++$4++")"}
          | one                                  {"1"}


{
 happyError = error "parse error"
}

该语法正确解析以下表达式:

> tparse ["if","1","then","if","1","then","1","else","1"]
"if 1 then (if 1 then (1) else (1))"

但编译会引发关于转移/减少冲突的警告.happy的文档包含了这种冲突的一个例子:http: //www.haskell.org/happy/doc/html/sec-conflict-tips.html

显示了两种解决方案,第一种是改变递归类型(在这种情况下不清楚如何做).第二个是不改变任何东西.这个选项对我来说还可以,但我需要咨询.

Answer 1

请注意,这是可能的不带S/R冲突LALR(1)语法来解决此问题:

stmt: open
    | closed

open: if one then stmt             {"if 1 then ("++$4++")"}
    | if one then closed else open {"if 1 then ("++$4++") else ("++$6++")"}

closed: one                            {"1"}
      | if one then closed else closed {"if 1 then ("++$4++") else ("++$6++")"}

这个想法来自这个关于解决悬空的其他/ if-else歧义的页面.

基本概念是我们将语句分为"开放"或"封闭":开放语句是指如果不与其他语句配对,则至少有一个语句; 封闭是那些没有如果可言,或者确实有他们,但他们都与配对别的.

解析if one then if one then one else one因此解析:

• . if- 转移
• if . one- 转移
• if one . then- 转移
• if one then . if- 转移
• if one then if . one- 转移
• if one then if one . then- 转移
• if one then if one then . one- 转移
• if one then if one then (one) . else- 按规则1 减少closed
• if one then if one then closed . else- 转移
• if one then if one then closed else . one- 转移
• if one then if one then closed else (one) .- 按规则1 减少closed
• if one then (if one then closed else closed) .- 按规则2 减少closed
• if one then (closed) .- 按规则2 减少stmt
• (if one then stmt) .- 按规则1 减少open
• (open) .- 按规则1 减少stmt
• stmt . - 停

(当发生减少时,我已经说明了哪个减少规则发生了,并且在令牌周围放了括号.)

我们可以看到解析器在LALR(1)中没有歧义(或者更确切地说,Happy或bison将告诉我们;-)),并且遵循规则产生正确的解释,内部如果与else一起被缩小.