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

问题描述

是否有任何常用的方法，甚至是一个库，用于漂亮地打印(和解析)带有(二元)运算符的语法树，这些运算符具有关联性和优先级，以便结果使用尽可能少的括号?

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) 

假设优先级是 Imp Imp或 <和 <Not(所以 Not 绑定最多)并且 And、Or 和 Imp应该关联到右边；所以例如 Imp (And (Imp (Atom "A") (Atom "B")) (Atom "A")) (Atom "B") 应该打印类似 (A-> B)/ A ->B.

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.

当然这可以通过模式匹配来实现，但这既乏味又令人不快；我正在从 Coq 证明助手中寻找与此符号类似的简单内容:

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.

推荐答案

Formula 的 Show 实例可能如下所示:

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

这将允许任何 Formula 使用适当的括号 shown :

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

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

打印(print 是 putStrLn .show):

(A -> B) / A -> B

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