时间戳

首页 > 解决方案 > 是什么导致我的 OCaml S 表达式解析器失败？

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

问题描述

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

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"; ")"; ")"]

标签： parsingocamllispmls-expression

解决方案

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

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

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

如果您发誓这只是一个个人项目，我愿意编写一个解析器。但是您应该尝试按照上述方式编写一些内容。

请注意，当您看到一个原子时，您并没有看到一对。Pair (Atom xyz, rest)看到原子时返回是不正确的。

更新

使事情在函数设置中工作的方法是让解析函数不仅返回它们看到的构造，而且还返回尚未解析的剩余标记。

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

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 = ()

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

推荐阅读