2.5. Реализация стека

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

Структуру данных назовем стеком, если:

1. Определены:

   1. тип данных, содержащихся в стеке (обозначим tData);

   2. процедуры инициализации стека : Init (var S: tStack);

   3. процедура добавления элемента в стек Push(var S: tStack: D: tData);

   4. процедура извлечения элемента из стека: Pop (var S: tStack: D: tData);

2. Процедуры Push и Pop подчиняются дисциплине LIFO.

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

Элементы помещаются в стек начиная с первой ячейки массива. Число элементов, находящихся в данный момент в стеке, будем хранить в переменной SP. Массив элементов и SP будут полями записи типа tStack.

const

nmax = …; {Предельный объем стека}

type

tStack = record

a: array [1..nmax] of tData;

SP: onteger;

end;

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

procedure Init (var S:tStack);

begin

S.SP :=0;

end;

procedure Push (var S: tStack: D: tData);

begin

if S.SP<nmax then begin

S.SP := S.SP+1;

S.a[S.SP] :=D;

end

else

Error (‘Переполнение стека’);

end;

procedure Pop(var S: tStack: D: tData);

begin

if S.SP > 0 then begin

D:= S.a[S.SP];

S.SP := S.SP – 1;

end

else

Error(‘Стек пуст’)

end;

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

Запишем теперь функции, позволяющие проверять состояние стека (стек не пуст или не полон).

function NotEmpty (S: tStack): Boolean;

begin

NotEmpty := S.SP >0;

end;

function NotFull (S: tStack): Boolean;

begin

NotFull := S.SP < nmax;

end;

2.6. Ll(1) – драйвер

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

tSynTable = array [1..n] of record

Ch :char; {Символ}

Go :integer; {Переход}

Err :Boolean; {Ошибка}

Call :Boolean; {Вызов}

Read :Boolean; {Читать}

Proc: integer; {Процедура}

end;

Драйвер использует следующие переменные:

T: tSynTable; {Таблица}

Ch: char; {Текущий символ}

Err: integer; {Признак ошибки}

Stack: tStack; {Стек}

i: integer; {Номер состояния}

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

ResetText;

Init(Stack);

Push(Stack, 0);

Err := 0;

i := 1;

repeat

if (Ch=T[i].Ch) or (T[i].Ch = Любой) or

(T{i}.Ch = Цифра) and (Ch in [‘0’..’9’]);

than begin

if T[i].Proc <> 0 then Proc(T[i].Proc);

if T[i].Read then NextCh;

if T[i].Go = 0 then

Pop(Stack, i)

else begin

if t[i].Call then Push(Stack, i+1);

i:= T[i].Go;

end;

end

else if T[i].Err then

Err:=i

else

i:=i+1;

until (i=0) or (Err<>0);

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

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

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