Табличні методи сиинтаксичного аналізу. Алгоритм Ерлі. Курсова робота з Дискретна математика. Робота № 529419

Перехід до торгівельного партнера Binance

Табличні методи сиинтаксичного аналізу. Алгоритм Ерлі

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Факультет:

УІ

Кафедра:

Кафедра прикладної математики

Інформація про роботу

Рік:

2016

Тип роботи:

Курсова робота

Предмет:

Дискретна математика

Група:

ПМ-32

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра прикладної математики КУРСОВА РОБОТА з курсу «Дискретна математика» на тему: «Табличні методи сиинтаксичного аналізу. Алгоритм Ерлі» АНОТАЦІЯ У курсовій роботі розглянуто поняття синтаксичного аналізу, а саме, табличні методи синтаксичного аналізу контекстно-вільних граматик та алгоритм Ерлі. Дано загальні характеристику синтаксичного аналізу, його застосування, розглянуто поняття синтаксичного аналізатора та його видів. Описані табличні методи синтаксичного аналізу: алгоритм Кока-Янгера-Касамі та алгоритм Ерлі. Детально розглянуто алгоритм Ерлі, що дає можливість побудувати дерево розбору. Зокрема розглянуто два види реалізації цього алгоритму: за час 0(n3), де n – довжина вхідного ланцюжка, та за час 0(n2). Показана різниця цих видів реалізації. Наведено реалізацію алгоритму Ерлі – код програми, що будує дерево розбору вхідного ланцюжка на основі введеної граматики. SUMMARY In the coursework is examined the concept parsing, namely, tabular methods of parse for context-free grammars and algorithm Early. Given the general description of the parsing, its application, the notion parser and its species. Described tabular methods of parsing: algorithm Coc-Younger-Kasami and Earley algorithm. Is reviewed in detail Early algorithm which gives an algorithm that makes it possible to build a tree parsing. Two particular types implement this algorithm: at time 0(n3), where n - the length of the input string, and at time 0(n2). Shown difference of these types of realization. Given an Early algorithm implementation - source code that builds the parse tree of the input string based on the entered grammar. ЗМІСТ ВСТУП 5 СИНТАКСИЧНИЙ АНАЛІЗ 6 МЕТОДИ ТАБЛИЧНОГО СИНТАКСИЧНОГО АНАЛІЗУ 9 АЛГОРИТМ ЕРЛІ 10 ВИСНОВОК 22 ДОДАТОК 23 СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 42 ВСТУП Алгоритм Ерлі являє собою низхідний алгоритм табличного синтаксичного аналізу, тобто побудову дерева розбору здійснюється зверху вниз. Хоча, як і в алгоритмі Кока-Янгера-Касамі, верхня оцінка на часову складність алгоритму являє собою куб по довжині слова, на практиці константа в алгоритмі Ерлі значно нижча. Крім того, для однозначних граматик доведена квадратична верхня оцінка на час роботи алгоритму, а для багатьох граматик в реальності складність виявляється лінійною. Через відносну простоту алгоритму це дозволяє використовувати його в окремих практичних додатках (хоча в цілому LR- і GLR-алгоритми розбору є значно більш популярними). Алгоритм Ерлі отримує на вхід контекстно-вільну граматику G=(N,

Курсова робота Дискретна математика

13.05.2017 14:05-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись