秒差距.exp不同优先级的重复前缀

Parsec.Expr.buildExpressionParser的文档说:

具有相同优先级的前缀和后缀操作符只能出现一次(即，如果-是前缀否定，则不允许-2)。

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

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

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

运算符优先级为:"~"结合强于"&"结合强于"!"

例如，我想要这个句子

! ~a & b

解析为

! ( (~a) & b )

和句子

~ ! a & b

~( ! ( a & b) )

Parsec允许我这样做(并指定操作符优先级)，但是，我希望能够链接前缀，例如~ ~ ! ~ a。秒差距不允许这样做。我已经找到了链接前缀的解决方案，但是这个解决方案不允许我为不同的前缀操作符指定不同的操作符优先级("~"one_answers"!"的绑定比"&"强，或者它们都不强)

有人有解决这个问题的办法吗?

编辑:

部分解决方案，使操作符绑定正确，但不允许链接: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)))

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

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

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

但是，如果将操作符表更改为:

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

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

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 (.)

新的答案…

您考虑过&操作符的结合性吗?

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

收集某项前的前缀操作符序列。
解析术语(标识符或父表达式)
通过从步骤1中收集的序列中移动~操作符来修复项。
如果下一个令牌是&，则安培算子的LHS为固定项。其余操作符应用于每个表达式。

我相信&的结合性很重要，例如:

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

相关内容

最新更新

热门标签：