Parsec.Expr以不同的优先级重复前缀 [英] Parsec.Expr repeated Prefix with different priority

问题描述

Parsec.Expr.buildExpressionParser的文档说：

相同优先级的前缀和后缀运算符只能出现一次（即 - -2是不允许的，如果 - 是前缀否定）。

然而，我想解析这样的字符串。

具体来说，请考虑以下语法：

 句子：
 |标识符
 | 〜句子
 |句子&句子
 | ！句子
  

运算符优先级为：〜绑定强于&绑定强于！

例如，我想要判刑

 ！ 〜a& b 
  

被解析为

 ！ （（〜a）& b）
  

以及

 〜！一个& b 
  

as

 〜（！（a& b））
  

Parsec允许我这样做（并指定运算符优先级），但是，我希望能够链接前缀，例如 ~~！ 〜a 。
Parsec不允许这样做。
我找到了解决方法链接前缀 ，但是这个解决方案不允许我为不同的前缀运算符指定不同的运算符优先级（或者〜和！绑定比&更强，或者它们都不会）

有没有人有解决方案？

编辑：

部分解决方案使运算符绑定正确，但允许无链：
http://lpaste.net/143362

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

编辑：一些与最佳答案。

实际上我希望& 是关联的。左或右无所谓。左和右关联性只在同一优先级的运算符之间存在。
对于您的示例，通过注意& 绑定强于！（<$

因此，您担心的表达式：

a& ！ b& c 应该变为：
（如有可能，首先绑定& ）
a& ！ （b& c）

同样，！一个& ！ b& c 应该被解析
（first bind&）
！一个& ！ （b& c），因此！一个& （！（b& c）），因此！ （a&（！（b& c）））

解决方案

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

我在网上搜索并发现了 Pratt递归下降解析表达式的方法。我能够实现一个紧凑的Haskell版本来替换 buildExpressionParser 。它与 buildExpressionParser 具有完全相同的接口，但不要求使用链接前缀组合符或使用术语解析器。我玩弄了你的语法，改变了& 的关联性，并将前缀运算符切换到后缀运算符，并且这一切似乎都奏效......

  buildPrattParser表termP =解析器precs其中
 
 precs =反转表
 
前缀P =选择前缀Ps < |> termP其中
 prefixPs = do 
 precsR @（ops：_）< -  tailils precs 
前缀opP < -  ops 
返回$ opP *<解析器precsR 
 
 infixP precs lhs =选择infixPs< |>纯lhs其中
 infixPs = do 
 precsR @（ops：precsL）<  - 尾数precs 
 op<  -  ops 
p<  -  
的情况opix opP assoc  - > do 
 let p precs = opP * *纯lhs *解析器precs 
返回$ case assoc 
 AssocNone  - >错误不支持非关联运算符
 AssocLeft  - > p precsL 
 AssocRight  - > p precsR 
 Postfix opP  - > 
返回$ opP< *>纯lhs 
前缀_  - > mzero 
 return $ p>> = infixP precs 
 
 parser precs = prefixP>> = infixP precs 
  

The documentation for Parsec.Expr.buildExpressionParser says:

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

However, I would like to parse such strings.

Concretely, consider the following grammar:

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

Where operator precedence is: "~" binds stronger than "&" binds stronger than "!"

For example, I would like the sentence

! ~a & b

to be parsed as

! ( (~a) & b )

And the sentence

~ ! a & b 

as

~( ! ( a & b) )

Parsec allows me to do this (and specify the operator precedence), however, I would like to be able to chain prefixes, e.g. ~ ~ ! ~ a. Parsec does not allow this. I have found the solution for chaining prefixes, but this solution does not allow me to specify a different operator priority for the different prefix operators (either both "~" and "!" bind stronger than "&", or none of them does)

Does anyone have a solution for this?

Edit:

Partial solution that gets the operator bindings correct, but allows no chaining: http://lpaste.net/143362

Partial solution with chaining but that has a wrong binding for the "~" operator: http://lpaste.net/143364

Edit: Some more clarifications related to the latest answer.

I actually want & to be associative. Left or right does not matter. Left vs right associativity only matters between operators of the same precedence. For your examples, it is all resolved by noting that & binds stronger than ! (& has greater operator precedence)

Hence, the expression you were worried about:

a & ! b & c should become: (first bind & where possible) a & ! (b & c)

Similarly, ! a & ! b & c should be parsed (first bind &) ! a & ! (b & c), thus ! a & (! (b & c)), thus ! (a & (! (b & c)))

解决方案

I wasn't satisfied with my original answer since it doesn't solve the general case of prefix and postfix operators at various precedences, and it requires the programmer to have to think about the grammar instead of just relying on buildExpressionParser to do the right thing.

I hunted around online and discovered the Pratt method for recursive descent parsing of expressions. I was able to implement a compact Haskell version that replaces buildExpressionParser. It has exactly the same interface as buildExpressionParser, but doesn't require you to use the chained prefix combinators or muck around with the term parser. I played around with your grammar, changing the associativity of &, and switching the prefix operators to postfix operators, and it all seems to work...

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

这篇关于Parsec.Expr以不同的优先级重复前缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！