Реальная база готовых
студенческих работ

Авторам Вопрос-ответ

Узнайте стоимость индивидуальной работы!

Тип задания

Предмет

Ваше имя

Вы нашли то, что искали?

Да, спасибо!

Нет, пока не нашел

Узнайте стоимость индивидуальной работы

Тип задания

Предмет

Ваше имя

это быстро и бесплатно

Оформите заказ сейчас и получите скидку 100 руб.!

Тип задания

Предмет

Ваше имя

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

Тип Реферат

Предмет Информатика

Просмотров

1243

Размер файла

26 б

Ознакомительный фрагмент работы:

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

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

Андрей Боровский

В этой статье речь пойдет о том, как анализировать информацию, переданную в виде последовательности символов (строку) и выделять из нее значимые элементы. Мы рассмотрим сравнительно простые ситуации, с которыми программистам приходится сталкиваться при решении самых разных задач: разбор выражений с простой синтаксической структурой, но с довольно свободными правилами записи.

Допустим, в программе, которую вы пишете, нужен модуль, анализирующий текст HTML-страницы. Мы напишем функцию, которая, получив строку, содержащую тэг, извлекала бы из этой строки все атрибуты тэга и их значения. Структуру тэга можно схематично представить следующим образом: <ТЭГ атрибут1 = "значение" атрибут2 = "значение" ...> На первый взгляд задача кажется очень простой, однако ситуация осложняется из-за достаточно мягких правил языка HTML. Между именем атрибута, знаком равенства и значением может стоять любое число разделительных символов (пробелов, символов табуляции и даже символов перехода на новую строку), или же разделительные символы могут вообще отсутствовать. Значения атрибутов могут быть либо заключены в кавычки, либо нет, при этом значение, заключенное в двойные кавычки, может содержать символы одинарных кавычек, и наоборот. Кроме того, не всем атрибутам тэгов присваиваются значения.

Для решения указанной проблемы мы напишем функцию ParseTag, анализирующую переданный ей тэг и создающую списки атрибутов тэга и их значений. Функция ParseTag действует по принципу конечного автомата. Конечные автоматы и подобные им структуры широко применяются при обработке строк. Сферы наиболее частого применения конечных автоматов включают поиск подстрок по заданному образцу, обработку регулярных выражений (regular expressions), лексический и синтаксический анализ. Конечные автоматы широко применяются в трансляторах и интерпретаторах (не говоря уже о таких задачах, как проектирование логических устройств).

Строгое определение конечных автоматов можно найти в любом учебнике по теории алгоритмов, мы же здесь ограничимся интуитивным определением. В каждый данный момент времени конечный автомат может находиться в одном из возможных состояний (число состояний, в которых может находиться конечный автомат – конечно). Автомат последовательно считывает символы входного текста (строки). Каждый считанный символ либо переводит автомат в новое состояние, либо оставляет его в прежнем состоянии. Формально автомат можно описать при помощи функции переходов. Аргументами этой функции являются предыдущее состояние автомата и очередной считанный символ, а значением – новое состояние автомата.

Множество состояний для нашего автомата включает:

ReadTag – читает имя тэга;

WaitAttr – ожидает имя атрибута;

WaitAttrOrEq – ожидает имя атрибута или символ '=';

ReadAttr – читает имя атрибута;

WaitValue – ожидает значение атрибута;

ReadValue – читает значение атрибута без кавычек;

ReadValueSQ – читает значение атрибута в одинарных кавычках;

ReadValueDQ – читает значение атрибута в двойных кавычках.

Следуя терминологии конечных автоматов, мы можем назвать состояния WaitAttr, WaitAttrOrEq, ReadAttr и ReadValue допускающими. Это означает, что если после обработки переданной строки автомат находится в каком-либо другом состоянии, значит, тэг содержит ошибку (автомат не проверяет, завершается ли строка символом '>', это – задача блока, вызывающего функцию ParseTag).

Процесс программной реализации автомата можно упростить, построив для него диаграмму переходов. Далее приводится диаграмма переходов для нашего автомата. Цифры на диаграмме соответствуют номерам состояний, перечисленных выше.

Рисунок 1

Пояснения к диаграмме:

a - символ-разделитель

b - любой символ кроме разделителя

c - символ "="

d - любой символ кроме разделителя и символа "="

e - любой символ кроме разделителя и кавычек

f - символ одинарных кавычек

g - символ двойных кавычек

Ниже приводится текст функции ParseTag и вспомогательной функции GetSubString. У функции ParseTag есть четыре параметра: строка, содержащая тэг, заключенный в '<' и '>', строка, в которой возвращается имя тэга, и объекты типа TStringList, содержащие имена и значения атрибутов соответственно. Если данному атрибуту не сопоставлено никакое значение, в списке значений имени атрибута соответствует пустая строка. В случае успешного выполнения функция возвращает значение 0, в противном случае – 1.

Автомат реализован в теле цикла функции ParseTag. Добавление нового элемента в список осуществляется в момент перехода из состояния ReadXXX в какое-либо другое состояние. Кроме этого в цикл добавлена проверка ошибок синтаксиса, например, двух символов '=', следующих подряд. После завершения цикла мы анализируем состояния автомата. Если автомат находится в одном из состояний ReadXXX, происходит добавление последнего элемента в соответствующий список. Если автомат не находится ни в одном из допускающих состояний, функция возвращает сообщение о синтаксической ошибке.

function GetSubString(const S : String; Start, Stop : Integer):

String;

begin

SetLength(Result, Stop-Start);

Move(S[Start], Result[1], Stop-Start);

end;

function ParseTag(const Tag : String; var TagName : String;

Attrs, Values : TStringList): Integer;

type

// Возможныесостояния

TState = (ReadTag, WaitAttr, WaitAttrOrEq, ReadAttr, WaitValue,

ReadValue, ReadValueSQ, ReadValueDQ);

const

// Значения, возвращаемыефункцией GetLink

resOK = 0; // разбор прошел успешно

resBadSyntax = -1; // синтаксическая ошибка

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

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;

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;

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;

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

Фактически представленная функция выполняет две операции: выделяет в переданной строке синтаксические элементы (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;

InDigit:

case S[i] of

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

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

')' :

begin

Dec(ParCount);

State := InRPrnt;

end;

' ' : State := AfterDigit;

else

begin

Result := i;

Exit;

end;

AfterDigit:

case S[i] of

' ' : ;

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

')' :

begin

Dec(ParCount);

State := InRPrnt;

end;

else

begin

Result := i;

Exit;

end;

InOp :

case S[i] of

' ' : ;

'0'..'9' : State := InDigit;

'(' :

begin

Inc(ParCount);

State := InLPrnt;

end;

else

begin

Result := i;

Exit;

end;

InLPrnt:

case S[i] of

'0'..'9' : State := InDigit;

'-' : State := InOp;

'(' : Inc(ParCount);

' ' : ;

else

begin

Result := i;

Exit;

end;

InRPrnt:

case S[i] of

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

')' : Dec(ParCount);

' ' : ;

else

begin

Result := i;

Exit;

end;

end; // case State of

if State in [InLPrnt, InOp] then //Недопустимыесостояния

Result := Length(S);

if ParCount > 0 then Result := resRPrntMissing else

if ParCount < 0 then Result := resLPrntMissing;

end;

Входное математическое выражение может содержать целочисленные константы, символы арифметических операций и скобки. Между символами операций, скобками и числами допустимо любое количество пробелов. Функция CheckMath возвращает значение 0, если переданное ей выражение не содержит ошибок. Если выражение содержит ошибку, функция возвращает положительное число, соответствующее позиции символа, в которой была обнаружена ошибка. Если число открытых скобок не равно числу закрытых, функция возвращает либо -1, либо -2, в зависимости от того, каких скобок не хватает.

В данной функции задействованы следующие состояния:

Start – начальное состояние;

InDigit – прочитана цифра;

AfterDigit – прочитан разделитель после цифры;

InOp – прочитан символ арифметической операции;

InLPrnt – прочитана открывающая скобка;

InRPrnt – прочитана закрывающая скобка.

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

Смотреть

Проект сети для центра информационных технологий
Реферат, Информатика и программирование

Смотреть

Створення власних бібліотек компонентів в Protel 99
Реферат, Информатика и программирование

Смотреть

Мифы и реальности Internet - известные и скрытые возможности сети
Реферат, Информатика и программирование

Смотреть

Программа для оценки шахматной ситуации
Реферат, Информатика и программирование

Смотреть

Нет нужной работы в каталоге?

Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Если работа вас не устроит – мы вернем 100% суммы заказа

Наши менеджеры всегда на связи и оперативно решат любую проблему

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +

Новых работ ежедневно

Требуются доработки?
Они включены в стоимость работы

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

Математика

История

Экономика

159599
рейтинг

3275
работ сдано

1404
отзывов

Математика

Физика

История

156450
рейтинг

6068
работ сдано

2737
отзывов

Химия

Экономика

Биология

105734
рейтинг

2110
работ сдано

1318
отзывов

Высшая математика

Информатика

Геодезия

62710
рейтинг

1046
работ сдано

598
отзывов

Тип работы

Тгу им. Г. Р. Державина

Реферат сделан досрочно, преподавателю понравилось, я тоже в восторге. Спасибо Татьяне за ...

РЭУ им.Плеханово

Альберт хороший исполнитель, сделал реферат очень быстро, вечером заказала, утром уже все ...

ФЭК

Маринаааа, спасибо вам огромное! Вы профессионал своего дела! Рекомендую всем ✌🏽😎

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

Подогнать готовую курсовую под СТО

Курсовая, не знаю

Срок сдачи к 7 дек.

только что

Выполнить 2 контрольные работы по Информационные технологии и сети в нефтегазовой отрасли. М-07765

Контрольная, Информационные технологии

Срок сдачи к 12 дек.

только что

Выполнить задания

Другое, Товароведение

Срок сдачи к 6 дек.

1 минуту назад

Архитектура и организация конфигурации памяти вычислительной системы

Лабораторная, Архитектура средств вычислительной техники

Срок сдачи к 12 дек.

1 минуту назад

Организации профилактики травматизма в спортивных секциях в общеобразовательной школе

Курсовая, профилактики травматизма, медицина

Срок сдачи к 5 дек.

2 минуты назад

краткая характеристика сбербанка анализ тарифов РКО

Отчет по практике, дистанционное банковское обслуживание

Срок сдачи к 5 дек.

2 минуты назад

Исследование методов получения случайных чисел с заданным законом распределения

Лабораторная, Моделирование, математика

Срок сдачи к 10 дек.

4 минуты назад

Проектирование заготовок, получаемых литьем в песчано-глинистые формы

Лабораторная, основы технологии машиностроения

Срок сдачи к 14 дек.

4 минуты назад

2504

Презентация, ММУ одна

Срок сдачи к 7 дек.

6 минут назад

выполнить 3 задачи

Контрольная, Сопротивление материалов

Срок сдачи к 11 дек.

6 минут назад

Вам необходимо выбрать модель медиастратегии

Другое, Медиапланирование, реклама, маркетинг

Срок сдачи к 7 дек.

7 минут назад

Ответить на задания

Решение задач, Цифровизация процессов управления, информатика, программирование

Срок сдачи к 20 дек.

7 минут назад

Написать реферат по Информационные технологии и сети в нефтегазовой отрасли. М-07764

Реферат, Информационные технологии

Срок сдачи к 11 дек.

8 минут назад

Все на фото

Курсовая, Землеустройство

Срок сдачи к 12 дек.

9 минут назад

Написать реферат по Информационные технологии и сети в нефтегазовой отрасли. М-07764

Реферат, Геология

Срок сдачи к 11 дек.

10 минут назад

Разработка веб-информационной системы для автоматизации складских операций компании Hoff

Диплом, Логистические системы, логистика, информатика, программирование, теория автоматического управления

Срок сдачи к 1 мар.

10 минут назад

Нужно решить задание по информатике и математическому анализу (скрин...

Решение задач, Информатика

Срок сдачи к 5 дек.

11 минут назад

перевод текста, выполнение упражнений

Перевод с ин. языка, Немецкий язык

Срок сдачи к 7 дек.

11 минут назад

Закажи индивидуальную работу за 1 минуту!

Размещенные на сайт контрольные, курсовые и иные категории работ (далее — Работы) и их содержимое предназначены исключительно для ознакомления, без целей коммерческого использования. Все права в отношении Работ и их содержимого принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие в связи с использованием Работ и их содержимого.