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

本文介绍了Parsec.Expr以不同的优先级重复前缀的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 Parsec.Expr.buildExpressionParser的文档说： 然而，我想解析这样的字符串。 具体来说，请考虑以下语法： 句子： |标识符 | 〜句子 |句子&句子 | ！句子 运算符优先级为：〜绑定强于&绑定强于！ 例如，我想要判刑 ！ 〜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：_）前缀opP 返回$ 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:However, I would like to parse such strings. Concretely, consider the following grammar:sentence: | identifier | "~" sentence | sentence & sentence | "!" sentenceWhere operator precedence is: "~" binds stronger than "&" binds stronger than "!" For example, I would like the sentence ! ~a & bto 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/143362Partial solution with chaining but that has a wrong binding for the "~" operator:http://lpaste.net/143364Edit: 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以不同的优先级重复前缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！