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

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，但此解决方案不允许我为不同的前缀运算符指定不同的运算符优先级（“~”和“！”绑定强于“&”，或 none 其中有）

有人对此有解决方案吗？

编辑：

使运算符绑定正确但不允许链接的部分解决方案： 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

我在 http://lpaste.net/143362 的部分解决方案的一个问题是它无法识别 ~ ! a。

但是，如果将运算符 table 更改为：

table   = [ [ Prefix tilde ]
          , [ Infix amper AssocLeft ]
          , [ Prefix bang ]
          , [ Prefix tilde ]
          ]

它可以正确解析该表达式以及 ! ~a & b、~ ! a & b。代码位于：http://lpaste.net/143370

所以现在将这个想法与您的链接结合起来并尝试：

table   = [ [ Prefix (chained tilde) ]
          , [ Infix amper AssocLeft ]
          , [ Prefix (chained bang) ]
          , [ Prefix (chained tilde) ]
          ]

chained  p = chainl1 p $ return (.)

代码位于：http://lpaste.net/143371

Answer 2

一个新答案...

你有没有想过&运算符的结合性？

这是我想出的另一个想法，假设 & 是右结合的。

收集术语前的前缀运算符序列。
解析术语（ident 或 paren 表达式）
通过从步骤 1 中收集的序列中移出 ~ 个运算符来修正术语。
如果下一个标记是 &，amper 运算符的 LHS 是固定项。其余运算符应用于 amper 表达式。
否则结果只是应用于术语的前缀运算符。

我相信 & 的关联性很重要，例如我们有：

a & ! b & c  -->   a & (! b & c)  --> a & ! (b & c)

或

a & ! b & c  -->   (a & (! b)) & c

另一个需要考虑的案例是 ! a & ! b & c - 您希望如何解析？

一个实现：

 {-# LANGUAGE NoMonomorphismRestriction, FlexibleContexts #-}

 import Text.Parsec
 import Control.Monad
 import Text.ParserCombinators.Parsec hiding (runParser, try)
 import Text.Parsec.Char

 data Sentence = Ident String | Bang Sentence | Tilde Sentence | Amper Sentence Sentence
   deriving (Show)

 lexer p = do x <- p; spaces; return x
 ident = lexer (many1 letter)
 sym ch  = lexer (char ch)

 tilde = sym '~'
 bang  = sym '!'
 amper = sym '&'

 parens p = between (sym '(') (sym ')') p

 term    =  parens expr 
          <|> (fmap Ident ident)
          <?> "simple expression"

 prefixOps = many (try tilde <|> bang)

 expr = do
   ops <- fmap reverse prefixOps
   lhs <- term

   let (ops', lhs') = popTildes ops lhs
       pre = mkPrefixNode ops'

   mrhs <- try (fmap Just (amper >> expr)) <|> (return Nothing)

   case mrhs of
     Nothing  -> return $ pre lhs'
     Just rhs -> return $ pre (Amper lhs' rhs)

 popTildes :: [Char] -> Sentence -> ([Char], Sentence)
 popTildes ('~':rest) s = popTildes rest (Tilde s)
 popTildes ops s        = (ops, s)

 mkPrefixNode :: [Char] -> (Sentence -> Sentence)
 mkPrefixNode [] = id
 mkPrefixNode ('~':rest) = mkPrefixNode rest . Tilde
 mkPrefixNode ('!':rest) = mkPrefixNode rest . Bang 
 mkPrefixNode _          = error "can't happen"

 check :: String -> IO ()
 check input = do
   let padded = input ++ (replicate (15-length input) ' ')
   case parse expr "-" input of
     Left e  -> do putStrLn $ "FAILED: " ++ input
                   putStrLn $ "  " ++ show e
     Right x -> do putStrLn $ "OK: " ++ padded ++ " -> " ++ show x

 inputs = [ "a", "! a", "~ a", "a & b", "! a & b", "~ a & b", "! ~ a & b"
          ,  "~ ! a", "! ~a & b", "~ ! a & b ", "! ~ ! a 2"
          ]

 main = mapM_ check inputs

Answer 3

您想要的解析器的左因子语法是：

sentence : '!' sentence
         | sentence1

sentence1 : sentence2 '&' sentence1
          | sentence2

sentence2 : '~' sentence2
          | term

term : '!' sentence
     | ident

在 EBNF 中可以改写为：

sentence : '!'* sentence1

sentence1 : sentence2 ('&' sentence2)*

sentence2 : '~'* term

term : '!' sentence
     | ident

buildExpressionParser 使用链式前缀运算符生成的解析器几乎可以生成此解析器，只是它不包含术语解析器中的 ! 规则；因此在 ~ 之后遇到 ! 时会出现解析错误。

鉴于以下情况：

{-# LANGUAGE NoMonomorphismRestriction #-}
module Main where

import Control.Monad
import Text.Parsec
import Text.Parsec.Expr
import Text.Parsec.Char
import Control.Applicative ( (<*), (*>), (<*>), (<$), (<$>) )

data Sentence = Tilde Sentence
              | Bang Sentence
              | Amper Sentence Sentence
              | Ident String
  deriving ( Eq, Ord, Show )

bangP  = Bang  <$ lexeme (char '!')
amperP = Amper <$ lexeme (char '&')
tildeP = Tilde <$ lexeme (char '~')
identP = Ident <$> lexeme (many1 alphaNum)

lexeme = (<* spaces)

parser = spaces *> sentence <* eof

main = do
  let inputs = [ "a", "! a", "~ a", "a & b", "! a & b"
               , "~ a & b", "! ~ a & b", "~ ! a & b", "! ~ ! a"
               , "~ a & b", "a & ! b & c & d"
               ]
  forM_ inputs $ \input -> do
    putStr input
    putStr " -> "
    parseTest parser input

我们可以手动定义 sentence 解析器：

sentence = sentence0 where
  sentence0 = chainl bangP (return (.)) id <*> sentence1
  sentence1 = chainl1 sentence2 amperP
  sentence2 = chainl tildeP (return (.)) id <*> term
  term = (bangP <*> sentence0) <|> identP

或者如果我们将 ! 规则添加到 term 解析器中，我们可以使用 buildExpressionParser：

sentence = buildExpressionParser table term where
  table = [ [prefix tildeP]
          , [Infix amperP AssocLeft]
          , [prefix bangP]
          ]
  term = (bangP <*> sentence) <|> identP
  prefix  p = Prefix . chainl1 p $ return (.)

Answer 4

我对我原来的答案不满意，因为它没有解决各种优先级的前缀和后缀运算符的一般情况，它要求程序员必须考虑语法而不是仅仅依赖 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

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

Parsec.Expr repeated Prefix with different priority

haskell

parsec