Парадигмы программирования

Конструирование распознавателей


Результативность функций высших порядков Хендерсон показывает на модельной задаче построения распознавателя контекстно-свободного языка, подробно описанной в курсе [[8],[23]]. В качестве примера такого языка рассмотрен синтаксис понятия "слог", образованный из гласных и согласных букв [[23]].

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

Таблица 12.1. Определение распознавателя языка, синтаксически подобное грамматики языка.

Грамматика

<слог> ::= <в-гр> <а-гр> | <а-гр> <в-гр> | <в-гр> <а-гр> <в-гр>

Распознаватель

(defun is-syllable (x ) (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) (is-alt (is-chain #'is-a-gr #'is-b-gr) (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-gr)) ) ) x ))

Вспомогательные функции

(defun is-alt (p q) #'(lambda (x) (cond ((funcall p x )T) ((funcall q x) T) (T Nil)))) (defun both (x y) (cond ( x y)(T Nil)) ) (defun is-chain (p q) #'(lambda (x ) (cond ((null x) nil) ((both(funcall p x) (funcall q nil)) T) ((both(funcall p Nil) (funcall q x)) T) ((both(funcall p (cons (car x)Nil)) (funcall q (cdr x)) ) T) (T(funcall (is-chain (lambda(y) (funcall p(cons(car x)y))) (lambda(y)(funcall q y)) ) (cdr x) )) )))



Содержание раздела