如何在Haskell中编写一个Lisp解析器？

Question

我正在尝试使用Haskell编写Lisp解释器，灵感来自Norvig在Python中的实现（http://norvig.com/lispy.html）。如果需要，我可以提供一个成功的标记生成器。它可以正确地输出代码，就像Norvig的Python标记生成器一样。

program = "(begin (define r 10) (* pi (* r r)))"
astTokenized = tokenize program
astTokenized == ["(","begin","(","define","r","10",")","(","*","pi","(","*","r","r",")",")",")"]

在这里，我定义了我的抽象语法树数据类型，尽管我知道它已经存在一些隐含的错误，因为它没有被包装在列表中。

data Ast x = Val x | Node [Ast x] deriving (Show)

这是我的第一次尝试：

parse :: [[Char]] -> [Ast [Char]]
parse (x:xs)
  | x == "(" = [Node (parse xs)]
  | x == ")" = []
  | otherwise = (Val x) : parse xs

希望，除了它在第一个 ')' 后就终止。

Prelude> parse astTokenized
[Node [Val "begin",Node [Val "define",Val "r",Val "10"]]]

我修改了[]的基本情况，并调整了')'的条件，以便它解析整个输入终止，但现在只是创建了更深层的树，因此无法正确分支。

parse [] = []
parse (x:xs)
  | x == "(" = [Node (parse xs)]
  | x == ")" = parse xs
  | otherwise = (Val x) : parse xs

Prelude> parse astTokenized
[Node [Val "begin",Node [Val "define",Val "r",Val "10",Node [Val "*",Val "pi",Node [Val "*",Val "r",Val "r"]]]]]

在某种程度上，它需要允许“并行”树，而不仅仅是嵌套的。任何帮助将不胜感激。

- user5775230

---

你可能会对https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours感兴趣，其中有一章关于解析的内容。 - Jean-Baptiste Potonnier

Answer 1

这道题是一道作业/练习题，下面的解释试图避免直接给出答案；它使用了Common Lisp编写（因为我不知道Haskell）。

在Common Lisp中，有一个名为READ-DELIMITED-LIST的中间函数，它会读取多个表单作为列表，直到读者达到结束字符为止。当遇到左括号时，读者会获取所有表单，直到右括号，然后继续从那里解析。不同之处在于它适用于字符流，而不是标记，并且该流用于副作用。

无副作用

在纯函数式方法中，就像你的代码一样，解析函数需要返回要处理的剩余标记以及返回的AST。 这允许您在解析过程中消耗尽可能多的标记，并允许调用者从解析器结束的地方继续解析。

换句话说，当您关闭一个括号时，必须将xs返回给调用上下文。因此，您需要随着代码进行携带一个累加器对象（状态）。我听说单子可以帮助您减少样板代码。

速成课程

• MULTIPLE-VALUE-BIND和VALUES一起工作： (values x y) 返回多个值，multiple-value-bind从表达式中捕获多个值，并将每个值绑定到变量上。

• DESTRUCTURING-BIND是模式匹配的祖先，简单地将列表解构为组件。

• 非特殊形式(f x1 .. x2)是函数应用

• (case test . clauses)是一个开关，其中每个子句都是以文字值（或该类值的列表）开头，后跟表达式。 t和otherwise是始终匹配的特殊关键字（默认情况）。

• 其余内容应该很容易理解（否则请询问）。

请注意，我使用符号<和>分别表示开放和关闭标记，以避免与Lisp的括号混淆。例如，列表(< a b c < d > >)包含8个标记，并且可以是"(a b c (d))"的内部表示。我本可以使用left-paren和right-paren，甚至复杂的数据结构，但这只是一种内部表示。此处未详细介绍词法分析器。

解析器

入口点parse函数接受标记列表并返回解析后的值和剩余的标记作为第二个值；它依赖于下面定义的parse-until-close函数：

(defun parse (tokens)
  (when tokens
    (destructuring-bind (head . tail) tokens
      (case head
        (> (error "unmatched closing parenthesis"))
        (< (parse-until-close tail))
        (otherwise (values head tail))))))

接下来是 parse-until-close 函数，它会递归解析标记，直到找到闭合标记；请注意，在不同的点上，tokens 会被重新绑定：

(defun parse-until-close (tokens)
  (when tokens
    (case (first tokens)
      (> (values nil (rest tokens)))
      (otherwise
       ;; first read the element in head of tokens
       (multiple-value-bind (head tokens) (parse tokens)
         ;; then recurse to read the remaining items in list
         (multiple-value-bind (tail tokens) (parse-until-close tokens)
           (values (cons head tail) tokens)))))))

上面的代码递归解析标记并构建列表。如果标记列表以>（闭合标记）开头，则返回空列表以及其余的标记。

否则，我们解析一个元素并使用parse-until-close进行递归。

测试

每次调用都返回两个值：解析的标记和剩余的标记。

(parse '(one token))
=> ONE
   (TOKEN)

(parse '(< abc < x > y >))
=> (ABC (X) Y)
   NIL

(parse '(< abc def >))
=> (ABC DEF)
   NIL

;; incomplete input
(parse '(< < < abc))
=> (((ABC)))
   NIL

- coredump

Answer 2

您是否希望得到这样的结果？

[Node [Val "begin",Node [Val "define",Val "r",Val "10"],Node [Val "*",Val "pi",Node [Val "*",Val "r",Val "r"]]]]

以下是一种方法：

data Ast x = Val x | Node [Ast x] deriving (Show)

parseh :: [[Char]] -> [Ast [Char]] -> (Ast [Char], [String])
parseh [] as = (Node as, [])
parseh (x : xs) as
  | x == "(" = (let (a, xs') = (parseh xs []) in (parseh xs' (as ++ [a])))
  | x == ")" = (Node as, xs) 
  | otherwise = parseh xs (as ++ [Val x])

parse :: [[Char]] -> [Ast [Char]]
parse xs = let (Node as, _) = parseh xs [] in as

- fal

---

这将解析单个s表达式。如何处理Common Lisp源代码，即s表达式列表？ - Alexandre Rademaker