Parsec.Expr以不同的优先级重复前缀

Question

Parsec.Expr.buildExpressionParser的文档说:

相同优先级的前缀和后缀运算符只能出现一次(如果 - 是前缀否定,则不允许--2).

但是,我想解析这样的字符串.

具体来说,请考虑以下语法:

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

运算符优先级为:"~"绑定强于"&"绑定强于"!"

例如,我想要这句话

! ~a & b

被解析为

! ( (~a) & b )

而且这句话

~ ! a & b 

如

~( ! ( a & b) )

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

有人有解决方案吗？

编辑:

部分解决方案使操作员绑定正确,但不允许链接:http: //lpaste.net/143362

带链接的部分解决方案,但对"〜"运算符有错误的绑定:http: //lpaste.net/143364

编辑:有关最新答案的更多说明.

我其实想要&联想.左或右无所谓.左与右关联性仅在具有相同优先级的运算符之间起作用.对于您的示例,通过注意&绑定强于!(&具有更大的运算符优先级)来解决所有问题

因此,你担心的表达方式:

a & ! b & c应该成为:( &在可能的情况下首先绑定) a & ! (b & c)

类似地,! a & ! b & c应被解析(第一绑定&) ! a & ! (b & c),从而! a & (! (b & c)),由此! (a & (! (b & c)))

Answer 1

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

我在网上搜索并发现了表达式递归下降解析的普拉特方法。我能够实现一个紧凑的 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