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. Методика проведения и результаты тестирования
При тестировании программы были выполнены следующие принципы: необходимо тщательно подбирать тест не только для правильных (предусмотренных) входных данных, но и для неправильных (непредусмотренных);