在 Haskell 中理解这个实现的递归下降解析器

Question

我有一个赋值问题，我必须在预定义的 AST 上解析标记化前缀计算器符号。我们得到了一个非常完整的解析算法（我们不得不添加一些东西）。

我提交的算法和AST如下：

data Ast = Tall Int | Sum Ast Ast | Mult Ast Ast | Min Ast | Var String  deriving (Eq, Show)

parseExpr :: [String] -> (Ast, [String])
parseExpr [] = error "Empty!"
parseExpr ("+":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Sum e1 e2, r2)
parseExpr ("*":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Mult e1 e2, r2)
parseExpr ("-":rs) = let (e1, r1) = parseExpr rs in (Min e1, r1)
parseExpr (x:rs)
        | all isDigit x = (Tall (read x), rs)
        | all isAlpha x = (Var x, rs)
        | otherwise = error ("Syntax errors "++x)

input/output的例子：

parseExpr ["+","4","*","8","-","5"] =
 (Sum (Tall 4) (Mult (Tall 8) (Min (Tall 5))),[])

我在继续作业时需要的是元组的第一部分。这是正确的，任务已提交，并且对于任务而言一切都很好。

话虽如此，递归函数里到底是怎么回事我也不知道。尤其是这三行：

parseExpr ("+":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Sum e1 e2, r2)
parseExpr ("*":rs) = let (e1, r1) = parseExpr rs ;(e2, r2) = parseExpr r1 in (Mult e1 e2, r2)
parseExpr ("-":rs) = let (e1, r1) = parseExpr rs in (Min e1, r1)

当然，我得到了 ("+":rs) 符号。我难以理解的是"let (e1, r1) = ....."等

在最后的守卫中，我没有看到任何递归调用。然而，递归发生了，对吧？这是如何工作的？

Answer 1

让我们以更传统的方式写出其中一个定义：

parseExpr ("+":rs) = let (e1, r1) = parseExpr rs -- recursive call #1
                         (e2, r2) = parseExpr r1 -- recursive call #2
                     in (Sum e1 e2, r2)

给定一个以 "+" 开头的列表，我们首先递归地解析 "+" 之后的标记；结果表达式被赋予名称 e1，未使用的 rs 后缀被赋予名称 r1。我们通过解析 r1 来重复这个过程，得到一个表达式 e2 和一个剩余的输入 r2。这样，我们可以使用两个子表达式 e1 和 e2 构造 Sum 值，并传回 r2 供我们的调用方解析。

使用你的例子，

-- Step 1
parseExpr ["+","4","*","8","-","5"] 
  = let (e1, r1) = parseExpr ["4","*","8","-","5"]
        (e2, r2) = parseExpr r1
    in (Sum e1 e2, r2)

在我们可以做更多之前，我们必须评估第一个递归调用

-- Step 2
parseExpr ["4","*","8","-","5"] = (Tall 4, ["*","8","-","5"])

现在我们可以将该结果插入步骤 1

-- Step 3
parseExpr ["+","4","*","8","-","5"] 
  = let (e1, r1) = (Tall 4, ["*","8","-","5"])
        (e2, r2) = parseExpr r1
    in (Sum e1 e2, r2)

-- Step 4
parseExpr ["+","4","*","8","-","5"] 
  = let (e2, r2) = parseExpr ["*","8","-","5"]
    in (Sum (Tall 4) e2, r2)

等等...

在 Haskell 中理解这个实现的递归下降解析器

Understanding this implemented recursive-descent parser in Haskell

parsing

haskell

abstract-syntax-tree

recursive-descent