|
Разработка программы-компилятора |
имвол 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;beginch: =0; // для римских константif (SS [2] ='X') or (SS [2] ='V') or (SS [2] ='I') thenbeginzn: =SS [1] ;delete (SS,1,1);while Length (SS) <>0 dobeginif SS [1] ='X' then begin ch: =ch+10; delete (SS,1,1); endelse beginif SS [1] ='V'then begin ch: =ch+5; delete (SS,1,1); endelse beginif ( (SS [1] ='I') and (SS [2] ='I')) or ( (SS [1] ='I') and (SS [2] ='')) then begin ch: =ch+1; delete (SS,1,1); endelse beginif (SS [1] ='I') and (SS [2] ='X') then begin ch: =ch+9; delete (SS,1,2); endelse beginif (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;end; // для 16-рич. константIf SS [3] in ['0'. '9']thench3: =StrToInt (SS [3]) *16elseif SS [3] in ['A'. 'F']thenbeginch3: =ord (SS [3]);case ch3 of65: ch3: =10*16;66: ch3: =11*16;67: ch3: =12*16;68: ch3: =13*16;69: ch3: =14*16;70: ch3: =15*16;end;end;If SS [4] in ['0'. '9']thench4: =StrToInt (SS [4])elseif SS [4] in ['A'. 'F']thenbeginch4: =ord (SS [4]);case ch4 of65: ch4: =10;66: ch4: =11;67: ch4: =12;68: ch4: =13;69: ch4: =14;70: ch4: =15;end;end;ch: =ch3+ch4;If (SS [3] ='0') and (SS [4] ='0')then Str16: =IntToStr (ch)else Str16: =SS [2] +IntToStr (ch);end;procedure TForm1. N3Click (Sender: TObject);beginclose;end;function Select_Lex (S: string; {исх. строка} var Rez: string; {лексема}N: integer {текущая позиция}): integer;label 1;begin // функция выбора слов из строкиk: = Length (S);Rez: ='';i: =N; // точка продолжения в строкеwhile (S [i] =' ') and (i<= k) do i: =i+1; // пропуск ' 'while not (S [i] in deleter) and (i<= k) do // накопление лексемыbeginif s [i] ='$' thenbeginRez: =s [i] +s [i+1] ;i: =i+2;endelse begin1: Rez: =Rez+s [i] ;i: =i+1;end;end;if Rez='' thenbeginif (s [i] =': ') thenbeginif (s [i+1] ='=') then // в случае операции из двух символовbeginRez: =s [i] +s [i+1] ;Select_Lex: =i+2;endelsebeginRez: =s [i] ;Select_Lex: =i+1;end;end elsebeginif ( (s [i] ='+') or (s [i] ='-')) and (s [i-1] =' (')then beginRez: =s [i] +s [i+1] ;i: =i+2;goto 1;endelse beginRez: =s [i] ;Select_Lex: =i+1;end; end;end else Select_Lex: =i;end;procedure Add_Const (Curr_term: integer; str_lex: string); // Процедура добавления идентификаторов в деревоbeginif NumConst=1 then // Если корень дерева еще не создан, то создаем его.beginperevod (str_lex,str16);Const_tab [NumConst]. value: =str_lex;Const_tab [NumConst]. nomer: =NumConst;Const_tab [NumConst]. Val10: =str16;Const_tab [NumConst]. Left: =0;Const_tab [NumConst]. Right: =0;Const_tab [NumConst]. Way: ='V';Exit;end;if (CompareStr (Const_tab [Curr_term]. value,str_lex) >0) then // Если значение текущего узла дерева больше добавляемогоif Const_tab [Curr_term]. Left=0 then // если у этого элемента дерева нет левого указателя, тоbeginperevod (str_lex,str16);Const_tab [Curr_term]. Left: =NumConst; // Создание левого элемента.Const_tab [NumConst]. value: =str_lex;Const_tab [NumConst]. nomer: =NumConst;Const_tab [NumConst]. Val10: =str16;Const_tab [NumConst]. Left: =0;Const_tab [NumConst]. Right: =0;Const_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'L';end else beginConst_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'L';Add_Const (Const_tab [Curr_term]. Left,str_lex); // Если левый указатель существует, то вызываем уже функцию для левого указателя.end;if (CompareStr (Const_tab [Curr_term]. value,str_lex) <0) then // если у этого элемента дерева нет правого указателя, тоif Const_tab [Curr_term]. Right=0 thenbeginperevod (str_lex,str16);Const_tab [Curr_term]. Right: =NumConst; // Создаем правый элемент.Const_tab [NumConst]. value: =str_lex;Const_tab [NumConst]. nomer: =NumConst;Const_tab [NumConst]. Val10: =str16;Const_tab [NumConst]. Left: =0;Const_tab [NumConst]. Right: =0;Const_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'R';end else beginConst_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'R';Add_Const (Const_tab [Curr_term]. Right,str_lex); // Если правый указатель существует, то вызываем уже функцию для правого указателя.end;end;procedure Add_Term (Curr_term: integer; str_lex: string); // Процедура добавления идентификаторов в деревоbeginif NumTerm=1 then // Если корень дерева еще не создан, то создаем его.beginTerm_tab [NumTerm]. lex: =str_lex;Term_tab [NumTerm]. nomer: =NumTerm;Term_tab [NumTerm]. Left: =0;Term_tab [NumTerm]. Right: =0;Term_tab [NumTerm]. Way: ='V';Exit;end;if (CompareStr (Term_tab [Curr_term]. lex,str_lex) >0) then // Если значение текущего узла дерева больше добавляемогоif Term_tab [Curr_term]. Left=0 then // если у этого элемента дерева нет левого указателя, тоbeginTerm_tab [Curr_term]. Left: =NumTerm; // Создание левого элемента.Term_tab [NumTerm]. lex: =str_lex;Term_tab [NumTerm]. nomer: =NumTerm;Term_tab [NumTerm]. Left: =0;Term_tab [NumTerm]. Right: =0;Term_tab [NumTerm]. Way: =Term_tab [NumTerm]. Way+'L';end else beginTerm_tab [NumTerm]. Way: =Term_tab [NumTerm]. Way+'L';Add_Term (Term_tab [Curr_term]. Left,str_lex); // Если левый указатель существует, то вызываем уже функцию для левого указателя.end;if (CompareStr (Term_tab [Curr_term]. lex,str_lex) <0) then // если у этого элемента дерева нет правого указателя, тоif Term_tab [Curr_term]. Right=0 thenbeginTerm_tab [Curr_term]. Right: =NumTerm; // Создаем правый элемент.Term_tab [NumTerm]. lex: =str_lex;Term_tab [NumTerm]. nomer: =NumTerm;Term_tab [NumTerm]. Left: =0;Term_tab [NumTerm]. Right: =0;Term_tab [NumTerm]. Way: =Term_tab [NumTerm]. Way+'R';end else beginTerm_tab [NumTerm]. Way: =Term_tab [NumTerm]. Way+'R';Add_Term (Term_tab [Curr_term]. Right,str_lex); // Если правый указатель существует, то вызываем уже функцию для правого указателя.end;end;procedure Add_Ident (str: string); // процедура добавления константыvar i: integer;beginkod: =Length (str) +2;hesh: =0;for i: =1 to Length (str) do hesh: =hesh+ord (str [i]); // вычисление хэшhesh: =round (hesh/kod); // метод деленияwhile (Id_tab [hesh]. lex<>'') and (hesh<maxnum) do // пока ячейка занятаbeginId_tab [hesh]. ssylka: =hesh+1;hesh: =hesh+1;end;Id_tab [hesh]. nomer: =Numid; // запись данныхId_tab [hesh]. lex: =str;end;function Search_Ident (str: string): integer; // функция поиска терминалаvar i: integer;label 1;beginkod: =Length (str) +2;hesh: =0;for i: =1 to Length (str) do hesh: =hesh+ord (str [i]); // вычисление хэшhesh: =round (hesh/kod);1: if str=Id_tab [hesh]. lex then Search_Ident: =Id_tab [hesh]. nomer else // поиск идентификатораbeginif Id_tab [hesh]. ssylka=0 then Search_Ident: =0 elsebeginhesh: =Id_tab [hesh]. ssylka;goto 1;end;end;end;procedure Search_Const (Curr_term: integer; str_lex: string); // Процедура поиска лексем в дереве идентификаторовbeginConstyes: =0; // флаг: найдена ли лексемаif (NumConst<>0) and (str_lex<>'') thenbeginif (CompareStr (Const_tab [Curr_term]. value,str_lex) >0) and (Const_tab [Curr_term]. Left<>0) thenSearch_Const (Const_tab [Curr_term]. Left,str_lex); // рекурсивный "спуск по дереву"if (CompareStr (Const_tab [Curr_term]. value,str_lex) <0) and (Const_tab [Curr_term]. Right<>0) thenSearch_Const (Const_tab [Curr_term]. Right,str_lex);if Const_tab [Curr_term]. value=str_lex then Constyes: =Const_tab [Curr_term]. nomer;end;end;procedure Search_Term (Curr_term: integer; str_lex: string); // Процедура поиска лексем в дереве идентификаторовbegin
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|