uu-parsinglib中计划外的贪婪行为

Question

问题

我今天遇到了一个问题，我不知道如何解决它。这对我来说很奇怪，因为我编写的代码应该是正确的(根据我目前的知识)。

所以下面你可以找到一个例子解析器组合器。最重要的是pOperator，它以非常简单的方式(仅为演示目的)构建操作符AST。它使用"x“，并可以使用由空格分隔的多个"x”。

我还得到了pParens组合器，定义如下：

pPacked pParenL (pWSpaces *> pParenR)

因此，它在结束括号之前消耗了空白空间。

样本输入/输出

正确的输入/输出应是：

in: "(x)"
out: Single "x"

in: "(x )"
out: Single "x"

但我得到了：

in: "(x)"
out: Single "x"

in: "(x )" 
out: Multi (Single "x") (Single "x")
--  Correcting steps: 
--    Inserted  'x' at position LineColPos 0 3 3 expecting one of ['\t', ' ', 'x']

但是在第二个例子中，我得到了错误--解析器的行为就像它贪婪地吃了一些令牌(并且没有贪婪的操作)。

我很感谢你在这方面的帮助。

示例代码

import Prelude hiding(lex)
import Data.Char hiding (Space)
import qualified Text.ParserCombinators.UU as UU
import           Text.ParserCombinators.UU hiding(parse)
import qualified Text.ParserCombinators.UU.Utils as Utils
import           Text.ParserCombinators.UU.BasicInstances hiding (Parser)


data El = Multi El El
        | Single String
        deriving (Show)


---------- Example core grammar ----------

pElement     = Single <$> pSyms "x"
pOperator    = applyAll <$> pElement <*> pMany (flip <$> (Multi <$ pWSpaces1) <*> pElement)

---------- Basic combinators ----------

applyAll x (f:fs) = applyAll (f x) fs
applyAll x []     = x

pSpace    = pSym ' '
pTab      = pSym '\t'
pWSpace   = pSpace <|> pTab
pWSpaces  = pMany pWSpace
pWSpaces1 = pMany1 pWSpace
pMany1 p  = (:) <$> p <*> pMany p

pSyms []       = pReturn []
pSyms (x : xs) = (:) <$> pSym x <*> pSyms xs

pParenL     = Utils.lexeme $ pSym '('
pParenR     = Utils.lexeme $ pSym ')'
pParens     = pPacked pParenL (pWSpaces *> pParenR)

---------- Program ----------

pProgram = pParens pOperator
-- if you replace it with following line, it works:
--  pProgram = pParens pElement
-- so it seems like something in pOperator is greedy

tests = [ ("test", "(x)")
        , ("test", "(x )")
        ]

---------- Helpers ----------

type Parser a = P (Str Char String LineColPos) a

parse p s = UU.parse ( (,) <$> p <*> pEnd) (createStr (LineColPos 0 0 0) s)

main :: IO ()
main = do 
    mapM_ (\(desc, p) -> putStrLn ("\n=== " ++ desc ++ " ===") >> run pProgram p) tests
    return ()

run :: Show t =>  Parser t -> String -> IO ()
run p inp = do  let (a, errors) =  parse p inp
                putStrLn ("--  Result: \n" ++ show a)
                if null errors then  return ()
                               else  do putStr ("--  Correcting steps: \n")
                                        show_errors errors
                putStrLn "-- "
             where show_errors :: (Show a) => [a] -> IO ()
                   show_errors = sequence_ . (map (putStrLn . show))

重要

pOperator    = applyAll <$> pElement <*> pMany (flip <$> (Multi <$ pWSpaces1) <*> pElement)

相当于：

foldr pChainl pElement (Multi <$ pWSpaces1)

根据：Combinator解析:一个简短的教程

它被用来定义运算符先例。

Answer 1

pMany的定义如下：

pMany :: IsParser p => p a -> p [a]
pMany p = pList p

这说明了解决办法。当看到空间时，我们不应该立即承诺选择继续使用更多的x-es，因此我们定义：

pMany :: IsParser p => p a -> p [a]
pMany_ng p = pList_ng p

当然，您也可以立即调用pList_ng。更好的办法是写：

pParens (pChainr_ng (pMulti <$ pWSpaces1) px) -- 

我没有测试它，因为我不确定在x-es之间是否应该至少有一个空格等等。

杜伊特