ReadP递归解析

Question

在一篇关于"(a*b+c^d)"使用ReadP将字符串解析为树的wikibooks文章中,有以下代码:

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希望它能帮助我理解它,但无济于事).有人可以解释this在do-block中如何评估(因为它看起来像无限递归给我,显然它不是)？

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递归调用自己.