parsing - Haskell:Graham Hutton Book Parsing(第 8 章): `parse (f v) out` 做什么，它是如何做的？

Question

我的问题是关于 Graham Hutton 的书 Programming in Haskell 1st Ed .

在第 8.4 节中创建了一个解析器，我假设任何回答的人都有这本书或者可以在上面的链接中看到幻灯片 8 的链接。

称为item 的基本解析器描述为:

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

item :: Parser Char

item = \inp -> case inp of
        [] -> []
        (x:xs) -> [(x,xs)]

与do一起使用定义另一个解析器p(do解析器)

p :: Parser (Char, Char)

p = do x <- item
       item
       y <- item
       return (x,y)

相关的bind定义是:

(>>=) :: Parser a -> (a -> Parser b) -> Parser b

p >>= f = \inp -> case parse p inp of
                       [] -> []
                       [(v,out)] -> parse (f v) out

return 定义为:

return  :: a -> Parser a

return v = \inp -> [(v,inp)]

解析定义为:

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

parse p inp = p inp

程序(do 解析器)获取一个字符串并选择第 1 个和第 3 个字符，并在元组中返回它们，字符串的其余部分在列表中，例如，"abcdef " 生成 [('a','c'), "def"]。

我想知道 (f v) 输出在 [(v,out)] -> 解析 (f v) out返回一个解析器，然后应用于 out。

• f 在 do 解析器中是 item 和 item 取一个字符 ' c' 返回 [('c',[])]?

• 它如何成为一个解析器，它如何将 out 作为参数？

也许我只是不明白(f v) 的作用。

• 此外，当再次调用 item 时，do 解析器如何每次“删除”返回值以对输入字符串的其余部分进行操作？

• 通过 do 解析器工作的对象是什么，它在每一步如何改变，通过什么方式改变？

Answer 1

f v产生 Parser b因为f是 a -> Parser b 类型的函数和 v是 a 类型的值.那么你调用parse有了这个Parser b和字符串 out作为论据。

F in the 'do' parser is item

不，不是。让我们考虑一下解析器的简化(尽管现在有些无意义)版本:

p = do x <- item
       return x

这将脱糖:

p = item >>= \x -> return x

所以>>= 的右操作数，即 f , 是 \x -> return x ，而不是 item .

Also how does the 'do' parser 'drop' the returned values each time to operate on the rest of the input string when item is called again? What is the object that works its way through the 'do' parser and how is it altered and each step and by what means is it altered?

当您应用解析器时，它会返回一个包含解析值的元组和一个表示输入其余部分的字符串。如果你看item例如，元组的第二个元素将是 xs这是输入字符串的尾部(即包含输入字符串除第一个字符之外的所有字符的字符串)。元组的第二部分将作为新输入提供给后续解析器(根据 [(v,out)] -> parse (f v) out )，这样每个后续解析器都会将前一个解析器生成的字符串作为其输出元组的第二部分作为输入(这将是 its 输入的后缀)。

---

回应您的评论:

When you write "p = item >>= \x -> return x", is that the equivalent of just the first line "p = do x <- item"?

不，它相当于整个 do -block(即 do {x <- item; return x} )。你不能翻译 do - 像这样逐行阻止。 do { x <- foo; rest }相当于 foo >>= \x -> do {rest} ，因此您将始终拥有 do 的其余部分-block 作为 >>= 的右操作数的一部分.

but not how that reduces to simply making 'out' available as the input for the next line. What is parse doing if the next line of the 'do' parser is a the item parser?

让我们来看一个调用 item 的示例。两次(这就像您的 p ，但没有中间项)。在下面我将使用 ===表示 === 上方和下方的表达式是等价的。

do x <- item
   y <- item
   return (x, y)
=== -- Desugaring do
item >>= \x -> item >>= \y -> return (x, y)
=== -- Inserting the definition of >>= for outer >>=
\inp -> case parse item inp of
             [] -> []
             [(v,out)] -> parse (item >>= \y -> return (v, y)) out

现在让我们将其应用于输入“ab”:

case parse item "ab" of
     [] -> []
     [(v,out)] -> parse (item >>= \y -> return (v, y)) out
=== Insert defintiion of `parse`
case item "ab" of
     [] -> []
     [(v,out)] -> parse (item >>= \y -> return (v, y)) out
=== Insert definition of item
case ('a', "b") of
     [] -> []
     [(v,out)] -> parse (item >>= \y -> return (v, y)) out
===
parse (item >>= \y -> return ('a', y)) out

现在我们可以展开第二个 >>=同样的，我们打了拳头，最终得到('a', 'b') .