Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра прикладної математики КУРСОВА РОБОТА з курсу «Дискретна математика» на тему: «Табличні методи сиинтаксичного аналізу. Алгоритм Ерлі» АНОТАЦІЯ У курсовій роботі розглянуто поняття синтаксичного аналізу, а саме, табличні методи синтаксичного аналізу контекстно-вільних граматик та алгоритм Ерлі. Дано загальні характеристику синтаксичного аналізу, його застосування, розглянуто поняття синтаксичного аналізатора та його видів. Описані табличні методи синтаксичного аналізу: алгоритм Кока-Янгера-Касамі та алгоритм Ерлі. Детально розглянуто алгоритм Ерлі, що дає можливість побудувати дерево розбору. Зокрема розглянуто два види реалізації цього алгоритму: за час 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,