是什么导致我的 OCaml S 表达式解析器失败？

Question

我正在用 OCaml 制作 Lisp 解释器。我很自然地从前端开始。到目前为止，我有一个大部分时间都有效的 S 表达式解析算法。对于像 (a b) 和 ((a b) (c d)) 这样的简单 S 表达式，我的函数 ast_as_str 显示输出列表结构不正确。我在下面记录了这一点。在 parse 上尝试了无数变体之后，似乎没有任何效果。是否有人擅长在 OCaml 中编写解析器，对我如何修复我的代码有建议？

type s_expression = Nil | Atom of string | Pair of s_expression * s_expression

let rec parse tokens =
    match tokens with
    | [] -> Nil
    | token :: rest ->
        match token with
            | "(" -> parse rest
            | ")" -> Pair(Nil, parse rest)
            | atom -> Pair(Atom atom, parse rest)

let rec ast_as_str ast =
    match ast with
        | Nil -> "nil"
        | Atom a -> Printf.sprintf "%s" a
        | Pair(a, b) -> Printf.sprintf "(%s %s)" (ast_as_str a) (ast_as_str b);;

let check_output test = print_endline (ast_as_str (parse test));;

(* 
Input:
(a b)
Output:
(a (b (nil nil)))
Almost correct...
*)
check_output ["("; "a"; "b"; ")"];;

(*
Input:
((w x) (y z))
Output:
(w (x (nil (y (z (nil (nil nil)))))))
Incorrect.
*)
check_output ["("; "("; "w"; "x"; ")"; "("; "y"; "z"; ")"; ")"]

Answer 1

我假设这不是家庭作业。如果是，我会将答案更改为一些不太具体的提示。

递归下降解析器的工作原理是识别构造的开始标记，然后解析构造的内容，然后（经常）识别构造的结束标记。 S 表达式只有一种结构，即带括号的列表。您的解析器没有识别构造的结尾。

如果您假设您的解析器工作正常，那么遇到右括号 ) 是一个语法错误。不应该有任何不匹配的右括号，并且匹配的右括号被解析为带括号的列表构造的一部分（如上所述）。

如果你发誓这只是一个个人项目，我愿意编写一个解析器。但是你应该试着写一些如上所述的东西。

请注意，当您看到原子时，您看到的不是原子对。看到原子时 return Pair (Atom xyz, rest) 不正确。

更新

让事情在功能设置中工作的方法是让解析函数 return 不仅是他们看到的构造，还有尚未解析的剩余标记。

以下代码适用于您的示例，可能非常接近正确：

let rec parse tokens =
    match tokens with
    | [] -> failwith "Syntax error: end of input"
    | "(" :: rest ->
        (match parselist rest with
        | (sexpr, ")" :: rest') ->  (sexpr, rest')
        | _ -> failwith "Syntax error: unmatched ("
        )
    | ")" :: _ -> failwith "Syntax error: unmatched )"
    | atom :: rest -> (Atom atom, rest)


and parselist tokens =
    match tokens with
    | [] | ")" :: _ -> (Nil, tokens)
    | _ ->
        let (sexpr1, rest) = parse tokens in
        let (sexpr2, rest') = parselist rest in
        (Pair (sexpr1, sexpr2), rest')

您可以这样定义 check_output：

let check_output test =
    let (sexpr, toks) = parse test in
    if toks <> [] then
        Printf.printf "(extra tokens in input)\n";
    print_endline (ast_as_str sexpr)

这是我看到的两个测试用例：

# check_output ["("; "a"; "b"; ")"];;
(a (b nil))
- : unit = ()
# check_output ["("; "("; "w"; "x"; ")"; "("; "y"; "z"; ")"; ")"];;
((w (x nil)) ((y (z nil)) nil))
- : unit = ()

我认为这些是正确的结果。

是什么导致我的 OCaml S 表达式解析器失败？

What's causing my OCaml S-expression parser to fail?

lisp

parsing

ocaml

ml

s-expression