Что вызывает сбой парсера S-выражения OCaml?

Я работаю над созданием интерпретатора Lisp в OCaml. Я, естественно, начал с фронтенда. Пока что у меня есть алгоритм разбора 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"; ")"; ")"]

parsing lisp ocaml ml s-expression
person Caspian Ahlberg    schedule 23.11.2020    source источник
comment
stackoverflow.com/questions/50562146/   -  person coredump    schedule 24.11.2020

Ответы (1)


arrow_upward
2
arrow_downward

Я собираюсь предположить, что это не домашнее задание. Если это так, я изменю ответ на несколько менее конкретных намеков.

Анализатор рекурсивного спуска работает, распознавая начальный токен конструкции, затем анализируя содержимое конструкции, а затем (очень часто) распознавая конечный токен конструкции. 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 = ()

Я думаю, что это правильные результаты.

person Jeffrey Scofield    schedule 23.11.2020