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

end;

function TSymbStack.GetSymbol(iIdx: integer): TSymbol;

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

begin Result:= TSymbol(Items[iIdx]); end;

function TSymbStack.TopLexem: TLexem;

{ Функция, возвращающая самую верхнюю лексему в стеке }

var i: integer;

begin

Result:= nil; { Начальный результат функции пустой }

for i:=Count-1 downto 0 do{Для символов от вершины стека}

if Symbols[i].SymbType = SYMB_LEX then

begin { Если это терминальный символ }

Result:= Symbols[i].Lexem; {Берем ссылку на лексему}

Break; { Прекращаем поиск }

end;

end;

function TSymbStack.Push(lex: TLexem): TSymbol;

{ Функция помещения лексемы в синтаксический стек }

begin { Создаем новый терминальный символ }

Result:= TSymbol.CreateLex(lex);

Add(Result); { Добавляем его в стек }

end;

function TSymbStack.MakeTopSymb: TSymbol;

{ Функция, выполняющая свертку. Результат функции:

nil – если не удалось выполнить свертку, иначе – ссылка

на новый нетерминальный символ (если свертка выполнена).}

var

symCur: TSymbol; {Текущий символ стека}

SymbArr: TSymbArray;{Массив хранения символов правила}

i,iSymbN: integer;{Счетчики символов в стеке и в правиле}

sRuleStr: string; {Строковое представление правила}

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

procedure AddToRule(const sStr: string;{Строка символа}

sym: TSymbol{Тек. символ});

begin

symCur:= sym; { Устанавливаем ссылку на текущий символ }

{ Добавляем очередной символ в массив символов правила }

SymbArr[iSymbN]:= Symbols[i];

{ Добавляем его в строку правила (слева!) }

sRuleStr:= sStr + sRuleStr;

Delete(i); { Удаляем символ из стека }

Inc(iSymbN); { Увеличиваем счетчик символов в правиле }

end;

begin

Result:= nil; { Сначала обнуляем результат функции }

iSymbN:= 0; { Сбрасываем счетчик символов }

symCur:= nil; { Обнуляем текущий символ }

sRuleStr:= ; { Сначала строка правила пустая }

for i:=Count-1 downto 0 do{ Выполняем алгоритм }

begin { Для всех символов начиная с вершины стека }

if Symbols[i].SymbType = SYMB_SYNT then

{ Если это нетерминальный символ, то добавляем его

в правило, текущий символ при этом не меняется }

AddToRule(Symbols[i].SymbolStr,symCur)

else { Если это терминальный символ }

if symCur = nil then {и текущий символ пустой }

{ Добавляем его в правило и делаем текущим }

AddToRule(LexTypeInfo(Symbols[i].Lexem.LexType),

Symbols[i])

else { Если это терминальный символ и он связан

отношением "=" с текущим символом }

if GramMatrix[Symbols[i].Lexem.LexType,

symCur.Lexem.LexType] = = then

{ Добавляем его в правило и делаем текущим }

AddToRule(LexTypeInfo(Symbols[i].Lexem.LexType),

Symbols[i])

else { Иначе – прерываем цикл, дальше искать не нужно }

Break;

if iSymbN > RULE_LENGTH then Break; { Если превышена

максимальная длина правила, цикл прекращаем }

end;

if iSymbN <> 0 then

begin { Если выбран хотя бы один символ из стека, то

ищем простым перебором правило, у которого строковое

представление совпадает с построенной строкой }

for i:=1 to RULE_NUM do

if GramRules[i] = sRuleStr then{Если правило найдено,}

begin { создаем новый нетерминальный символ }

Result:= TSymbol.CreateSymb(i,iSymbN,SymbArr);

Add(Result); { и добавляем его в стек. }

Break; { Прерываем цикл поиска правил }

end;

{ Если не был создан новый символ (правило не найдено),

надо удалить все исходные символы, это ошибка }

if Result = nil then

for i:=0 to iSymbN-1 do SymbArr[i].Free;

end;

end;

function BuildSyntList(

const listLex: TLexList{входная таблица лексем};

symbStack: TSymbStack{стек для работы алгоритма}

): TSymbol;

{ Функция, выполняющая алгоритм «сдвиг-свертка».

Результат функции:

– нетерминальный символ (корень синтаксического дерева),

если разбор был выполнен успешно;

– терминальный символ, ссылающийся на лексему, где была

обнаружена ошибка, если разбор выполнен с ошибками. }

var

i,iCnt: integer; {счетчик лексем и длина таблицы лексем}

lexStop: TLexem; { Ссылка на начальную лексему }

lexTCur: TLexType; { Тип текущей лексемы }

cRule: char;{ Текущее отношение предшествования }

begin

Result:= nil; { Сначала результат функции пустой }

iCnt:= listLex.Count-1; { Берем длину таблицы лексем }

{ Создаем дополнительную лексему «начало строки» }

lexStop:= TLexem.CreateInfo('Начало файла',0,0,0);

try { Помещаем начальную лексему в стек }

symbStack.Push(lexStop);

i:= 0; { Обнуляем счетчик входных лексем }

while i<=iCnt do { Цикл по всем лексемам от начала }

begin { до конца таблицы лексем }

{ Получаем тип лексемы на вершине стека }

lexTCur:= symbStack.TopLexem.LexType;

{ Если на вершине стека начальная лексема,

а текущая лексема – конечная, то разбор завершен }

if (lexTCur = LEX_START)

and (listLex[i].LexType = LEX_START) then Break;

{ Смотрим отношение лексемы на вершине стека

и текущей лексемы в строке }

cRule:= GramMatrix[lexTCur,listLex[i].LexType];

{ Корректируем отношение. Если корректировка матрицы

предшествования не используется, то функция должна

вернуть то же самое отношение }

cRule:= CorrectRule(cRule,lexTCur,

listLex[i].LexType,symbStack);

case cRule of

'<, =: { Надо выполнять сдвиг (перенос) }

begin { Помещаем текущую лексему в стек }

symbStack.Push(listLex[i]);

Inc(i); { Увеличиваем счетчик входных лексем }

end;

'>: { Надо выполнять свертку }

if symbStack.MakeTopSymb = nil then

begin { Если не удалось выполнить свертку, }

{ запоминаем текущую лексему как место ошибки }

Result:= TSymbol.CreateLex(listLex[i]);

Break; { Прерываем алгоритм }

end;

else { Отношение не установлено – ошибка разбора }

begin {Запоминаем текущую лексему (место ошибки)}

Result:= TSymbol.CreateLex(listLex[i]);

Break; { Прерываем алгоритм }

end;

end{case};

end{while};

if Result = nil then { Если разбор прошел без ошибок }

begin{Убеждаемся, что в стеке осталось только 2 символа}

if symbStack.Count = 2 then

{ Если да, то верхний символ – результат разбора }

Result:= symbStack[1]

{ Иначе это ошибка – отмечаем место ошибки }

else Result:= TSymbol.CreateLex(listLex[iCnt]);

end;

finally { Уничтожаем временную начальную лексему }

lexStop.Free;

end;

end;

end.

unit TrdType; {!!! Зависит от входного языка!!!}

interface

{ Модуль для описания допустимых типов триад }

const { Имена предопределенных функций и переменных }

NAME_PROG = 'MyCurs';

NAME_INPVAR = 'InpVar';

NAME_RESULT = 'Result';

NAME_FUNCT = 'CompileTest';

NAME_TYPE = 'integer';

type { Типы триад, соответствующие типам допустимых

операций, а также три дополнительных типа триад:

– CONST – для алгоритма свертки объектного кода;

– SAME – для алгоритма исключения лишних операций;