15.1.2. Анализ трансформационных грамматик

После начального периода, когда был предложен ряд способов решения задачи, стал развиваться метод анализа трансформационных грамматик. Один и тот же основной метод описывался по крайней мере в нескольких статьях (Бобров и Фрезер, 1969; Каплан, 1972; Торн, Бретли и Дьюар, 1969; Вудс, 1970). Однако следует помнить, что алгоритмы анализа для трансформационных грамматик были исследованы еще не так глубоко, как для НС-грамматик, и не будет неожиданным, если вскоре появится совершенно новый метод анализа трансформационных языков.

Рис. 15.4. Сеть переходов с конечным числом состояний.

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

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

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

(2) Каждая дуга помечается либо символом окончания цепочки, либо именем подмножества терминальных символов. Когда дуга пройдена, должен быть взят один из терминальных символов этого подмножества, соответствующий этой дуге.

(3) Продолжать процесс до тех пор, пока не будет достигнут узел Здесь цепочка кончается.

Допустим, например, что с помощью рис. 15.4 нужно получить

Порядок рассматриваемых узлов будет таким:

Теперь рассмотрим вопрос о восприятии цепочки. Для данной цепочки мы должны сказать, могла ли породить ее грамматика, определенная этой сетью. Чтобы ответить на вопрос, начнем с состояния , беря по порядку каждое из слов на входе, найдем дугу, которую можно пройти, чтобы породить данный символ. Если после мы оказались в это предложение считается воспринятым.

Модели с конечным числом состояний несовершенны, ибо они не способны работать с правилами рекурсивного порождения. Это правила, в которых одиночный символ слева воспроизводится справа. Например,

В наших примерах для естественных языков была эта форма. Все глубинные структуры для (13), (15) и (16) имели вид

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

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

(1) Начать с в исходной сети. Завершение пути по этой сети к эквивалентно успешному анализу.

(2) На каждом шаге пройти дугу и породить (или воспринять) нетерминальные символы, как ранее, с одним лишь исключением:

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

Назовем сеть, из которой передается управление, вызывающей, а вторую сеть — вызванной. Вызванная сеть начинает анализ со своего собственного начального символа, используя следующий символ в цепочке как свой первый входной символ. При достижении своего выходного узла вызванная сеть передает управление обратно определенному узлу в вызывающей сети. Теперь „следующим символом, подлежащим прочтению" (порождению), будет первый символ после тех, которые были распознаны только что закончившей работу вызванной сетью.

(4) Вызванная сеть может вызывать другие сети. Разрешены рекурсивные вызовы (в этом случае сеть переходит к собственному начальному состоянию либо непосредственно, либо через промежуточную сеть).

При исследовании того, как сеть переходов анализирует предложение, полезно представлять себе две различные составляющие алгоритма анализа: собственно сеть и управляющую программу. Управляющая программа ответственна за запоминание слова, считываемого из входной цепочки, последовательности вызовов и места в сети, активного в данный момент. В сети с конечным числом состояний без возможностей рекурсии управляющая программа просто проверяет, является ли только что считанное слово возможной меткой для одной из дуг, выходящих из активного в данный момент узла. Если система располагает к тому же возможностью вызова, управляющая программа должна уметь выполнять еще две операции: PUSH и POP (заталкивание и выталкивание). Предположим, что программа читает слово во входной цепочке и находится в узле нашей сети. Этот узел будет связываться с дугами, выходящими из него и, кроме того, со списком сетей, которые можно вызвать из него. Если входное слово не является допустимой меткой

для одной из этих дуг, то управляющая программа вызывает PUSH к одной из сетей, которые можно вызвать. Операция PUSH помещает указатель к узлу в „магазинном списке" и затем приступает к анализу вызванных сетей. Магазинный список — это список узлов, имена которых считываются в порядке, обратном порядку записи их в этот список. (В терминах исследования операций это называется очередью типа „последним вошел, первым вышел“.) Таким образом, если элементы помещаются в магазинный список в порядке они будут считываться в порядке Операция POP обратна операции PUSH, она берет имя первого узла из магазинного списка и передает ему управление. POP применяется для передачи управления назад к вызывающей сети после того, как достигнут концевой узел вызванной сети. POP применяется также при указании на неудачу, если нельзя найти никакого пути через вызванную сеть.

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

Анализ начинается с состояния в сети Управление сразу передается к и входным словом все еще будет Сеть обнаружит на пути что the detective — это NP. Заключим эту смысловую единицу в скобки, чтобы отметить ее как составляющую предложения. В соответствии с операцией POP в управление возвращается к Заметим, что возвращение опустошает магазинный список. Теперь предложение принимает вид

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

Магазинный список представляет собой Сеть можно использовать для непосредственного распознавания но слово требует для распознавания связанной с ним фразы вызова сети

Рис. 15.5. (см. скан) Пример сети с конечным числом состояний и с процедурой вызова.

Когда управление передается к магазинным списком будет и неполный анализ предложения на этом этапе таков:

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

Heard, последнее слово предложения, считывается в (D), и выполняются операции POP в порядке и Это опустошает магазинный список и управление передается к состоянию которое является заключительной точкой сети самого высокого уровня. Грамматический анализ теперь завершен:

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

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

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

Анализ осуществляется следующими этапами:

(1) Войти в узел Перейти к и передать управление сети В магазинный список записать

Рис. 15.6. (см. скан) Сеть с конечным числом состояний, с процедурой вызова и регистрами (SUBJECT, VERB, OBJECT, AGENT).

(2) С помощью сети опознать (Lady Agatha) как группу существительного. POP возвращает управление к В точке А поместить Lady Agatha) в регистр SUBJECT.

(3) Войти в и передать управление сети Опознать как глагол. (Заметим, что это предпочтительная конструкция. Управляющая программа пытается читать от

к Только в случае неудачи она вернется к попытке чтения от к . В точке В поместить в регистр

(4) Управление переходит к узлу а из него к сети Сеть однако, неудачна, поскольку следующее слово в цепочке, а именно не является ни существительным, ни определением. Затем управляющая программа возвращается к последней точке, где принималось решение, т. е. к выходу из и выбирает ветвь к AUX.

(5) Was распознается как вспомогательный глагол, — как глагол в страдательном залоге. Тогда помещается в регистр VERB с отметкой прошедшее время, страдательный залог)).

(6) Управление переходит к узлу а из него к сети Цепочка опознается как предложная группа места и помечается. Операции POP проходят от через к точке С.

(7) К этому моменту анализ предложения дошел до В точке С используются возможности трансформации. Завершив идентификацию группы глагола, управляющая программа находит, что регистр VERB содержит указатель страдательного залога. Трансформационное правило, содержащееся в данной задаче, гласит: „Для глаголов в страдательном залоге переместить содержимое регистра в SUBJECT и регистра SUBJECT в Поскольку регистр пуст, его содержимым считается (некто). Перестройка регистров дает

Получили правильную глубинную структуру.

Расширенные сети обладают той же мощностью, что и машины Тьюринга. Это значит, что любой язык, распознаваемый программой для ЭВМ, можно распознать программой, применяющей метод расширенных сетей переходов. Такое значительное увеличение мощности достигнуто для идейно достаточно простого механизма графового представления грамматики. Это, однако, далось не даром. Управляющая программа должна стать гораздо более сложной. Фактически увеличение сложности управляющей программы, обусловленное использованием регистров и структурным переупорядочением, качественно отличается от увеличения сложности, обусловленного операциями PUSH и POP. Чтобы перейти от анализа одного языка к анализу другого с помощью сети с конечным числом состояний без регистров, достаточно изменить лишь эти сети. Управляющие программы инвариантны относительно языков. Как только на управляющую программу будет возложена ответственность за

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