Конструирование распознавателей
Результативность функций высших порядков Хендерсон показывает на модельной задаче построения распознавателя контекстно-свободного языка [3].
В качестве примера такого языка рассмотрен синтаксис понятия «слог», образованный по правилам из гласных и согласных звуков, что можно представить грамматикой вида:
<а-гр> ::= А | А <а-гр>
<в-гр> ::= В | В <в-гр>
<слог> ::= <а-гр> <в-гр> | <в-гр> <а-гр> | <в-гр> <а-гр> <в-гр>
В этой грамматике «А» и «В» — терминальные символы, «слог», «а-гр» и «в-гр» — нетерминальные символы (метапонятия), «слог» — основное понятие. Необходимо быстро построить предикат is-syllable, выделяющий списки, представляющие правильно построенные слоги в соответствии с приведенными правилами.
Такое построение можно выполнить с помощью ряда функций высокого порядка, конструирующих распознаватели для альтернатив и цепочек из понятий, к которым сводится определение грамматики языка. Предполагается, что каждому правилу будет соответствовать свой распознающий предикат. Для простоты ограничимся случаями из пар альтернатив и двухзвенных цепочек.
Пусть тексты этого языка представляются списками из однобуквенных атомов A и B. Допустим, имеются предикаты is-A и is-B, выделяющие одноэлементные списки (A) и (B), соответственно.
(defun is-a (x)(cond ((eq(car x) 'a) (null (cdr x))) )) ; распознаватель A (defun is-b (x)(cond ((eq(car x) 'b) (null (cdr x))) )) ; распознаватель B
Типовые ранги этих функций одинаковы: List (X) -> Bool. Таким же должен быть и ранг результирующей функции is-syllable. При ее построении будет применена вспомогательная функция более высокого порядка is-alt, которая из произвольных предикатов конструирует новый предикат, перебирающий варианты правил и выдающий Nil, если ни одно из них не подходит. Функция is-alt может быть определена следующим образом:
(defun is-alt (p q) #'(lambda (x) (cond ((funcall p x )T) ; конструктор распознавателя альтернатив ((funcall q x) T) (T Nil))))
Ее типовый ранг имеет вид:
(List(X)->Bool List(X)->Bool ) -> List(X)->Bool
Можно использовать эквивалент:
(defun is-alt (p q) #'(lambda (x) (if (funcall p x) T (funcall q x)) )
Предикат both, работающий как логическая связка «и», можно реализовать как обычную функцию с типовым рангом (Bool Bool) -> Bool.
(defun both (x y) (cond ( x y)(T Nil)) ) ; проверка одновременности условий
Еще одна вспомогательная функция высокого порядка is-chain из произвольных предикатов конструирует новый предикат, выясняющий, не выделяют ли исходные предикаты смежные звенья цепочки. Типовый ранг этой функции должен быть таким же, как у is-alt, т.к. их результаты используются при разборе и анализе текста в одинаковых позициях.
(defun is-chain (p q) #'(lambda (x ) ; конструктор распознавателя цепочек (cond ((null x) (both (funcall p x) (funcall q 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))) q ) (cdr x) )) ))) ; сдвиг границы разбиения вправо
Из данного распознавателя is-a можно бы и без функций высших порядков построить распознаватель is-a-gr, распознающий группу из любого числа символов A:
(defun is-a-gr (x ) (if x ; распознаватель цепочек из A (cond ((eq (car x) 'a) (is-a-tl (cdr x)) ) ; <а-гр> ::= А | А <а-гр> (t nil) ) Nil))
(defun is-a-tl (x)(cond ((null x)T)((eq (car x)'A)(is-a-tl (cdr x )) )))) ; хвост цепочки из A
Но использование конструкторов is-alt и is-chain, показанное на примере распознавателя is-b-gr, позволяет построить определение, синтаксически подобное правилу грамматики:
(defun is-b-gr (x ) (funcall (is-alt #'is-b is-chain #'is-b #'is-b-gr)) x )) ; распознаватель цепочек из B ; <в-гр> ::= В | В <в-гр>
Теперь опробованные приемы конструирования распознавателей применяем к построению функции is-syllable, активно опираясь на чисто внешнее, синтаксическое подобие определению заданной грамматики:
(defun is-syllable (x ) ; распознаватель слога (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) ; BA (is-alt (is-chain #'is-a-gr #'is-b-gr) ; AB (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr)) ; BAB ) ) x ))
(is-syllable '(a b)) (is-syllable '(b a)) (is-syllable '(b a b )) (is-syllable '(b b b b a a b b ))
Сопоставляя правила и полученное определение распознавателя, можно убедиться, что собственно конструирование распознавателя осуществляется и модернизируется сравнительно быстро: достаточно свести распознаваемый язык к композиции альтернатив и цепочек.
<слог> ::= <в-гр> <а-гр> | <а-гр> <в-гр> | <в-гр> <а-гр> <в-гр>
(defun is-syllable (x ) ; распознаватель слога ; <слог> ::= (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) ; BA ; <в-гр> <а-гр> (is-alt (is-chain #'is-a-gr #'is-b-gr) ; AB ; | <a-гр> <b-гр> (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr)) ; BAB ; | <в-гр> <а-гр> <в-гр>
) ) x ))
Результат сопоставления показывает, что достигнуто синтаксическое подобие определения грамматики и построенного распознавателя. Это значит, что определение можно автоматически отобразить в такой распознаватель. Отображение — функция высокого порядка, вырабатывающая в качестве результата распознаватель языка, порождаемого исходной грамматикой.
(defun is-alt (p q) #'(lambda (x) (cond ((funcall p x )T) ((funcall q x) T) (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))) )))
(defun is-syllable (x ) ; распознаватель слога (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) ; BA (is-alt (is-chain #'is-a-gr #'is-b-gr) ; AB (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr)) ; BAB ) ) x ))
<слог> ::= <в-гр> <а-гр> | <а-гр> <в-гр> | <в-гр> <а-гр> <в-гр>
