Разработка программы-компилятора (стр. 2 из 9)

2.2 Разработка автоматных грамматик для распознавания лексем

Автоматными или регулярными грамматиками называются грамматики, продукции которых имеют одну из двух форм:

Праволинейная	Леволинейная
A→aB	A→Ba
A→a	A→a

где a Î Т; А, В Î N

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

Грамматика для идентификаторов:

<имя>→<буква>{<буква>|<цифра>’_’}

<буква>→ (’a’. ’z’)

<цифра>→ (‘0’. ’9’)

Грамматика для констант:

<константа>→<16-рич. константа>|<римск. константа>

Для 16-ричных констант:

<16-рич. константа>→ (‘$+’,’$-‘) (<цифра>, ‘A’. ’F’) { (<цифра>,‘A’. ’F’) }

Для римских констант:

2.3 Разработка автоматов, работающих по правилам грамматики

2.3.1 Автомат для распознавания имён

рис.1. Автомат для распознавания имён

Состояния автомата:

S - начальное состояние;

1 - промежуточное состояние, соответствующее продолжению формирования имени;

2 - конечное состояние, соответствующее выделению правильного идентификатора;

3 - конечное состояние, соответствующее ошибке при выделении идентификатора.

2.3.2 Автомат для распознавания 16-ричных констант

рис.3. Автомат для распознавания 16-ричных констант

Состояния автомата:

S - начальное состояние;

1 - промежуточное состояние, обозначающее, что распознан символ начала константы ‘$’;

2 - промежуточное состояние, обозначающее, что распознан знак константы, и продолжение формирования константы;

3 - конечное состояние, соответствующее выделению правильной 16-ричной константы;

4 - конечное состояние, соответствующее ошибке при выделении 16-ричной константы.

2.3.3 Автомат для распознавания римских констант

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

Римская система нумерации состоит из семи знаков: I - 1, V - 5, X - 10, C - 100, D - 500, M - 1000. В данной работе используются только три первых знака, т.е. автомат может распознавать числа от 1 (I) до 39 (XXXIX).

Если меньший знак пишется после большего, то его прибавляют к большему числу; если же перед большим - вычитают. Вычитать можно только числа, начинающиеся с 1, в данном случае - 1, т.к не имеет смысла вычитать, например, 5 из 5 (в результате 0) или из 10 (в результате 5).

Знаки, эквивалентные числам, начинающимся с 1 (1, 10, 100, 1000), могут использоваться от одного до 3 раз. Знаки, эквивалентные числам, начинающимся с 5 (5, 50, 500) могут использоваться только 1 раз. Таким образом, чтобы образовать число 4, нужно из 5 вычесть 1 (IV), а чтобы образовать число 6, нужно прибавить 1 к 5 (VI).

В соответствии с приведёнными правилами, сформируем ряд ограничений для автомата-распознавателя:

Символ X может встречаться в начале строки от 1 до 3 раз подряд (см. правило 3).

Символ V может встречаться не более 1 раза в начале строки и после 1 или более символов X (см. правило 3).

Символ I может встречаться от 1 до 3 раз подряд в начале строки, а также в конце правильной строки, образованной символами X и V (см. ограничения 1 и 2, правило 3).

Символ X может встречаться в конце строки 1 раз после символа I, если перед последним находятся только символы X или ничего (иначе будет нарушено правило 2 - неизвестно, к какому символу будет относиться символ I).

Символ V может встречаться в конце строки 1 раз после символа I, если перед последним находятся только символы X (аналогично ограничению 4).

рис.4. Автомат для распознавания римских констант

Состояния автомата:

S - начальное состояние;

Sg - промежуточное состояние, соответствующее распознаванию знака константы.

1 - промежуточное состояние, соответствующее распознаванию символа X.

2 - промежуточное состояние, соответствующее распознаванию символа V.

3 - промежуточное состояние, соответствующее распознаванию символа I.

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

5 - промежуточное состояние, соответствующее распознаванию строки XX.

6 - промежуточное состояние, соответствующее распознаванию строки XXX.

7 - промежуточное состояние, соответствующее распознаванию символа I после V, XV, XXV или XXXV.

8 - промежуточное состояние, соответствующее распознаванию символа X после I, XI, XXI или XXXI.

9 - промежуточное состояние, соответствующее распознаванию символа V после I, XI, XXI или XXXI.

10 - промежуточное состояние, соответствующее распознаванию символа I после правильной строки, заканчивающейся на I.

11 - промежуточное состояние, соответствующее распознаванию символа I после правильной строки, заканчивающейся на II.

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

2.3.4 Объединённый автомат

Объединённый автомат является соединением приведённых выше автоматов при общем начальном состоянии S. Все состояния и входные сигналы останутся теми же.

2.4 Разработка алгоритма и программы лексического анализа

Непосредственно лексический анализ представляет собой 2 этапа: выделение лексем и их распознавание. На экран выводятся таблицы констант, идентификаторов, терминальных символов и кодов лексем. Все таблицы сохраняются в файлы на диске.

После завершения лексического анализа становится возможным выполнить синтаксический анализ.

2.4.1 Выделение лексем

Процесс выделения лексем состоит в просмотре входной строки по одному символу и в случае обнаружения символа-разделителя формирование лексемы. Символами разделителями являются как сами разделители (терминальные символы) так и знаки операций. В программе предусмотрены двойные знаки операций (‘: =’).

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

Такая последовательность действий повторяется до окончания входной строки. Процесс выделения лексем реализован в функции Select_Lex, которая возвращает строки, содержащие выделенные лексемы.

2.4.2 Распознавание лексем

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

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

константа, определяющая начальное состояние (обычно 0);

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

множество состояний, свидетельствующих об ошибке в лексеме;

Распознавателем идентификаторов является функция Ident, 16-ричных констант - функция FConst, римских констант - функция Rome. Все они возвращают значение 1, если лексема распознана и - 1 в противном случае. Распознавателем терминальных символов является функция Termin. Она возвращает значение 3, если лексема - ключевое слово, 1 - если разделитель, 2 - если знак операции. Если лексема не является терминальным символом, то функция возвращает значение - 1. Если лексема ошибочна, то она заносится в таблицу кодов лексем с типом E и выдаётся сообщение об ошибке (процедура Err_Lex). Все эти подпрограммы вызываются из процедуры TForm1. N5Click (соответствует выбору пункта меню Анализатор/Лексический). В ней производится обнуление всех таблиц, вызов функции выделения лексем и процедуры WriteLex (см. ниже).

Поиск идентификаторов, констант и терминальных символов в соответствующих таблицах производится, соответственно, процедурами Search_Ident, Search_Const и Search_Term, добавление в таблицы - процедурами Add_Ident, Add_Const и Add_Term. Все они вызываются из процедуры WriteLex, входными данными для которой являются результаты распознавания лексем, т.е. типы лексем. Запись в таблицу кодов лексем производится процедурой WriteCode, вывод всех таблиц на экран - процедурой vyvod.

Перевод констант в десятичную форму производится процедурой perevod.

2.4.3 Реализация лексического анализатора

Приведём текст подпрограммы лексического анализатора:

// процедура перевода констант в десятичную форму

procedure perevod (SS: string; var Str16: string);

var ch3,ch4,ch, i: integer;

zn: string;

begin

ch: =0; // для римских констант

if (SS [2] ='X') or (SS [2] ='V') or (SS [2] ='I') then

begin

zn: =SS [1] ;

delete (SS,1,1);

while Length (SS) <>0 do

begin

if SS [1] ='X' then begin ch: =ch+10; delete (SS,1,1); end

else begin

if SS [1] ='V'then begin ch: =ch+5; delete (SS,1,1); end

else begin

if ( (SS [1] ='I') and (SS [2] ='I')) or ( (SS [1] ='I') and (SS [2] ='')) then begin ch: =ch+1; delete (SS,1,1); end

else begin

if (SS [1] ='I') and (SS [2] ='X') then begin ch: =ch+9; delete (SS,1,2); end

else begin

if (SS [1] ='I') and (SS [2] ='V') then begin ch: =ch+4; delete (SS,1,2); end;

end; end; end; end; end;

str16: =zn+IntToStr (ch);

exit;