haskell - Parsec.Expr 以不同优先级重复 Prefix

Question

Parsec.Expr.buildExpressionParser 的文档说:

Prefix and postfix operators of the same precedence can only occur once (i.e. --2 is not allowed if - is prefix negate).

但是，我想解析这样的字符串。

具体来说，考虑以下语法:

sentence: 
    | identifier
    | "~" sentence
    | sentence & sentence
    | "!" sentence

其中运算符优先级为: "~"比 "&" 更强的结合力比 "!" 更强的结合力

例如，我想要句子

! ~a & b

被解析为

! ( (~a) & b )

还有那句话

~ ! a & b 

作为

~( ! ( a & b) )

Parsec 允许我这样做(并指定运算符优先级)，但是，我希望能够链接前缀，例如 ~ ~ ! ~ a .
Parsec 不允许这样做。
我找到了解决方案 for chaining prefixes ，但是这个解决方案不允许我为不同的前缀运算符指定不同的运算符优先级(“~”和“!”的绑定(bind)比“&”强，或者它们都没有)

有人对此有解决方案吗？

编辑:

使运算符绑定(bind)正确但不允许链接的部分解决方案:
http://lpaste.net/143362

带有链接但对“~”运算符有错误绑定(bind)的部分解决方案:
http://lpaste.net/143364

编辑:与 latest answer 相关的更多说明.

我其实想要 &是联想的。左或右无所谓。左与右关联仅在具有相同优先级的运算符之间起作用。
对于您的示例，请注意 &比 ! 更强的结合力( & 具有更高的运算符优先级)

因此，您担心的表达式:
a & ! b & c应该变成:
(在可能的情况下首先绑定(bind) &) a & ! (b & c)
同样， ! a & ! b & c应该被解析
(先绑定(bind)&) ! a & ! (b & c) ，因此 ! a & (! (b & c)) ，因此 ! (a & (! (b & c)))

Answer 1

我对我的原始答案不满意，因为它不能解决各种优先级的前缀和后缀运算符的一般情况，它要求程序员必须考虑语法，而不是仅仅依赖 buildExpressionParser做正确的事。

我在网上四处寻找，发现了Pratt method for recursive descent parsing of expressions .我能够实现一个紧凑的 Haskell 版本来替换 buildExpressionParser .它的界面与buildExpressionParser 完全相同。 ，但不需要您使用链式前缀组合器或使用术语解析器。我玩弄了你的语法，改变了 & 的关联性，并将前缀运算符切换为后缀运算符，这一切似乎都有效......

buildPrattParser table termP = parser precs where

  precs = reverse table

  prefixP = choice prefixPs <|> termP where
    prefixPs = do
      precsR@(ops:_) <- tails precs 
      Prefix opP <- ops
      return $ opP <*> parser precsR

  infixP precs lhs = choice infixPs <|> pure lhs where
    infixPs = do
      precsR@(ops:precsL) <- tails precs
      op <- ops
      p <- case op of
        Infix opP assoc -> do
          let p precs = opP <*> pure lhs <*> parser precs
          return $ case assoc of
            AssocNone  -> error "Non associative operators are not supported"
            AssocLeft  -> p precsL
            AssocRight -> p precsR
        Postfix opP ->
          return $ opP <*> pure lhs
        Prefix _ -> mzero
      return $ p >>= infixP precs

  parser precs = prefixP >>= infixP precs