如何在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"]]]]]

在某种程度上,它需要允许"并行"树,而不仅仅是嵌套.任何帮助,将不胜感激.

Answer 1

在Common Lisp中有一个名为的中间函数READ-DELIMITED-LIST,它将多个表单作为列表读取,直到读者到达结束字符.当遇到一个左括号时,阅读器抓取所有形式直到右括号,然后继续从那里解析.区别在于它适用于字符流,而不是令牌,并且流用于副作用.

没有副作用

在纯函数方法中,就像在代码中一样,解析函数需要返回要处理的剩余标记以及返回的AST.这允许您在解析期间消耗尽可能多的令牌,并允许调用者继续从解析器结束的位置进行解析.

换句话说,当您关闭括号时,您必须返回xs到调用上下文.因此,您携带一个累加器对象(状态)以及您的代码.我听说monads可以帮助你使用样板.

以下是Common Lisp中非破坏性概念的证明.

速成班

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

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

• 其余的应该是不言自明的(否则请问).请注意,我使用符号(f x1 .. x2)并(case test . clauses)分别表示开始和结束令牌.

分析器

首先,定义t:

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

上面的递归解析标记并构建一个列表.如果我们的令牌列表otherwise以关闭令牌开头,我们返回空列表以及其余的令牌.

否则,我们解析一个元素并递归<.这在某种程度上变得有点复杂,因为我们必须>在每一步都绑定以处理延续.

(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 '(one token))
=> ONE
   (TOKEN)

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

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

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