showsPrec和运算符优先级

Question

我之前已经问过这个问题，但是似乎我表达得太狭窄了。让我们看看我是否能解释一下我真正想要的。

假设我有某种类型，支持几个二元运算符，每个运算符具有不同的优先级和结合性。如何编写一个正确括号子表达式的 Show 实例？

我知道我在这里很愚钝，但是每次我尝试做到这一点时，我都会做错。一定有一些机械的步骤可以使这个程序正确工作，但我无法找到它。有人能给我举个例子吗？

我知道这最终归结为用 showParen 包装所有内容，并使用正确的魔术数字使用 showsPrec 显示子表达式，我可以使其 几乎 工作，但在 所有 情况下都不完全正确。

---

编辑： 考虑以下代码

data Expr =
  Const Int |
  Expr :+: Expr |
  Expr :-: Expr |
  Expr :*: Expr |
  Expr :/: Expr

infixl 6 :+:
infixl 6 :-:
infixl 7 :*:
infixl 7 :/:

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showParen (p > 6) $ (showsPrec 6 x) . (" :+: " ++) . (showsPrec 6 y)
     x :-: y -> showParen (p > 6) $ (showsPrec 6 x) . (" :-: " ++) . (showsPrec 6 y)
     x :*: y -> showParen (p > 7) $ (showsPrec 7 x) . (" :*: " ++) . (showsPrec 7 y)
     x :/: y -> showParen (p > 7) $ (showsPrec 7 x) . (" :/: " ++) . (showsPrec 7 y)

这个几乎正确地工作：

*Main> Const 1 :+: Const 2 :*: Const 3 :+: Const 4
1 :+: 2 :*: 3 :+: 4
*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(1 :+: 2) :*: (3 :+: 4)

但还不完全一样：

*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
1 :+: 2 :-: 3 :-: 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
1 :+: 2 :-: 3 :-: 4

看起来优先级没问题，但是结合性有问题。

- MathematicalOrchid

---

谷歌建议这两个问题：最小括号美化AST 和 在生成C / C++代码时表达式的结合性和优先级？。这些可能会给你一些想法。我不确定这是否符合其中一个的重复，但目前我倾向于“不是重复”，因为这个问题在一定程度上涉及如何使通用技术顺利地适应Haskell生态系统。 - Daniel Wagner

Answer 1

以下的 Show 实例将以最小括号方式打印 Expr 类型:

data Expr =
  Const Int |
  Expr :+: Expr |
  Expr :-: Expr |
  Expr :*: Expr |
  Expr :/: Expr

infixl 6 :+:
infixl 6 :-:
infixl 7 :*:
infixl 7 :/:

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> showParen (p > 10) $ showString "Const " . showsPrec 11 n
     x :+: y -> showParen (p > 6) $ showsPrec 6 x . showString " :+: " . showsPrec 7 y
     x :-: y -> showParen (p > 6) $ showsPrec 6 x . showString " :-: " . showsPrec 7 y
     x :*: y -> showParen (p > 7) $ showsPrec 7 x . showString " :*: " . showsPrec 8 y
     x :/: y -> showParen (p > 7) $ showsPrec 7 x . showString " :/: " . showsPrec 8 y

这将导致：

*Main> Const 1 :+: Const 2 :*: Const 3 :+: Const 4
Const 1 :+: Const 2 :*: Const 3 :+: Const 4
*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
Const 1 :+: Const 2 :-: Const 3 :-: Const 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)

通用规则是

• infix n: 在左边使用showParen (p > n)，showsPrec (n+1)，在右边使用showsPrec (n+1)
• infixl n: 在左边使用showParen (p > n)，showsPrec n，在右边使用showsPrec (n+1)
• infixr n: 在左边使用showParen (p > n)，showsPrec (n+1)，在右边使用showsPrec n
• 非中缀: 在参数上使用showParen (p > 10)和showsPrec 11

遵循这个规则将始终产生正确的语法，最小化括号，除了一个特殊情况：如果您具有相同优先级的infixl和infixr构造函数，则可能会产生模糊的输出。只要您不这样做，就应该没问题。

---

我如何知道在showParen中使用什么参数？它是为了匹配Haskell对派生Show实例所做的操作。我们可以这样测试：

data T = P :# P | T P
  deriving Show

infix 6 :#

data P = P

instance Show P where
  showsPrec p P = shows p

我们可以看到，在 infix 6 :# 中，Show T 实例在 :# 的参数上调用 showsPrec 7，并且仅在优先级大于6的情况下显示括号：

*Main> showsPrec 6 (P :# P) ""
"7 :# 7"
*Main> showsPrec 7 (P :# P) ""
"(7 :# 7)"

对于普通的构造函数T，生成的实例在参数上调用showsPrec 11并显示优先级大于10的括号：

*Main> showsPrec 10 (T P) ""
"T 11"
*Main> showsPrec 11 (T P) ""
"(T 11)"

- Brian Huffman

Answer 2

由于showsPrec没有办法获取上下文的结合性，我认为不可能像获取最小的Haskell括号化那样来修复它。为了确保正确性而不添加比必要更多的冗余括号，请在showParen条件中使用>=：

  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showParen (p >= 6) $ (showsPrec 6 x) . (" :+: " ++) . (showsPrec 6 y)
     x :-: y -> showParen (p >= 6) $ (showsPrec 6 x) . (" :-: " ++) . (showsPrec 6 y)
     x :*: y -> showParen (p >= 7) $ (showsPrec 7 x) . (" :*: " ++) . (showsPrec 7 y)
     x :/: y -> showParen (p >= 7) $ (showsPrec 7 x) . (" :/: " ++) . (showsPrec 7 y)

这就产生了：

*Main> Const 1 :+: Const 2 :*: Const 3 :+: Const 4
(1 :+: (2 :*: 3)) :+: 4
*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(1 :+: 2) :*: (3 :+: 4)
*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
((1 :+: 2) :-: 3) :-: 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
(1 :+: 2) :-: (3 :-: 4)

虽然看起来不太美观，但也不错，而且肯定比使用 showParen (p > n) 要好。基本上，如果我们只有“infix”，没有“infixl”或“infixr”，那么这给出了最小的括号。

如果您只想显示那些必需的括号，则需要传递比上下文优先级更多的信息。我为HaTeX实现了这种扩展符号数学扩展，基本上只是在运行时镜像了Haskell的infixl等注释。例如：

     exaDisp $ 5 - (4 - 3) + 2 + 1

然后呈现为

- leftaroundabout

Answer 3

这样怎么样：

prec :: Expr -> Int
prec (Const _) = 10
prec (_ :*: _) = 7
prec (_ :/: _) = 7
prec (_ :+: _) = 6
prec (_ :-: _) = 6

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showbin 6 " + " x y
     x :-: y -> showbin 6 " - " x y
     x :*: y -> showbin 7 " * " x y
     x :/: y -> showbin 7 " / " x y
    where showbin pr s x y =
            showParen (p > pr) $
             showsPrec pr x . (s ++) .
             showParen (prec y == pr) (showsPrec pr y)

导致

*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(1 + 2) * (3 + 4)
*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
1 + 2 - 3 - 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
1 + 2 - (3 - 4)
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4 :-: Const 5)
1 + 2 - (3 - 4 - 5)
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: (Const 4 :-: Const 5))
1 + 2 - (3 - (4 - 5))
*Main> Const 1 :+: Const 2 :-: (Const 3 :*: (Const 4 :/: Const 5))
1 + 2 - 3 * (4 / 5)
*Main> (Const 1 :*: (Const 2 :-: (Const 3 :*: (Const 4 :/: Const 5))))
1 * (2 - 3 * (4 / 5))

- myzoski