On Tue, Apr 10, 2007 at 09:20:52AM +0200, Alfonso Acosta wrote:
I have to prettyprint infix expressions writing the least possible parenthesis (taking in account precedence and associativity). A simplified expression type could be:
Your use of 'have' is slightly suspicious here. That said, the rest of your problem looks very un-homework-y, so I'll look at it. "Associativity" is ambiguous here. Do you mean: 1 + 2 + 3 => (1 + 2) + 3 (Associativity of parsing) (1 + 2) + 3 == 6 == 1 + (2 + 3) (Associativity of functions) ?
data Expr = Val String | -- Binary operators (using infix constructors) Expr :+: Expr | Expr :-: Expr | Expr :*: Expr | Expr :/: Expr | Expr :^: Expr | -- Unary operators Negate Expr
I'm using HughesPJ for the rest of my AST (not just expressions) but the library doesn't provide any mechanism to help coding this kind of prettyprinter so I decided to simply use the standard showsPrec and then feed HughesPJ with the obtained text.
That seems very counter-productive. By using showsPrec, you lose all the information that could be used to guide line breaks. It would be far better to do it yourself. Note that the method I am about to show is exactly the same as that used by the standard showsPrec: -- let +, - have infixl 1 -- let *, / have infixl 2 -- let ^ have infixr 3 -- let uminus have (nofix) 4 pprExpr :: Int -- ^ Precedence context - if you're like me no -- explanation of this will make more sense than the -- code -> Expr -> Doc pprExpr cx (Val str) = text str pprExpr cx (a :+: b) = cparen (cx >= 1) $ pprExpr 1 a <+> char '+' <+> pprExpr 1 b pprExpr cx (a :-: b) = cparen (cx >= 1) $ pprExpr 1 a <+> char '+' <+> pprExpr 1 b pprExpr cx (a :*: b) = cparen (cx >= 2) $ pprExpr 2 a <+> char '+' <+> pprExpr 2 b pprExpr cx (a :/: b) = cparen (cx >= 2) $ pprExpr 2 a <+> char '+' <+> pprExpr 2 b pprExpr cx (a :^: b) = cparen (cx >= 3) $ pprExpr 3 a <+> char '+' <+> pprExpr 3 b pprExpr cx (Negate a) = cparen (cx >= 4) $ char '-' <+> pprExpr 4 a -- this is provided for ShowS under the name showsParen, but -- unfortunately does not exist for Doc standardly cparen :: Bool -> Doc -> Doc cparen False = id cparen True = parens
showsPrec helps to take advantage of the precedence information. However, I don't find a way to remove parenthesis according to associativity.
A simple modification of the above code will do it: pprExpr cx (Val str) = text str pprExpr cx (a :+: b) = cparen (cx >= 1) $ pprExpr 0 a <+> char '+' <+> pprExpr 1 b pprExpr cx (a :-: b) = cparen (cx >= 1) $ pprExpr 0 a <+> char '-' <+> pprExpr 1 b pprExpr cx (a :*: b) = cparen (cx >= 2) $ pprExpr 1 a <+> char '*' <+> pprExpr 2 b pprExpr cx (a :/: b) = cparen (cx >= 2) $ pprExpr 1 a <+> char '/' <+> pprExpr 2 b pprExpr cx (a :^: b) = cparen (cx >= 3) $ pprExpr 3 a <+> char '^' <+> pprExpr 2 b pprExpr cx (Negate a) = cparen (cx >= 4) $ char '+' <+> pprExpr 4 a Handling line breaks is left as an excercise for the reader.
I'm sure this kind of prettyprinting has been already done zillions of times in Haskell. Any suggestions?
Stefan