OCaml S-expressionパーサーが失敗する原因は何ですか？
私はOCamlでLispインタプリタを作ることに取り組んでいます。私は当然フロントエンドから始めました。これまでのところ、ほとんどの場合に機能するS式解析アルゴリズムがあります。のような単純なS式(a b)と((a b) (c d))私の関数の両方について、、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式には、括弧で囲まれたリストという1つの構成があります。パーサーは、構成の終わりの認識を行っていません。
パーサーが正しく機能すると想定している場合、正しい括弧に遭遇)すると構文エラーになります。一致しない右括弧があってはなりません。一致する右括弧は、括弧で囲まれたリスト構造の一部として解析されます（前述のとおり）。
これが単なる個人的なプロジェクトであると誓うなら、私はパーサーを作成したいと思います。しかし、あなたは上記のように何かを書いてみるべきです。
原子が表示されている場合、ペアは表示されていないことに注意してください。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)
これがあなたの2つのテストケースについて私が見るものです：
# check_output ["("; "a"; "b"; ")"];;
(a (b nil))
- : unit = ()
# check_output ["("; "("; "w"; "x"; ")"; "("; "y"; "z"; ")"; ")"];;
((w (x nil)) ((y (z nil)) nil))
- : unit = ()
これらは正しい結果だと思います。