MaterStudiorum.ru - домашняя страничка студента.
Минимум рекламы - максимум информации.


Авиация и космонавтика
Административное право
Арбитражный процесс
Архитектура
Астрология
Астрономия
Банковское дело
Безопасность жизнедеятельности
Биографии
Биология
Биология и химия
Биржевое дело
Ботаника и сельское хоз-во
Бухгалтерский учет и аудит
Валютные отношения
Ветеринария
Военная кафедра
География
Геодезия
Геология
Геополитика
Государство и право
Гражданское право и процесс
Делопроизводство
Деньги и кредит
Естествознание
Журналистика
Зоология
Издательское дело и полиграфия
Инвестиции
Иностранный язык
Информатика
Информатика, программирование
Исторические личности
История
История техники
Кибернетика
Коммуникации и связь
Компьютерные науки
Косметология
Краткое содержание произведений
Криминалистика
Криминология
Криптология
Кулинария
Культура и искусство
Культурология
Литература и русский язык
Литература(зарубежная)
Логика
Логистика
Маркетинг
Математика
Медицина, здоровье
Медицинские науки
Международное публичное право
Международное частное право
Международные отношения
Менеджмент
Металлургия
Москвоведение
Музыка
Муниципальное право
Налоги, налогообложение
Наука и техника
Начертательная геометрия
Новейшая история, политология
Оккультизм и уфология
Остальные рефераты
Педагогика
Полиграфия
Политология
Право
Право, юриспруденция
Предпринимательство
Промышленность, производство
Психология
Психология, педагогика
Радиоэлектроника
Разное
Реклама
Религия и мифология
Риторика
Сексология
Социология
Статистика
Страхование
Строительные науки
Строительство
Схемотехника
Таможенная система
Теория государства и права
Теория организации
Теплотехника
Технология
Товароведение
Транспорт
Трудовое право
Туризм
Уголовное право и процесс
Управление
Управленческие науки
Физика
Физкультура и спорт
Философия
Финансовые науки
Финансы
Фотография
Химия
Хозяйственное право
Цифровые устройства
Экологическое право
Экология
Экономика
Экономико-математическое моделирование
Экономическая география
Экономическая теория
Эргономика
Этика
Юриспруденция
Языковедение
Языкознание, филология
    Начало -> Информатика, программирование -> Синтаксический разбор строк и конечные автоматы

Название:Синтаксический разбор строк и конечные автоматы
Просмотров:74
Раздел:Информатика, программирование
Ссылка:Скачать(31 KB)
Описание:В этой статье речь пойдет о том, как анализировать информацию, переданную в виде последовательности символов (строку) и выделять из нее значимые элементы.

Университетская электронная библиотека.
www.infoliolib.info

Часть полного текста документа:

Синтаксический разбор строк и конечные автоматы Андрей Боровский
    В этой статье речь пойдет о том, как анализировать информацию, переданную в виде последовательности символов (строку) и выделять из нее значимые элементы. Мы рассмотрим сравнительно простые ситуации, с которыми программистам приходится сталкиваться при решении самых разных задач: разбор выражений с простой синтаксической структурой, но с довольно свободными правилами записи.
    Допустим, в программе, которую вы пишете, нужен модуль, анализирующий текст HTML-страницы. Мы напишем функцию, которая, получив строку, содержащую тэг, извлекала бы из этой строки все атрибуты тэга и их значения. Структуру тэга можно схематично представить следующим образом: На первый взгляд задача кажется очень простой, однако ситуация осложняется из-за достаточно мягких правил языка HTML. Между именем атрибута, знаком равенства и значением может стоять любое число разделительных символов (пробелов, символов табуляции и даже символов перехода на новую строку), или же разделительные символы могут вообще отсутствовать. Значения атрибутов могут быть либо заключены в кавычки, либо нет, при этом значение, заключенное в двойные кавычки, может содержать символы одинарных кавычек, и наоборот. Кроме того, не всем атрибутам тэгов присваиваются значения.
    Для решения указанной проблемы мы напишем функцию ParseTag, анализирующую переданный ей тэг и создающую списки атрибутов тэга и их значений. Функция ParseTag действует по принципу конечного автомата. Конечные автоматы и подобные им структуры широко применяются при обработке строк. Сферы наиболее частого применения конечных автоматов включают поиск подстрок по заданному образцу, обработку регулярных выражений (regular expressions), лексический и синтаксический анализ. Конечные автоматы широко применяются в трансляторах и интерпретаторах (не говоря уже о таких задачах, как проектирование логических устройств).
    Строгое определение конечных автоматов можно найти в любом учебнике по теории алгоритмов, мы же здесь ограничимся интуитивным определением. В каждый данный момент времени конечный автомат может находиться в одном из возможных состояний (число состояний, в которых может находиться конечный автомат - конечно). Автомат последовательно считывает символы входного текста (строки). Каждый считанный символ либо переводит автомат в новое состояние, либо оставляет его в прежнем состоянии. Формально автомат можно описать при помощи функции переходов. Аргументами этой функции являются предыдущее состояние автомата и очередной считанный символ, а значением - новое состояние автомата.
    Множество состояний для нашего автомата включает:
    ReadTag - читает имя тэга;
    WaitAttr - ожидает имя атрибута;
    WaitAttrOrEq - ожидает имя атрибута или символ '=';
    ReadAttr - читает имя атрибута;
    WaitValue - ожидает значение атрибута;
    ReadValue - читает значение атрибута без кавычек;
    ReadValueSQ - читает значение атрибута в одинарных кавычках;
    ReadValueDQ - читает значение атрибута в двойных кавычках.
    Следуя терминологии конечных автоматов, мы можем назвать состояния WaitAttr, WaitAttrOrEq, ReadAttr и ReadValue допускающими. Это означает, что если после обработки переданной строки автомат находится в каком-либо другом состоянии, значит, тэг содержит ошибку (автомат не проверяет, завершается ли строка символом '>', это - задача блока, вызывающего функцию ParseTag).
    Процесс программной реализации автомата можно упростить, построив для него диаграмму переходов. ............




Нет комментариев.



Оставить комментарий:

Ваше Имя:
Email:
Антибот:  
Ваш комментарий:  



Похожие работы:

Название:Декабрьские события 1986г в Казахстане и их историческое значение
Просмотров:76
Описание: Министерство образования и науки республики Казахстан Карагандинский Государственный Университет им. Е.А. Букетова Курсовая работа по дисциплине история Казахстана На тему: «Де

Название:Синтез керуючих автоматів
Просмотров:109
Описание: ВСТУП Принцип мікропрограмного керування припускає, що цифровий пристрій складається з двох частин: операційний автомат (ОА) і керуючий автомат (КА). ОА виконує найпростіші операції (мікрооперації) типу зсув,

Название:Причины и значение введения христианства на Руси
Просмотров:208
Описание: Тема «Причины и значение введения христианства на Руси» Севастополь 2010г. Введение В черноморских греческих городах, так же как и на Подунавье,

Название:Значение и особенности функционирования таможенных зон Российской Федерации
Просмотров:156
Описание: ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ГЛАВА 1. ТАМОЖЕННЫЕ ЗОНЫ, КАК МЕСТО ОСУЩЕСТВЛЕНИЯ ТАМОЖЕННОГО КОНТРОЛЯ 1.1 Понятие и значение таможенного контроля в таможенной политике России. Сущность понятия таможенных зон 1.2 Вид

Название:Автоматизированная система в здравоохранении
Просмотров:90
Описание: АСУ в здравоохранении ― это система управления медицинским учреждением, отраслью, основанная на регулярном применении современных математических методов и технических средств обработки данных в учете, анали

 
     

Вечно с вами © MaterStudiorum.ru