parsing - 应用程序解析器陷入无限循环
问题描述
我正在尝试实现自己的 Applicative 解析器,这是我使用的代码:
{-# 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
or进行任何计算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
是 a Parser _
,我们仍然必须检查pure (:)
,v
和some_v <|> pure []
,但是由于事实上“管道懒惰”,这就是我们需要检查的全部- 我们可以确信这some_v <|> pure []
是 aParser _
没有 first递归地检查some_v
和pure []
是。
(接下来,您将了解- 当从 更改为使两个newtype
实现都工作时,您将再次感到困惑!)data
newtype
推荐阅读
- sql - 查看 2 个不同年份之间售出的单位
- c# - 如何将 LINQ IQueryable / Expression 解构为组成部分?
- r - 如何找到第一四分位数、中位数和第二四分位数的索引号?
- java - 如何从 .key 文件加载私钥
- c++ - 规则“@com_google_protobuf//:protobuf”的 C++ 编译失败(退出 1)
- javascript - 获取 UTC 中两个不同日期字符串之间的时差(小时、秒、分钟)
- django - 有没有办法使时区与用户的时区相关
- typescript - 嵌套的 RXJS 可观察对象
- reactjs - React Rest Call Infinite Loop 使用 Hooks
- php - 无法从自定义 Blade 指令中获取变量 - 花括号丢失?