Построение отдельных фаз компиляции (стр. 2 из 4)

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

Экранная форма поиска существующего идентификатора представлена на рис. 1.8.

Рис. 1.8. Экранная форма поиска существующего идентификатора

Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.

Рис. 1.9. Экранная форма поиска несуществующего идентификатора

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

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

2.1. Исходные данные

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

Лексемами данного языка являются:

- ключевыеслова (prog, end., begin, end, while ,do, if, then, else);

- скобки ( «(», «)» );

- оператор присваивания ( := );

- операторы сравнения ( >, <, = );

- разделитель ( ; );

- арифметические операции ( +, –, ++);

- шестнадцатеричные константы (тип данных word);

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

- логические операции (or, not, and).

Кроме перечисленных лексем распознаватель должен определять и исключать из входного текста комментарии (неограниченной длины). Комментарии заключаются в фигурные скобки со звездочкой {*…*}.

2.2. Принцип работы лексического анализатора

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

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

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

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

Любой КА может быть задан с помощью пяти параметров:

М(Q, V,δ,q₀,F), (2.1)

где: Q – конечное множество состояний автомата;

V– конечное множество допустимых входных символов (алфавит автомата);

δ – функция переходов, отображающая декартовое произведение множеств V´Q во множество подмножеств Q:R(Q);

q₀

Q – начальное состояние автомата;

Q – непустое множество конечных состояний автомата.

Работа автомата выполняется по тактам. На каждом очередном тактеi автомат, находясь в некотором состоянии q_iÎQ, считывает очередной символ vÎV из входной цепочки символов и изменяет свое состояние на q_i₊₁=d(q_i,w), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед первым тактом автомат находится в начальном состоянии q₀.

Графически автомат отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы из одного состояния в другое, а пометки дуг соответствуют функции перехода. Если функция перехода предусматривает переход из состояния q_iв q_i₊₁ по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q_i в q_i₊₁.

2.3. Схема распознавателя

Распознавателем лексем входного языка является конечный детерминированный автомат без внешней памяти (приложение Б).

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

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

- ┴ – пробел, табуляция, перевод строки, +, –, =, <, >, (, ), ;, :, {

- ┴c – перевод строки

- x0 – любой символ

- x1 – любой символ, кроме символа *

- x2 – любой символ, кроме символа }

- x3 – любой символ, кроме символа ┴

- x4 – любой символ, кроме символа h

- x5 – любой символ, кроме символов 0..9, A..F

- x6 – любой символ, кроме символа =

- x7 – любой символ, кроме символа +

- x8 – символы A..Z, c, f..h, j..m, q..s, u, v, x..z, _

- x9 –символы A..Z, a..d, f..z, _

- x10 – любой символ, кроме символов A..Z, a..z, _

- x11 – символыA..Z, a..f, h..z, _

- x12 – символыA..Z, a..h, j..z, _

- x13 – символыA..Z, a..g, i..z, _

- x14 – символыA..Z, a..z, _

- x15 – символыA..Z, a..k, m..z, _

- x16 – символыA..Z, a..m, o..z, _

- x17 – символыA..Z, a..e, g..z, _

- x18 –символыA..Z, a..q, s..z, _

- x19 – символыA..Z, a..n, p..z, _

- x20 – символыA..Z, a..s, u..z, _

- x21 – символыA..Z, a..c, e..z, _

- x22 – символыA..Z, a..k, m,o..z, _

- x23 – символыA..Z, a..r, t..z, _

- x24 – любой символ, кроме символов A..Z, a..z, _, ┴

- x25 – символыA..F, 0..9

- x26 – любой символ, кроме символов A..Z, a..z, _, ┴, '.'

Регулярная грамматика входного языка в форме Бэкуса-Наура имеет вид:

G ( {0..9, A..Z, a..z, +, – , <, >, =, (, ), ;, :, {, }, *, '.'}, {S, H, BEGIN1, BEGIN2, BEGIN3, BEGIN4, BEGIN5, WHILE1, WHILE2, WHILE3, WHILE4, WHILE5, THEN1, THEN2, THEN3, THEN4, IF1, IF2, PROG1, PROG2, PROG3, PROG4, VAR, NOT1, NOT2, NOT3, AND1, AND2, AND3, OR1, OR2, DO1, DO2, E1, END2, END3, END4, ELSE2, ELSE3, ELSE4}, P, S )

PROG1 ®pPROG2 ®PROG1 r

PROG3 ®PROG2 o PROG4 ®PROG3 g

BEGIN1 ®b BEGIN2 ®BEGIN1 e

BEGIN3 ®BEGIN2 g BEGIN4 ®BEGIN3 i

BEGIN5 ®BEGIN4 n WHILE1 ®w

WHILE2 ®WHILE1 h WHILE3 ®WHILE2 i

WHILE4 ®WHILE3 l WHILE5 ®WHILE4 e

DO1 ®d DO2 ®DO1 o

IF1 ®i IF2 ®IF1 f

THEN1 ®t THEN2 ®THEN1 h

THEN3 ®THEN2 e THEN4 ®THEN3 n

E1 ®e ELSE2 ®E1 l

ELSE3 ®ELSE2 s ELSE4 ®ELSE3 e

END2 ®E1 n END3 ®END2 d

END4 ®END3 .AND1 ®a

AND2 ®AND1 n AND3 ®AND2 d

OR1 ®o OR2 ®OR1 r

CONST1 ® 0 CONST2 ®CONST1 x25

CONST3 ®CONST2 x25 CONST4 ®CONST3 x25

CONST5 ®CONST4 x25 CONST6 ®CONST5 h

ASSI1 ® : ASSI2 ®ASSI1 =

SEMI® ; SUB® –

ADD® + INC®ADD +

OPEN® ( CLOSE® )

RAVN® = MEN® <

BOL® >

COMM1 ® {

COMM2 ®COMM1 * | COMM2 x1

COMM3 ®COMM2 *

COMM4 ®COMM3 }