Теоретическая часть. Работа любого компилятора складывается из двух основных этапов: анализа и синтеза

Работа любого компилятора складывается из двух основных этапов: анализа и синтеза. Этап анализа разбивается на две части: 1) лексический анализ исходного текста программы и 2) синтаксический анализ. Первый из них выполняется лексическим анализатором (ЛА) или сканером, а второй - синтаксическим анализатором (СА). Сканер читает символы исходной программы, выделяет из них лексемы, распознает их тип и формирует внутренний код каждой лексемы. На этапе синтаксического анализа коды лексем выступают в качестве терминальных символов.

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

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

v идентификаторы;

v служебные слова;

v целые и вещественные константы;

v строки;

v операции;

v разделители.

Идентификаторы (имена)

Наиболее часто они описываются регулярным выражением вида <буква>{<буква>|<цифра>}[1]. Здесь <буква>::=a|b|c|…|z, <цифра>::=0|1|…|9. Возможен и другой синтаксис. Например, в некоторых языках допускается использовать в идентификаторах символ “_”(подчёркивание). Идентификатор может заканчиваться символами % или $.

Служебные слова

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

Целые константы

Обычно они описываются регулярным выражением вида <цифра>{цифра}. При сканировании целых чисел одновременно может выполнятся вычисление их значения, т. е. преобразование во внутреннюю (машинную) форму представления.

Вещественные константы

Используются различные способы записи вещественных констант:

- с десятичной точкой: <цифра>{цифра}.{цифра} или.<цифра>{<цифра>};

- с порядком: <цифра>{<цифра>}.{цифра}Е[+|-]<цифра>{<цифра>}.

Строки

Последовательность символов, заключённая в апострофы или кавычки, называется строкой. Если в строке содержится апостроф иди кавычка, то они повторяются дважды, например, ‘U’ | ‘pas’’cal’ | “kurs”.

Операции

Они могут быть одно-, двух- или многосимвольными, например, - | + | * | / |** | >= |:= |.AND.

Разделители

К ним относятся специальные символы, разделяющие конструкции языка, например:; |, |. | (|) | комментарий | пробелы | символы табуляции и перехода на новую строку. Они могут либо возвращаться в синтаксический анализатор в качестве лексем, либо только указывать на окончание предыдущей лексемы и пропускаться при вводе следующей. Некоторые из этих символов одновременно могут играть роль терминальных символов в грамматическом описании отдельных конструкций языка.

Обобщенный алгоритм работы сканера может быть описан следующей блок-схемой:

	D

		Нет

B

		Обработка текущей лексемы

	Формирование сообще- ния об ошибке

В ходе лексического анализа решаются две основные задачи:

1. Разбор входной строки символов (т. е. исходной программы) на лексические единицы (лексемы);

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

Входная строка разделяется на лексические единицы символами-разделителями. Лексическая обработка представляет собой циклическую процедуру, в начале которой символы исходной программы последовательно читаются, проверяются на корректность и принадлежность к одному из разделителей. Если выясняется, что прочитаны все символы программы, то на этом работа сканера завершается. Стоящие подряд символы, не являющиеся разделителями, объединяются в лексему. Затем осуществляется анализ выделенной лексемы с целью определения ее типа. Если лексема удовлетворяет лексическим правилам, описывающим один из заданных типов лексических единиц, то выполняется обработка полученной лексемы. Она состоит из двух шагов:

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

2). Вне зависимости от того, была ли создана новая запись в таблице лексем, формируется код лексемы, который записывается в выходную таблицу кодов лексем сканера. Далее цикл работы ЛА повторяется.

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

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

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