Как я могу сделать неконтекстный синтаксический анализатор в ocaml, используя чисто функциональное программирование?
Я пытаюсь создать неконтекстный синтаксический анализатор, используя чисто функциональное программирование в OCaml. Функция возьмет список строк и вернет true, если он соответствует формату (a^xb^yc^zd^k), что означает, что список должен содержать любое число (больше 0) "a", "b" , «в» и «г».
Мне было рекомендовано попытаться создать набор взаимно рекурсивных функций, но я изо всех сил пытался найти способ сделать это успешно.
Вот несколько примеров входных и выходных данных функции:
# string(["a";"b";"c";"d"]);;
- : bool = true
# string(["a";"a";"b";"c";"c";"c";"d"]);;
- : bool = true
# string(["a";"c";"d";"d"]);;
- : bool = false
Любая помощь будет принята с благодарностью!
@ДанД. Точно. Список строк должен соответствовать регулярному выражению a+b+c+d+ с использованием чисто функционального программирования.
Ответы 1
Ключ к тому, чтобы сделать что-то чисто функциональным, заключается в том, что все состояние должно передаваться как параметры функции и возвращаемые значения. В вашем случае состояние - это входной поток; т. е. список, который еще не проанализирован.
Один из способов сделать это — заставить каждую функцию синтаксического анализа возвращать логическое значение, указывающее, увидела ли она то, что ожидалось, а также возвращать не проанализированный остаток списка.
Это означает, что вы должны использовать функции синтаксического анализа с таким типом:
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) заключается в том, что ваши функции синтаксического анализа должны возвращать оставшуюся часть входного потока, а также индикацию успеха/неудачи.
(Обратите внимание, что здесь пока нет рекурсии, но она появится, когда вы напишете отдельные функции синтаксического анализа.)
Похоже на соответствие обычному языку
a+b+c+d+?