BESofБиблиотека рефератов и курсовых

Разработка программы-компилятора

Обновлено

113

Содержание

  • Введение
    • 1. Анализ задания
    • 2. Разработка лексического анализатора
    • 2.1 Выбор и обоснование структур данных
    • 2.2 Разработка автоматных грамматик для распознавания лексем
    • 2.3 Разработка автоматов, работающих по правилам грамматики
    • 2.3.1 Автомат для распознавания имён
    • 2.3.2 Автомат для распознавания 16-ричных констант
    • 2.3.3 Автомат для распознавания римских констант
    • 2.3.4 Объединённый автомат
    • 2.4 Разработка алгоритма и программы лексического анализа
    • 2.4.1 Выделение лексем
    • 2.4.2 Распознавание лексем
    • 2.4.3 Реализация лексического анализатора
    • 2.4.4 Тестирование лексического анализатора
    • 3. Разработка синтаксического анализатора
    • 3.1 Уточнение грамматики языка применительно к варианту задания
    • 3.2 Разработка алгоритма синтаксического анализа
    • 3.3 Алгоритмы распознающих функций
    • 3.3.1 Функция Lex_Progr
    • 3.3.2 Функция Lex_Descr_List
    • 3.3.3 Функция Lex_Descr
    • 3.3.4 Функция Lex_Name_List
    • 3.3.5 Функция Lex_Oper_List
    • 3.3.6 Функция Lex_Assign
    • 3.3.7 Функция Lex_Exp
    • 3.3.8 Функция Lex_Simple_Exp
    • 3.3.9 Функция Lex_Term
    • 3.3.10 Функция Lex_mnozh
    • 3.3.12 Функция Lex_Body
    • 3.4 Тексты распознающих процедур
    • 3.5 Результаты тестирования синтаксического анализатора
    • 4. Реализация двухфазного компилятора
    • 4.1 Результаты тестирования двухфазного компилятора
    • 5. Описание программы
    • 5.1 Общие сведения и функциональное назначение
    • 5.2 Вызов и загрузка
    • 5.3 Входные данные
    • 5.4 Выходные данные
    • 5.5 Описание логической структуры программы
    • 5.5.1 Файлы программы
    • 5.5.2 Общее описание работы программы
    • Список использованной литературы
ВведениеПо классификации программного обеспечения ЭВМ компиляторы относятся к системным обрабатывающим программам. Их функцией является перевод программы с языка высокого уровня в машинный код. В процессе перевода в программе выделяются и изменяются такие уровни или слои как алфавит, лексика, синтаксис при сохранении семантики.Алфавит - набор допустимых символов и знаков, из которых строятся элементарные конструкции языка. Отдельные знаки объединяются в лексемы.Лексема - отдельная неделимая конструкция, имеющая смысл.Слова (лексемы) объединяются в предложения (операторы) согласно правилам синтаксиса.Синтаксис - описание правильных конструкций языка или правил получения правильных конструкций языка.Компиляция состоит из этапов анализа и синтеза. В анализ входит лексический, синтаксический и семантический анализ.Лексический анализ состоит из распознавания лексем, их классификации и определения правильности.Синтаксический анализ заключается в проверке правильности структур языка, таких как предложения или операторы и всей программы в целом.1. Анализ заданияЗадание можно разделить на 3 части: лексический анализ, синтаксический анализ, разработка компилятора в целомЛексический анализ включает этапы:преобразование исходного текста в длинную строку;выделение лексических единиц (лексем);распознавание типов лексем;добавление лексем в соответствующие таблицы;сохранение таблиц в виде файлов.В данном задании используются следующие типы лексем:идентификаторы;ключевые слова;16-ричные и римкие константы;знаки операций;разделители.Идентификаторы (имена)Следует отметить, что идентификатор может начинаться только с буквы, следующие символы могут быть как буквы, так и цифры и знак подчеркивания (`_'). Кроме того, идентификаторы не могут совпадать со служебными словами.В данном задании встречаются следующие идентификаторы:`var15', `n'. Их следует записать в таблицу идентификаторов.Ключевые словаЭтот класс лексем, как правило, описывается тем же синтаксисом, что и идентификаторы. Основное отличие состоит в том, что все ключевые слова заранее перечислены и каждое играет в языке свою особую роль. Оно не может заменяться другими ключевыми словами. Лексический анализатор должен отличать ключевые слова от обычных имен, различать между собой и возвращать для каждого из них свои (уникальные) значения.Лексический анализатор должен различить следующие ключевые слова:`program', `var', `integer', `begin', `repeat', `until', `end', и записать их в таблицу терминальных символов.Константы.В данном задании встречаются как 16-ричные, так и римские константы. Необходимо, чтобы лексический анализатор правильно различал константы и различал их тип (16-ричная константа, римская константа) и записывал тип в таблицу констант.Константа считается римской, если она состоит из знака и символов `X','V' и `I' и образована по правилам составления римских констант. Она считается 16-ричной, если начинается с символа `$' и знака и состоит из цифр и букв `A'. 'F'. Константы могут быть как положительными, так и отрицательными, это зависит от знака после символа `$'.Лексический анализатор должен различить константы:`$+00', `$-0A' - как 16-ричные;`-XII' - как римскую.Эти лексемы он должен записать в таблицу констант с указанием их типа ('16-рич. ' - для 16-ричной константы, 'римск. ' - для римской константы) и указанием десятичной формы.Знаки операций.Их особенность состоит в том, что они могут быть одно - или двухсимвольными. В данном задании встречаются как односимвольные, так и двухсимвольные операции. Такие лексемы лексический анализатор должен распознать правильно (двухсимовольные операции не разбивать на отдельные операции) и записать их в таблицу терминальных символов.В данном задании встречаются следующие операции:Односимовольные: `-', `<';Двухсимвольные: `: ='.Разделители.К ним относятся специальные символы, разделяющие конструкции языка, например:; |, |. | (|) | пробелы | символы табуляции и перехода на новую строку. Они могут либо возвращаться в синтаксический анализатор в качестве лексем, либо только указывать на окончание предыдущей лексемы и пропускаться при вводе следующей. Некоторые из этих символов одновременно могут играть роль терминальных символов в грамматическом описании отдельных конструкций языка.В данном задании встречаются следующие разделители:`; ', `: ', `. ',' (`,') '.Границами лексем являются разделители, знаки операций, пробелы.В процессе синтаксического анализа решаются две задачи:распознавание предложений языка;определение правильности конструкций.Предложение считается синтаксически правильным, если оно представляет сентенциальную форму грамматики языка, т.е. может быть выведено с помощью некоторой цепочки переходов из начального символа грамматики.В процессе синтаксического анализа всего исходного текста в целом и каждого предложения в отдельности возможно два направления движения по цепочке правил: сверху вниз и снизу вверх.В процессе синтаксического анализа строится дерево грамматического разбора для каждого предложения. Это дерево строится от начального к конечному символу или наоборот.Дерево вывода состоит из начального (корневого) узла. В него включают еще промежуточные узлы и внешние узлы.Каждой ветви соответствует одно из правил грамматики.Входные данные - таблица кодов лексем, сформированная на стадии лексического анализа.Выходные данные - сообщение об успешном завершении анализа или сообщение об имеющихся ошибках.2. Разработка лексического анализатора2.1 Выбор и обоснование структур данных1. Таблица констант организована в виде двоичных деревьевДля хранения таблицы имен используется массив из записей Const_tab, содержащих следующие элементы:Номер лексемы.Лексема.Тип константы (16-ричная или римская).Ширина константы.10-тичная форма.Левая ветвь дерева (номер элемента, который является левой ветвью для данного).Правая ветвь дерева (номер элемента, который является правой ветвью для данного).Путь к элементу по дереву (последовательность левых и правых ветвей, которые необходимо пройти, чтобы достичь данного элемента).2. Таблица терминальных символов организована в виде двоичных деревьевДля хранения таблицы имен используется массив из записей Term_tab, содержащих следующие элементы:Номер лексемы.Лексема.Разделитель (если лексема является разделителем, то это поле равно 1, если нет, то 0).Знак операция (если лексема является знаком операции, то это поле равно 1, если нет, то 0).Ключевое слово (если лексема является ключевым словом, то это поле равно 1, если нет, то 0)Левая ветвь дерева (номер элемента, который является левой ветвью для данного).Правая ветвь дерева (номер элемента, который является правой ветвью для данного).Путь к элементу по дереву (последовательность левых и правых ветвей, которые необходимо пройти, чтобы достичь данного элемента).3. Для хранения таблицы идентификаторов используется метод с использованием хэш-функцийДля хранения таблицы констант используется массив из записей Id_tab, содержащих следующие элементы:Ссылка на элемент цепочки.Номер.Лексема.В данном случае хэш-функция вычисляется по методу деления, т.е.h (k): = {K/б}где K - ключ записи, б - некоторый коэффициентДля наиболее удобного распределения данных в таблице коэффициент б примем:б= Li+2где L - количество символов i-той строки, в которой хранится идентификатор.Код K рассчитывается как сумма ASCII-кодов символов строки, в которой хранится идентификатор.4. Для хранения таблицы кодов лексем используется массив из записей Code_tab, содержащих следующие элементы:Номер.Тип лексемы (C - константа, I - идентификатор, T - терминальный символ).Номер в таблице констант, идентификаторов или терминальных символов.Лексема.Номер в таблице кодов лексем.Для организации поиска используется последовательный метод.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;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); // Процедура поиска лексем в дереве идентификаторовbeginTermyes: =0; // флаг: найдена ли лексемаif (NumTerm<>0) and (str_lex<>'') thenbeginif (CompareStr (Term_tab [Curr_term]. lex,str_lex) >0) and (Term_tab [Curr_term]. Left<>0) thenSearch_Term (Term_tab [Curr_term]. Left,str_lex); // рекурсивный "спуск по дереву"if (CompareStr (Term_tab [Curr_term]. lex,str_lex) <0) and (Term_tab [Curr_term]. Right<>0) thenSearch_Term (Term_tab [Curr_term]. Right,str_lex);if Term_tab [Curr_term]. lex=str_lex then Termyes: =Term_tab [Curr_term]. nomer;end;end; // функция распознавания 16-рич. константfunction FConst (str: string): integer;varsost: byte;beginsost: =0;if str [1] ='$' then // распознаём символ '$'beginsost: =1;delete (str,1,1);endelse exit;if (str [1] ='+') or (str [1] ='-') then // распознаём знакbeginsost: =2;delete (str,1,1)endelse begin sost: =4; exit; end;if str='' then exit;while length (str) >0 do beginif (str [1] in cifra) or (str [1] in bukva)then sost: =2 // распознаём буквы или цифрыelse begin sost: =4; exit;end;delete (str,1,1);end;sost: =3;if sost=3 then FConst: =1 else FConst: =-1;end;function termin: integer; // распознаватель терминальных символовbegintermin: =-1;for k: =1 to 14 do if Words [k] =Lexem then termin: =3;for k: =1 to 8 do if Razdel [k] =Lexem then termin: =1;for k: =1 to 11 do if Operacii [k] =Lexem then termin: =2;end;function Rome (str: string): integer; // распознаватель римских константvar sost: byte;beginsost: =0;if (str [1] ='-') or (str [1] ='+')then begin sost: =12; delete (str,1,1); end;if str='' then exit;if str [1] ='X'then begin sost: =1; delete (str,1,1) endelse beginif str [1] ='V' then begin sost: =2; delete (str,1,1) endelse beginif str [1] ='I' then begin sost: =3; delete (str,1,1) endelse begin sost: =4; exit; end; end; end;while Length (str) <>0 do begincase sost of1: if str [1] ='X'then begin sost: =5; delete (str,1,1) endelse beginif str [1] ='V' then begin sost: =2; delete (str,1,1) endelse beginif str [1] ='I' then begin sost: =3; delete (str,1,1) endelse begin sost: =4; exit; end; end; end;2: if str [1] ='I'then begin sost: =7; delete (str,1,1) endelse begin sost: =4; exit; end;3: if str [1] ='X'then begin sost: =8; delete (str,1,1) endelse beginif str [1] ='V' then begin sost: =9; delete (str,1,1) endelse beginif str [1] ='I' then begin sost: =10; delete (str,1,1) endelse begin sost: =4; exit; end; end; end;4: exit;5: if str [1] ='X'then begin sost: =6; delete (str,1,1) endelse beginif str [1] ='V' then begin sost: =2; delete (str,1,1) endelse beginif str [1] ='I' then begin sost: =3; delete (str,1,1) endelse begin sost: =4; exit; end; end; end;6: if str [1] ='V'then begin sost: =2; delete (str,1,1) endelse beginif str [1] ='I' then begin sost: =3; delete (str,1,1) endelse begin sost: =4; exit; end; end;7: if str [1] ='I'then begin sost: =10; delete (str,1,1) endelse begin sost: =4; exit; end;8: begin sost: =4; exit; end;9: begin sost: =4; exit; end;10: if str [1] ='I'then begin sost: =11; delete (str,1,1) endelse begin sost: =4; exit; end;11: begin sost: =4; exit; end;end;end;if (sost=4) or (sost=12) then Rome: =-1 else Rome: =1;end; // функция распознавания идентификаторовfunction Ident (str: string): integer;varsost: byte;beginsost: =0; // реализация конечного автоматаif str [1] in ['a'. 'z'] thenbeginsost: =1;delete (str,1,1)endelse exit;while length (str) >0 do beginif str [1] in ['a'. 'z','0'. '9','_']then begin sost: =1; delete (str,1,1); endelse begin sost: =3; exit; end;end;sost: =2;if sost=2 then ident: =1 else ident: =-1;end;procedure WriteCode (nomer: integer; lex: string; typ: char; num: integer); // запись в таблицу кодов лексемbeginCode_Tab [NumLex]. nomer: =nomer;Code_Tab [NumLex]. Lex: =lex;Code_Tab [NumLex]. typ: =typ;Code_Tab [NumLex]. Num: =num;Code_Tab [NumLex]. numstr: =string_counter+1;end;procedure WriteLex (typelex: char); // запись лексем в таблицыbegincase typelex of'C': begin // если лексема-16-рич. константаNumLex: =NumLex+1;Search_Const (1,Lexem);if Constyes=0 then // если лексема не найденаbeginNumConst: =NumConst+1;Add_Const (1,Lexem);Const_tab [NumConst]. Typ: ='16-рич. ';Const_tab [Numconst]. Width: ='2 байта';WriteCode (NumLex,Lexem,'C',NumConst);end else // если лексема найденаbeginWriteCode (NumLex,Lexem,'C',Constyes);end;end;'M': begin // если лексема-римская константаNumLex: =NumLex+1;Search_Const (1,Lexem);if Constyes=0 then // если лексема не найденаbeginNumConst: =NumConst+1;Add_Const (1,Lexem);Const_tab [NumConst]. Typ: ='римск. ';Const_tab [Numconst]. Width: ='2 байта';WriteCode (NumLex,Lexem,'C',NumConst);end else // если лексема найденаbeginWriteCode (NumLex,Lexem,'C',Constyes);end;end;'I': begin // если лексема-идентификаторNumLex: =NumLex+1;y: =Search_Ident ({1,}Lexem);if y=0 then // если лексема не найденаbeginNumId: =NumId+1;WriteCode (NumLex,Lexem,'I',NumId);Add_Ident (Lexem);end else WriteCode (NumLex,Lexem,'I',y); // если лексема найденаend;'K': begin // если лексема-служебное словоNumLex: =NumLex+1;Search_Term (1,Lexem);if Termyes=0 then // если лексема не найденаbeginNumTerm: =NumTerm+1;Add_Term (1,Lexem);Term_tab [Numterm]. razd: =0;Term_tab [Numterm]. oper: =0;Term_tab [Numterm]. slug: =1;WriteCode (NumLex,Lexem,'T',NumTerm);end else WriteCode (NumLex,Lexem,'T',Termyes); // если лексема найденаend;'R': begin // если лексема-разделительNumLex: =NumLex+1;Search_Term (1,Lexem);if Termyes=0 then // если лексема не найденаbeginNumTerm: =NumTerm+1;Add_Term (1,Lexem);Term_tab [NumTerm]. razd: =1;Term_tab [NumTerm]. oper: =0;Term_tab [NumTerm]. slug: =0;WriteCode (NumLex,Lexem,'T',NumTerm)end else WriteCode (NumLex,Lexem,'T',Termyes) // если лексема найденаend;'O': begin // если лексема-знак операцияNumLex: =NumLex+1;Search_Term (1,Lexem);if Termyes=0 then // если лексема не найденаbeginNumTerm: =NumTerm+1;Add_Term (1,Lexem);Term_tab [Numterm]. razd: =0;Term_tab [Numterm]. oper: =1;Term_tab [Numterm]. slug: =0;WriteCode (NumLex,Lexem,'T',NumTerm)end else WriteCode (NumLex,Lexem,'T',Termyes) // есди лексема найденаend;end;end;procedure TForm1. N5Click (Sender: TObject);var i,pip: integer;beginfor k: =1 to numid do // обнуление таблицы идентификаторовbeginid_tab [k]. lex: ='0';id_tab [k]. nomer: =0;id_tab [i]. ssylka: =0;end;for i: =1 to numlex do // обнуление выходной таблицыbeginCode_Tab [i]. Lex: ='';Code_Tab [i]. typ: =#0;Code_Tab [i]. Num: =0;Code_Tab [i]. nomer: =0;end;for i: =0 to numconst do // обнуление таблицы константbeginConst_tab [i]. nomer: =0;Const_tab [i]. value: ='';Const_tab [i]. Typ: ='';Const_tab [i]. Width: ='';Const_tab [i]. Val10: ='';Const_tab [k]. Left: =0;Const_tab [k]. Right: =0;Const_tab [k]. Way: ='';end;for i: =1 to numterm dobeginTerm_tab [i]. nomer: =0;Term_tab [i]. Lex: ='';Term_tab [i]. razd: =0;Term_tab [i]. oper: =0;Term_tab [i]. slug: =0;Term_tab [k]. Left: =0;Term_tab [k]. Right: =0;Term_tab [k]. Way: ='';end; // инициализацияNumLex: =0; NumId: =0; NumConst: =0; NumErr: =0; NumTerm: =0;Error: =false; Found: =false;i: =0; j: =0; k: =0; y: =0;String_counter: =0;Memo2. Lines. Clear;N6. Enabled: =true;while string_counter<=Memo1. Lines. Count do // цикл по строкам файлаbeginn: =1;m: =1;s: =Form1. Memo1. Lines. Strings [string_counter] ;for l: =1 to 2 dowhile m<=Length (s) do // цикл по строкеbeginn: =m;m: =Select_Lex (s,Lexem,n);if (Lexem<>'') and not (Lexem [1] in [#0. #32]) thenbeginif FConst (Lexem) =1 then WriteLex ('C') else // вызов процедуры записиif Termin=3 then WriteLex ('K') elseif Rome (Lexem) =1 then WriteLex ('M') elseif Ident (Lexem) =1 then WriteLex ('I') elseif Termin=1 then WriteLex ('R') elseif Termin=2 then WriteLex ('O')else Err_lex;end;end;string_counter: =string_counter+1;end;vyvod; // вызов процедуры выводаend;procedure TForm1. vyvod; // Вывод результатовvarf: textfile; // выходной файлbeginStringGrid1. RowCount: =NumConst+1; // определение числа строк в таблицахStringGrid2. RowCount: =NumId+1;StringGrid3. RowCount: =NumTerm+1;StringGrid4. RowCount: =NumLex+1;StringGrid1. Cells [0,0]: ='№'; StringGrid1. Cells [1,0]: ='Константа'; StringGrid1. Cells [2,0]: ='Тип';StringGrid1. Cells [3,0]: ='Ширина'; StringGrid1. Cells [4,0]: ='10-тичный формат';StringGrid1. Cells [5,0]: ='L'; StringGrid1. Cells [6,0]: ='R';StringGrid1. Cells [7,0]: ='Путь'; // определение заголовковfor k: =1 to NumConst do // вывод таблицы константbeginStringGrid1. cells [0,k]: = Inttostr (Const_Tab [k]. nomer);StringGrid1. cells [1,k]: = Const_Tab [k]. value;StringGrid1. cells [2,k]: = Const_Tab [k]. Typ;StringGrid1. cells [3,k]: = Const_Tab [k]. Width;StringGrid1. cells [4,k]: = Const_Tab [k]. Val10;StringGrid1. cells [5,k]: = Inttostr (Const_Tab [k]. Left);StringGrid1. cells [6,k]: = Inttostr (Const_Tab [k]. Right);StringGrid1. cells [7,k]: = Const_Tab [k]. Way;end;AssignFile (F,'Const. txt'); // запись в файл таблицы константRewrite (F);for k: =1 to NumConst doWriteln (F, StringGrid1. cells [0,k] +' '+StringGrid1. cells [1,k] +' '+StringGrid1. cells [2,k] +' '+StringGrid1. cells [3,k]);CloseFile (F);StringGrid2. Cells [0,0]: ='№'; StringGrid2. Cells [1,0]: ='Имя'; // определение заголовковk: =0;k1: =0;while k<numid do // вывод таблицы идентификаторовbeginif Id_tab [k1]. lex<>'' thenbeginStringGrid2. cells [0,k+1]: =IntToStr (Id_tab [k1]. nomer);StringGrid2. cells [1,k+1]: =Id_Tab [k1]. lex;k: =k+1;end;k1: =k1+1;end;AssignFile (F,'Ident. txt'); // запись в файл таблицы константRewrite (F);for k: =1 to NumId do Writeln (F, StringGrid2. cells [0,k] +' '+StringGrid2. cells [1,k]);CloseFile (F);StringGrid3. Cells [0,0]: ='№'; StringGrid3. Cells [1,0]: ='Символ'; StringGrid3. Cells [2,0]: ='Раздел. ';StringGrid3. Cells [3,0]: ='Зн. операции'; StringGrid3. Cells [4,0]: ='Ключ. слово';StringGrid3. Cells [5,0]: ='L'; StringGrid3. Cells [6,0]: ='R';StringGrid3. Cells [7,0]: ='Путь'; // определение заголовковfor k: =1 to NumTerm do // вывод таблицы терминальных символовbeginStringGrid3. cells [0,k]: = Inttostr (Term_Tab [k]. nomer);StringGrid3. cells [1,k]: = Term_Tab [k]. lex;StringGrid3. cells [2,k]: = Inttostr (Term_Tab [k]. razd);StringGrid3. cells [3,k]: = Inttostr (Term_Tab [k]. oper);StringGrid3. cells [4,k]: = Inttostr (Term_Tab [k]. slug);StringGrid3. cells [5,k]: = Inttostr (Term_Tab [k]. Left);StringGrid3. cells [6,k]: = Inttostr (Term_Tab [k]. Right);StringGrid3. cells [7,k]: = Term_Tab [k]. Way;end;AssignFile (F,'Term. txt'); // запись в файл таблицы терминальных символовRewrite (F);for k: =1 to NumTerm do Writeln (F, StringGrid3. cells [0,k] +' '+StringGrid3. cells [1,k] +' '+StringGrid3. cells [2,k] +' '+StringGrid3. cells [3,k] +' '+StringGrid3. cells [4,k]);

Страницы: 1, 2, 3