Как я могу сделать неконтекстный парсер в ocaml, используя чисто функциональное программирование? - PullRequest
Новая
       12

Как я могу сделать неконтекстный парсер в ocaml, используя чисто функциональное программирование?

1 голос
/ 09 апреля 2019

Я пытаюсь создать неконтекстный парсер с использованием чисто функционального программирования в OCaml. Функция возьмет список строк и вернет true, если она соответствует формату (a ^ xb ^ yc ^ zd ^ k), что означает, что список должен содержать любое число (больше 0) из "a", "b" , "c" и "d".

Мне было рекомендовано попытаться создать набор взаимно рекурсивных функций, но я изо всех сил пытался найти способ сделать это успешно.

Вот несколько примеров входов и выходов функции: 

# string(["a";"b";"c";"d"]);;
- : bool = true

# string(["a";"a";"b";"c";"c";"c";"d"]);;
- : bool = true

# string(["a";"c";"d";"d"]);;
- : bool = false

Любая помощь будет принята с благодарностью!

1 Ответ

2 голосов
/ 09 апреля 2019

Ключом к созданию чего-то чисто функционального является то, что все состояния должны быть переданы как параметры функции и возвращаемые значения. В вашем случае состояние является входным потоком; то есть список, который еще не был проанализирован.

Один из способов сделать это состоит в том, чтобы каждая функция синтаксического анализа возвращала логическое значение, указывающее, увидела ли она то, что ожидалось, а также возвращала непарсированный остаток списка.

Это означает, что вы будете использовать функции разбора такого типа: 

aplus : string list -> bool * string list
bplus : string list -> bool * string list

Если вы просто ищете a, а затем b, вы можете написать его следующим образом: 

let parse strings =
    let (good, rest) = aplus strings in
    if not good then false
    else let (good, rest) = bplus rest in
    good && rest = []

Это довольно громоздкий код. Это может быть аккуратнее, если у вас есть функция, которая работает как «&&», за исключением того, что она передает непарсированный список следующей функции. Такие вещи часто возникают, когда вы начинаете писать чисто функциональный код.

Было бы много других способов структурировать синтаксический анализ, некоторые, вероятно, намного лучше, чем описанные выше. Но ключ (IMHO) в том, что ваши функции синтаксического анализа должны возвращать остаток входного потока, а также указание успеха / неудачи.

(Обратите внимание, что здесь пока нет рекурсии, но это произойдет, когда вы напишите отдельные функции синтаксического анализа.)

...