На самом нижнем уровне разбор сводится к многократной проверке, является ли следующее неразобранное слово элементом списка слов для данной части речи. Чтобы реализовать это, мы заводим глобальную переменную *unparsed*, содержащую еще неразобранный ввод. Каждый раз, проверяя слово, мы требуем, чтобы *unparsed* не была пустым списком и чтобы ее значение начиналось со слова из указанного списка. Если это так, мы убираем слово из *unparsed* и возвращаем его вместе с частью речи (которую можно найти в голове списка):51

(define (parse-word word-list)

(require (not (null? *unparsed*)))

(require (memq (car *unparsed*) (cdr word-list)))

(let ((found-word (car *unparsed*)))

(set! *unparsed* (cdr *unparsed*))

(list (car word-list) found-word)))

Чтобы запустить разбор, нужно только присвоить переменной *unparsed* весь имеющийся ввод, попытаться проанализировать предложение и убедиться, что ничего не осталось в конце:

(define *unparsed* ())

(define (parse input) (set! *unparsed* input) (let ((sent (parse-sentence))) (require (null? *unparsed*)) sent))

Теперь мы можем опробовать анализатор и убедиться, что он работает на нашем простом примере:

;;; Ввод Amb-Eval: (parse (the cat eats)) ;;; Начало новой задачи ;;; Значение Amb-Eval:

(sentence (noun-phrase (article the) (noun cat)) (verb eats))

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

Добавим к грамматике список предлогов:

(define prepositions (prep for to in by with))

и определим предложную группу (например, for the cat, «для кошки») как последовательность из предлога и именной группы:

(define (parse-prepositional-phrase) (list prep-phrase

(parse-word prepositions) (parse-noun-phrase)))

51 Обратите внимание, что parse-word изменяет список необработанных слов при помощи set!. Для того, чтобы это работало, amb-интерпретатор при возврате должен отменять действия операций set! .

Теперь мы можем сказать, что предложение - это именная группа, за которой следует глагольная группа, а глагольная группа - это либо глагол, либо глагольная группа, дополненная предложной группой:59

(define (parse-sentence) (list sentence

(parse-noun-phrase) (parse-verb-phrase)))

(define (parse-verb-phrase)

(define (maybe-extend verb-phrase) (amb verb-phrase

(maybe-extend (list verb-phrase verb-phrase

(parse-prepositional-phrase))))) (maybe-extend (parse-word verbs)))

Раз уж мы занялись этим делом, можно также уточнить определение именной группы и разрешить выражения вроде a cat in the class («кошка в аудитории»). То, что раньше называлось именной группой, теперь мы будем называть простой именной группой, а именная группа теперь может быть либо простой именной группой, либо именной группой, которая дополняется предложной группой:

(define (parse-simple-noun-phrase) (list simple-noun-phrase

(parse-word articles) (parse-word nouns)))

(define (parse-noun-phrase)

(define (maybe-extend noun-phrase) (amb noun-phrase

(maybe-extend (list noun-phrase noun-phrase

(parse-prepositional-phrase))))) (maybe-extend (parse-simple-noun-phrase)))

Обновленная грамматика позволяет разбирать более сложные предложения. Например,

(parse (the student with the cat sleeps in the class))

(«студент с кошкой спит в аудитории») дает

(sentence (noun-phrase

(simple-noun-phrase (article the) (noun student)) (prep-phrase (prep with)

(simple-noun-phrase (article the) (noun cat))))

(verb-phrase (verb sleeps)

52Заметим, что это определение рекурсивно - за глаголом может следовать любое число предложных групп.

(prep-phrase (prep in)

(simple-noun-phrase (article the) (noun class)))))

Заметим, что входное предложение может иметь более одного законного анализа. В предложении The professor lectures to the student with the cat («Профессор читает лекцию студенту с кошкой») может иметься в виду, что профессор вместе с кошкой читают лекцию, или что кошка - у студента. Наша недетерминистская программа находит оба варианта:

(parse (the professor lectures to the student with the cat))

дает

(sentence

(simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb-phrase (verb lectures) (prep-phrase (prep to)

(simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep with)

(simple-noun-phrase (article the) (noun cat)))))

Если попросить интерпретатор поискать еще, получится

(sentence

(simple-noun-phrase (article the) (noun professor)) (verb-phrase (verb lectures) (prep-phrase (prep to)

(noun-phrase (simple-noun-phrase

(article the) (noun student)) (prep-phrase (prep with)

(simple-noun-phrase (article the) (noun cat)))))))

Упражнение 4.45.

Согласно заданной выше грамматике, следующее предложение можно проанализировать пятью различными способами: The professor lectures to the student in the class with the cat («Профессор читает лекцию студенту в аудитории с кошкой»). Покажите эти пять разборов и объясните разницу в оттенках значения между ними.

Упражнение 4.46.

Интерпретаторы в разделах 4.1 и 4.2 не определяют, в каком порядке вычисляются операнды при вызове процедуры. Мы увидим, что amb-интерпретатор вычисляет их слева направо. Объясните, почему программа разбора не стала бы работать, если бы операнды вычислялись в каком-нибудь другом порядке.