How to tell whether parentheses are necessary or not?

Question

I have written a parser in Haskell, which parses formulas in the form of string inputs and produces a Haskell data type defined by the BNF below.

formula ::=  true  
         |  false  
         |  var  
         |  formula & formula  
         |  ∀ var . formula
         |  (formula)

    var ::=  letter { letter | digit }*

Now I would like to create an instance of Show so that I can nicely print the formulas defined by my types (I don't want to use deriving (Show)). My question is: How do I define my function so that it can tell when parentheses are necessary? I don't want too many, nor too little parentheses.

For example, given the formula ∀ X . (X & Y) & (∀ Y . Y) & false which, when parsed, produces the data structure

And (And (Forall "X" (And (Var "X") (Var "Y"))) (Forall "Y" (Var "Y"))) False

we have

   Too little parentheses:    ∀ X . X & Y & ∀ Y . Y & false
   Too much parentheses:      (∀ X . (((X) & (Y)))) & (∀ Y . (Y)) & (false)
   Just right:                ∀ X . (X & Y) & (∀ Y . Y) & false

Is there a way to gauge how many parenthesis are necessary so that the semantics is never ambiguous? I appreciate any feedback.

Answer 1

Untested pseudocode:

instance Show Formula where
   showsPrec _p True  = "True"
   showsPrec _p False = "False"
   showsPrec p (And f1 f2) = showParen (p > 5) $
      showsPrec 5 f1 . (" & " ++) . showsPrec 5 f2
   showsPrec p (Forall x f) = showParen (p > 8) $
      ("forall " ++ x ++) . showsPrec 8 f
   ...

(I should probably use showString instead of those ++ above. It should work anyway, I think.)

Above, the integer p represents the precedence of the context where we are showing the current formula. For example, if we are showing f inside f & ... then p will have the precedence level of &.

If we need to print a symbol in a context which has higher precedence, we need to add parentheses. E.g. if f is a | b we can't write a | b & ..., otherwise it is interpreted as a | (b & ...). We need to put parentheses around a | b. This is done by the showParen (p > ...).

When we recurse, we pass the precedence level of the symbol at hand to the subterms.

Above, I chose the precedence levels randomly. You need to adjust them to your tastes. You should also check that the levels you choose play along the standard libraries. E.g. printing Just someFormula should not generate things like Just a & b, but add parentheses.