Для студентов МГТУ им. Н.Э.Баумана по предмету ДругиеОслабленный синтаксический анализ динамически формируемых выражений на основе алгоритма GLLОслабленный синтаксический анализ динамически формируемых выражений на основе алгоритма GLL
2024-07-202024-07-20СтудИзба
Курсовая работа: Ослабленный синтаксический анализ динамически формируемых выражений на основе алгоритма GLL
Описание
Оглавление
3
Введение
При работе с формальными языками и грамматиками выводимость цепочки в грамматике можно рассматривать как следующее свойство: цепочка ω обладает свойством S , если ω выводима из S: (S ⇒∗ ω). При решении практических задач, как правило, выполняют провер-ку свойства выводимости в грамматике для отдельно взятых цепочек, либо же для конечного множества цепочек, представленных в явном виде (например, в виде множества файлов с исходным текстом про-грамм). На практике такие множества могут оказаться бесконечными, что делает такую проверку невозможной. Подобная ситуация может возникнуть, если цепочки генерируются автоматически. Множество по-рождаемых генератором цепочек в этом случае будет регулярным. Для описания регулярных множеств часто используются конечные автома-ты. Таким образом возникает задача проверки свойства выводимости
КС-грамматике для все
| Введение | 4 | ||
| 1. | Постановка задачи | 7 | |
| 2. | Обзор | 8 | |
| 2.1. | Обобщённый синтаксический анализ . . . . . . . . . . . . | 8 | |
| 2.2. | Структурированный в виде графа стек . . . . . . . . . . | 10 | |
| 2.3. | Сжатое представление леса разбора . . . . . . . . . . . . | 12 | |
| 2.4. | АлгоритмGLL......................... | 15 | |
| 2.5. | Подходы к анализу встроенных языков . . . . . . . . . . | 17 | |
| 2.6. | YaccConstructor . . . . . . . . . . . . . . . . . . . . . . . . | 20 | |
| 2.7. | Анализ метагеномной сборки . . . . . . . . . . . . . . . . | 21 | |
| 2.8. | Выводы............................. | 22 | |
| 3. | Алгоритм анализа регулярных множеств | 24 | |
| 3.1. | Примерработыалгоритма . . . . . . . . . . . . . . . . . . | 29 | |
| 3.2. | Доказательство корректности . . . . . . . . . . . . . . . . | 30 | |
| 3.3. | Анализ данных большого объёма . . . . . . . . . . . . . . | 35 | |
| 4. | Реализация | 37 | |
| 4.1. | Архитектура предложенного решения . . . . . . . . . . . | 37 | |
| 4.2. | Особенности используемых структур данных . . . . . . . | 39 | |
| 5. | Эксперименты | 44 | |
| Заключение | 49 | ||
| Список литературы | 51 | ||
3
Введение
При работе с формальными языками и грамматиками выводимость цепочки в грамматике можно рассматривать как следующее свойство: цепочка ω обладает свойством S , если ω выводима из S: (S ⇒∗ ω). При решении практических задач, как правило, выполняют провер-ку свойства выводимости в грамматике для отдельно взятых цепочек, либо же для конечного множества цепочек, представленных в явном виде (например, в виде множества файлов с исходным текстом про-грамм). На практике такие множества могут оказаться бесконечными, что делает такую проверку невозможной. Подобная ситуация может возникнуть, если цепочки генерируются автоматически. Множество по-рождаемых генератором цепочек в этом случае будет регулярным. Для описания регулярных множеств часто используются конечные автома-ты. Таким образом возникает задача проверки свойства выводимости
КС-грамматике для все
Характеристики курсовой работы
Предмет
Учебное заведение
МГТУ им. Н.Э.БауманаСеместр
Просмотров
1
Размер
1,01 Mb
Список файлов
Ослабленный синтаксический анализ динамически формируемых выражений на основе алгоритма GLL.doc
Tortuga
20 июля 2024 в 09:18
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
