Синтаксический разбор строк и конечные автоматы

Информация - Компьютеры, программирование

Другие материалы по предмету Компьютеры, программирование

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



ых разделительных символов

Delimeters = [ , #9, #13, #10];

var

State : TState;

StartPos, i : Integer;

begin

Result := resOK;

// очищаем список элементов

Attrs.Clear;

Values.Clear;

State := ReadTag; // входное состояние автомата

i := 2; // пропускаем символ <

while (Tag[i]) and (i<Length(Tag)) do

begin

case State of

ReadTag:

if Tag[i] in Delimeters then

begin

// чтение имени тэга закончено

TagName := GetSubString(Tag, StartPos, i);

State := WaitAttr;

end;

WaitAttr:

if (Tag[i] in Delimeters) = False then

begin

if Tag[i] = = then

begin

Result := resBadSyntax;

Exit;

end;

StartPos := i;

State := ReadAttr;

end;

ReadAttr:

if (Tag[i] in Delimeters) or (Tag[i] = =) then

begin

// чтение имени атрибута закончено, добавляем имя атрибута в список

Attrs.Add(GetSubString(Tag, StartPos, i));

if Tag[i] = = then State := WaitValue

else State := WaitAttrOrEq;

end;

WaitAttrOrEq:

if (Tag[i] in Delimeters) = False then

begin

if Tag[i] = = then State := WaitValue else

begin

// начинается чтение имени атрибута

// предыдущему атрибуту не присвоено никаких значений,

// добавляем пустую строку в список Values

Values.Add();

State := ReadAttr;

StartPos := i;

end;

end;

WaitValue:

if (Tag[i] in Delimeters) = False then

begin

if Tag[i] = = then

begin

// два символа = подряд

Result := resBadSyntax;

Exit;

end;

if Tag[i] = " then

begin

// чтение значения начнется со следующего символа после кавычек:

StartPos := i + 1;

State := ReadValueDQ;

end else

if Tag[i] = then

begin

// чтение значения начнется со следующего символа после кавычек:

StartPos := i + 1;

State := ReadValueSQ;

end else

begin

// чтение значения без кавычек

StartPos := i;

State := ReadValue;

end;

end;

ReadValue:

if Tag[i] in Delimeters then

begin

// чтение значения закончено

Values.Add(GetSubString(Tag, StartPos, i));

State := WaitAttr;

end;

ReadValueDQ:

if Tag[i] = " then

begin

// чтение значения в двойных кавычках закончено

Values.Add(GetSubString(Tag, StartPos, i));

State := WaitAttr;

end;

ReadValueSQ:

if Tag[i] = then

begin

// чтение значения в одинарных кавычках закончено

Values.Add(GetSubString(Tag, StartPos, i));

State := WaitAttr;

end;

end; // case State of

Inc(i);

end; // while (Body[i]) and (i<Length(Tag)) do

// проверяем состояние автомата после обработки строки

// последним символом строки должен быть >

case State of

ReadValue : Values.Add(GetSubString(Tag, StartPos, i));

ReadAttr : Attrs.Add(GetSubString(Tag, StartPos, i));

ReadTag : TagName := GetSubString(Tag, StartPos, i);

WaitAttr, WaitAttrOrEq: ; // ничего не делаем

else Result := resBadSyntax; // другие состояния недопустимы

end;

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

Фактически представленная функция выполняет две операции: выделяет в переданной строке синтаксические элементы (tokens) и определяет, что представляет собой данный элемент (имя тэга, имя атрибута, значение атрибута). Решение о том, чем является следующий элемент, принимается заранее, на основании данных о предыдущем элементе и простых правил: за именем тэга следует имя атрибута; за именем атрибута следует либо имя атрибута, либо символ =; за символом = следует значение атрибута.

Процедуры, основанные на конечных автоматах, широко применяются для проверки синтаксиса. В качестве примера рассмотрим функцию CheckMath, выполняющую синтаксический анализ математического выражения:

function CheckMath(const S : String) : Integer;

type

TState = (Start, InDigit, AfterDigit, InOp, InLPrnt, InRPrnt);

const

resLPrntMissing = -1;

resRPrntMissing = -2;

var

State : TState;

i, ParCount : Integer;

begin

Result := 0;

ParCount := 0; // счетчик скобок

State := Start;

for i := 1 to Length(S) do

case State of

Start: // входное состояние

case S[i] of

: ; // состояние не меняется

0..9 : State := InDigit;

- : State := InOp; // символ - перед числом или скобкой

( :

begin

Inc(ParCount);

State := InLPrnt;

end;

else

begin

// Синтаксическая ошибка

Result := i;

Exit;

end;

end;

InDigit:

case S[i] of

0..9 : ; // состояние не меняется

+, -, *, / : State := InOp;

) :

begin

Dec(ParCount);

State := InRPrnt;

end;

: State := AfterDigit;

else

begin

Result := i;

Exit;

end;

end;

AfterDigit:

case S[i] of

: ;

+, -, *, / : State := InOp;

) :

begin

Dec(ParCount);

State := InRPrnt;

end;

else

begin

Result := i;

Exit;

end;

end;

InOp :

case S[i] of

: ;

0..9 : State := InDigit;

( :

begin

Inc(ParCount);

State := InLPrnt;

end;

else

begin

Result := i;

Exit;

end;

end;

InLPrnt:

case S[i] of

0..9 : State := InDigit;

- : State := InOp;

( : Inc(ParCount);

: ;

else

begin

Result := i;

Exit;

end;

end;

InRPrnt:

s