在Haskell中具有运算符优先级和关联性的漂亮打印语法树 [英] Pretty Printing Syntax Tree with Operator Precedence and Associativity in Haskell

问题描述

是否有任何常用的方法，甚至是一个用于使用（二进制）运算符打印（和解析）语法树的库，这些运算符具有指定的关联性和优先级，以便结果使用尽可能少的括号？ / p>

---

以命题演算公式为例：

 数据公式
 =原子字符串
 |不是（公式）
 |和（公式）（公式）
 |或（公式）（公式）
 | Imp（公式）（公式）
  

假设优先级为 Imp < 或< 和< 不是（所以不是最多）和并且 ，或者和 Imp 应该关联到右侧;例如 Imp（And（Imp（AtomA）（AtomB））（AtomA））（AtomB）如（A - > B）/ \\ A - > B 。

---

当然，这可以通过模式匹配来实现，但这非常单调乏味不愉快;我正在寻找类似于Coq证明助理这种符号的简单方法：

 符号A / \ B： =（和AB）（在等级80，右结合）。 
  

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

公式的显示实例可能如下所示：解决方案 / p>

  instance显示公式其中
显示Prec _（Atom name）= showString name 
 showsPrec p（非公式） = 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 
  

这将允许任何公式 显示 n与适当的元素：

  main = print $ Imp （And（Imp（AtomA）（AtomB））（AtomA））（AtomB）
  

Prints（ print 是 putStrLn。show ）：

 （A  - > B）/ \ A  - > B 
  

Is there any commonly used method or even a library for pretty printing (and parsing) a syntax tree with (binary) operators that have an associativity and a precedence level assigned, so that the result uses as few brackets as possible?

---

Take the formulas of propositional calculus as an example:

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

Assume that the precedence is Imp < Or < And < Not (so Not binds the most) and that And, Or and Imp should associate to the right; so for example Imp (And (Imp (Atom "A") (Atom "B")) (Atom "A")) (Atom "B") should print something like (A -> B) /\ A -> B.

---

Of course this could be achieved by pattern matching but this is tedious and very unpleasant; I'm looking for something similarly simple to this notation from the Coq proof assistant:

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

which generates a parser and a pretty printer.

解决方案

A Show instance for Formula might look like this:

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

Which will allow any Formula to be shown with appropriate parens:

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

Prints (print is putStrLn . show):

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

这篇关于在Haskell中具有运算符优先级和关联性的漂亮打印语法树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！