Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

Условные обозначения:

• А – любой алфавитно-цифровой символ;

• А(*) – любой алфавитно-цифровой символ, кроме перечисленных в скобках;

• П – любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки);

• Б – любая буква английского алфавита (прописная или строчная) или символ подчеркивания («_»);

• Б(*) – любая буква английского алфавита (прописная или строчная) или символ подчеркивания («_»), кроме перечисленных в скобках;

• Ц– любая цифра от 0 до 9;

• F – функция обработки таблицы лексем, вызываемая при переходе КА из одного состояния в другое, обозначения ее аргументов:

v – переменная, запомненная при работе КА;

d – константа, запомненная при работе КА;

a – текущий входной символ КА.

В остальных случаях аргументом функции F является соответствующая лексема.

Конечный автомат:

M(Q,Σ,δ,q 0,F):

Q = {H, C, C1, G, S, L, V, D, P1, P2, P3, P4, E1, E2, E3, I1, I2, L2, L3, L4, B1, B2, B3, B4, B5, W1, W2, W3, W4, W5, O1, O2, D1, D2, X1, X2, X3, A1, A2, A3, N1, N2, N3, F}

Σ = А (все допустимые алфавитно-цифровые символы); q 0= H; F = {F, S}.

В таблице П2.1. указаны значения функции переходов δ.

При описании функции переходов через разделитель «|» указаны вызовы функции F, необходимые при выполнении того или иного перехода (если они есть).

Следует обратить внимание, что функция Upper в листинге П3.1 построена на основе условной компиляции:

• если при компиляции определено имя «REGNAME», то таблицы идентификаторов строятся на основе имен переменных, не зависящих от регистра символов (прописные и строчные буквы не различаются);

• если при компиляции имя «REGNAME» не определено, то таблицы идентификаторов строятся на основе имен переменных, зависящих от регистра символов (прописные и строчные буквы различаются).

unit TblElem;

interface

{ Модуль, описывающий структуру данных элементов

таблицы идентификаторов }

type

TAddVarInfo = class(TObject) { Класс для описания базового

типа данных, связанных с элементом таблицы идентификаторов}

public

procedure SetInfo(iIdx: integer; iInfo: longint);

virtual; abstract;

function GetInfo(iIdx: integer): longint;

virtual; abstract;

property Info[iIdx: integer]: longint

read GetInfo write SetInfo; default;

end;

TVarInfo = class(TObject)

protected { Класс для описания элемента хэш-таблицы }

sName: string; { Имя элемента }

pInfo: TAddVarInfo; { Дополнительная информация }

minEl,maxEl: TVarInfo; { Ссылки на меньший и больший

элементы для организации бинарного дерева }

public

{ Конструктор создания элемента хэш-таблицы }

constructor Create(const sN: string);

{ Деструктор для освобождения памяти, занятой элементом }

destructor Destroy; override;

{ Функция заполнения дополнительной информации элемента }

procedure SetInfo(pI: TAddVarInfo);

{ Функции для удаления дополнительной информации }

procedure ClearInfo;

procedure ClearAllInfo;

{ Свойства «Имя элемента» и «Дополнительная информация» }

property VarName: string read sName;

property Info: TAddVarInfo read pInfo write SetInfo;

{ Функции для добавления элемента в бинарное дерево }

function AddElCnt(const sAdd: string;

var iCnt: integer): TVarInfo;

function AddElem(const sAdd: string): TVarInfo;

{ Функции для поиска элемента в бинарном дереве }

function FindElCnt(const sN: string;

var iCnt: integer): TVarInfo;

function FindElem(const sN: string): TVarInfo;

{Функция записи всех имен идентификаторов в одну строку}

function GetElList(const sLim,sInp,sOut: string): string;

end;

function Upper(const x: string): string;

implementation

uses SysUtils;

{ Условная компиляция: если определено имя REGNAME,

то имена переменных считаются регистронезависимыми,

иначе – регистрозависимыми }

{$IFDEF REGNAME}

function Upper(const x: string): string;

begin Result:= UpperCase(x); end;

{$ELSE}

function Upper(const x: string): string;

begin Result:= x; end;

{$ENDIF}

constructor TVarInfo.Create(const sN: string);

{ Конструктор создания элемента хэш-таблицы }

begin

inherited Create; {Вызываем конструктор базового класса}

{ Запоминаем имя элемента и обнуляем все ссылки }

sName:= sN; pInfo:= nil;

minEl:= nil; maxEl:= nil;

end;

destructor TVarInfo.Destroy;

{ Деструктор для освобождения памяти, занятой элементом }

begin

{Освобождаем память по каждой ссылке, при этом в дереве

рекурсивно будет освобождена память для всех элементов}

ClearAllInfo;

minEl.Free; maxEl.Free;

inherited Destroy; {Вызываем деструктор базового класса}

end;

function TVarInfo.GetElList(const sLim{разделитель списка},

sInp,sOut{имена, не включаемые в строку}: string): string;

{ Функция записи всех имен идентификаторов в одну строку }

var sAdd: string;

begin

Result:= ; { Первоначально строка пуста }

{ Если элемент таблицы не совпадает с одним

из невключаемых имен, то его нужно включить в строку }

if (Upper(sName) <> Upper(sInp))

and (Upper(sName) <> Upper(sOut)) then Result:= sName;

if minEl <> nil then { Если есть левая ветвь дерева }

begin { Вычисляем строку для этой ветви }

sAdd:= minEl.GetElList(sLim,sInp,sOut);

if sAdd <> then { Если она не пустая, }

begin { добавляем ее через разделитель }

if Result <> then Result:= Result + sLim + sAdd

else Result:= sAdd;

end;

end;

if maxEl <> nil then { Если есть правая ветвь дерева }

begin { Вычисляем строку для этой ветви }

sAdd:= maxEl.GetElList(sLim,sInp,sOut);

if sAdd <> then { Если она не пустая, }

begin { добавляем ее через разделитель }

if Result <> then Result:= Result + sLim + sAdd

else Result:= sAdd;

end;

end;

end;

procedure TVarInfo.SetInfo(pI: TAddVarInfo);

{ Функция заполнения дополнительной информации элемента }

begin pInfo:= pI; end;

procedure TVarInfo.ClearInfo;

{ Функция удаления дополнительной информации элемента }

begin pInfo.Free; pInfo:= nil; end;

procedure TVarInfo.ClearAllInfo;

{ Функция удаления связок и дополнительной информации }