parsing - 如何判断括号是否必要？

Question

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

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 之类的内容, 但添加括号。