haskell - 转移/减少快乐中的冲突

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))"

但是编译会引发关于 shift/reduce 冲突的警告。幸福的文档包含此类冲突的示例: http://www.haskell.org/happy/doc/html/sec-conflict-tips.html

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

Answer 1

请注意，可以使用 LALR(1) 中的语法解决此问题而不会发生 S/R 冲突:

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++")"}

这个想法来自 resolving the dangling else/if-else ambiguity 上的这个页面.

基本概念是我们将语句分类为“开放”或“封闭”:开放语句是那些至少有一个 if 没有与以下 else< 配对的语句/em>;封闭的是那些根本没有 if 的，或者有它们的，但它们都与 else 配对。

解析 if one then if one then one else one 这样解析:

• 。 if — 转移
• 如果。一个 — shift
• 如果一个。然后 — shift
• 如果一个那么。 if — 转移
• 如果一个那么如果。一个 — shift
• 如果一个那么如果一个。然后 — shift
• 如果一个那么如果一个那么。一个 — shift
• if one then if one then (one) 。 else — reduce closed 规则 1
• if one then if one then closed 。 else — 转移
• if one then if one then closed else 。一个 — shift
• if one then if one then closed else (one) . — reduce closed 规则 1
• if one then (if one then closed else closed) . — reduce closed 规则 2
• if one then (closed) . — reduce stmt 规则 2
• (if one then stmt) . — reduce open 规则 1
• (open) . — reduce stmt 规则 1
• stmt . — 停止

(当发生 reduce 时，我已经说明发生了哪个 reduction 规则，并在要减少的标记两边加上了括号。)

我们可以看到解析器在 LALR(1) 中没有歧义(或者更确切地说，Happy 或 bison 会告诉我们 ;-))，并且遵循规则会产生正确的解释，其中内部的 if 与 else 一起减少。