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

问题

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

因此，您可以在下面找到一个示例解析器组合器。最重要的是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

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

最佳答案

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

杜阿塞

关于parsing - uu-parsinglib中的计划外贪婪行为，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18294268/