相关疑难解决方法(0)

我正在为一个JavaScript AST实现一个漂亮的打印机,我想问一下是否有人知道一个"正确的"算法,根据运算符优先级和关联性自动用最小括号括起表达式.我没有在谷歌上找到任何有用的材料.

显而易见的是,父级具有更高优先级的运算符应该用括号括起来,例如:

(x + y) * z // x + y has lower precedence

但是,也有一些运算符不是关联的,在这种情况下仍需要括号,例如:

x - (y - z) // both operators have the same precedence

我想知道后一种情况的最佳规则是什么.对于除法和减法,是否足以说明,如果rhs子表达式的优先级小于或等于,则应将其括起来.

我在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 …