Синтаксичний аналіз з поверненням. Моделювання МП-перетворювача. Неформальний опис та алгоритм аналізу «зверху-вниз». Оцінки складності а

Міністерство освіти і науки України

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

Інститут прикладної математики та фундаментальних наук

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

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

з курсу «Дискретна математика»

на тему «Синтаксичний аналіз з поверненням. Моделювання МП-перетворювача. Неформальний опис та алгоритм аналізу «зверху-вниз». Оцінки складності алгоритму»

Виконала:

Прийняв:

Львів 2017

Зміст

1. Анотація………………………………………………………………..………….. 3
2. Annotation………………………………………………………………………….. 4
3. Постановка задачі……………………….…………………………………..…….. 5
4. Вступ…………………………………………………………………….…………. 6
5. Основна частина……………………………………….………………………….. 7
6. Висновки………………………………………………………………..…………. 21
7. Додаток……………................................................................................................. 22
8. Список використаної літератури…………...…………………………………..…27

Анотація

У курсовій роботі досліджуються головні функції синтаксичного аналізатора. Розглядаються типи синтаксичних аналізаторів для контекстно-вільних мов, а також розглянуто синтаксичний аналіз з поверненням, на якому базується розбір граматичної структури вхідного ланцюжка, класи, що містять у собі спадні або ж висхідні алгоритми. Проаналізовано роботу автоматів, які виконують синтактичний аналіз, що називаються синтаксичними аналізаторами. Досліджуються методи моделювання спадного розпізнавача. Також буде протестована робота на прикладах різних вхідних ланцюжків. Виконано аналіз швидкодії спадного синтаксичного аналізатора. В основу роботи лягли дослідження здійснені раніше. Головну роль в тому, як функціонує синтаксичний аналізатор і який алгоритм лежить в його основі, відіграють принципи побудови розпізнавачів для КВ-мов. Без застосування цих принципів неможливо виконати ефективний синтаксичний розбір пропозицій вхідної мови. Питання, пов'язані з поданням інформації, що є результатом роботи синтаксичного аналізатора, і з породженням на основі цієї інформації тексту результуючої програми, розглянуті в наступному розділі, тому тут на них зупинятися не будемо. Справа в тому, що процес побудови синтаксичного аналізатора набагато складніший аналогічного процесу для лексичного аналізатора. Так відбувається, оскільки КВ-граматики і МП-автомати, що лежать в основі синтаксичного аналізу, складніші, ніж регулярні граматики, що лежать в основі лексичного аналізу.

Annotation

In this course work are studied the main functions of the parser analyzer. The are considered different types of syntactic analyzers for context-free languages, as well as a syntactic analysis with a return on which the analysis of the grammatical structure of the input chains is based, classes that include descending or ascending algorithms. There is also analyzed work of automatic machines performing syntactic analysis, called syntactic analyzers. There are studied methods of modeling of a downward recognizer. Also, work will be tested on examples of different input chains. In this paper is performed analysis of the speed of the downstream parser. The basis of the work are the studies carried out earlier. The main role in how the parser analyzer functions and which algorithm is based on it, have the principles of constructing recognizers for context-free languages. Without applying these principles it is impossible to perform an effective syntax analysis of the input language suggestions. Issues related to the presentation of information, which are the result of the work of the parser, and the generation on the basis of this information of the text of the resulting program, are discussed in the next section, so here we will not stop there. The fact is that the process of constructing a parser is much more complicated than a similar process for a lexical analyzer. This is the case, since context-free grammar and mp automatic machine, which are the basis of parsing, are more complex than regular grammar, which are the basis of lexical analysis.

Постановка задачі

Метою курсової роботи було закріпити та розширити знання при вивченні курсу, дослідити особливості синтаксичного аналізу , а конкретніше розглянути синтаксичний аналіз з поверненням, розглянути синтаксичні аналізатори, їх особливості та методи використання, принципи роботи. Було поставлено завдання оглянути стандартний алгоритм моделювання МП-перетворювача, як різновид автомата. Метою роботи було вивчити та науково дослідити методи аналізу «зверху-вниз», науково обгрунтувати їх алгоритми дій та приклади їх застосувань, висвітлити реалізацію спадного синтаксичного аналізу у конкретному методі рекурсивного спуску.