Назначение синтаксического анализатора

По иерархии грамматик Хомского выделяют четыре основные группы языков (и описывающих их грамматик) [1, 3, 4, 7]. При этом наибольший интерес представляют регулярные и контекстно-свободные (КС) грамматики и языки. Они используются при описании синтаксиса языков программирования. С помощью регулярных грамматик можно описать лексемы языка – идентификаторы, константы, служебные слова и прочие. На основе КС-грамматик строятся более крупные синтаксические конструкции: описания типов и переменных, арифметические и логические выражения, управляющие операторы и, наконец, полностью вся программа на входном языке.

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

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

• найти и выделить синтаксические конструкции в тексте исходной программы;

• установить тип и проверить правильность каждой синтаксической конструкции;

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

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

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

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

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

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

 

Проблема распознавания цепочек КС-языков

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

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

МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход МП-автомата из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.

При выполнении перехода МП-автомата из одной конфигурации в другую из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и тем самым он будет входным символом при следующем переходе). Эти переходы называются ^-переходами. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка считается принятой (после окончания цепочки могут быть сделаны Х-переходы). Иначе цепочка символов не принимается.

МП-автомат называется недетерминированным, если при одной и той же его конфигурации возможен более чем один переход. В противном случае (если из любой конфигурации МП-автомата по любому входному символу возможно не более одного перехода в следующую конфигурацию) МП-автомат считается детерминированным (ДМП-автоматом). ДМП-автоматы задают класс детерминированных КС-языков, для которых существуют однозначные КС-грамматики. Именно этот класс языков лежит в основе синтаксических конструкций всех языков программирования, так как любая синтаксическая конструкция языка программирования должна допускать только однозначную трактовку [1–4, 7].

По произвольной КС-грамматике

всегда можно построить недетерминированный МП-автомат, который допускает цепочки языка, заданного этой грамматикой [1–3, 7]. А на основе этого МП-автомата можно создать распознаватель для заданного языка.

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

Поэтому для построения распознавателя для языка, заданного КС-грамматикой, рекомендуется воспользоваться соответствующим математическим аппаратом и одним из существующих алгоритмов.

 

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

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

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

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

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

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

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

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

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

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

• что необходимо выполнять: сдвиг или свертку;

• если выполнять свертку, то какую цепочку у выбрать для поиска правил (цепочка у должна встречаться в правой части правил грамматики);

• какое правило выбрать для свертки, если окажется, что существует несколько правил вида A → γ (несколько правил с одинаковой правой частью).

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

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

Функционирование обоих рассмотренных распознавателей реализуется достаточно простыми алгоритмами, которые можно найти в [3, 7]. Однако оба они имеют один существенный недостаток – время их функционирования экспоненциально зависит от длины входной цепочки n = |α|, что недопустимо для компиляторов, где длина входных программ составляет от десятков до сотен тысяч символов. Так происходит потому, что оба алгоритма выполняют разбор входной цепочки символов методом простого перебора, подбирая правила грамматики произвольным образом, а в случае неудачи возвращаются к уже прочитанной части входной цепочки и пытаются подобрать другие правила.

Существуют более эффективные табличные распознаватели, построенные на основе алгоритмов Эрли и Кока—Янгера—Касами [1, 3]. Они обеспечивают полиномиальную зависимость времени функционирования от длины входной цепочки (n3 для произвольного МП-автомата и n2 для ДМП-автомата). Это самые эффективные из универсальных распознавателей для КС-языков. Но и полиномиальную зависимость времени разбора от длины входной цепочки нельзя признать удовлетворительной.

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

В настоящее время известно множество линейных распознавателей и соответствующих им классов КС-языков. Каждый из них имеет свой алгоритм функционирования, но все известные алгоритмы являются модификацией двух базовых алгоритмов – алгоритма с подбором альтернатив и алгоритма «сдвиг-свертка», рассмотренных выше. Модификации заключаются в том, что алгоритмы выполняют подбор правил грамматики для разбора входной цепочки символов не произвольным образом, а руководствуясь установленным порядком, который создается заранее на основе заданной КС-грамматики. Такой подход позволяет избежать возвратов к уже прочитанной части цепочки и существенно сокращает время, требуемое на ее разбор.

Среди всего множества можно выделить следующие наиболее часто используемые распознаватели:

• распознаватели на основе рекурсивного спуска (модификация алгоритма с подбором альтернатив);

• распознаватели на основе LL(1) – и LL(k) – грамматик (модификация алгоритма с подбором альтернатив);

• распознаватели на основе LR(0) – и LR(1) – грамматик (модификация алгоритма «сдвиг-свертка»);

• распознаватели на основе SLR(1) – и LALR(1) – грамматик (модификация алгоритма «сдвиг-свертка»);

• распознаватели на основе грамматик предшествования (модификация алгоритма «сдвиг-свертка»).

Алгоритмы функционирования всех перечисленных и ряда других линейных распознавателей описаны в [1–4, 7].

 

Построение синтаксического анализатора

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

Но, как и в случае лексического анализа, задача синтаксического анализа не ограничивается только проверкой принадлежности цепочки заданному языку. Необходимо оформить найденные синтаксические конструкции для дальнейшей генерации текста результирующей программы. Синтаксический анализатор должен иметь некий выходной язык, с помощью которого он передает следующим фазам компиляции информацию о найденных и разобранных синтаксических структурах. В таком случае он уже является не разновидностью МП-автомата, а преобразователем с магазинной памятью – МП-преобразователем [1, 2, 7].

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

Построение синтаксического анализатора – это более творческий процесс, чем построение лексического анализатора. Этот процесс не всегда может быть полностью формализован.

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

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

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

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

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

На вопрос о том, какой распознаватель – нисходящий или восходящий – выбрать для построения синтаксического анализатора, нет однозначного ответа. Эту проблему необходимо решать, опираясь на некую дополнительную информацию о том, как будут использованы или каким образом будут обработаны результаты работы распознавателя. Более подробно обсуждение этого вопроса можно найти в [1, 7].

Совет.

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

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

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

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

1. Выполнить простейшие преобразования над заданной КС-грамматикой.

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

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

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

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

6. Определить, в какой форме синтаксический распознаватель будет передавать результаты своей работы другим фазам компилятора (эта форма называется внутренним представлением программы в компиляторе).

Реализовать выбранный в п. 3 или 5 алгоритм с учетом структур данных, соответствующих п. 6.

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

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

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

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

В качестве основного пути выполнения лабораторной работы автор предлагает распознаватель на основе грамматик операторного предшествования, поэтому именно этот класс КС-грамматик далее рассмотрен более подробно (описания остальных известных классов и подклассов КС-грамматик можно найти в [1–3, 7]).

 

Грамматики предшествования

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

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

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

Отношения предшествования будем обозначать знаками «=.», «<.» и «.>». Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования – это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций (хотя по внешнему виду они очень похожи) – они не обладают ни свойством коммутативности, ни свойством ассоциативности. Например, если известно, что Вi.> Вj, то не обязательно выполняется Вj <. Вi (поэтому знаки предшествования помечают специальной точкой: «=.», «<.», «.>»).

Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:

• Вi <. Bi+1, если символ Bi+1 – крайний левый символ некоторой основы (это отношение между символами можно назвать «предшествует основе» или просто «предшествует»);

• Вi.> Bi+1, если символ Вi – крайний правый символ некоторой основы (это отношение между символами можно назвать «следует за основой» или просто «следует»);

• Вi =. Вi+1, если символы Вi и Вi+1 принадлежат одной основе (это отношение между символами можно назвать «составляют основу»).

Исходя из этих соотношений выполняется разбор входной строки для грамматик предшествования.

Суть принципа такого разбора поясняет рис. 3.1. На нем изображена входная цепочка символов αγβδ в тот момент, когда выполняется свертка цепочки γ. Символ α является последним символом подцепочки α, а символ b – первым символом подцепочки β. Тогда, если в грамматике удастся установить непротиворечивые отношения предшествования, то в процессе выполнения разбора по алгоритму «сдвиг-свертка» можно всегда выполнять сдвиг до тех пор, пока между символом на верхушке стека и текущим символом входной цепочки существует отношение <. или =.. А как только между этими символами будет обнаружено отношение.>, сразу надо выполнять свертку. Причем для выполнения свертки из стека надо выбирать все символы, связанные отношением =. Все различные правила в грамматике предшествования должны иметь различные правые части – это гарантирует непротиворечивость выбора правила при выполнении свертки.

Рис. 3.1. Отношения между символами входной цепочки в грамматике предшествования.

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

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

Существует несколько видов грамматик предшествования. Они различаются по тому, какие отношения предшествования в них определены и между какими типами символов (терминальными или нетерминальными) могут быть установлены эти отношения. Кроме того, возможны незначительные модификации функционирования самого алгоритма «сдвиг-свертка» в распознавателях для таких грамматик (в основном на этапе выбора правила для выполнения свертки, когда возможны неоднозначности) [1]Молчанов А. Ю. Системное программное обеспечение: Учебник для вузов. – СПб.: Питер, 2003. – 396 с.
.

Выделяют следующие виды грамматик предшествования:

• простого предшествования;

• расширенного предшествования;

• слабого предшествования;

• смешанной стратегии предшествования;

• операторного предшествования.

Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для грамматик операторного предшествования.

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

Если имеется КС-грамматика

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

– множество крайних левых символов относительно нетерминального символа U;

– множество крайних правых символов относительно нетерминального символа U,

где U – заданный нетерминальный символ

T – любой символ грамматики

а z – произвольная цепочка символов (

цепочка z может быть и пустой цепочкой).

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

– множество крайних левых терминальных символов относительно нетерминального символа U;

– множество крайних правых терминальных символов относительно нетерминального символа U,

где t – терминальный символ

U и С – нетерминальные символы (U,

а z – произвольная цепочка символов (

цепочка z может быть и пустой цепочкой).

Множества L(U) и R(U) могут быть построены для каждого нетерминального символа

по очень простому алгоритму:

1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части. Во множество L(U) включаем самый левый символ из правой части правил, а во множество R(U) – самый правый символ из правой части (то есть во множество L(U) записываем все символы, с которых начинаются правила для символа U, а во множество R(U) – символы, которыми эти правила заканчиваются). Если в правой части правила для символа U имеется только один символ, то он должен быть записан в оба множества – L(U) и R(U).

2. Для каждого нетерминального символа U выполняем следующее преобразование: если множество L(U) содержит нетерминальные символы грамматики [U', U', …, то его надо дополнить символами, входящими в соответствующие множества L(U'), L(U')… и не входящими в L(U). Ту же операцию надо выполнить для R(U). Фактически, если какой-то символ U' входит в одно из множеств для символа U, то надо объединить множества для U' и U, а результат записать во множество для символа U.

3. Если на предыдущем шаге хотя бы одно множество L(U) или R(U) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе – построение закончено.

Для нахождения множеств Lt(U) и Rt(U) используется следующий алгоритм:

1. Для каждого нетерминального символа грамматики U строятся множества L(U) и R(U).

2. Для каждого нетерминального символа грамматики U ищутся правила вида U → tz и U → Ctz, где

терминальные символы t включаются во множество Lt(U). Аналогично для множества Rt(U) ищутся правила вида U → zt и U → ztC (то есть во множество Lt(U) записываются все крайние слева терминальные символы из правых частей правил для символа U, а во множество Rt(U) – все крайние справа терминальные символы этих правил). Не исключено, что один и тот же терминальный символ будет записан в оба множества – Lt(U) и Rt(U).

3. Просматривается множество L(U), в которое входят символы U', U' … Множество Lt(U) дополняется терминальными символами, входящими в Lt(U'), Lt(U')… и не входящими в Lt(U). Аналогичная операция выполняется и для множества Rt(U) на основе множества R(U).

Для практического использования матрицу предшествования дополняют терминальными символами

и

(начало и конец цепочки). Для них определены следующие отношения предшествования:

Имея построенные множества Lt(U) и Rt(U), заполнение матрицы операторного предшествования для КС-грамматики G(VT,VN,P,S) можно выполнить по следующему алгоритму:

1. Берем первый символ из множества терминальных символов грамматики VT:

Будем считать этот символ текущим терминальным символом.

2. Во всем множестве правил Р ищем правила вида C → xaiby или C → xaiUbjy, где аi – текущий терминальный символ, Ьj – произвольный терминальный символ

U и С – произвольные нетерминальные символы

а х и у – произвольные цепочки символов, возможно пустые

Фактически производится поиск таких правил, в которых в правой части символы аi и Ъj стоят рядом или же между ними есть не более одного нетерминального символа (причем символ аi обязательно стоит слева от Ьj).

3. Для всех символов Ьj, найденных на шаге 2, выполняем следующее: ставим знак «=.» («составляет основу») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом аi, и столбца, помеченного символом bj.

4. Во всем множестве правил Р ищем правила вида С → xaiUjy, где аi – текущий терминальный символ, Uj и С– произвольные нетерминальные символы (Uj,

а х и у – произвольные цепочки символов, возможно пустые

Фактически ищем правила, в которых в правой части символ аi стоит слева от нетерминального символа Uj.

5. Для всех символов Uj, найденных на шаге 4, берем множество символов Lt(Uj). Для всех терминальных символов ck, входящих в это множество, выполняем следующее: ставим знак «<.» («предшествует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом ai, и столбца, помеченного символом сk.

6. Во всем множестве правил Р ищем правила вида С → xUjaiy, где ai – текущий терминальный символ, Uj и С – произвольные нетерминальные символы

а x и y – произвольные цепочки символов, возможно пустые

Фактически ищем правила, в которых в правой части символ а стоит справа от нетерминального символа Uj.

7. Для всех символов Uj, найденных на шаге 6, берем множество символов Rt(Uj). Для всех терминальных символов ck, входящих в это множество, выполняем следующее: ставим знак «.>» («следует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом сk, и столбца, помеченного символом аi.

8. Если рассмотрены все терминальные символы из множества VT, то переходим к шагу 9, иначе – берем очередной символ

из множества VT, i:= i + 1, делаем его текущим терминальным символом и возвращаемся к шагу 2.

9. Берем множество Lt(S) для целевого символа грамматики S. Для всех терминальных символов ck, входящих в это множество, выполняем следующее: ставим знак «<.» («предшествует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом

(«начало строки»), и столбца, помеченного символом ck.

10. Берем множество Rt(S) для целевого символа грамматики S. Для всех терминальных символов ck, входящих в это множество, выполняем следующее: ставим знак «.>» («следует») в клетки матрицы операторного предшествования на пересечении строки, помеченной символом ck, и столбца, помеченного символом

(«конец строки»). Построение матрицы закончено.

Если на всех шагах алгоритма построения матрицы операторного предшествования не возникло противоречий, когда в одну и ту же клетку матрицы надо записать два или три различных символа предшествования, то матрица построена правильно (в каждой клетке такой матрицы присутствует один из символов предшествования – «=.», «<.» или «.>» – или же клетка пуста). Если на каком-то шаге возникло противоречие, значит, исходная КС-грамматика G(VT,VN,P,S) не является грамматикой операторного предшествования. В этом случае можно попробовать преобразовать грамматику так, что она станет удовлетворять требованиям операторного предшествования (что не всегда возможно), либо необходимо использовать другой тип распознавателя.

Более подробно работа с грамматиками предшествования и другими типами распознавателей описана в [1–4, 7].

 

Алгоритм «сдвиг-свертка» для грамматик операторного предшествования

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования выполняется МП-автоматом с одним состоянием. Для моделирования его работы необходима входная цепочка символов и стек символов, в котором автомат может обращаться не только к самому верхнему символу, но и к некоторой цепочке символов на вершине стека.

Этот алгоритм для заданной КС-грамматики G(VT,VN,P,S) при наличии построенной матрицы предшествования можно описать следующим образом:

1. Поместить в верхушку стека символ «начало строки», считывающую головку МП-автомата поместить в начало входной цепочки (текущим входным символом становится первый символ входной цепочки). В конец входной цепочки надо дописать символ «конец строки».

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

3. Если символ sj – это символ начала строки, а символ ai – символ конца строки, то алгоритм завершен, входная цепочка символов разобрана.

4. В матрице предшествования ищется клетка на пересечении строки, помеченной символом sj, и столбца, помеченного символом ai (выполняется сравнение текущего входного символа и терминального символа на верхушке стека).

5. Если клетка, найденная на шаге 3, пустая, то значит, входная строка символов не принимается МП-автоматом, алгоритм прерывается и выдает сообщение об ошибке.

6. Если клетка, найденная на шаге 3, содержит символ «=.» («составляет основу») или «<.» («предшествует»), то необходимо выполнить перенос (сдвиг). При выполнении переноса текущий входной символ ai помещается на верхушку стека, считывающая головка МП-автомата во входной цепочке символов сдвигается на одну позицию вправо (после чего текущим входным символом становится следующий символ ai+1, i:= i+ 1). После этого надо вернуться к шагу 2.

7. Если клетка, найденная на шаге 3, содержит символ «.>» («следует»), то необходимо произвести свертку. Для выполнения свертки из стека выбираются все терминальные символы, связанные отношением «=.» («составляет основу»), начиная от вершины стека, а также все нетерминальные символы, лежащие в стеке рядом с ними. Эти символы вынимаются из стека и собираются в цепочку γ (если в стеке нет символов, связанных отношением «=.», то из него вынимается один самый верхний терминальный символ и лежащие рядом с ним нетерминальные символы).

8. Во всем множестве правил Р грамматики G(VT,VN,P,S) ищется правило, у которого правая часть совпадает с цепочкой γ (по условиям грамматик предшествования все правые части правил должны быть различны, поэтому может быть найдено или одно такое правило, или ни одного). Если правило найдено, то в стек помещается нетерминальный символ из левой части правила, иначе, если правило не найдено, это значит, что входная строка символов не принимается МП-автоматом, алгоритм прерывается и выдает сообщение об ошибке. Следует отметить, что при выполнении свертки считывающая головка автомата не сдвигается и текущий входной символ ai остается неизменным. После выполнения свертки необходимо вернуться к шагу 2.

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

Выполнение алгоритма может быть прервано, если на одном из его шагов возникнет ошибка. Тогда входная цепочка не принимается.

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Это преобразование заключается в том, что все нетерминальные символы в правилах грамматики заменяются на один нетерминальный символ (чаще всего – целевой символ грамматики).

Построенная в результате такого преобразования грамматика называется остовной грамматикой, а само преобразование – остовным преобразованием [1, 7].

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

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

В общем виде последовательность построения распознавателя для КС-грамматики операторного предшествования G(VT,VN,P,S) можно описать следующим образом:

1. На основе множества правил грамматики Р построить множества крайних левых и крайних правых символов для всех нетерминальных символов грамматики

2. На основе множества правил грамматики Р и построенных на шаге 1 множеств L(U) и R(U) построить множества крайних левых и крайних правых терминальных символов для всех нетерминальных символов грамматики

: Lt(U) и Rt(U).

3. На основе построенных на шаге 2 множеств Lt(U) и Rt(U) для всех терминальных символов грамматики

заполняется матрица операторного предшествования.

4. Исходная грамматика G(VT,VN,P,S) преобразуется в остовную грамматику G'(VT,{S},P,S) с одним нетерминальным символом.

5. На основе построенной матрицы предшествования и остовной грамматики строится распознаватель на базе алгоритма «сдвиг-свертка» для грамматик операторного предшествования.

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

Далее в примере выполнения работы проиллюстрирован именно такой подход к построению распознавателя.

 

Порядок выполнения работы

Для выполнения лабораторной работы требуется написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Синтаксис входного языка и перечень допустимых лексем указаны в задании. Допускается исходить из условия, что текст содержит не более одного предложения входного языка.

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

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

Для выполнения лексического анализа рекомендуется использовать программные модули, созданные в результате выполнения лабораторной работы № 2.

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

1. Получить вариант задания у преподавателя.

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

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

4. Подготовить и защитить отчет.

5. Написать и отладить программу на ЭВМ.

6. Сдать работающую программу преподавателю.

 

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

• Задание по лабораторной работе.

• Краткое изложение цели работы.

• Запись заданной грамматики входного языка в форме Бэкуса—Наура (если для построения синтаксического распознавателя используется механизм, требующий преобразования исходной грамматики входного языка, то эти преобразования и полученная в результате их грамматика должны быть отражены в отчете).

• Множества крайних правых и крайних левых символов с указанием шагов построения.

• Множества крайних правых и крайних левых терминальных символов.

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

• Пример выполнения разбора простейшего предложения входного языка.

• Текст программы (оформляется после выполнения программы на ЭВМ).

 

Основные контрольные вопросы

• Какую роль выполняет синтаксический анализ в процессе компиляции?

• Какие проблемы возникают при построении синтаксического анализатора и как они могут быть решены?

• Какие типы грамматик существуют? Что такое КС-грамматики? Расскажите об их использовании в компиляторе.

• Какие типы распознавателей для КС-грамматик существуют? Расскажите о недостатках и преимуществах различных типов распознавателей.

• Поясните правила построения дерева вывода грамматики.

• Что такое грамматики простого предшествования?

• Как вычисляются отношения предшествования для грамматик простого предшествования?

• Что такое грамматика операторного предшествования?

• Как вычисляются отношения для грамматик операторного предшествования?

• Расскажите о задаче разбора. Что такое распознаватель языка?

• Расскажите об общих принципах работы распознавателя языка.

• Что такое перенос, свертка? Для чего необходим алгоритм «перенос-свертка»?

• Расскажите, как работает алгоритм «перенос-свертка» в общем случае (с возвратами).

• Как работает алгоритм «перенос-свертка» без возвратов (объясните на своем примере)?

 

Варианты исходных грамматик

Далее приведены варианты грамматик. Во всех вариантах символ S является начальным символом грамматики; S, F, T и Е обозначают нетерминальные символы.

Терминальные символы выделены жирным шрифтом. Вместо символа а должны подставляться лексемы.

1. S → a:= F;

F → F+T |Т

Т → Т·Е | TIE | Е

Е → (F) | – (F) | а

2. S → a:= F;

F → F or Т | F хог T | T

T → Т and E | Е

Е → (F) | not (F) | a

3. S → F;

F → if E then T else F| if E then F| a:= a

T → if E then T else T | a:= a

E → aa | a=a

4. S → F;

F → for (T) do F | a:= a

T → F;E;F |;E;F | F;E; |;E;

E → aa I a=a