Лабораторная работа по "Программированию"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧЕРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«МОСКОВСКИЙ АВИАЦИОННЫЙ  ИНСТИТУТ

(национальный исследовательский  университет)»

 

 

Кафедра ВТ                                               «УТВЕРЖДАЮ»

                  Преподаватель Манака Д. А.

                       ________«___»_______  2012г.

   

 

Отчёт

Лабораторной работе №1

 

по дисциплине: СПО

 

 

 

 

 

 

Студент гр. ДВМ5-62   ____________ /Сарсенбаев А. Б.

                                                                  ^{подпись студента}              

«___»_____________ 2012г.

 

 

 

 

 

 

 

 

 

 

Байконур 2012г.

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

Задание

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

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

 

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

 

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

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

Хеш-адресация с рехешированием.

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

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

h_i(A) = ( h(A)+i ) mod N_m,                 (1)

где i – число возникновения коллизий, а N_m – максимальное значение из области значений (равное 509).

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

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

 

 

 

 

 

 

 

Упорядоченный список

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

В этом методе применяется  бинарный или логарифмический способ поиска элементов. Алгоритм этого поиска заключается в следующем: искомый  символ сравнивается с элементом (N+1)/2 в середине таблицы; если этот элемент не является искомым, то мы должны просмотреть только блок элементов, пронумерованных от 1 до (N+1)/2 – 1, или блок элементов от (N+1)/2 + 1 до N в зависимости от того, меньше или больше искомый элемент того, с которым его сравнивали. Затем процесс повторяется с блоком в два раз меньшего размера. Так продолжается до тех пор, пока либо не будет найден искомый элемент, либо алгоритм не дойдет до очередного блока.

Так как на каждом шаге число  элементов, которые могут содержать  искомый элемент, сокращается в 2 раза, максимальное число сравнений  равно 1+log₂(N).

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

 

 

 

 

 

 

 

 

 

 

 

 

Приложение А

(обязательное)

 

 

 

Рисунок А1 – экранная форма работы программы

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение Б

(обязательное)

 

Листинг программы 

unit Unit1;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ComCtrls, Grids, Math;

type

  TForm1 = class(TForm)

    PageControl1: TPageControl;

    TabSheet1: TTabSheet;

    OpenDialog1: TOpenDialog;

    Button1: TButton;

    Memo3: TMemo;

    Memo4: TMemo;

    Memo5: TMemo;

    Memo6: TMemo;

    StringGrid2: TStringGrid;

    StringGrid3: TStringGrid;

    Button3: TButton;

    Button5: TButton;

    Edit1: TEdit;

    Memo7: TMemo;

    Button6: TButton;

    Label2: TLabel;

    Label3: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    Label6: TLabel;

    Label7: TLabel;

    GroupBox1: TGroupBox;

    Label8: TLabel;

    Label9: TLabel;

    GroupBox2: TGroupBox;

    Label12: TLabel;

    Button7: TButton;

    procedure FormCreate(Sender: TObject);

    procedure Button1Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

    procedure Button5Click(Sender: TObject);

    procedure Button6Click(Sender: TObject);

    procedure Button7Click(Sender: TObject);

 

 

  private

    { Private declarations }

  public

    { Public declarations }

    ukazatel,vssrav,knop,knop1:integer;

    srsrav,srsrav1,vssrav1: real;

    inputString:TStringList;

  end;

 

var

  Form1: TForm1;

implementation

 

{$R *.dfm}

 

function Hesh(St:string):integer;

var dlina:integer;

begin

dlina:=length(St);

if dlina=0 then Result:=0

  else

begin

  dlina:=length(St);

  if dlina=0 then  Result:=0 else

    begin

     if dlina=1 then

        Result:=ord(St[1])

     else

        Result:=ord(St[1])+ord(St[2]);

    end;

end;

end;

 

procedure TForm1.FormCreate(Sender: TObject);

var i:integer;

begin

 

  srsrav:=0;

  knop:=0;

  vssrav:=0;

  srsrav1:=0;

  knop1:=0;

  vssrav1:=0;

  Edit1.Text:='';

 

  Memo3.Text:='';

  Memo4.Text:='';

  Memo5.Text:='';

  Memo6.Text:='';

  Memo7.Text:='';

 

  StringGrid2.Cells[0,0]:='ХФ';

  StringGrid2.Cells[1,0]:='Иден-р';

  StringGrid3.Cells[0,0]:='Номер';

  StringGrid3.Cells[1,0]:='Иден-р';

 

  for i:=1 to 510 do

    begin

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

    end;

end;

 

 

procedure TForm1.Button1Click(Sender: TObject);

begin

close;

end;

 

procedure TForm1.Button3Click(Sender: TObject);

var i,k,dlina,hash,j,f,kol:integer;

    stroka:string;

    a,b,buf:string;

    max1,lk,ss,li,min,max,p,lj,sr,lf:integer;

label 1,2;

begin

      for i:=1 to 510 do

    begin

      StringGrid2.Cells[0,i]:=IntToStr(i);

    end;

   j:=0;

   k:=2;

   kol:=0;

   ukazatel:=0;

   dlina:=memo3.Lines.Count;

   if dlina<>0 then

     begin

      for i:=0 to dlina-1 do

         begin

           stroka:=memo3.Lines[i];

           hash:=Hesh(stroka);

           if (StringGrid2.cells[1,hash])='' then

             begin

              StringGrid2.cells[1,hash]:=stroka;

              end

           else

             begin

  1:           if (StringGrid2.cells[1,hash])=stroka then

                 begin

                   memo4.Lines[j]:='Удален повтор '+stroka;

                   j:=j+1;

                   ukazatel:=ukazatel+1;

                   goto 2;

                 end

               else

                 begin

                  kol:=kol+1;

                  hash:=(Hesh(stroka)*k) mod 509;

                  if (StringGrid2.cells[1,hash])='' then

                    begin

                      StringGrid2.cells[1,hash]:=stroka;

                    end

                  else

                    begin

                      k:=k+1;

                      goto 1;

                    end;

                 end;

             end;

2:      end;

     end;

    Label8.Caption:='Кол-во коллизий                   '+inttostr(kol);

 

for li:=1 to 510 do

 begin

   StringGrid3.Cells[1,li]:='';

 end;

lk:=0;

p:=Memo3.Lines.Count;

if p>=1 then

  begin

    StringGrid3.Cells[1,1]:=Memo3.Lines[0];

    memo6.Lines[0]:=Memo3.Lines[0];

  end;

for li:=1 to p-1 do

 begin

   lf:=0;

   min:=0;

   max:=510;

   a:=Memo3.Lines[li];

   while max-min<>1 do

    begin

      sr:=(max+min) div 2;

      if  StringGrid3.Cells[1,sr]=a then

       begin

         Memo4.Lines[lk]:='Удален повтор '+a;

         lk:=lk+1;

         lf:=1;

         break;

       end

        else

           if (StringGrid3.Cells[1,sr]>a) or (StringGrid3.Cells[1,sr]='') then

              max:=sr

           else

              min:=sr;

    end;

    lj:=509;

   if lf=0 then

     begin  while lj>min do

       begin

         StringGrid3.Cells[1,lj+1]:=StringGrid3.Cells[1,lj];

         lj:=lj-1;

       end;

       StringGrid3.Cells[1,max]:=a;

       memo6.Lines.Append(a)

     end;

 end;

   while  (StringGrid3.Cells[1,max1]<>'') do

    begin

      max1:=max1+1;

    end;

end;

 

procedure TForm1.Button5Click(Sender: TObject);

var max1,k,hash,dlina,i,srav,j,si: integer;

    stroka: string;

    lk,ss,min,max,p,sr,sravn:integer;

    a:string;

label met1,met2,met3;

begin

  memo5.Lines[0]:='';

  memo7.Lines[0]:='';

  k:=2;

  srav:=0;

  stroka:=Edit1.Text;

  if stroka='' then

    begin

      memo5.Lines[0]:='Поле пусто!';

      memo7.Lines[0]:='Поле пусто!';

      goto met3;

    end;

  dlina:=memo3.Lines.Count;

  hash:=Hesh(stroka);

  for i:=1 to 510 do

    begin

      srav:=srav+1;

 

      if StringGrid2.Cells[0,hash]=IntToStr(hash) then

        begin

          if stroka=StringGrid2.Cells[1,hash] then

            begin

              memo5.Lines[0]:='Иден-р  '+stroka+'  найден! Его номер '+ IntToStr(hash);

              goto met1;

            end

          else

            begin

              for j:=1 to 510 do

               begin

                srav:=srav+1;

                hash:=(Hesh(stroka)*k) mod 509;

                k:=k+1;

                if StringGrid2.Cells[0,hash]=IntToStr(hash) then

                  begin

                    if stroka=StringGrid2.Cells[1,hash] then

                      begin

                        memo5.Lines[0]:='Иден-р  '+stroka+'  найден! Его номер '+ IntToStr(hash);

                        goto met1;

                      end;

                  end

                else memo5.Lines[0]:='Иден-р  '+stroka+'  не найден!';

               end;

            end;

        end

      else begin

        memo5.Lines[0]:='Иден-р  '+stroka+'  не найден!';

        goto met1; end;

    end;

met1: Label9.Caption:='Кол-во сравнений                 '+inttostr(srav);

 

dlina:=memo6.Lines.Count;

for si:=1 to dlina do

 begin

  k:=2;

  srav:=0;

  stroka:=memo6.Lines[si];

  hash:=Hesh(stroka);

  for i:=1 to 510 do

    begin

      srav:=srav+1;

      if StringGrid2.Cells[0,hash]=IntToStr(hash) then

        begin

          if stroka=StringGrid2.Cells[1,hash] then

            begin

              goto met2;

            end

          else

            begin

              for j:=1 to 510 do

               begin

                srav:=srav+1;

                hash:=(Hesh(stroka)*k) mod 509;

                k:=k+1;

                if StringGrid2.Cells[0,hash]=IntToStr(hash) then

                  begin

                    if StringGrid2.Cells[1,hash]=stroka then

                      begin

                          goto met2;

                      end;

                  end;

               end;

            end;

        end

      else

        goto met2;

    end;

met2:      vssrav:=vssrav+srav;

 end;

      srsrav:=vssrav/dlina;

 

      vssrav:=0;

      srsrav:=0;

 

  knop1:=knop1+1;

  sravn:=0;

  max1:=1;

  dlina:=Memo6.Lines.Count;

  while  (StringGrid3.Cells[1,max1]<>'') do

    begin

      max1:=max1+1;

    end;

  for i:=1 to 10 do

    begin

     min:=0;

     max:=max1;

     a:=Edit1.Text;

     while (StringGrid3.Cells[1,sr]<>a) and (max-min<>1) do

       begin

        sravn:=sravn+1;

        sr:=(max+min) div 2;

        if (StringGrid3.Cells[1,sr]>a) or (StringGrid3.Cells[1,sr]='') then

          begin

            max:=sr;

          end

        else

          begin

            min:=sr;

          end;

       end;

    end;

  if  StringGrid3.Cells[1,sr]=a then

    Memo7.Lines[0]:='Иден-р  '+a+'  найден! Его номер  '+ IntToStr(sr)

  else Memo7.Lines[0]:='Иден-р '+a+' не найден!';

    dlina:=dlina-(dlina-max1);

    srsrav1:=1+log2(dlina);

    Label12.Caption:='Кол-во сравнений                  '+inttostr(sravn);

 

met3: end;

 

procedure TForm1.Button6Click(Sender: TObject);

var i: integer;

begin

  for i:=1 to 510 do StringGrid2.Cells[1,i]:='';

  for i:=1 to 510 do StringGrid2.Cells[2,i]:='';

  for i:=1 to 510 do StringGrid3.Cells[1,i]:='';

  for i:=0 to Memo6.Lines.Count-1 do Memo6.Text:='';

  for i:=0 to Memo3.Lines.Count-1 do Memo3.Text:='';

  for i:=0 to Memo4.Lines.Count-1 do Memo4.Text:='';