Книга: Системное программное обеспечение. Лабораторный практикум

Листинг П3.7. Описание структур данных синтаксического анализатора и реализация алгоритма «сдвиг-свертка»

unit SyntSymb;

interface

{ Модуль, обеспечивающий выполнение функций синтаксического

разбора с помощью алгоритма «сдвиг-свертка» }

uses Classes, LexElem, SyntRule;

{ Типы символов: терминальные (лексемы) и нетерминальные }

type TSymbKind = (SYMB_LEX, SYMB_SYNT);

TSymbInfo = record{Структура данных для символа грамматики}

case SymbType: TSymbKind of { Тип символа }

{ Для терминального символа – ссылка на лексему }

SYMB_LEX: (LexOne: TLexem);

{ Для нетерминального символа – ссылка на список

символов, из которых он был построен }

SYMB_SYNT: (LexList: TList);

end;

TSymbol = class; {Предварительное описание класса «Символ»}

{ Массив символов, составляющих правило грамматики }

TSymbArray = array[0..RULE_LENGTH] of TSymbol;

TSymbol = class(TObject)

protected { Структура, описывающая грамматический символ }

SymbInfo: TSymbInfo; { Информация о символе }

iRuleNum: integer; {Номер правила, которым создан символ}

public

{ Конструктор создания терминального символа по лексеме }

constructor CreateLex(Lex: TLexem);

{ Конструктор создания нетерминального символа }

constructor CreateSymb(iR,iSymbN: integer;

const SymbArr: TSymbArray);

{ Деструктор для удаления символа }

destructor Destroy; override;

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

function GetItem(iIdx: integer): TSymbol;

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

function Count: integer;

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

function SymbolStr: string;

{ Свойство, возвращающее тип символа }

property SymbType: TSymbKind read SymbInfo.SymbType;

{Свойство «Ссылка на лексему» для терминального символа}

property Lexem: TLexem read SymbInfo.LexOne;

{ Свойство, возвращающее символ правила по номеру }

property Items[i: integer]: TSymbol read GetItem; default;

{ Свойство, возвращающее номер правила }

property Rule: integer read iRuleNum;

end;

TSymbStack = class(TList)

public { Структура, описывающая синтаксический стек }

destructor Destroy; override; { Деструктор для стека }

procedure Clear; override; { Функция очистки стека }

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

function GetSymbol(iIdx: integer): TSymbol;

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

function Push(lex: TLexem): TSymbol;

{ Свойство выборки символа по номеру от вершины стека }

property Symbols[iIdx: integer]: TSymbol read GetSymbol;

default;

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

function TopLexem: TLexem;

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

на вершину стека }

function MakeTopSymb: TSymbol;

end;

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

function BuildSyntList(const listLex: TLexList;

symbStack: TSymbStack): TSymbol;

implementation

uses LexType, LexAuto;

constructor TSymbol.CreateLex(Lex: TLexem);

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

begin

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

SymbInfo.SymbType:= SYMB_LEX;{Ставим тип «терминальный»}

SymbInfo.LexOne:= Lex; { Запоминаем ссылку на лексему }

iRuleNum:= 0; { Правило не используется, поэтому «0» }

end;

constructor TSymbol.CreateSymb(iR{Номер правила},

iSymbN{количество исходных символов}: integer;

const SymbArr: TSymbArray{Массив исходных символов});

{ Конструктор создания нетерминального символа

на основе правила и массива символов }

var i: integer;

begin

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

{ Тип символа «нетерминальный» }

SymbInfo.SymbType:= SYMB_SYNT;

{ Создаем список для хранения исходных символов }

SymbInfo.LexList:= TList.Create;

{Переносим исходные символы в список в обратном порядке}

for i:=iSymbN-1 downto 0 do

SymbInfo.LexList.Add(SymbArr[i]);

iRuleNum:= iR; { Запоминаем номер правила }

end;

function TSymbol.GetItem(iIdx: integer): TSymbol;

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

begin Result:= TSymbol(SymbInfo.LexList[iIdx]) end;

function TSymbol.Count: integer;

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

begin Result:= SymbInfo.LexList.Count; end;

function TSymbol.SymbolStr: string;

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

begin { Если это нетерминальный символ, формируем его

представление в зависимости от номера правила }

if SymbType = SYMB_SYNT then

Result:= MakeSymbolStr(iRuleNum)

{ Если это терминальный символ, формируем его

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

else Result:= Lexem.LexInfoStr;

end;

destructor TSymbol.Destroy;

{ Деструктор для удаления символа }

var i: integer;

begin

if SymbInfo.SymbType = SYMB_SYNT then

with SymbInfo.LexList do

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

{ удаляем все его исходные символы из списка }

for i:=Count-1 downto 0 do TSymbol(Items[i]). Free;

Free; { Удаляем сам список символов }

end;

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

end;

destructor TSymbStack.Destroy;

{ Деструктор для удаления синтаксического стека }

begin

Clear; { Очищаем стек }

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

end;

procedure TSymbStack.Clear;

{ Функция очистки синтаксического стека }

var i: integer;

begin { Удаляем все символы из стека }

for i:=Count-1 downto 0 do TSymbol(Items[i]). Free;

inherited Clear; { Вызываем функцию базового класса }

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.

Оглавление книги