Happy中的移位/减少冲突

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冲突的警告。happy的文档包含了这种冲突的一个例子：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上的这个页面。

基本的概念是，我们将语句分类为" open“或" closed "：open语句是那些至少有一个if的语句，它不与以下语句配对；closed是那些根本没有if的语句，或者有if的语句，但它们都与else配对。

因此，解析if one then if one then one else one会解析：

• . if - shift
• if . one - shift
• if one . then - shift
• if one then . if - shift
• if one then if . one - shift
• if one then if one . then - shift
• if one then if one then . one - shift
• if one then if one then (one) . else -reduce by closed规则1
• if one then if one then closed . else - shift
• D51shift
• if one then if one then closed else (one) . - reduce by closed规则2
• (if one then stmt) . - reduce by closed规则1
• stmt . -reduce by closed规则1
• stmt .-e175 reduce E276 by D77规则-E181reduce规则D83reduce E282 stmt -stop H287F288

(当reduce发生时，我已经说明了发生哪个reduce规则，并将被reduce的标记放在圆括号中。)

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