使用Haskell实现操作符优先级和结合性的漂亮打印语法树

Question

有没有常用的方法或者库可以将带有结合性和优先级的（二元）操作符的语法树进行漂亮的打印（和解析），以便结果使用尽可能少的括号？

---

以命题演算公式为例：

data Formula
    = Atom String
    | Not (Formula)
    | And (Formula) (Formula)
    | Or (Formula) (Formula)
    | Imp (Formula) (Formula) 

假设优先级为Imp < Or < And < Not（因此，Not 优先级最高），并且 And ， Or 和 Imp 应该向右结合； 因此，例如， Imp（And（Imp（Atom“ A”）（Atom“ B”））（Atom“ A”））（Atom“ B”）应打印类似于（A -> B）/\ A -> B 的内容。

---

当然可以通过模式匹配来实现，但这很繁琐而且非常不愉快。我正在寻找与Coq证明助手的此表示法类似的东西：

Notation "A /\ B" := (and A B) (at level 80, right associativity).

生成一个解析器和一个漂亮的打印机。

- jules

---

在Haskell中没有像Coq那样的语言特性，你很可能需要自己编写一个解析器。标准的parsec可以很容易地处理这种情况。一些库（比如）允许您从语法规范定义解析器和漂亮打印机。 - user2407038

Answer 1

一个Formula的Show实例可能如下所示：

instance Show Formula where
  showsPrec _ (Atom name) = showString name
  showsPrec p (Not formula) = showParen (p > 3) $
    showString "\\+ " . showsPrec 3 formula
  showsPrec p (And lhs rhs) = showParen (p > 2) $
    showsPrec 3 lhs . showString " /\\ " . showsPrec 2 rhs
  showsPrec p (Or lhs rhs) = showParen (p > 1) $
    showsPrec 2 lhs . showString " \\/ " . showsPrec 1 rhs
  showsPrec p (Imp lhs rhs) = showParen (p > 0) $
    showsPrec 1 lhs . showString " -> " . showsPrec 0 rhs

这将允许任何公式以适当的括号形式显示：

main = print $ Imp (And (Imp (Atom "A") (Atom "B")) (Atom "A")) (Atom "B")

打印（print 是 putStrLn . show）：

(A -> B) /\ A -> B

- pat