Синтаксический анализ в СП

В основе универсального синтаксического анализатора рассматриваемого СП лежит алгоритм нисходящего синтаксического анализа с возвратами, который в системах искусственного интеллекта получил название бэктрекинга. Напомним его основные моменты, воспользовавшись образным его изложением, позаимствованным из монографии Гриса [5].

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

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

Некоему человеку предстоит провести разбор предложения a. Прежде всего ему необходимо отыскать вывод S Þ⁺ a где S - начальный символ грамматики; следовательно, первым непосредственным выводом должен быть S Þ x, где S ® x - правило грамматики. Пусть для S существуют правила: S ® X₁¼X _n½Y₁¼Y_m½Z₁¼Z_{l .} Сначала человек пытается применить правило S ® X₁¼X _n. Если дерево вывода построить нельзя, то он применит правило S ® Y₁¼Y_m и т.п.

Как ему определить, правильно ли он выбрал непосредственный вывод SÞX₁¼X_{n .} Заметим, что если он правилен, то для некоторых цепочек a _i будет иметь место a = a₁¼a_n где X _i Þ^* a_i, для i = 1¸n. Прежде всего человек, выполняющий разбор, возьмет себе приемного сына M₁, который должен найти вывод X₁Þ^*a₁ для любого a ₁, такого что a=a₁¼. Если сыну М₁ удалось найти такой вывод он (или любой из его сынов, внуков и т.д.) закрывает цепочку a₁ в предложении a и сообщает своему отцу об успехе. Тогда его отец усыновит М₂ , чтобы тот нашел вывод X₂ Þ ^*a₂ где a=a₁a_2¼ и ждет ответа от него и т.д. Как только сообщит об успехе М _i-1 сын, - отец усыновит М_i , чтобы тот нашел вывод X _iÞ^* a _i . Сообщение об успехе сына М _n означает, что разбор предложения закончен и оно правильно.

Как быть, если сыну M _i не удалось найти вывод X _iÞ^*a _i. В этом случае M _i сообщает о неудаче отцу, тот от него отрекается и дает старшему брату M _i – M _i-1 такое распоряжение: “Ты уже нашел вывод, но он неверен! Найди-ка мне другой”. Если M _i-1 сумеет найти другой вывод, он вновь сообщит об успехе и все пойдет по-прежнему. Если же M _i-1 сообщит о неудаче, то отец отречется и от него и попросит осуществить попытку M _i-2 и т.п. Если придется отречься и от M₁, то это означает, что вывод SÞX₁¼X_n неверный и человек начинает разбор, воспользовавшись другим выводом – S ÞY₁¼Y_m.

Как же действует каждый из M _i ? Предположим, что его целью является терминал a _{i .} Входная цепочка имеет вид a=a_1¼a_i где a_1¼a_i уже проанализированы другими людьми. От M _i требуется просто проверить, совпадает ли очередной символ грамматики x _i с символом строки а _i. Если да, то сообщить об успехе, если нет, - то о неудаче.

Если цель M _i нетерминал A _i, то M _i поступит точно также как и его отец. Он начинает проверять правые части правил, относящиеся к этому нетерминалу, и, если необходимо, усыновляет или отрекается от сыновей. Если все его сыновья сообщают об успехе, то он сообщит об успехе своему отцу. Если отец попросит M _i найти другой вывод и цель - терминал, то M _i сообщит о неудаче, так как другого такого вывода не существует. В противном случае M _i просит своего младшего сына найти другой вывод и реагирует на него так же, как и раньше. Если все сыновья сообщают о неудаче, то он сообщает об этом своему отцу, и этот процесс усыновления может быть очень глубоким (все зависит от грамматики фразы). Привлекательность этого метода в том, что каждый человек должен помнить лишь о своей цели, о своем отце, о своих сыновьях, а также о своем месте в грамматике и цепочке, которую он анализирует. И никому не нужны точные сведения о том, что происходит в иных местах. Это как раз то, к чему вообще надо стремиться в программировании: В каждом фрагменте программы, в каждой процедуре надо заботится только о собственной входной и выходной информации и ни о чем больше.

Казалось бы, что приведенный алгоритм достаточно сложен, но важно помнить, что и отец, и сын, и внук делают здесь то же, что и каждый из них. В основе синтаксического анализатора лежит одна рекурсивная функция DESCENT (спуск). Она осуществляет просмотр правой части заданной продукции или ее фрагмента (альтернативы, факультатива, итерации) и возвращает TRUE, если указанный фрагмент продукции был полностью отождествлен с текущим фрагментом анализируемого текста, и FALSE в противном случае. Параметр этой функции - индекс IG, играющий роль курсора в заданной грамматике языка. При обращении к функции DESCENT, ей задается положение первого символа отождествляемой части продукции. Побочный эффект функции DESCENT - сдвиг курсора IG за конец отождествляемой части продукции. Процедуру DESCENT можно рассматривать как синтаксически управляемый монитор, осуществляющий вызов таких ветвей анализа как разделитель, терминал, синтерм, семантика, нетерминал, альтернатива, итерация, факультатив.

Процесс рекурсивного спуска управляется положением двух индексов: IG указывает на позицию в грамматике, а L – на позицию в строке лексем исходной программы. Кроме того, индекс M связан с позицией файла семантических действий. Поскольку процесс спуска связан с рекурсией, все индексы имеют множество локальных копий, которые сохраняются в стеке и восстанавливаются при возврате из рекурсии, обеспечивая возможность спуска по альтернативной ветви и подъема к конечному результату: TRUE или FALSE.

Прежде чем обсудить алгоритм функции DESCENT, приведенный на рис. 4.8, введем некоторые обозначения и соглашения. Обозначим через GRAM [IG] символ грамматики, на который указывает индекс IG. При этом нетерминал вместе со ссылкой на соответствующую продукцию, терминал или разделитель вместе со ссылкой на соответствующую таблицу, синтерм, номер семантического действия, любой метасимвол будем считать одним символом грамматики.

Перемещение индекса IG по грамматике выполняется с помощью процедуры
INC (IG), перемещающей его на шаг вправо, на соседний символ, и путем вычисления его нового положения функциями PROD (IG), HI (IG) и LO (IG). Функция PROD вычисляет позицию начала продукции для нетерминала, на который указывает индекс IG. Функция HI\LO выполняет вычисление позиции, на которую указывает верхняя\нижняя ссылка отдельных метасимволов (см. рис. 4.6).

Запись вида GRAM[IG] = <…> или GRAM[IG] = @…@ следует понимать как символ под курсором - нетерминал или синтерм и т.п.

Процедура SEMANTICS (семантика)формирует очередную запись в промежуточном файле семантических действий, работу с которым мы рассмотрим в разделе 4.3.4. Логическая функция SYNTERM (синтаксический терминал)определяет, имеется ли во входном тексте лексема, соответствующая типу синтерма, указанному в GRAM [IG]. Если это так, то индекс L перемещается по тексту на следующую лексему.

Функции DELIMITER (разделитель) и TERMINAL (терминал) проверяют, есть ли в текущей позиции исходного текста лексема данного типа, и в случае успеха сравнивает табличные индексы из грамматики и текста. При их совпадении возвращает TRUE, иначе FALSE. Эти процедуры нерекурсивны, что определяется природой самой грамматики.

Наиболее простое направление рекурсивного спуска связано здесь с анализом нетерминала. Завершение работы функции DESCENT с результатом TRUE (положительный бэктрекинг) позволяет продолжить анализ входного текста, сообразуясь с положением пары индексов: IG и L.

Процедуры ALTERNATIVE (альтернатива), ITERATION (итерация) и FACULTATIVE (факультатив)характеризуются наличием собственных вызовов DESCENT. Кроме того эти процедуры способны изменить позицию индекса грамматики IG, сдвигая его не только вперед по продукции, но и восстанавливая его старое положение (сдвигая назад). Аналогично они работают с индексами входного текста - L и семантики - M.

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

Функция DESCENT, представленная на рис. 4.8, написана на языке очень похожем на ПАСКАЛЬ. Надеюсь, что выбранный язык и масса комментариев в тексте программы сделают обсуждаемые алгоритмы прозрачными для читателя, и рисовать здесь еще и блок-схему нет необходимости.

Логическая функция ALTERNATIVE представлена на рис. 4.9.

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

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

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

“Ожидается ¢,¢, ¢;¢” или “Ожидается идентификатор, целое число”

Если ошибок обнаружено не было, то формируется файл семантических действий, который и обрабатывается на третьем проходе.

Поиск по сайту: