代码之家 › 专栏 › 技术社区 › Luke Collins

如何判断括号是否必要?

pretty-print haskell parsing

7

Luke Collins · 技术社区 · 6 年前

我用Haskell编写了一个解析器,它以字符串输入的形式解析公式并生成一个Haskell data

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

有没有办法衡量有多少括号是必要的,以便语义永远不含糊不清?我很感激你的反馈。

1 回复 | 直到 6 年前

1

chi 6 年前

未经测试的伪代码:

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 & ... 然后优先级别为 & .

如果需要在优先级较高的上下文中打印符号,则需要添加括号。E、 g.如果 f型 a | b 我们不能写 a | b & ... ,否则解释为 a | (b & ...) a | b公司 showParen (p > ...) .

上面,我随机选择了优先级别。你需要根据你的口味调整它们。您还应该检查选择的级别是否与标准库一起播放。E、 g.印刷 Just someFormula 不应该产生 Just a & b ,但添加括号。