Co powoduje awarię parsera wyrażeń S OCaml?

Nov 24 2020

Pracuję nad stworzeniem interpretera Lispa w OCaml. Naturalnie zacząłem od front-endu. Jak dotąd mam algorytm analizy wyrażenia S, który działa przez większość czasu. W przypadku prostych wyrażeń S, takich jak (a b)i ((a b) (c d))moja funkcja ast_as_str, pokazuje, że struktura listy wyników jest niepoprawna. Udokumentowałem to poniżej. Po wypróbowaniu niezliczonych odmian parsenic nie wydaje się działać. Czy ktoś biegły w pisaniu parserów w OCaml ma sugestie, jak mogę naprawić mój kod?

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

Odpowiedzi

2 JeffreyScofield Nov 24 2020 at 02:40

Zakładam, że to nie jest praca domowa. Jeśli tak, zmienię odpowiedź na kilka mniej szczegółowych wskazówek.

Parser zstępowania rekurencyjnego działa poprzez rozpoznawanie początkowego tokenu konstrukcji, następnie analizowanie zawartości konstrukcji, a następnie (bardzo często) rozpoznawanie końcowego tokenu konstrukcji. Wyrażenia S mają tylko jedną konstrukcję, listę w nawiasach. Twój parser nie rozpoznaje końca konstrukcji.

Jeśli założysz, że twój parser działa poprawnie, to napotkanie właściwego nawiasu )jest błędem składniowym. Nie powinno być żadnych niedopasowanych prawych nawiasów, a pasujące prawe nawiasy są analizowane jako część konstrukcji listy w nawiasach (jak opisałem powyżej).

Jeśli przysięgniesz, że to tylko osobisty projekt, chętnie napiszę parser. Ale powinieneś spróbować napisać coś, jak opisano powyżej.

Zauważ, że kiedy widzisz atom, nie widzisz pary. Nie jest dobrze wracać, Pair (Atom xyz, rest)gdy widzisz atom.

Aktualizacja

Sposobem na to, aby rzeczy działały w ustawieniu funkcjonalnym, jest zwrócenie przez funkcje analizujące nie tylko konstrukcji, którą widziały, ale także pozostałych tokenów, które nie zostały jeszcze przeanalizowane.

Poniższy kod działa w przypadku Twoich przykładów i prawdopodobnie jest bardzo bliski poprawności:

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')

Możesz zdefiniować check_output w ten sposób:

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)

Oto, co widzę dla twoich dwóch przypadków testowych:

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

Myślę, że to są właściwe wyniki.