Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Курсовой проект

по дисциплине «Системное программирование»

Тема: Разработка приложения «Парсер текста»

Выполнил: Андреев Д.А.

Руководитель кафедры СИ Веселов А.В.

Улан-Удэ

2019

Задание на курсовой проект

Дисциплина: Системное программирование

Тема: Разработка приложения «Парсер текста»

Краткое содержание проекта: Необходимо разработать программу "Парсер текста" выполняющую основные текстовые операции в среде программирования Python.

1.Теоретическая часть: словесная постановка задачи, анализ предметной области задачи, основные понятия, краткое описание существующих методов и алгоритмов, описание выбранного метода

2. Практическая часть:

Сроки выполнения проекта по графику:

1. Теоретический раздел - 25% к 3 неделе.

2. Основной раздел. Проектирование. - 50% к 4 неделе.

3. Основной раздел. Кодирование. - 80% к 6 неделе.

4. Экспериментальный раздел. - 95% к 7 неделе.

5. Защита. - 100% к 8 неделе.

Требования к оформлению:

1. Расчетно-пояснительная записка курсового проекта должна быть представлена в электронной и твердой копиях.

2. Объем РПЗ должен быть не менее 20 машинописных страниц без учета приложений.

Аннотация

Данный курсовой проект посвящен разработке приложения «Парсер текста».

Целью данного курсового проекта является создание программы "Парсер текста", которая и будет являться объектом исследования. Приобретение и закрепление навыков в организации вычислительных процессов и программирования на алгоритмическом языке.

Содержание

• Введение
• 1. Аналитический раздел
• 1.1 Словесная постановка задачи
• 1.2 Анализ предметной области
• 1.3 Обзор и анализ существующих программных решений
• 1.4 Определение функциональных требований
• 2. Проектный раздел
• 2.1 Выбор языка и среды программирования
• 2.2 Организация данных
• 3. Программный раздел
• 2.3 Определение структуры и состава программной системы
• 2.4 Описание разработанных алгоритмов программы
• 4. Тестирование программы
• 5. Методика проведения и результаты тестирования
• Заключение
• Список литературы

Введение

В общем смысле, парсинг - это линейное сопоставление последовательности слов с правилами языка. Парсинг сайтов - последовательный синтаксический анализ информации, размещённой на интернет-страницах. Текст интернет-страниц представляет собой иерархичный набор данных, структурированный с помощью человеческих и компьютерных языков. На человеческом языке предоставлена информация, знания, ради которых, собственно, люди и пользуются Интернетом. Компьютерные языки (html, JavaScript, css) определяют, как информация выглядит на мониторе.

Парсинг сайтов является эффективным решением для автоматизации сбора и изменения информации.

По сравнению с человеком, компьютерная программа-парсер:

- быстро обойдёт тысячи веб-страниц;

- аккуратно отделит техническую информацию от «человеческой»;

- безошибочно отберёт нужное и отбросит лишнее;

- эффективно упакует конечные данные в необходимом виде.

Цель: приобретение и закрепление навыков в организации вычислительных процессов и программирования на алгоритмическом языке.

Для достижения поставленной цели необходимо выполнить следующие задачи:

- программа должна работать в графическом режиме;

- в программе должны использоваться кнопки для ввода данных (операций) и графическое меню;

- программа должна содержать поле для ввода данных и вывода результата.

- программа должна выводить результат парсинга.

1. Аналитический раздел

1.1 Словесная постановка задачи

В этой задаче нам нужно создать парсер текста.

1.2 Анализ предметной области

Парсинг (Parsing) - это принятое в информатике определение синтаксического анализа. Для этого создается математическая модель сравнения лексем с формальной грамматикой, описанная одним из языков программирования. Например, PHP, Perl, Ruby, Python.

Когда человек читает, то, с точки зрения науки филологии, он совершает синтаксический анализ, сравнивая увиденные на бумаге слова (лексемы) с теми, что есть в его словарном запасе (формальной грамматикой).

Как работает парсинг, что это такое? Алгоритм работы парсера.

Независимо от того на каком формальном языке программирования написан парсер, алгоритм его действия остается одинаковым:

1) выход в интернет, получение доступа к коду веб-ресурса и его скачивание;

2) чтение, извлечение и обработка данных;

3) представление извлеченных данных в удобоваримом виде - файлы.txt,.sql,.xml,.html и других форматах.

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

Сбор информации в интернете - трудоемкая, рутинная, отнимающая много времени работа. Парсеры, способные в течение суток перебрать большую часть веб-ресурсов в поисках нужной информации, автоматизируют ее. Наиболее активно «парсят» всемирную сеть роботы поисковых систем. Но информация собирается парсерами и в частных интересах. На ее основе, например, можно написать диссертацию. Парсинг используют программы автоматической проверки уникальности текстовой информации, быстро сравнивая содержимое сотен веб-страниц с предложенным текстом. Без программ парсинга владельцам интернет-магазинов, которым требуются сотни однотипных описаний товаров, технических характеристик и другого контента, не являющегося интеллектуальной собственностью, было бы трудно вручную заполнять характеристики товаров.

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

Разновидности парсинга

Parsing позволяет осуществлять работу с данными любой тематики. Среди основных сфер применения такой технологии можно выделить:

- поиск и наполнение ресурсов текстовым и мультимедийным контентом;

- товары и цены в интернет-магазинах;

- данные из объявлений, размещенных на специальных ресурсах;

- поиск и сбор контактных данных пользователей;

- в рамках социальных сетей (например, отзывы и комментарии);

- сайты, специализирующиеся на публикации спортивных результатов.

Основа работы парсера.

Конечно же, парсеры не читают текста, они всего лишь сравнивают предложенный набор слов с тем, что обнаружили в интернете и действуют по заданной программе. То, как поисковый робот должен поступить с найденным контентом, написано в командной строке, содержащей набор букв, слов, выражений и знаков программного синтаксиса. Такая командная строка называется «регулярное выражение». Русские программисты используют жаргонные слова «маска» и «шаблон».

Чтобы парсер понимал регулярные выражения, он должен быть написан на языке, поддерживающем их в работе со строками. Такая возможность есть в РНР, Perl. Регулярные выражения описываются синтаксисом Unix, который хотя и считается устаревшим, но широко применяется благодаря свойству обратной совместимости.

Синтаксис Unix позволяет регулировать активность парсинга, делая его «ленивым», «жадным» и даже «сверхжадным». От этого параметра зависит длина строки, которую парсер копирует с веб-ресурса. Сверхжадный парсинг получает весь контент страницы, её HTML-код и внешнюю таблицу CSS.

Парсеры и PHP.

Этот серверный язык удобен для создания парсеров:

- У него есть встроенная библиотека libcurl, с помощью которой скрипт подключается к любым типам серверов, в том числе работающих по протоколам https (зашифрованное соеди-нение), ftp, telnet.

- PHP поддерживает регулярные выражения, с помощью которых парсер обрабатывает данные.

- У него есть библиотека DOM для работы с XML - расширяемым языком разметки текста, на котором обычно представляются результаты работы парсера.

- Он отлично ладит с HTML, поскольку создавался для его автоматической генерации.

Этические и технические сложности парсинга

Вопрос о том, является ли парсинг воровством контента, активно обсуждается во Всемирной сети. Большинство оппонентов считают, что заимствование части контента, не являющегося интеллектуальной собственностью, например, технических описаний, допустимо. Ссылка на первоисточник контента рассматривается как способ частичной легитимации. В то же время, наглое копирование, включая грамматические ошибки, осуждается интернет-сообществом, а поисковыми системами рассматривается как повод для блокировки ресурса.

Парсер можно написать самому или заказать на бирже фриланса, если вам требуются конкретные условия для поиска и чтения информации. Или купить эту программу в готовом виде с усредненным функционалом на специализированном веб-ресурсе.

1.3 Обзор и анализ существующих программных решений

Для этого необходимо изучить следующие существующие решения. Сегодня повсеместное использование парсеров существенно облегчает работу человека в самых различных сферах.

При парсинге исходный текст преобразуется в структуру данных, обычно - в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.

Для того чтобы определить происхождение парсинга придется обратиться в недалекое прошлое.

1960 - Выпущена спецификация ALGOL 60, в которой впервые описан язык с блочной структурой. Комитету ALGOL хорошо известно, что никто не знает, как парсить такой язык. Но они считают, что, если они детально описали язык с блочной структурой, то для него будет изобретен анализатор/парсер. Рискованный подход, который впоследствии окупился.

1961 - Нед Айронс выпускает свой парсер ALGOL. Фактически, алгоритм Айронса является первым подобным анализатором, который был описан в печати. Парсер Неда является лево-рекурсивным (форма рекурсивного спуска) парсером. В отличие от современного рекурсивного спуска, алгоритм Айронса носит общий характер и является синтаксически-управляемым. «Общий» означает, что они могут разобрать что написано в БНФ (форма Бэкуса - Наура - формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории). «Синтаксически-управляемый» (декларативный) означает, что анализатор фактически создается из БНФ - парсер не нужно создавать самому.

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

- В 1960-х память и CPU очень ограничены. Ручное кодирование (hand-coding) окупается даже тогда, когда выигрыш от его применения мал.

- Чистый леворекурсивный анализ - очень слабый метод синтаксического анализа. Ручному кодированию часто приходится преодолевать эти ограничения. Это утверждение верно, как в 1961, так и в наши дни.

- Леворекурсивный анализ хорошо работает в сочетании с ручным кодированием - они дополняют друг друга.

1965 - Дональд Кнут (Don Knuth) изобретает алгоритм LR. Ученый в первую очередь заинтересован в математической стороне задачи. Кнут описывает алгоритм анализа, но его подход считается непрактичным.

1968 - Джей Эрли (Jay Earley) изобретает алгоритм, названный в его честь. Как и алгоритм Irons, алгоритм Эрли является синтаксически-управляемым и носит общий характер. В отличие от алгоритма Irons, не использует метод поиска с возвратом. Основная идея Эрли состоит в том, чтобы отслеживать этапы работы алгоритма в таблицах. Алгоритм Эрли заманчив, но имеет три основных недостатка:

- Во-первых, есть ошибка в обработке правил нулевой длины.

- Во-вторых, при право-сторонней рекурсии необходимо применять алгоритм дважды.

- В-третьих, чтобы создать таблицы, необходимо вести учёт системных ресурсов, что, по меркам аппаратных средств 1968 года, является довольно сложной задачей.

1969 - Фрэнк ДеРемер (Frank DeRemer) описывает новый вариант LR Кнута. Для алгоритма LALR ДеРемера необходим только стек и таблица состояний, размер которой можно легко изменить.

1972 - Ахо (Aho) и Алманн (Ullmann) описали простой способ исправить ошибку правила нулевой длины в оригинальном алгоритме Эрли. К сожалению, это исправление требует даже больше системных ресурсов, чем алгоритм Эрли.

1975 - Белл Лэбс (Bell Labs) преобразует свой компилятор языка C из самокодируемого рекурсивного спуска в алгоритм LALR ДеРемера.

1977 - Выходит первая «Книга дракона». Этот, вскоре ставший классическим, учебник назван так из-за обложки, на которой изображен рыцарь, бросающий вызов дракону. На копье рыцаря выгравированы буквы «LALR». Впредь, говорить легкомысленно LALR -- значит запятнать герб теории синтаксического анализа.

1979 - Bell Labs выпустила новую версию UNIX -- седьмую. V7 включает в себя безусловно наиболее полный, полезный и доступный инструментарий для разработки компиляторов. Центральное место занимает инструментарий Yacc, генератор синтаксических анализаторов на основе LALR. С небольшим трудом Yacc парсит свой собственный язык ввода, а также язык основного компилятора V7 -- переносимого компилятора языка C. Кажется, что после двух десятилетий исследований, проблема синтаксического анализа наконец решается.

1987 - Ларри Уолл (Larry Wall) представляет Perl 1. Perl позволяет решать более сложные задачи, чем отличается от уже существующих языков. Ларри активно использует LALR -- насколько известно автору, чаще, чем кто-либо до или после него.

1991 - Джуп Лео (Joop Leo) обнаруживает способ ускорить правосторонние рекурсии в алгоритме Эрли. Алгоритм Лео является линейным практически для любой: как однозначной, так и неоднозначной грамматики, представляющей практический интерес. Аппаратное обеспечение в 1991 на шесть порядков быстрее, чем в 1968 году, так что вопрос учёта системных ресурсов стал не столь важен. Однако, если дело касается скорости, то выигрывает алгоритм Эрли. Алгоритм Лео оказался важным открытием, но его практическая реализация появится лишь через 20 лет.

1990-2002 - Алгоритм Эрли забыт. Пользователи LALR делают неприятные открытия. В то время как LALR автоматически генерирует свои анализаторы, их отладка настолько трудна, что проще написать парсер самому. После отладки их LALR анализаторы при правильных входных данных работают быстро. Но почти все, что они говорят пользователям о некорректных входных данных -- лишь сообщение о неверном формате без указания дополнительной информации. По словам Ларри, LALR «быстр, но глуп».

2006 - GNU объявляет, что был переписан парсер компилятора GCC. В течение трех десятилетий, компиляторы языка C промышленного флагмана использовали LALR в качестве парсера -- доказательство утверждения, что LALR и серьезный алгоритм эквивалентны. Теперь GNU заменяет LALR технологией, которую тот заменил четверть века назад: рекурсивным спуском.

С 2000 и до сегодняшнего дня.

С отступлением от LALR приходит крах престижа теории синтаксического анализа. Спустя полтора века, мы пришли к тому, с чего начали. Если вы возьмете оригинальный алгоритм Ned Irons 1961 года, измените имена и даты и переведете код из смеси ассемблера и ALGOL в Haskell, то вы бы легко смогли выпустить его в наши дни и представить, как новый и революционный подход.

Рис. 1. Пример современного парсера Site Creator

1.4 Определение функциональных требований

Проанализировав существующие программные решения, были определены следующие функциональные требования к разрабатываемой программе:

1) соблюдение правильности синтаксического анализа;

2) программа должна иметь простой, но в то же время понятный и наглядный интерфейс, который не должен перегружать ресурсы компьютера;

3) программа должна иметь возможность сброса полученного результата;

4) пользователь должен иметь возможность видеть выполняемые им действия и полученный результат;

5) программа не должна занимать большой объем памяти и не должна требовать установки на жесткий диск компьютера;

6) работоспособность приложения в среде Windows.

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

программа python алгоритм

2. Проектный раздел

2.1 Выбор языка и среды программирования

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

Реализуемая задача состоит в том, чтобы при выборе действия выполнялась определенная операция.

Python - это высокоуровневый язык программирования, который используется в различных сферах IT, таких как машинное обучение, разработка приложений, web, парсинг и другие.

В 2019 году Python стал самым популярным языком программирования, обогнав Java на 10%. Это обусловлено многими причинами, одна из которых - высокая оплата труда квалифицированных специалистов (около 100 тысяч долларов в год).

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

2.2 Организация данных

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

Выводимые данные это то, что сообщается пользователю. Входные данные это то, что пользователь сообщает программе.

Выводимые данные в программе представлены в виде графического отображения окна программы (рис.2.):

Рис.2. Окно программы

Входные данные представлены в виде программного кода, который необходимо выполнить при определенных действиях пользователя, а именно нажатие кнопки в окне программы.

2.3 Определение структуры и состава программной системы

В программе используются библиотека Tkiner.

Tkiner - это графическая библиотека, позволяющая создавать программы с оконным интерфейсом. Эта библиотека является интерфейсом к популярному языку программирования и инструменту создания графических приложений tcl/tk. Tkinter, как и tcl/tk, является кроссплатформенной библиотекой и может быть использована в большинстве распространённых операционных систем (Windows, Linux, Mac OS X и др.).

Для нанесения надписей на кнопки, используемые в интерфейсе программы, мы используем text='Какое-либо название для кнопки'.

2.4 Описание разработанных алгоритмов программы

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

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

Импорт библиотек и исходные данные

Создаем окно приложения - объект Tk с заголовком self. self.geometry отвечает за размер окна.

from tkinter import *

class Parser(Tk):

def __init__(self):

Вычисление результата

Функция splits получает из parc_entry и parc_end заголовки и ключевые слова для конца парсинга. Результат отображается в надписи text.

def parsing(self):

pars_text = str(self.input_text.get('0.0', END)).replace('\n', '')

end_str = str(self.pars_end_entry.get())

splits = str(self.parc_entry.get()).split(' ')

self.input_text.delete(0.0, END)

for split in splits:

for part in pars_text.split(split)[1:]:

self.input_text.insert(END, split+part.split(end_str)[0]+end_str+'\n')

root = Parser()

mainloop()

Внешний вид

Теперь займемся оформлением внешнего вида парсера и зададим обработку нажатия кнопки.

def __init__(self):

super().__init__()

self.geometry('500x250')

self.parc_entry = Entry(self)

self.parc_entry.place(relx=0.3, relwidth=0.4, rely=0.05, relheight=0.1)

self.pars_end_entry = Entry(self)

self.pars_end_entry.place(relx=0.3, relwidth=0.4, rely=0.15, relheight=0.1)

self.input_text = Text(self)

self.input_text.place(relx=0.05, relwidth=0.9, rely=0.25, relheight=0.5)

self.parser_button = Button(self, text='Найти', command=self.parsing)

self.parser_button.place(relx=0.3, relwidth=0.4, rely=0.8, relheight=0.1)

def parsing(self):

pars_text = str(self.input_text.get('0.0', END)).replace('\n', '')

end_str = str(self.pars_end_entry.get())

splits = str(self.parc_entry.get()).split(' ')

self.input_text.delete(0.0, END)

for split in splits:

for part in pars_text.split(split)[1:]:

self.input_text.insert(END, split+part.split(end_str)[0]+end_str+'\n')

4. Тестирование программы

Тестирование программы - это этап, на котором проверяется, как ведет себя программа на как можно большем количестве входных наборов данных, в том числе и на заведомо неверных.

Основные принципы организации тестирования:

- необходимой частью каждого теста должно являться описание ожидаемых результатов работы программы, чтобы можно было быстро выяснить наличие или отсутствие ошибки в ней;

- следует по возможности избегать тестирования программы ее автором, т.к. кроме уже указанной объективной сложности тестирования для программистов здесь присутствует и тот фактор, что обнаружение недостатков в своей деятельности противоречит человеческой психологии (однако отладка программы эффективнее всего выполняется именно автором программы);

- по тем же соображениям организация - разработчик программного обеспечения не должна "единолично” его тестировать (должны существовать организации, специализирующиеся на тестировании программных средств);

- должны являться правилом доскональное изучение результатов каждого теста, чтобы не пропустить малозаметную на поверхностный взгляд ошибку в программе;

- необходимо тщательно подбирать тест не только для правильных (предусмотренных) входных данных, но и для неправильных (непредусмотренных);

- следует сохранять использованные тесты (для повышения эффективности повторного тестирования программы после ее модификации или установки у заказчика);

- тестирования не должно планироваться исходя из предположения, что в программе не будут обнаружены ошибки (в частности, следует выделять для тестирования достаточные временные и материальные ресурсы);

- следует учитывать так называемый "принцип скопления ошибок”: вероятность наличия не обнаруженных ошибок в некоторой части программы прямо пропорциональна числу ошибок, уже обнаруженных в этой части.

5. Методика проведения и результаты тестирования

При тестировании программы были выполнены следующие принципы: необходимо тщательно подбирать тест не только для правильных (предусмотренных) входных данных, но и для неправильных (непредусмотренных);

- должны являться правилом доскональное изучение результатов каждого теста, чтобы не пропустить малозаметную на поверхностный взгляд ошибку в программе;

- следует всегда помнить, что тестирование - творческий процесс, а не относиться к нему как к рутинному занятию;

- следует по возможности избегать тестирования программы ее автором.

Тестирование не выявило ряд ошибок в алгоритме, синтаксисе кода программы и ее интерфейсе.

Заключение

В результате выполнения данного курсового проекта была разработана программа "Парсер". При помощи этой программы можно производить синтаксический анализ небольших введенных текстов. Программа не занимает много места, не требовательна к установленному программному обеспечению.

Также было проведено исследование полученного программного продукта. В результате были выявлены следующие достоинства и недостатки полученного программного продукта:

Достоинства:

- Существует возможность фильтрования текста;

- Программный продукт малотребователен к системным ресурсам компьютера.

Недостатки:

- Невозможно выполнение более сложных парсинговых операций;

- Невозможность сохранения результата в памяти программы;

В целом, поставленная в начале курсового проекта цель была достигнута. В программе выполняются все необходимые функциональные требования.

Список литературы

1. Учебно-методический практикум по дисциплине "Информационные технологии в экономике" / ГАЙДУК Н.В.; Куб. гос. аграр. ун-т, Каф. информационных систем. - Краснодар: КубГАУ, 2008. - 299с

2. https://pythonworld.ru/samouchitel-python

3. Кнут, Д.Э. Искусство программирования: учеб. пособие: в 3 т.: пер. с англ. Т.1: Основные алгоритмы. - 3-е изд. - М. и др.: Вильямс, 2000. - 720 с.

4. Гловацкая, А.П. Методы и алгоритмы вычислительной математики: учеб. пособие для вузов / А.П. Головыцкая. - М.: Радио и связь, 1999. - 408с.

5. Бежанова, М.М. Практическое программирование: структуры данных и алгоритмы: учеб. для вузов / М.М. Бежанова, Л.А. Москвина, И.В. Поттосин. - М.: Логос, 2001. - 223с.

Размещено на Allbest.ru