 |
Метод и алгоритм синтаксического анализа
|
|
|
|
Синтаксический анализ – это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. В принципе, по любой грамматике можно построить синтаксический анализатор, но грамматики, используемые на практике, имеют специальную форму. Анализаторы реально используемых языков обычно имеют линейную сложность; это достигается, например, за счет просмотра исходной программы слева направо с просмотром вперед на один терминальный символ (лексический класс).
Вход синтаксического анализатора – последовательность лексических и таблицы, например, таблица внешних представлений, которые являются выходом лексического анализатора.
Выход синтаксического анализатора – дерево разбора и таблицы, например, таблица идентификаторов и таблица типов, которые являются входом для следующего просмотра компилятора (например, это может быть просмотр, осуществляющий контроль типов).
В большинстве компиляторов лексический и синтаксический анализаторы – это взаимосвязанные части. Лексический разбор исходного текста в таком варианте выполняется поэтапно так, что синтаксический анализатор, выполнив разбор очередной конструкции языка, обращается к сканеру за следующей лексемой. При этом он может сообщить информацию о том, какую лексему следует ожидать. В процессе разбора может даже происходить «откат назад», чтобы выполнить анализ текста на другой основе. Работу синтаксического и лексического анализаторов можно изобразить в виде схемы, приведенной на рис.1 [3,4].
Рис.1. Взаимодействие лексического анализатора с синтаксическим.
В простейшем случае фазы лексического и синтаксического анализа могут выполняться компилятором последовательно. Но для многих языков программирования информации на этапе лексического анализа может быть недостаточно для однозначного определения типа и границ очередной лексемы. Работа синтаксического и лексического анализаторов в варианте их последовательного взаимодействия изображена в виде схемы на рисунке 2.
|
|
|
Рис. 2. Последовательное взаимодействие лексического и синтаксического анализаторов
При параллельном варианте лексический анализ текста исходной программы выполняется поэтапно по шагам. Структура параллельной реализации взаимодействия лексического и синтаксического анализаторов приведена на рис. 3.
Рис. 3. Параллельное взаимодействие лексического и синтаксического анализаторов
Лексический анализатор выделяет очередную лексему в исходном коде и передает ее синтаксическому анализатору. Синтаксический анализатор может подтвердить правильность найденной лексемы и обратиться к лексическому анализатору за следующей лексемой либо же отвергнуть найденную лексему. Во втором случае он может проинформировать лексический анализатор о том, что надо вернуться назад к уже просмотренному ранее фрагменту исходного кода и сообщить ему дополнительную информацию о том, лексему какого типа следует ожидать. Взаимодействуя между собой таким образом, лексический и синтаксический анализаторы могут перебрать несколько возможных вариантов лексем, и, если ни один из них не подойдет, будет считаться, что исходная программа содержит ошибку. Только после того, как синтаксический анализатор успешно выполнит разбор очередной конструкции исходного языка, лексический анализатор помещает найденные лексемы в таблицу лексем и в таблицу идентификаторов и продолжает разбор дальше в том же порядке.
Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой – восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.
|
|
|
Нисходящие анализаторы строят вывод, начиная от аксиомы грамматики и заканчивая цепочкой терминальных символов. С нисходящими анализаторами связаны так называемые LL-грамматики. Они обладают следующими свойствами [1]:
· Они могут быть проанализированы без возвратов;
· Первая буква L означает, что мы просматриваем входную цепочку слева направо (leftto-right scan);
· Вторая буква L означает, что строится левый вывод цепочки (leftmost derivation).
Популярность нисходящих анализаторов связана с тем, эффективный нисходящий анализатор достаточно легко может быть построен вручную, например, методом рекурсивного спуска. Кроме того, LL-грамматики легко обобщаются: грамматики, не являющиеся LL-грамматиками, обычно могут быть проанализированы методом рекурсивного спуска с возвратами.
Ниже приведен псевдокод реализации алгоритма нисходящего анализа
void S ()
{ Выбираем S-правило S ® X1X2…Xk;
for (i от 1 до k) {
if (Xi — нетерминал)
Вызов процедуры Хi ();
else if (Xi равно текущему входному символу)
Переходим к следующему входному символу; else
/* Обнаружена ошибка */; } }
Восходящие анализаторы могут анализировать большее количество грамматик, чем нисходящие, и поэтому именно для таких методов существуют программы, которые умеют автоматически строить анализаторы. С восходящими анализаторами связаны LR-грамматики. В этом обозначении буква L по-прежнему означает, что входная цепочка просматривается слева направо (left-to-right scan), а буква R означает, что строится правый вывод цепочки (rightmost derivation). С помощью LR-грамматик можно определить большинство использующихся в настоящее время языков программирования.
В процессе разбора восходящего разбора строится дерево разбора входной строки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как «свертку» строки к начальному символу грамматики. На каждом шаге свертки подстрока, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подстрока, то в обратном порядке прослеживается правосторонний вывод.
|
|
|
LR-анализ привлекателен по нескольким причинам:
· LR-анализ - наиболее мощный метод анализа без возвратов типа сдвиг-свертка;
· LR-анализ может быть реализован довольно эффективно;
· практически LR-анализаторы могут быть построены для всех конструкций языков программирования;
· класс грамматик, которые могут быть проанализированы LR-методом, строго включает класс грамматик, которые могут быть анализированы предсказывающими анализаторами (сверху вниз типа LL).
Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицу имен. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы. На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи «описание-использование», в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов [5].
|
|
|
