Интерпретатор математических формул, реализованный на основе метода Дейкстры
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-список.