parsing - ReadP递归解析

Question

在wikibooks article中关于使用 ReadP 将 "(a*b+c^d)" 之类的字符串解析为树，有如下一段代码:

import Text.ParserCombinators.ReadP

brackets p = do char '('
                r <- p
                char ')'
                return r

data Operator = Add | Mul | Exp deriving Show
operators = [(Add,'+'),(Mul,'*'),(Exp,'^')]

data Tree = Branch Operator Tree Tree | Leaf String deriving Show

leaf = do s <- many1 (choice (map char ['a'..'z']))
          return (Leaf s)

tree = foldr (\(op,name) p ->
               let this = p +++ (p +++ brackets tree
                        >>= (\a -> char name
                        >>= (\_ -> this
                        >>= (\b -> return (Branch op a b)))))
                in this)
             (leaf +++ brackets tree)
             operators

我无法得到的是 this 的递归在这里工作的方式(我已经取消了 do 希望它能帮助我理解它，但无济于事)。有人可以解释一下 do block 中的 this 是如何被求值的吗(因为它对我来说看起来像是无限递归，但显然不是)？

Answer 1

让我们看看 this 的定义(我发现使用 do 符号更容易):

let this = p +++ do a <- p +++ brackets tree
                    char name
                    b <- this
                    return (Branch op a b)
 in this

所以在这里，唯一出现 this在右侧，位于 +++ 的第二个参数内操作，即:

do a <- p +++ brackets tree
   char name
   b <- this
   return (Branch op a b)

如您所见，在此表达式中，this出现在一些其他操作之后，即 a <- p +++ brackets tree和char name 。这意味着这些其他操作将在 this 之前先尝试。 。如果其中一项失败，则不会尝试后续操作。例如，如果 a <- p +++ brackets tree成功，但输入流不包含等于 name 引用的值的字符, char name将会失败并且 b <- this根本不会尝试线路。所以这意味着 this 没有必要将无条件递归地调用自身。