내 OCaml S-expression 파서가 실패하는 원인은 무엇입니까?

Question

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

Answer 1

나는 이것이 숙제가 아니라고 가정 할 것이다. 그렇다면 덜 구체적인 힌트로 답변을 변경하겠습니다.

재귀 하강 파서는 구성의 시작 토큰을 인식 한 다음 구성의 내용을 구문 분석 한 다음 (매우 자주) 구성의 종료 토큰을 인식하는 방식으로 작동합니다. 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 = ()

나는 이것이 올바른 결과라고 생각합니다.