我试图通过Haskell编写一个简单的解析器,但陷入了无限循环。代码是:
import Control.Applicative (Alternative, empty, many, (<|>))
data Parser a = Parser {runParser :: String -> [(a, String)]}
instance Functor Parser where
fmap f (Parser p) = Parser $ \s -> [(f x', s') | (x', s') <- p s]
instance Applicative Parser where
pure x = Parser $ \s -> [(x, s)]
(Parser pf) <*> (Parser p) = Parser $ \s -> [(f' x, ss') | (f', ss) <- pf s, (x, ss') <- p ss]
instance Alternative Parser where
empty = Parser $ \s -> []
(Parser p1) <|> (Parser p2) = Parser $ \s ->
case p1 s of
[] -> p2 s
xs -> xs
singleSpaceParser :: Parser Char
singleSpaceParser = Parser $ \s ->
( case s of
x : xs -> if x == ' ' then [(' ', xs)] else []
[] -> []
)
multiSpaceParser :: Parser [Char]
multiSpaceParser = many singleSpaceParser
我只是在ghci中加载此文件,然后运行:
runParser multiSpaceParser " 123"
我希望它得到[(" ", "123")]
,但实际上它得到了一个无限循环
我用trace调试了一下,好像many
是错的
如何修复此错误?
1条答案
按热度按时间67up9zun1#
我们假设
并考虑呼叫
(The字符串在这里实际上并不重要,
many singleSpaceParser
调用将始终循环。)一个还原步骤产生
现在注意到,为了减少对
(<|>)
的调用,我们必须将(<|>)
的两个参数都计算为Parser ...
的形式。让我们考虑一下
(:) <$> singleSpaceParser <*> many singleSpaceParser
的情况,因为(<$>)
和(<*>)
都是infixl 4
,所以这是<*>
在最外层的应用。但是现在观察到,为了约简
(<*>)
,我们必须再次计算(<*>)
的两个参数,使其具有Parser ...
的形状,因此特别是递归调用many singleSpaceParser
。这就是我们得到无限循环的地方。
通过将
data
切换到newtype
(或者,至少避免在所有第二个参数中对Parser
构造函数进行积极的模式匹配),可以避免这些问题。