Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Интерпретатор математических формул, реализованный на основе метода Дейкстры.





Unit Aintr;

Interface

Uses Astream, Astack, Apro;

Type {Если мы будем проверять правильность соседства лексем, то во флаге удобно держать тип предыдущей лексемы. Для этого объявим новый тип.}

LexType = (opar { (}, cpar {) }, sgn {знак}, value{значение});

Type Pintr = ^Cintr;

Cintr = object

Public constructor Init (Pst:PFStreamTxt); {Передается указатель на поток}

Destructor Done; virtual;

Procedure Interpretate;

Private

P:PFStreamTxt;

Pro:Cpro;

St:CstackCh; {стек Дейкстры}

Oldlex:lextype; {флаг Дейкстры}

Procedure Failure (n:word);

Procedure Lexem; {процедура обработки очередной лексемы}

Procedure Number; {интерпретатор числа }

Function Weight (x:char):byte; {возвращает приоритет операции или скобки}

Function Right (x:byte):boolean; {возвращает значение ассоциативности; на входе – вес, на выходе истина если операции с таким весом правоассоциативны и ложь в противном случае}

Procedure PushPop (x:char); {организует выталкивание из стека Дейкстры}

End;

 

Implementation

Uses Crt;

Constructor Cintr.Init;

Begin

P:=PST;

Writeln(‘Pro.Create’);

Pro.Create;

St.Create;

{oldlex будет установлена в процессе интерпритации}

end;

 

Destructor Cintr.Done;

Begin

St.Destroy;

Writeln (‘Pro.Destroy’);

Pro.Destroy;

P:=nil;

End;

 

Procedure Cintr.Interpretate;

Var S:string;

Begin

St.Push (‘(‘); {помещаем первую неявную скобку}

Oldlex:= opar;

While not p^.IsEnd do Lexem;

If not ((oldlex=value) or (oldlex=cpar)) then failure (1);

PushPop (‘)’);

If not st.IsEmpty then failure(2);

Writeln (‘Pro.Show’);

Pro.Top2Str (s); {вершина стекового процессора преобразуется в строковую переменную}

Writeln (‘Ответ =’,s);

{далее необязательная часть}

Pro.Del; {чистим стековый процессор}

If not Pro.IsEmpty then Failure(3);

End;

 

Procedure Cintr.Lexem;

Var c:char;

Begin

C:= p^.getchar;

Case c of

‘0’..’9’: begin

if not ((oldlex=opar) or (oldlex=sgn)) then failure(11);

number;

oldlex:=value;

end;

‘(‘: begin if not ((oldlex=opar) or (oldlex=sgn)) then failure(12);

st.Push (c);

p^.skip;

oldlex:=opar;

end;

‘)’:begin If not ((oldlex=value) or (oldlex=cpar)) then failure (13);

PushPop (c);

P^.Skip;

Oldlex:=cpar;

End;

‘+’,’-‘,’*’,’/’:begin

if (c=’+’) and ((oldlex=opar) or (oldlex=sgn)) then

begin

if not ((weight(‘p’)>weight(st.top)) or

(((weight(‘p’)=weight(st.top)) and

right(weigth(‘p’))) then failure (14);

p^.skip;

Oldlex:=sgn;

End else

if (c=’-’) and ((oldlex=opar) or (oldlex=sgn)) then

begin

if not ((weight(‘m’)>weight(st.top)) or

(((weight(‘m’)=weight(st.top)) and

right(weigth(‘m’))) then failure (15);

PushPop(‘m’);

p^.skip;

Oldlex:=sgn;

End else if c in [‘+’,’-’,’*’,’/’] then

Begin

If not ((oldlex=value) or (oldlex=cpar)) then

failure (16);

PushPop(c);

P^.skip;

Oldlex:=sgn;

End {else if одноместные операции};

End;

Else failure(17);

End;

End;

 

{Текст можно было несколько сократить в части обработки операций, если запоминать значение веса вершины стека. Удобнее Top заменить на GetTop.}

 

procedure Cintr.PushPop;

var y:char;

begin

while true do

begin

if st.IsEmpty then failure(21);

if ((weight(x)>weight(st.top)) or

(((weight(x)=weight(st.top)) and right(weigth(x))) then break

else begin

st.pop(y);

case y of

‘m’:begin writeln (‘Pro.Inv’); pro.Inv; end;

‘+’: begin writeln (‘Pro.Add’); pro.Add; end;

‘-‘:begin writeln (‘Pro.Sub’); pro.sub; end;

‘*’:begin writeln (‘Pro.Mul’); pro.Mul; end;

‘/’:begin writeln (‘Pro.Div’); pro._Div; end;

end;

end;

end;

if x in [‘m’,’+’,’-‘,’*’,’/’] then st.Push(x);

else if x=’)’ then begin

if not (st.top=’(‘) then failure(22);

st.Pop(y);

end;

end;

 

function Cintr.Weight;

begin

case x of

‘(‘:weight:=0;

‘)’:weight:=1;

‘+’,’-‘:weight:=2;

‘/’:weight:=3;

‘*’:weight:=4;

‘p’,’m’:weight:=5;

else failure(31);

end;

end;

 

function Cintr.Right;

begin

case x of

2:Right:=false;

3:right:=true;

4:right:=false;

5:right:=true;

else right:=false;

end;

end;

 

procedure Cintr.Number;

…….

End;

 

Procedure Cintr.Failure;

Begin

……

halt(1);

end;

 

end.

 

Может возникнуть вполне резонный вопрос: какой из представленных двух компиляторов лучше? Ответ на него очень прост: первый проще создавать, а второй изменять. Если вы программировали первый вариант, то обратили внимание, что в нем практически пишешь программу по грамматике, при этом лишается всякая самостоятельность. Тогда как во втором компиляторе

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

Похожим образом создаются языки программирования. Только там компилятор обеспечивает перевод программы с языка программирования на машинный язык. Кроме этого в нашей работе используется однопроходной вариант, не содержащий отдельного блока лексического анализа. Обычно вначале файл преобразуется: лексемы заменяются кодами. В наше случае лексемы достаточно просты поэтому дополнительное преобразование не понадобилось. В работе настоящего компилятора не ограничиваются однопроходным вариантом. Например, в языке Alpha компилятор выполняет около 30 проходов (притом из них 15 - оптимизация). В результате получается программа по скорости работы опережающая программу на Assembler'е.

 

Абстрактные структуры данных.

Часть 2

Последовательность.

Последовательность – это набор элементов разделенный на две части: первая часть состоит из всех элементов уже прочитанных к данному моменту времени (before), вторая часть состоит из всех непрочитанных элементов (after).


Основные операции производимые над последовательностью:

1. Конструктор – создает по умолчанию пустую последовательность.

2. Деструктор – уничтожает последовательность.

3. Доступ для чтения (Get) – считывает значение 1-го элемента непрочитанной части.

4. Доступ для изменения (Put, Set,…) –изменение значения 1-го элемента непрочитанной части.

5. Вперед (Skip) – изменение соотношения между прочитанной и непрочитанной частями.

6. Пуста? (IsEmpty) – проверка является ли последовательность пустой или нет.

7. Сделать пустой (DoEmpty, Clear, …) – выбрасывает все элементы из последовательности и делает пустыми обе части.

8. В конце? (IsEnd) – проверяет совпадает ли прочитанная часть со всей последовательностью.

9. В начало (GoTop) – непрочитанная часть совпадает со всей последовательностью.

10. Добавить (Append) – добавляет элемент в конец непрочитанной части.

11. Прочесть очередной элемент (Read) – считывает элемент и увеличивает прочитанную часть на 1.(является дополнительной т.к имеются методы 3 и 5)

Если сравнить набор методов последовательности и набор методов потока то можно заметить, что поток – частный случай видоизменённой последовательности.

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

Принципы реализации:

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

2. Односвязный список в куче.

3. На основе физического файла во внешней памяти.

Приведем пример реализации последовательности на основе односвязного списка.

1. Односвязный список без буфера


Для реализации последовательности на базе односвязного списка необходимо хранить также указатель на начало (Pb), на начало непрочитанной части (Pt), на конец (Pe).

2. Односвязный список с буфером.

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

Линейный двунаправленный список (L2 - список):

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

 
 

Набор методов для работы со L2 – списком:

1. Конструктор - создает по умолчанию пустой список.

2. Деструктор – уничтожает список.

3. Пуст? (IsEmpty) - функция, проверяющая пустоту списка.

4. В начало\В конец – переход в начало\конец списка.

5. Доступ для чтения элемента до\за указателем (GetBefore\GetAfter). (д)

6. Доступ для изменения элемента до\за указателем. (д)

7. Вперед\назад - перемещение текущего указателя.

8. В конце\В начале – функция, проверяющая положение текущего указателя списка.

9. Вставить за\до – вставка элемента после\перед указателя.

10. Изъять за\до - изъятие элемента после\перед указателем.

11:.Удалить за\до – удаление в соответствующей части. (д)

12.Сделать пустым. (д)

(д) – методы, которые могут быть получены с помощью комбинации остальных.

Идея реализации.

1. на основе сплошной памяти

2.
на основе двух стеков (аналогично 1, но не обязательно сплошная память)

3. на основе двусвязного списка.

Рассмотрим более подробно 3-ий способ реализации.

1-ый случай (без буфера). Схематично этот вариант можно показать следующим образом:


В этом случае не важно где хранить указатель Pt так как последний элемент части “до’’ и первый элемент части “после” имеют ссылки друг на друга. Необходимо также чтобы соответсвующие указатели первого и последнего элемента указывали на NIL.

2-ой случай (с буфером).

 


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

 

 
 

3-ий случай (с двумя буферами)

 

Этот метод является симметричным, так как часть «до» является зеркальным отражением части «за» это свойство позволяет значительно упростить написание этой реализации.

4-й случай (с общим буфером).


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







Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.