是什么导致我的 OCaml S 表达式解析器失败?
What's causing my OCaml S-expression parser to fail?
我正在用 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"; ")"; ")"]
我假设这不是家庭作业。如果是,我会将答案更改为一些不太具体的提示。
递归下降解析器的工作原理是识别构造的开始标记,然后解析构造的内容,然后(经常)识别构造的结束标记。 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 制作 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"; ")"; ")"]
我假设这不是家庭作业。如果是,我会将答案更改为一些不太具体的提示。
递归下降解析器的工作原理是识别构造的开始标记,然后解析构造的内容,然后(经常)识别构造的结束标记。 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 = ()
我认为这些是正确的结果。