如何判断括号是否必要？

Question

我在Haskell中编写了一个解析器,它以字符串输入的形式解析公式,并生成data由下面的BNF定义的Haskell 类型.

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

    var ::=  letter { letter | digit }*

现在我想创建一个实例,Show以便我可以很好地打印我的类型定义的公式(我不想使用deriving (Show)).我的问题是:如何定义我的功能,以便它可以告诉括号何时是必要的？我不想要太多,也不要太少括号.

例如,给定公式? X . (X & Y) & (? Y . Y) & false,在解析时,生成数据结构

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

我们有

   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

有没有办法衡量需要多少括号,以便语义永远不会模糊？我感谢任何反馈.

Answer 1

未经测试的伪代码：

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
   ...

（我可能应该使用showString而不是++上面的那些。无论如何，我认为它应该有效。）

上面，整数p表示我们显示当前公式的上下文的优先级。例如，如果我们显示f内部f & ...，则p优先级将为&。

如果我们需要在具有更高优先级的上下文中打印符号，则需要添加括号。例如如果f是a | b我们不能写a | b & ...，否则它被解释为a | (b & ...)。我们需要把括号括起来a | b。这是由showParen (p > ...).

当我们递归时，我们将手头符号的优先级传递给子项。

上面，我随机选择了优先级。您需要根据自己的口味调整它们。您还应该检查您选择的级别是否符合标准库。例如，打印Just someFormula不应生成类似 的内容Just a & b，而应添加括号。