是我的解析器懶？

我正在玩Hutton和Meijer的功能性珍珠（https://www.cs.nott.ac.uk/~gmh/pearl.pdf）。隨着它定義的基本功能，我做了一個非常基本的CSV解析器：是我的解析器懶？

csvFile :: Parser [[String]] 
csvFile = record `sepBy` char '\n' 

record :: Parser [String] 
record = (quotedField +++ unquotedField) `sepBy` char ';' 

unquotedField :: Parser String 
unquotedField = many (sat (not . (`elem` ";\n"))) 

quotedField :: Parser String 
quotedField = do 
    char '"' 
    xs <- many (sat (not . (== '"'))) 
    char '"' 
    ys <- do { zs <- quotedField; return ('"':zs) } +++ return [] 
    return (xs++ys)

我一直想把你當我把這個解析器什麼真正評估感。所以在GHCI：

*Main> let tst = "123;123;123\n123;\"123;123\";124\n124;122;125" 
*Main> let psd = parse csvFile tst 
*Main> let x = head . fst . head $ psd 
*Main> x 
["123","123","123"] 
*Main> :p psd 
psd = [(["123","123","123"] : (_t5::[[String]]),[])]

所以我看到下一個解析步驟仍然是一個thunk（_t5）。然而，輸入流現在是：[] - 所以它似乎已被完全消耗。

它去了哪裏？我應該從中推斷出什麼？我想知道如果我的解析器是懶在所有...

編輯：自包含代碼的要求：

import Control.Monad 
import Data.Char 

newtype Parser a = Parser (String -> [(a, String)]) 

parse :: (Parser a) -> (String -> [(a, String)]) 
parse (Parser p) = p 

instance Monad Parser where 
    return a = Parser (\cs -> [(a, cs)]) 
    p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a, cs') <- parse p cs]) 

instance MonadPlus Parser where 
    mzero = Parser(\cs -> []) 
    mplus p q = Parser (\cs -> (parse p cs) ++ (parse q cs)) 

(+++) :: Parser a -> Parser a -> Parser a 
p +++ q = Parser (\cs -> case (parse (p `mplus` q) cs) of 
           [] -> [] 
           (x:xs) -> [x]) 

item :: Parser Char 
item = Parser (\cs -> case cs of 
         (c:nc) -> [(c, nc)] 
         _ -> []) 

sat :: (Char -> Bool) -> Parser Char 
sat f = do { c <- item ; if f c then return c else mzero } 

char :: Char -> Parser Char 
char c = sat (c ==) 

many :: Parser a -> Parser [a] 
many p = many1 p +++ (return []) 

many1 :: Parser a -> Parser [a] 
many1 p = do {t <- p; ts <- many p; return (t:ts) } 

sepBy :: Parser a -> Parser b -> Parser [a] 
p `sepBy` sep = sepBy1 p sep +++ do {x <- p; return [x]} 

sepBy1 :: Parser a -> Parser b -> Parser [a] 
p `sepBy1` sep = do { x <- p; sep; xs <- p `sepBy` sep; return (x:xs)} 

csvFile :: Parser [[String]] 
csvFile = record `sepBy` char '\n' 

record :: Parser [String] 
record = (quotedField +++ unquotedField) `sepBy` char ';' 

unquotedField :: Parser String 
unquotedField = many (sat (not . (`elem` ";\n"))) 

quotedField :: Parser String 
quotedField = do 
    char '"' 
    xs <- many (sat (not . (== '"'))) 
    char '"' 
    ys <- do { zs <- quotedField; return ('"':zs) } +++ return [] 
    return (xs++ys)

來源

2015-05-16 papagaga

如果你可以鏈接到一個自包含的，可運行的代碼版本，那將是很好的。 –

我懷疑這個問題可能存在於你的「+++」的定義中，它會拋棄除第一個解析之外的所有東西。「案件」陳述嚴格;它會強制解析找到p +++ q的第一個完整解析，如果你做了更多的跟蹤，你可能會發現它必須掃描到文本的末尾才能確定有效的解析是什麼。「sepBy」和「many」可能會遇到這個問題，因爲它們使用「+++」來允許空分析。你爲什麼不說「（+++）= mplus」？ –

@PaulJohnson：（+++）是mplus的確定性版本。但你說得對，我知道：*主要>：psd psd =（[「123」; 1456「，」123「，」122「]：（_t1 :: [[String]]），[]）：（_t2 :: [（[[String]]，String）]）。但它不能解釋爲什麼ghci顯示一個thunk和一個被消耗的流，或者它是否？ – papagaga

問題可能出在你的「+++」的定義，這將引發除了第一個解析之外，所有的東西都移除「案件」陳述嚴格;它會強制解析找到p +++ q的第一個完整解析，如果你做了更多的跟蹤，你可能會發現它必須掃描到文本的末尾才能確定有效的解析是什麼。「sepBy」和「many」可能會遇到這個問題，因爲它們使用「+++」來允許空分析。

你爲什麼不說「（+++）= mplus」？

來源

2016-03-20 17:52:48

是我的解析器懶？

回答

相關問題