Всего за 133 руб. Купить полную версию
Работу распознавателя на основе алгоритма "сдвиг-свертка" можно описать так: если на верхушке стека МП-автомата находится цепочка символов у, то ее можно заменить на нетерминальный символ A при условии, что в грамматике языка существует правило вида A → у, не сдвигая при этом считывающую головку автомата (этот шаг работы называется "свертка"); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки a, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется "сдвиг" или "перенос").
Этот распознаватель потенциально имеет больше неоднозначностей, чем рассмотренный выше распознаватель, основанный на алгоритме подбора альтернатив. На каждом шаге работы автомата надо решать следующие вопросы:
• что необходимо выполнять: сдвиг или свертку;
• если выполнять свертку, то какую цепочку у выбрать для поиска правил (цепочка у должна встречаться в правой части правил грамматики);
• какое правило выбрать для свертки, если окажется, что существует несколько правил вида A → γ (несколько правил с одинаковой правой частью).
Для моделирования работы этого расширенного МП-автомата надо на каждом шаге запоминать все предпринятые действия, чтобы иметь возможность вернуться к уже сделанному шагу и выполнить эти же действия по-другому. Этот процесс должен повторяться до тех пор, пока не будут перебраны все возможные варианты.
Распознаватель на основе алгоритма "сдвиг-свертка" является восходящим распознавателем: он читает входную цепочку символов слева направо и строит правосторонний вывод. Название "восходящий" дано ему потому, что дерево вывода в этом случае следует строить снизу вверх, от концевых вершин к корню.
Функционирование обоих рассмотренных распознавателей реализуется достаточно простыми алгоритмами, которые можно найти в [3, 7]. Однако оба они имеют один существенный недостаток – время их функционирования экспоненциально зависит от длины входной цепочки n = |α|, что недопустимо для компиляторов, где длина входных программ составляет от десятков до сотен тысяч символов. Так происходит потому, что оба алгоритма выполняют разбор входной цепочки символов методом простого перебора, подбирая правила грамматики произвольным образом, а в случае неудачи возвращаются к уже прочитанной части входной цепочки и пытаются подобрать другие правила.
Существуют более эффективные табличные распознаватели, построенные на основе алгоритмов Эрли и Кока-Янгера-Касами [1, 3]. Они обеспечивают полиномиальную зависимость времени функционирования от длины входной цепочки (n для произвольного МП-автомата и n для ДМП-автомата). Это самые эффективные из универсальных распознавателей для КС-языков. Но и полиномиальную зависимость времени разбора от длины входной цепочки нельзя признать удовлетворительной.
Лучших универсальных распознавателей не существует. Однако среди всего типа КС-языков существует множество классов и подклассов языков, для которых можно построить распознаватели, имеющие линейную зависимость времени функционирования от длины входной цепочки символов. Такие распознаватели называют линейными распознавателями КС-языков.
В настоящее время известно множество линейных распознавателей и соответствующих им классов КС-языков. Каждый из них имеет свой алгоритм функционирования, но все известные алгоритмы являются модификацией двух базовых алгоритмов – алгоритма с подбором альтернатив и алгоритма "сдвиг-свертка", рассмотренных выше. Модификации заключаются в том, что алгоритмы выполняют подбор правил грамматики для разбора входной цепочки символов не произвольным образом, а руководствуясь установленным порядком, который создается заранее на основе заданной КС-грамматики. Такой подход позволяет избежать возвратов к уже прочитанной части цепочки и существенно сокращает время, требуемое на ее разбор.
Среди всего множества можно выделить следующие наиболее часто используемые распознаватели:
• распознаватели на основе рекурсивного спуска (модификация алгоритма с подбором альтернатив);
• распознаватели на основе LL(1) – и LL(k) – грамматик (модификация алгоритма с подбором альтернатив);
• распознаватели на основе LR(0) – и LR(1) – грамматик (модификация алгоритма "сдвиг-свертка");
• распознаватели на основе SLR(1) – и LALR(1) – грамматик (модификация алгоритма "сдвиг-свертка");
• распознаватели на основе грамматик предшествования (модификация алгоритма "сдвиг-свертка").
Алгоритмы функционирования всех перечисленных и ряда других линейных распознавателей описаны в [1–4, 7].
Построение синтаксического анализатора
Синтаксический анализатор должен распознавать весь текст исходной программы. Поэтому, в отличие от лексического анализатора, ему нет необходимости искать границы распознаваемой строки символов. Он должен воспринимать всю информацию, поступающую ему на вход, и либо подтвердить ее принадлежность входному языку, либо сообщить об ошибке в исходной программе.
Но, как и в случае лексического анализа, задача синтаксического анализа не ограничивается только проверкой принадлежности цепочки заданному языку. Необходимо оформить найденные синтаксические конструкции для дальнейшей генерации текста результирующей программы. Синтаксический анализатор должен иметь некий выходной язык, с помощью которого он передает следующим фазам компиляции информацию о найденных и разобранных синтаксических структурах. В таком случае он уже является не разновидностью МП-автомата, а преобразователем с магазинной памятью – МП-преобразователем [1, 2, 7].
Вопросы, связанные с представлением информации, являющейся результатом работы синтаксического анализатора, и с порождением на основе этой информации текста результирующей программы, рассмотрены в лабораторной работе № 4, поэтому здесь на них останавливаться не будем.
Построение синтаксического анализатора – это более творческий процесс, чем построение лексического анализатора. Этот процесс не всегда может быть полностью формализован.
Имея грамматику входного языка, разработчик синтаксического анализатора должен в первую очередь выполнить ряд формальных преобразований над этой грамматикой, облегчающих построение распознавателя. После этого он должен проверить, относится ли полученная грамматика к одному из известных классов КС-языков, для которых существуют линейные распознаватели. Если такой класс найден, можно строить распознаватель (если найдено несколько классов, следует выбрать тот, для которого построение распознавателя проще либо построенный распознаватель будет обладать лучшими характеристиками). Если же такой класс КС-языков найти не удалось, то разработчик должен попытаться выполнить над грамматикой некоторые преобразования, чтобы привести ее к одному из известных классов. Эти преобразования не могут быть описаны формально, и в каждом конкретном случае разработчик должен попытаться найти их сам (иногда преобразования имеет смысл искать даже в том случае, когда грамматика подпадает под один из известных классов КС-языков, с целью найти другой класс, для которого можно построить лучший по характеристикам распознаватель).
Сложностей с построением синтаксических анализаторов не существовало бы, если бы для КС-грамматик были разрешимы проблемы преобразования и эквивалентности. Но поскольку в общем случае это не так, то одним классом КС-грамматик, для которого существуют линейные распознаватели, ограничиться не удается. По этой причине для всех классов КС-грамматик существует принципиально важное ограничение: в общем случае невозможно преобразовать произвольную КС-грамматику к виду, требуемому данным классом КС-грамматик, либо же доказать, что такого преобразования не существует. То, что проблема неразрешима в общем случае, не говорит о том, что она не решается в каждом конкретном частном случае, и зачастую удается найти такие преобразования. И чем шире набор классов КС-грамматик с линейными распознавателями, тем проще их искать.
Только, когда в результате всех этих действий не удалось найти соответствующий класс КС-языков, разработчик вынужден строить универсальный распознаватель. Характеристики такого распознавателя будут существенно хуже, чем у линейного распознавателя: в лучшем случае удается достичь квадратичной зависимости времени работы распознавателя от длины входной цепочки. Такое бывает редко, поэтому все современные компиляторы построены на основе линейных распознавателей (иначе время их работы было бы недопустимо велико).
Часто одна и та же КС-грамматика может быть отнесена не к одному, а сразу к нескольким классам КС-грамматик, допускающих построение линейных распознавателей. Тогда необходимо решить, какой из нескольких возможных распознавателей выбрать для практической реализации.
Ответить на этот вопрос не всегда легко, поскольку могут быть построены два принципиально разных распознавателя, алгоритмы работы которых несопоставимы. В первую очередь речь идет именно о восходящих и нисходящих распознавателях: в основе первых лежит алгоритм подбора альтернатив, в основе вторых – алгоритм "сдвиг-свертка".
На вопрос о том, какой распознаватель – нисходящий или восходящий – выбрать для построения синтаксического анализатора, нет однозначного ответа. Эту проблему необходимо решать, опираясь на некую дополнительную информацию о том, как будут использованы или каким образом будут обработаны результаты работы распознавателя. Более подробно обсуждение этого вопроса можно найти в [1, 7].
Совет.