Создание компилятора

 

Дисциплина: Системное программное обеспечение

 

 

Курсовая работа

 

 

Тема: Создание компилятора

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

       

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

                                                                                                                          

 

Введение                                                                                                                              3

1. Организация таблиц идентификаторов                 4

1.2. Назначение таблиц идентификаторов      4

1.3. Метод рехеширования с использованием  случайных чисел    4

1.4. Метод упорядоченного списка        8

1.5.Основные используемые функции          9

1.6. Результаты сравнения методов       14

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

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

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

2.4. Алгоритм лексического анализатора       25

2.5. Основные используемые функции        26

2.4. Результаты работы лексического  анализатора     30

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

3.2. Синтаксический анализатор       33

3.3. Грамматика простого предшествования       34

3.4. Грамматика операторного предшествования      35

3.5. Построение распознавателя  для операторного предшествования   36

3.6. Основные используемые функции        37

3.7. Результаты работы  синтаксического анализатора     39

Заключение            40

Список литературы           41

Приложение А. Исходный текст программы       42 

Приложение Б. Граф состояний лексического анализатора    54

 

 

Введение

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

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

Курсовая работа заключается  в реализации отдельных фаз компиляции заданного языка.

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

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

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

В качестве среды разработки для реализации программы был использован Borland Delphi 7.

 

 

 

 

 

 

 

1. Организация таблицы  идентификаторов

1.2. Назначение таблицы идентификаторов

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

Под идентификаторами подразумеваются  константы, переменные, имена процедур и функций, формальные и фактические  параметры.[1]

1.3. Метод рехеширования с использованием случайных чисел

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

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

вычислить значение функции n₁=h₁(A) и проверить занятость ячейки по адресу n₁. Если и она занята, то вычисляется значение h₂(A) и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h_i(A) совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена, и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице.

Такую таблицу идентификаторов можно организовать по следующему алгоритму размещения элемента:

Шаг 1: Вычислить значение хеш-функции n = h(A) для нового элемента A.

Шаг 2: Если ячейка по адресу n пустая, то поместить в нее элемент A и завершить алгоритм, иначе i:=1 и перейти к шагу 3.

Шаг 3: Вычислить n_i = h_i(A). Если ячейка по адресу n_i пустая, то поместить в нее элемент A и завершить алгоритм, иначе перейти к шагу 4.

Шаг 4: Если n = n_i, то сообщить об ошибке и завершить алгоритм, иначе i:=i+1 и вернуться к шагу 3.

Тогда поиск элемента A в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:

Шаг 1: Вычислить значение хеш-функции n = h(A) для искомого элемента A.

Шаг 2: Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе сравнить имя элемента в ячейке n с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:=1 и перейти к шагу 3.

Шаг 3: Вычислить n_i = h_i(A). Если ячейка по адресу n_i пустая или n = n_i, то элемент не найден и алгоритм завершен, иначе сравнить имя элемента в ячейке n_i с именем искомого элемента A. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:=i+1 и повторить шаг 3.

 

 

Схема алгоритма добавления идентификатора приведена на рис. 1.1.

Рис. 1. 1 Схема алгоритма добавления идентификатора

 

 

 

 

 

 

 

 

 

Схема алгоритма поиска идентификатора приведена на рис. 1.2.

Рис. 1.2. Схема алгоритма  поиска идентификатора

 

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

Этот метод является простым методом построения таблиц идентификаторов. Элементы записываются в таблицу в порядке возрастания. Так как упорядочивание таблицы идентификаторов происходит на всех этапах обращения к таблице, то для ее построения можно пользоваться только алгоритмом прямого упорядоченного включения элементов. При добавлении нового элемента в таблицу идентификаторов он сначала добавляется в конец таблицы, а затем идет переупорядочивание элементов таблицы идентификаторов. Эффективным методом для поиска элементов является логарифмический поиск, на каждом шаге которого, число элементов, которые могут содержать искомый элемент, сокращается в два раза. Максимально число сравнений при поиске  1+log₂(N). [1]

Схема алгоритма добавления идентификатора представлена на рис. 1.3.

Рис. 1.3. Схема алгоритма  добавления идентификатора

 

 

Схема алгоритма поиска идентификатора представлена на рис. 1.4.

Рис. 1.4. Схема алгоритма  поиска идентификатора

Недостатком такого метода является требование упорядочивания таблицы  идентификаторов на всех этапах обращения  к этой таблице.

К положительным качествам  метода можно отнести простоту его организации.

1.5. Основные используемые функции

Хеш-функция.

  function HeshFunc(St:string):integer;

var dlina,sred:integer;

begin

  dlina:=length(St);

  if dlina=0 then Result:=0

  else begin

 

    sred:=(dlina+1)div 2;

    if dlina=1 then Result:=ord(St[1])-64 else

      if dlina=2 then Result:=ord(St[1])+ord(St[dlina])-64 else

        Result:=(ord(St[1])+ord(St[sred])+ord(St[dlina]))-64;

  end

end;

 

Заполнение  хэш-таблицы и таблицы идентификаторов,  
подсчет коллизий.

  label Shag3;

var

   S,Word:String;

   NRow, i, Kol, u, KolO, Com, Key, Key1: Integer;

begin

{Рисование ХТ и занесение  пустых значений во все ее  ячейки}

KolO:=0;{Количество колизий}

Com:=0;{Количество сравнений}

u:=1;

with StringGrid1 do

begin

For NRow:=1 to 302 do

                     begin

                      cells[0,NRow]:=InttoStr(NRow+64);

                      cells[1,NRow]:=''

                     end

end;

{Собственно хэширование}

for i:=0 to Words.Count-1 do

begin

Kol:=0;

s:=Words[i];

key:=HeshFunc(s);

        if StringGrid1.Cells[1,Key]='' then begin {ячейка с данным значением ХФ свободна}

        Com:=Com+1;{число сравнений}

        StringGrid1.Cells[1,Key]:=S;{Заносим  запись в ТИ по значению  указателя}

end

        else {ячейка  с данным заначением ХФ занята}

        begin

Shag3:  Kol:=Kol+1;

        KolO:=KolO+1;

        Com:=Com+1;

        Key1:=((Key + Sl[u]) mod 302)+64;

        if StringGrid1.Cells[1,Key1]='' then begin

        {ячейка с данным значением ХФ свободна}

        Com:=Com+1;{число  сравнений}

        StringGrid1.Cells[1,Key1]:=S;{Заносим запись в ТИ по значению указателя}

end

        else {ячейка  с данным заначением ХФ занята}

        if Key1=Key then begin

        ShowMessage('Ошибка! В ХТ нет свободного места');

        Exit

                    end

                    else begin

                    key:=key1;

                    u:=u+1;

                    goto Shag3;

 

                    end

        end;

end;

Word:=InttoStr(KolO);

Form1.Memo2.Lines.Add('ПРИ ДОБАВЛЕНИИ ВСЕХ ЭЛЕМЕНТОВ:');

Form1.Memo2.Lines.Add('Количество колизей '+Word);

word:=InttoSTR(Com);

Form1.Memo2.Lines.Add('Количество сравнений '+Word);

end;

Поиск в таблице идентификаторов.

 

var j,i,t,k,a,b,m,n:integer;s1:string;

label 1,2,3,4,5;

begin

k:=0; t:=memo1.Lines.Count; s1:=Edit1.text;

for j:=1 to t do

   if  StringGrid2.Cells[1,j]<>'' then k:=k+1;

if s1='' then

  begin

  MessageDlg('Поле ввода пусто', mtInformation,[mbOk],0);

  goto 3;

  end;

a:=1; b:=k; i:=0;

1: if ((a+b) div 2)=0 then m:=(a+b) div 2  else m:=(a+b) div 2;

   i:=i+1;

   if s1=StringGrid2.Cells[1,m] then

    begin

    MessageDlg('Элемент найден', mtInformation,[mbOk],0);

    n:=m; goto 2;

    end

 

   else

    if s1<StringGrid2.Cells[1,m] then

     begin

     b:=m;

     if a=b-1 then

      begin

       i:=i+1;

       if s1=StringGrid2.Cells[1,a] then

         begin

         MessageDlg('Элемент найден', mtInformation,[mbOk],0);

         n:=a; goto 2;

         end

       else

         begin

         MessageDlg('Элемент не найден', mtInformation,[mbOk],0); goto 3;

         end;

      end

     else goto 1;

     end

    else

     begin

     a:=m;

     if a=b then

      begin

       i:=i+1;

       if s1=StringGrid2.Cells[1,b] then

         begin

         MessageDlg('Элемент найден', mtInformation,[mbOk],0);

         n:=b; goto 3;

 

         end

       else

         begin

         MessageDlg('Элемент не найден', mtInformation,[mbOk],0); goto 3;

         end;

      end

     else goto 1;

     end;

2:

Memo3.Lines.Add('ПРИ ПОИСКЕ');

Memo3.Lines.Add('Количество сравнений  '+IntToStr(i));

Memo3.Lines.Add('Номер ID = '+IntToStr(n));  goto 4;

3:

Memo3.Lines.Add('ПРИ ПОИСКЕ');

Memo3.Lines.Add('Количество  сравнений '+IntToStr(i));

Memo3.Lines.Add('Идентификатор  не найден!');;

4:

end;

1.6. Результаты сравнения методов

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

На рис. 1.5 представлена экранная форма метода рехеширования с использованием случайных чисел и упорядоченного списка.

Рис. 1.5. Экранная форма  организации таблицы идентификаторов

 

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

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

 

 

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

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