我正在尝试实现自己的应用解析器,这是我使用的代码:
{-# LANGUAGE ApplicativeDo, LambdaCase #-}
module Parser where
-- Implementation of an Applicative Parser
import Data.Char
import Control.Applicative (some, many, empty, (<*>), (<$>), (<|>), Alternative)
data Parser a = Parser { runParser :: String -> [(a, String)] }
instance Functor Parser where
-- fmap :: (a -> b) -> (Parser a -> Parser b)
fmap f (Parser p) = Parser (\s -> [(f a, s') | (a,s') <- p s])
instance Applicative Parser where
-- pure :: a -> Parser a
-- <*> :: Parser (a -> b) -> Parser a -> Parser b
pure x = Parser $ \s -> [(x, s)]
(Parser pf) <*> (Parser p) = Parser $ \s ->
[(f a, s'') | (f, s') <- pf s, (a, s'') <- p s']
instance Alternative Parser where
-- empty :: Parser a
-- <|> :: Parser a -> Parser a -> Parser a
empty = Parser $ \_s -> []
(Parser p1) <|> (Parser p2) = Parser $ \s ->
case p1 s of [] -> p2 s
xs -> xs
char :: Char -> Parser Char
char c = Parser $ \case (c':cs) | c == c' -> [(c,cs)] ; _ -> []
main = print $ runParser (some $ char 'A') "AAA"
当我运行它时,它会卡住并且永远不会返回。在深入研究问题之后,我指出了根本原因是我对
<|>
方法的实现。如果我使用以下实现,那么一切都会按预期进行:instance Alternative Parser where
empty = Parser $ \_s -> []
p1 <|> p2 = Parser $ \s ->
case runParser p1 s of [] -> runParser p2 s
xs -> xs
以我的理解,这两个实现是相当等效的。我猜想这可能与Haskell的惰性评估方案有关。有人可以解释发生了什么吗?
最佳答案
事实“星”:在您的(<*>)
实现中:
Parser p1 <*> Parser p2 = ...
...我们必须进行足够的计算才能知道这两个参数实际上都是
Parser
构造函数对某些事物的应用,然后才能继续访问等式的右侧。事实“严格”:在此实现中:
Parser p1 <|> Parser p2 = ...
...我们必须进行足够的计算才能知道两个解析器实际上都是
Parser
构造函数对某些事物的应用,然后才能继续进行等号的右侧。事实“懒惰”:在此实现中:
p1 <|> p2 = Parser $ ...
...我们可以继续进行等号的右侧,而无需对
p1
或p2
进行任何计算。这很重要,因为:
some v = some_v where
some_v = pure (:) <*> v <*> (some_v <|> pure [])
让我们以您的第一个实现为例,我们知道它的“管道严格”事实。我们想知道
some_v
是否是Parser
的应用。由于有了事实“星号”,因此我们必须知道pure (:)
,v
和some_v <|> pure []
是否是Parser
对某些事物的应用。要知道最后一个,实际上是“严格”的,我们必须知道some_v
和pure []
是否是Parser
对某些东西的应用。哎呀!我们只是表明要知道some_v
是否是Parser
在某物上的应用,我们需要知道some_v
是否是Parser
在某物上的应用-无限循环!另一方面,在第二种实现中,要检查
some_v
是否是Parser _
,我们仍然必须检查pure (:)
,v
和some_v <|> pure []
,但是由于事实“pipe lazy”,这就是我们需要检查的所有内容–我们可以放心some_v <|> pure []
是Parser _
,无需先递归检查some_v
和pure []
是。(接下来,您将学习
newtype
,并且当从data
更改为newtype
时,再次使它们困惑,这两种实现都起作用!)
关于parsing - 应用解析器陷入无限循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58625324/