1

两节课前，我们的教授给我们介绍了一个 Parser 模块。

这是代码：

module Parser (Parser,parser,runParser,satisfy,char,string,many,many1,(+++)) where

import Data.Char
import Control.Monad
import Control.Monad.State

type Parser = StateT String []

runParser :: Parser a -> String -> [(a,String)]
runParser = runStateT

parser :: (String -> [(a,String)]) -> Parser a
parser = StateT

satisfy :: (Char -> Bool) -> Parser Char
satisfy f = parser $ \s -> case s of
    [] -> []
    a:as -> [(a,as) | f a]

char :: Char -> Parser Char
char = satisfy . (==)

alpha,digit :: Parser Char
alpha = satisfy isAlpha
digit = satisfy isDigit

string :: String -> Parser String
string = mapM char

infixr 5 +++
(+++) :: Parser a -> Parser a -> Parser a
(+++) = mplus

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

今天他给我们一个作业，介绍“(+++) 的左偏或短路版本”，称为 (<++)。他的提示是让我们考虑 (+++) 的原始实现。当他第一次向我们介绍 +++ 时，这是他编写的代码，我将其称为原始实现：

infixr 5 +++
(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser $ \s -> runParser p s ++ runParser q s

自从我们被引入解析以来，我一直遇到很多麻烦，所以它继续存在。

我已经尝试/正在考虑两种方法。

1）使用“原始”实现，如 p +++ q = Parser $ \s -> runParser ps ++ runParser qs

2) 使用最终实现，如 (+++) = mplus

以下是我的问题：

1）如果我使用原始实现，模块将无法编译。错误：不在范围内：数据构造函数“解析器”。它使用 (+++) = mplus 编译得很好。使用最终实现避免的原始实现有什么问题？

2）如何检查第一个解析器是否返回任何内容？像 (not (isNothing (Parser $ \s -> runParser ps) 之类的东西在正确的轨道上吗？看起来应该很容易，但我不知道。

3）一旦我弄清楚如何检查第一个 Parser 是否返回任何内容，如果我要将我的代码基于最终实现，它会像这样简单吗？：

-- if p returns something then
p <++ q = mplus (Parser $ \s -> runParser p s) mzero
-- else
(<++) = mplus

最好的，杰夫

PS哦，是的，这段代码到底是做什么的？即使它编译，我也不知道如何测试它以确保它按预期工作。

4

2 回答 2

4

这里发生了很多事情！您正在查看的是一个（非确定性的）“解析器组合库”，您可以在parsec, attoparsec, uu-parsinglib... 中找到其他示例，这在 Haskell 中是一个很常见的想法，但它肯定有点复杂。我将在这里解开核心思想。

要考虑的第一个想法是增量解析“步骤”的概念。这就是上面代码中表示的Parser a内容，您可能会将其视为“运行解析步骤以尝试解析某种类型的内容a”。

“解析步骤”涉及查看某种类型的字符输入流，提取但需要许多字符来表示某种a类型，然后返回未使用的新鲜a字符和剩余字符。在这个级别的描述中，很容易用 Haskell 写出来

String {- input stream -} -> (a {- fresh -}, String {- leftovers -})

这是解析器步骤的基础，值得注意的是，在解析库之外我们称之为State String a.

newtype State s a = State { runState :: s -> (a, s) }

>>> :t runState (undefined :: State String a)
String -> (a, String)

我们也可以尝试以这种分解的格式构建解析器步骤。考虑一个解析器，它消耗单个字符来创建一个Int

parseInt :: String -> (Int, String)
parseInt (x:xs) = case x of
  '0' -> (0, xs)
  '1' -> (1, xs)
  ...
  '9' -> (9, xs)
  _   -> error "What! Failure!"
parseInt []     = error "What! Another failure!"

>>> parseInt "3leftovers"
(3, "leftovers")

马上我们可以看到这个模型太简单了——我们只能通过一直抛出错误到运行时来提供解析器失败。这很危险，表明我们对解析器的建模很差。不过，我们可以非常简单地为其添加失败。

-- String -> Maybe (a, String)

parseInt :: String -> Maybe (Int, String)
parseInt []     = Nothing
parseInt (x:xs) = case x of
  '0' -> Just (0, xs)
  '1' -> Just (1, xs)
  ...
  '9' -> Just (9, xs)
  _   -> Nothing

>>> parseInt "foo"
Nothing

这也是一个非常常见的 Haskell 主题，即使在称为 State Transformer 或StateT. 定义看起来像这样

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

>>> :t runStateT (undefined :: StateT String Maybe a)
String -> Maybe (a, String)

它允许我们将Maybe体现的失败概念与State原始解析器的概念结合起来。事实上，这就是你的教授用他自己的版本所做的，除了他没有使用Maybe他使用的[]

>>> :t runStateT (undefined :: StateT String [] a)
String -> [(a, String)]

它允许失败（作为空列表[]）和多个同时成功。这就是使他的解析器具有不确定性的原因——它在每个解析步骤中收集并处理多个成功。这可能对记忆非常不利，但却是一种谨慎使用的强大技术。

不过，到目前为止，我所写的内容中还缺少其他内容——我们如何将多个解析器组合在一起？parseInt比如跑三遍就相当痛苦

parse3Ints :: String -> Maybe ((Int, Int, Int), String)
parse3Ints input = case parseInt input of
  Nothing -> Nothing
  Just (i1, input') -> case parseInt input' of
    Nothing -> Nothing
    Just (i2, input'') -> case parseInt input'' of
      Nothing -> Nothing
      Just (i3, leftovers) -> Just ((i1, i2, i3), leftovers)

啊。我们能做得更好吗？我们需要以某种方式将失败和input字符串的传递联系在一起。幸运的是，这正是Monads 所做的，我们所看到的所有三种数据类型都Monad具有这些确切的行为

instance Monad m => Monad (StateT s m) where ...
instance Monad [] where ...
instance Monad Maybe where ...

请注意，仅当其参数为时才StateT为 a ---这是因为它允许我们将s 分层，因此它需要调用“内部”以进行自己的排序。MonadmMonadMonad

结果是，通过将这些简单的函数转换为StateT String Maybe aorStateT String [] a我们立即开始使用do-notation 让内置Monad实例处理我们的复杂排序

parse3Ints :: StateT String Maybe (Int, Int, Int)
parse3Ints = do
  i1 <- parseInt
  i2 <- parseInt
  i3 <- parseInt
  return (i1, i2, i3)

-- or even
parse3Ints = liftM3 (,,) parseInt parseInt parseInt

这里的最后一个兴趣点是关于你的教授的问题(+++)。在这里，他使用了mplus来自其类型类的函数，MonadPlus并且StateT是[]实例。我们可以看看那个代码

instance MonadPlus [] where
  mzero = []
  mplus as bs = as ++ bs

instance MonadPlus m => MonadPlus (StateT s m) where
  mzero                         = StateT $ \input -> mzero
  mplus (StateT sa) (StateT sb) = StateT $ \input -> mplus (sa input) (sb input)

所以我们可以看到，这段代码的真正权重在于[]实例，因为StateT实例只是将责任推给了它的内部Monad, m。

在MonadPlus []做什么？它表示使用“或”组合失败的概念。如果[]是列表中的失败，Monad那么mzero是立即失败，并且仅mplus as bs当两者 都是失败时才失败。我们可以写成asbs

mplus mzero a = a
mplus a mzero = a

人们可能会认为这是一种代数定律的定义MonadPlus（尽管这里有一些争议，但这对这里的代码无关紧要）。

那么通过使用mplus实例来组合解析器，是怎么回事呢？简而言之，它允许您将解析器“或”在一起，这样它们只有在所有解析器一起失败时才会失败。

(pa +++ pb +++ pc) is mzero ONLY if pa, pb, AND pc are mzero

这在列表中效果很好，Monad因为它允许我们一起收集多个成功。没有偏见，因为 list monad 尝试了所有不同的解析，它们都只是进入列表而没有任何优先级。

我们可以将其与Maybe Monad固有的偏见进行比较，因为它只能在任何给定时间考虑“最佳”解析成功。也就是说，我们可以看一下MonadPlus实例Maybe

instance MonadPlus Maybe where
  mzero                   = Nothing
  mplus Nothing x         = x
  mplus x Nothing         = x
  mplus (Just a) (Just b) = Just a

在mplus定义的最后一行，我们抛弃了除了“最左边”的成功之外的所有东西。这是左倾的核心。

但正如我很久以前所说的，对我们来说，平等地优先考虑所有解析可能是一件坏事。存储整个潜在解析树并在每个新字符被消耗时随身携带它在内存中可能非常痛苦。

为此，我们可以将偏差保留(+++)为(<++)。这里的想法是我们希望立即返回成功的解析，并且只有在必须时才“向右”传递

StateT sa <++ StateT sb = StateT $ \input -> case sa input of
  []   -> sb input
  els  -> els

这里我们只在解析器没有结果的情况下尝试sb解析器。sa这意味着我们丢弃了许多潜在的“右”解析来加快我们“左”解析的速度。它让我们可以明智地修剪潜在解析树。

于 2013-11-08T22:37:23.950 回答
2
  • 1）正如@andras 指出的那样，更改Parser为parser
  • 2+3) 查看代码+++

p +++ q = parser $ \s -> runParser p s ++ runParser q s

我们可以扩展一下，让事情更清楚

p +++ q = parser $ \s -> resP ++ resQ
  where resP = runParser p s
        resQ = runParser q s

这只需要一个小的改动（in resP +++ resQ）就可以使<++左偏。

于 2013-11-08T22:27:57.557 回答