НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

Компиляция расширенных сетей переходов в программы на Лиспе

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

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

  • Несколько меньших сетей могут быть связаны вместе в одну большую систему согласно условию, что некоторые дуги соответствуют успешному прохождению сети, а не просто поглощению одного слова. Например, сеть группы существительного имеет дугу предложной группы, а предложная группа имеет дугу группы существительного, что придает всему формализму рекурсивный характер.
  • На дугах может производиться больше действий, чем просто узнавание классов слов и продвижение по предложению. Сеть переходов считается расширенной, если по мере прохождения дуг разрешается на них делать пометки, а в дальнейшем отсылать к этим пометкам. Можно, например, при движении по дуге определителя со словом а сделать заметку, что группа существительного стоит несомненно в единственном числе*. В дальнейшем можно применить какой-то тест для проверки этого заключения, когда встречается соответствующее существительное.

* (Неопределенный артикль а в английском языке как раз и указывает на это.- Прим. перев.)

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

Предупреждение: свойство автоматического возвращения стандартных РСП нами реализовано не будет. Для этого есть две причины. Во-первых, имеются серьезные сомнения в разумности использования поиска в глубину и в процессе создания находятся лучшие альтернативы. А во-вторых, опуская поиск, мы добиваемся еще большей простоты, хотя и путем потери эффективности.

Приведение в соответствие с расширенной сетью переходов представляет собой некоторый вариант сопоставления с образцом

С некоторой точки зрения, расширенная сеть переходов - это обобщенный образец того типа, который мы недавно рассматривали. Изменения, однако, значительны:

  • В случае РСП "при сопоставлении" может быть проверено не только само слово, но и любая его характеристика.
  • В случае "образцов" типа РСП могут быть определены под образцы путем отсылки к ассоциированным сетям. Эти отсылки могут носить рекурсивный характер.
  • При "выполнении" РСП процесс может направляться динамическими изменениями режима, путем установки и проверки состояния регистров.

Для расширенных сетей переходов нетрудно построить программы на Лиспе

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

Каждое состояние в сети переходов будет иметь соответствующую метку в функции PROG при придании сети формы программы. Предположим пока, что S представляет собой переменную, ее значение - список слов, которые еще предстоит проанализировать, W - также переменная, ее значение - это рассматриваемое в данный момент слово, то слово, которое является CAR от S. Тогда следующий фрагмент программы будет искать определитель, за которым идет любое число прилагательных, а за ними следует существительное*.


* (В этой и последующих программах DET - сокращение для определителя, ADJ - для прилагательного, a NOUN - для существительного.- Прим. перев)

Отсюда видно, что классификационный тип слова появляется в списке свойств этого слова, как значение свойства FEATURES (ХАРАКТЕРИСТИКИ). В том же списке, что и характеристика типа, могут быть и такие характеристики, как SING для единственного числа и IMP для повелительного наклонения.

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


Обратите внимание, что функция GOBBLE проверяет, не является ли S значением CDR от конца некоторого списка. В функции PUTF (ВВЕСТИ-ХАРАКТЕРИСТИКУ) используется тест, чтобы избежать дублирования*. Эта функция дает возможность добавлять новую характеристику или целый список характеристик. Используя новые функции, первоначальный фрагмент программы мы можем переписать так**:


* (Входящая в POTF функция UNION является библиотечкой и определяет объединение элемента со списком, в результате чего порождается новый список.- Прим. перев.)

** ( Функция GETF позволяет извлекать характеристики.- Прим. перев.)

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

  • Должны иметься специалисты для различных типов групп. NOUNG (ГРУППА-СУЩЕСТВИТЕЛЬНОГО) - это такой специалист для группы существительного.
  • Для вновь обнаруженной группы существительного создается новый атом. NOUNG3 представляет собой типичное имя для группы существительного. Этот новый атом может иметь свойство FEATURES (ХАРАКТЕРИСТИКИ) для хранения информации, относящейся к соответствующей группе.
  • В памяти должно храниться отношение между каждой группой существительного и группой более высокого уровня, частью которой она является. Это реализуется благодаря передаче имени группы высокого уровня программе-специалисту в качестве аргумента и использованию функции PUTPROP для создания и модифицирования соответствующих свойств PARENT (РОДИТЕЛЬ) и OFFSPRING (ПОТОМОК).
  • При необходимости группа может быть инициализирована путем установки характеристик (признаков) через отличное от NIL значение для аргумента FEATURES специалиста.
  • Если поиск некоторой группы оказывается безуспешным, то переменные S и W должны быть возвращены к их первоначальным значениям.

В следующей структуре эти цели достигаются путем использования инструкций вызова и выхода. Заметьте, что команды (RETURN Т) и (RETURN NIL) из предыдущего фрагмента должны быть заменены на (GO WIN) и (GO LOSE)*.


* (Метки WIN и LOSE обозначают, соответственно, успех и неудачу.- Прим. перев.)

Функция GENNAME (СОЗДАТЬ-ИМЯ) при каждом к ней обращении создает новое имя для атома. Когда значением аргумента функции GENNAME является NOUNG, как это имеет место выше, новый атом имеет имя NOUNGrc, где число n увеличивается на единицу всякий раз, когда эта функция используется с NOUNG в качестве значения аргумента. Функция GENNAME не является стандартной функцией системы Лиспа*, но она может быть определена через функции EXPLODE и IMPLODE.

До сих пор все идет хорошо. Предусмотрев дальнейшую передачу характеристик и предложные группы, за которыми идет существительное, мы получаем следующее:


* ()

Эта программа становится более простой, а отсюда и более понятной, если специалист по словам - WORD возьмет на себя обязанности проверки слов и хранения соответствующей информации, когда обнаруживаются ожидаемые слова. Тогда новая переменная LAST-CREATED (ПОСЛЕДНЯЯ-ИЗ-СОЗДАННЫХ) получает значение в рамках специалиста по словам. Значением ее является узел, построенный для слова*.

* (В приведенной ниже программе PROPERNOUN обозначает имя собственное, PREPG - предложную группу, a DET - определитель.- Прим. перев.)

Заметьте, что когда прекращается работа функции NOUNG (ГРУППА-СУЩЕСТВИТЕЛЬНОГО), переменная LAST-CREATED получает новое значение. Таким образом, по нашей логике LAST- CREATED всегда связана с последним из созданных узлов. Заметьте также, что эта новая версия функции NOUNG работает и с именами собственными. Появившийся здесь специалист по словам определяется следующим образом*::


Поскольку специалист по словам создает узлы для тех слов, с которыми он встречается, то начальное значение для S в виде предложения (THE PYRAMID ON A RED BLOCK), т. e. (ПИРАМИДА НА КРАСНОМ БЛОКЕ), порождает довольно много узлов, когда оценивается функция (NOUNG 'CLAUSE NIL)*.



* (PARTICLE в этой распечатке означает ЧАСТИЦА,- Прим. перев.)

Древовидная структура для этих узлов изображена на рис. 15.1

Рис. 15.1. Расширенные сети переходов, помимо обнаружения признаков и заполнения ячеек, строят деревья. Здесь приведена структура для группы существительного 'эта пирамида на некотором красном блоке'
Рис. 15.1. Расширенные сети переходов, помимо обнаружения признаков и заполнения ячеек, строят деревья. Здесь приведена структура для группы существительного 'эта пирамида на некотором красном блоке'

Перевести сети РСП на Лисп можно путем компиляции, исходя из очевидных спецификаций

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

  • Компилятор представляет собой программу, которая переводит описания процедур с одного языка на другой.

Прежде всего должен иметься какой-то исходный язык для РСП, удобный для набора на клавиатуре терминала, и в то же время этот язык должен иметь удобный синтаксис, чтобы для создания описаний не требовалось больших усилий. Эти детали в значительной степени определяются вкусом и изобретательностью. Таким образом, следующий базовый синтаксис для состояния с одним входом представляет собой реализацию одной из многих возможностей:


Тест может представлять собой любой фрагмент на Лиспе. Стрелка создает графический образ перехода по сети. Большее число переходов просто увеличивает число содержащих стрелку описаний изменения состояния. Если переход должен сопровождаться побочными эффектами, то эти побочные эффекты определяются фрагментом на Лиспе, идущим за красноречивым атомом AFTER (ПОСЛЕ):


Таким образом, определения специалистов по словам и группам существительного можно переписать как на стр. 410.

Теперь задача сводится к созданию функции ABSORB на Лиспе, которая преобразует это новое прозрачное описание в старое, которое Лисп понимает непосредственно. Хорошо, что для этого не требуется ничего большего, чем те возможности по манипулированию списками, которые столь характерны для языка Лисп.

Во-первых, конечно, каждая спецификация, определяемая переходом по сети, должна быть отделена от других и помещена в некоторое предложение с функцией COND. Затем несколько предложений для каждого состояния должны быть объединены в рамиах одной структуры с функцией COND. Естественно, что функции CAR, CDR и CONS используются в большом количестве. Fс ли предполагать, что переменная CLAUSE (ПРЕДЛОЖЕНИЕ) имеет


значение, соответствующее одной из спецификаций перехода, то выполняется следующее соответствие:


На рис. 15.2 показано, как эти элементы входят в условное предложение, содержащее COND. Эта конструкция может быть осуществлена следующим фрагментом:


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

Заметим, что наш запрятанный тест просто осуществляет проверку, присутствуют ли описания побочных эффектов, и возвращает их, если они имеются. Если нет, то возвращается NIL, который исчезает в результате выполнения функции APPEND.

Рис. 15.2. Расширенные сети переходов компилируются с языка со специально подобранным синтаксисом в эквивалентные выражения на Лисп путем реорганизации частей. В показанном случае осуществляется перевод описания дуги в предложение с функцией COND. Здесь широко используются присущие Лиспу возможности манипулирования символами
Рис. 15.2. Расширенные сети переходов компилируются с языка со специально подобранным синтаксисом в эквивалентные выражения на Лисп путем реорганизации частей. В показанном случае осуществляется перевод описания дуги в предложение с функцией COND. Здесь широко используются присущие Лиспу возможности манипулирования символами

Предложения COND для конкретного состояния собираются вместе комбинацией MAPCAR и LAMBDA, оперирующей над списком спецификаций перехода, существующим в виде значения переменной STATE (СОСТОЯНИЕ), которая, по предположению, содержит весь пакет описания.


После того как это понято, требуемая структура с COND и все ее предложения могут быть собраны с помощью следующих инструкций:


Предложение (Т (GO LOSE)) в конце списка предложений дает возможность пользователю опустить это подразумеваемое по умолчанию утверждение в описаниях переходов между состояниями. Атом COND прикреплен, разумеется, к другому концу списка, и всему пакету предшествует имя состояния, которое устанавливается функцией (CAR STATE).

Вся средняя часть создаваемой программы строится путем многократного использования такого предложения для каждого состояния, определяемого телом описания РСП. Осуществление такого повторения с помощью комбинации MAPCAR и LAMBDA приводит к следующему результату, который выглядит несколько сложновато:


По счастью, на этом весь перевод оказывается почти законченным, поскольку средняя часть создаваемой нами программы является единственным ее участком, который зависит от даваемого описания. В самом деле, заключительная часть всегда одна и та же и появляется в виде гигантского "квотированного" списка:


Начало лишь немногим более сложно. Соответствующая общая форма, которой предшествует одиночная кавычка, должна быть модифицирована с тем, чтобы включить имя программы в подходящем месте внутри функции GENNAME (СОЗДАТЬ-ИМЯ). Для этой модификации подойдет функция SUBST, поскольку она подставляет свой первый аргумент в места всех вхождений ее второго аргумента в состав третьего аргумента:


Располагая началом, серединой и концом, нетрудно построить описание и всей программы:


Значением величины PROGRAM (ПРОГРАММА) является обычная для Лиспа форма нужной нам программы. Чтобы в действительности реализовать это определение, вновь построенная программа в языке Лисп должна быть объединена с некоторым именем и списком аргументов в рамках формы DEFINE, а затем выполнена:


Теперь почти все на месте. Остается только обсудить, каким образом переменные NAME (ИМЯ) и BODY (ТЕЛО) принимают те значения, которые необходимы, чтобы все заработало. Проще всего определить функцию ABSORB как функцию двух аргументов:


Хотя этот путь и годится, но при этом требуется "квотировать" каждый аргумент, это немного раздражает:


FEXPR представляет собой функцию, которая не оценивает своих аргументов

Поскольку функция ABSORB всегда должна манипулировать аргументами без их предварительного оценивания, то было бы удобно иметь возможность избежать постоянного применения знака кавычки. Но поскольку обычные, определяемые пользователем функции всегда оценивают свои аргументы, то очевидно, что необходимо что-то новое. Должна присутствовать возможность определять не обычные функции. Вот как это делается:


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

Указанный специальный учет ограничивается тем, как обрабатываются аргументы функции. Во-первых, FEXPR никогда не оценивают свои аргументы. Во-вторых, все аргументы, которые встречаются при использовании FEXPR, независимо от того, сколько их, собираются в список, который становится затем значением одного атома, появляющегося вместе с именем функции, когда дается определение FEXPR. Пример поможет прояснить ситуацию. Предположим, что функция DEMONSTRATE (ДЕМОНСТРИРОВАТЬ) определяется как


Теперь предположим, что функция DEMONSTRATE используется следующим образом:


При этом не делается попытки оценить ни THIS, ни FUNCTION. Напротив, список (THIS FUNCTION) становится значением аргумента ARG. Поэтому функция PRINT приводит к печати (THIS FUNCTION), а функция LENGTH приводит к тому, что 2 возвращается в качестве значения этой функции:


Теперь функция ABSORB, компилирующая функция для РСП, может быть определена, как FEXPR без "квотирования" аргументов. На этом наше построение заканчивается. Распечатка результата в целом показывает, почему функция ABSORB вводилась нами по частям.


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

Построение компиляторов - обычно серьезное предприятие

В примере с РСП Лисп является языком реализации и компилятора и того языка, на который рассчитан компилятор. Построение компилятора принципиально было несложным, потому что и компилирование, и работа с цепочками слов являются задачами оперирования символами, для которых Лисп приспособлен более всего. Часто компиляторы транслируют с языка-источника на язык ассемблера, чтобы достичь высокого быстродействия. Работа над такими компиляторами является намного более трудной задачей, тем более если, опять-таки по причинам быстродействия, компилятор сам по себе должен быть написан на языке ассемблера.

предыдущая главасодержаниеследующая глава

Предпочитаете заниматься интимом в компании великолепной проститутки? Портал http://prostitutkihabarovskasex.com предлагает воспользоваться услугами рискованных шлюх, которые согласны даже на опыты в трахе.








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь