Книга: Системное программное обеспечение. Лабораторный практикум

Виды распознавателей для КС-языков

Виды распознавателей для КС-языков

Существуют несложные преобразования КС-грамматик, выполнение которых гарантирует, что построенный на основе преобразованной грамматики МП-автомат можно будет промоделировать за конечное время на основе конечных вычислительных ресурсов. Описание сути и алгоритмов этих преобразований можно найти в [1, 3, 7].

Эти преобразования позволяют строить два основных типа простейших распознавателей:

• распознаватель с подбором альтернатив;

• распознаватель на основе алгоритма «сдвиг-свертка».

Работу распознавателя с подбором альтернатив можно неформально описать следующим образом: если на верхушке стека МП-автомата находится нетерминальный символ A, то его можно заменить на цепочку символов а при условии, что в грамматике языка есть правило A ? а, не сдвигая при этом считывающую головку автомата (этот шаг работы называется «подбор альтернативы»); если же на верхушке стека находится терминальный символ a, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется «выброс»). Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида A ? а, тогда функция ?(q,?,A) будет содержать более одного следующего состояния – у МП-автомата будет несколько альтернатив.

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

Распознаватель с подбором альтернатив является нисходящим распознавателем: он читает входную цепочку символов слева направо и строит левосторонний вывод. Название «нисходящий» дано ему потому, что дерево вывода в этом случае следует строить сверху вниз, от корня к концевым вершинам («листьям»).[3]

Работу распознавателя на основе алгоритма «сдвиг-свертка» можно описать так: если на верхушке стека МП-автомата находится цепочка символов у, то ее можно заменить на нетерминальный символ 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].

Оглавление книги