6

问题

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

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

根据:组合器解析:简短教程

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

4

1 回答 1

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

多艾采

于 2013-08-27T07:54:33.533 回答