parsing - 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']

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

我会感谢任何帮助。

示例代码

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 Parsing: A Short Tutorial

它用于定义运算符优先级。

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 之间是否应该至少有一个空格等。

多艾采