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

 

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

 

 

 

 

 

 

 

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

                                          (q,w,n),                                                      (2.2)

где:    q – текущее состояние автомата;

w – цепочка входных символов автомата;

n – положение указателя;

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

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

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

Допустимые лексемы  входного языка: идентификаторы и римские  числа

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

E – конечное состояние автомата

 

Запишем  КС-грамматику входного языка в форме Бэкуса-Наура:

G(VT, VN, P, S)

VT – множество терминальных символов;

VN – множество нетерминальных символов;

P – множество правил;

E – целевой символ.

 

Регулярная грамматика входного языка имеет вид:

G ( {I,V,X, a..z, ‘+’, - , ‘;’, ‘(‘, ‘ )’, = ,  ’/’, ’ *’,’ : ’,’ . ‘},

{ N, L, E, I, F1, F2, O1, O2, T1}, P, E )

 

P: E® N | L | E| I| F2| O1| O2| T1| H _

      L® H;

      N® I |V|X|e|.|-|H0|H1|H2|H3|H4|H5|H6|H7|H8|H9

      E®H+

E®H-

 E®H*

 E®H/

I®a|b|c|….|z|I |V|X|Ha|Hb|Hc|….|Hz

F1®H:

F2®F1=

O2®H(

O1®H)

      T1® . | H .

      H® N_| L _| E_| I_| F2_| O1_| O2_| T1_| H_| _

 

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

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

 

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

Работа  лексического анализатора.

begin

  for i:=0 to 2 do

    for i1:=1 to 999 do

      StringGrid3.Cells[i,i1]:='';

  i1:=Memo4.Lines.Count;

  ind:=1;

  pos:=1;

  for i:=1 to i1 do

    begin

      str:='';

      stroka:=Memo4.Lines[i-1];

      stroka:=stroka+' ';

      d1:=Length(stroka);

      sost:=Auto_H;

      f1:=0;

      zn:=0;

      for j:=1 to d1 do

        begin

          st:=stroka[j];

          case sost of

            Auto_H:

                    case stroka[j] of             //  1

                      ';': begin sost:=Auto_L; str:=str+st; end;

                      'I','X','V': begin sost:=Auto_N; str:=str+st; end;

                      ':': begin sost:=Auto_F1; str:=str+st; end;

                      '(': begin sost:=Auto_O2; str:=str+st; end;

                      ')': begin sost:=Auto_O1; str:=str+st; end;

                      ' ': begin sost:=Auto_H; str:=''; end;

                      '-','+','''','*','/':begin sost:=Auto_E; str:=str+st; end;

                      else begin sost:=Auto_E; str:=str+st; end;

                    end;

           Auto_L:        //  ;

                    case stroka[j] of

                      ' ': begin sost:=Auto_H; f1:=1; zn:=1; end;

                      else begin sost:=Auto_E; str:=str+st; end;

                    end;

            Auto_N:    //  Римские буквы

                    case stroka[j] of

                      'X','I','V': begin sost:=Auto_N; str:=str+st; end;

                      ' ':begin sost:=Auto_H; f1:=1; zn:=12; end;

                      'a'..'h','j'..'u','w','y','z': begin sost:=Auto_H; f1:=1; zn:=5; str:=str+st; end;

                      else begin sost:=Auto_E; str:=str+st; end;

                    end;

            Auto_O2:  //  (

                    case stroka[j] of

                      ' ':begin sost:=Auto_H; f1:=1; zn:=2; end;

                      else begin sost:=Auto_E; str:=str+st; end;

                    end;

            Auto_O1:  //  )

                    case stroka[j] of

                      ' ':begin sost:=Auto_H; f1:=1; zn:=3; end;

                      else begin sost:=Auto_E; str:=str+st; end;

                    end;

            Auto_F1:  //  :=

                    case stroka[j] of

 

                      '=':begin sost:=Auto_F2; str:=str+st; end;

                      else begin sost:=Auto_E; str:=str+st; end;

                    end;

            Auto_F2:  //  :=

                    case stroka[j] of

                      ' ':begin sost:=Auto_H; f1:=1; zn:=4; end;

                      else begin sost:=Auto_E; str:=str+st; end;

                    end;

            Auto_E:

                    begin

                      if stroka[j]<>' ' then

                        begin

                          sost:=Auto_E;

 

                          str:=str+st;

                        end

                      else

                        begin

                          sost:=Auto_H;

                          Memo5.Lines.Append(str);

                          str:='';

                        end;

                    end;

          end;

          if f1=1 then

            begin

              StringGrid3.Cells[0,ind]:=IntToStr(ind);

              StringGrid3.Cells[1,ind]:=str;

              case zn of

 

                1: StringGrid3.Cells[2,ind]:='Разделяющий знак';

                2: StringGrid3.Cells[2,ind]:='Круглые открывающиеся скобки';

                3: StringGrid3.Cells[2,ind]:='Круглые закрывающиеся  скобки';

                4: StringGrid3.Cells[2,ind]:='Знак присваивания';

                5: StringGrid3.Cells[2,ind]:='Идентификатор';

                12: StringGrid3.Cells[2,ind]:='Римские цифры';

              end;

              str:='';

              ind:=ind+1;

              f1:=0;

            end;

      end;

    end;

Очистка данных программы.

begin

  for i:=0 to 2 do

    for i1:=1 to 999 do

      StringGrid3.Cells[i,i1]:='';

  Memo4.Clear;

  Label2.Caption:='Число лексем:0';

  Memo5.Clear;

  Label1.Caption:='Всего строк в файле:0';

end;

 

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

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

Экранная    форма    работы    лексического    анализатора    представлена на рис.2.2.

Рис. 2.2. Экранная форма работы лексического анализатора

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

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

Ошибка возникает при обнаружении неправильно введенных данных.

Экранная  форма  при  обнаружении   ошибки  представлена на рис. 2.3.

Рис. 2.3. Экранная форма при обнаружении лексической ошибки

 

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

 

 

 

 

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

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

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

Программирование работы недетерминированного МП-автомата - это сложная задача. Разработанный алгоритм, позволяет  для произвольной КС-грамматики определить, принадлежит ли ей заданная входная  цепочка (алгоритм Кока-Янгера-Касами).

Доказано, что время работы этого  алгоритма пропорционально n³, где n – длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n². Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка – большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.

КС-языки делятся на классы в  соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.

Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического  разбора цепочек с помощью  алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:

• простого предшествования;
• расширенного предшествования;

 

• слабого предшествования;
• смешанной стратегии предшествования;
• операторного предшествования.[1]

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

Грамматикой простого предшествования  называют такую КС-грамматику G(VT,VN,P,S), V=VTÈVN в которой:

1. Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:

• S_i = S_j (" S_i,S_jÎV), если и только если $ правило U®xS_iS_jy ÎP, где UÎVN, x,yÎV^*;

• S_i < S_j (" S_i,S_jÎV), если и только если $ правило U®xS_iDy ÎP и вывод DÞ*S_jz, где U,DÎVN, x,y,zÎV^*;
• S_i > S_j (" S_i,S_jÎV) , если и только если $ правило U®xCS_jy ÎP и вывод CÞ*zS_i или $ правило U®xCDy ÎP и выводы CÞ*zS_i и DÞ*S_jw, где U,C,DÎVN, x,y,z,wÎV^*.[1,2]