Теория языков программирования: проектирование и реализация (300,00 руб.)

Стр.4

Стр.5

Стр.6

УДК 004.43(075.8) Ш 795 Рецензенты: В. Е. Зюбин, д-р техн. наук, зав. лабораторией киберфизических систем Института автоматики и электрометрии СО РАН В. И. Гужов, д-р техн. наук, профессор кафедры ССОД НГТУ Шорников Ю. В. Ш 795 Теория языков программирования: проектирование и реализация : учебное пособие / Ю. В. Шорников. – Новосибирск : Изд-во НГТУ, 2022. – 290 с. – (Учебники НГТУ). ISBN 978-5-7782-4817-5 Учебное пособие подготовлено в соответствии с Государственным образовательным стандартом по направлениям 09.03.01 «Информатика и вычислительная техника», 09.03.03 «Прикладная информатика» для цикла дисциплин информационных специальностей. Основой учебного пособия стал материал, прочитанный автором студентам соответствующих специальностей в Новосибирском государственном техническом университете и Казахстанско-Британском техническом университете в курсах «Теория формальных языков и компиляторов», «Системное программное обеспечение», «Лингвистическое обеспечение». В учебном пособии рассмотрена теория порождающих грамматик, конечных автоматов и регулярных выражений. Все теоретические механизмы анализа и синтеза языковых конструкций строго формализованы и составляют теоретические основы проектирования языков программирования. Реализация языков программирования представлена разработкой языковых процессоров. Переход от формальных языков к языковым процессорам выполнен через конструктивные методы анализа со строгими моделирующими алгоритмами, которые могут быть реализованы на языках высокого уровня или с помощью современных средств автоматизации программирования. В пособии рассмотрены средства ANTLR и FLEX & BIZON для автоматизации программирования парсера и лексера. Несмотря на образовательную направленность, пособие может быть Работа подготовлена на кафедре автоматизированных систем управления УДК 004.43(075.8) DOI 10.17212/978-5-7782-4817-5 ISBN 978-5-7782-4817-5 © Шорников Ю. В., 2022 © Новосибирский государственный технический университет, 2022 4 полезно всем, кто занимается проектированием и реализацией новых языков, языковых процессоров и конечно-автоматных распознавателей.

Стр.4

ОГЛАВЛЕНИЕ Введение .................................................................................................................. 7 1. СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ................................ 11 1.1. Определения и логические связи языковых процессоров .............. 11 1.2. Системные исследования в России ................................................... 16 1.3. Место языковых процессоров ........................................................... 28 1.4. Потребность в разработке языковых процессоров .......................... 32 1.5. Современные архитектурные решения ............................................. 35 2. ПОРОЖДАЮЩИЕ ГРАММАТИКИ И ЯЗЫКИ ..................................... 43 2.1. Обозначения и определения .............................................................. 43 2.2. Порождающие грамматики ................................................................ 46 2.3. Языки порождающих грамматик ...................................................... 52 2.4. Прямая и обратная задачи формальных языков и грамматик ........ 53 2.5. Геометрическая интерпретация синтаксического разбора ............. 58 2.6. Эквиалентность и однозначность ...................................................... 63 2.7. Классификация Хомского .................................................................. 70 2.8. Графы автоматной грамматики ......................................................... 73 3. КОНЕЧНО-АВТОМАТНЫЕ РАСПОЗНАВАТЕЛИ И ЯЗЫКИ ............. 77 3.1. Автоматные распознаватели и грамматики Хомского .................... 77 3.2. Конечные автоматы ............................................................................ 79 3.3. Синтаксические диаграммы и конечные автоматы ......................... 81 3.4. Недетерминированные конечные автоматы .................................... 86 3.5. Детерминированный конечный автомат .......................................... 87 3.6. Моделирование НКА .......................................................................... 96 3.7. Минимизация ДКА ............................................................................. 96 3.8. МП-автоматы ...................................................................................... 99 3.9. Детерминированные МП-автоматы ................................................ 102 4. ЯЗЫКИ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ ............................................. 107 4.1. Регулярные множества и языки ....................................................... 109 4.2. Регулярные выражения .................................................................... 111 5

Стр.5

4.3. Автоматные грамматики и регулярные выражения ..................... 113 4.4. Регулярные выражения и конечные автоматы ............................... 115 4.5. Анализ алгоритмов ........................................................................... 122 4.6. Целесообразность перехода от НКА к ДКА .................................. 127 5. СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ .................... 131 5.1. Процессор числовых констант ........................................................ 131 5.2. Сканер ................................................................................................ 135 5.3. Организация таблиц символов ........................................................ 145 5.4. Рекурсивный спуск ........................................................................... 152 5.5. Диагностика и нейтрализация синтаксических ошибок ............... 157 5.6. Вычисленние арифметических выражений .................................... 159 5.7. Восходящие методы анализа ........................................................... 166 6. ПРОЕКТИРОВАНИЕ И РЕАЛИЗАЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ........................................................................ 175 6.1. Препроцессор к станкам с ЧПУ ...................................................... 175 6.2. Интерпретатор задачи Коши ........................................................... 182 6.3. ИСМА 2015 ....................................................................................... 201 7. ГЕНЕРАТОРЫ ЯЗЫКОВЫХ ПРОЦЕССОРОВ .................................... 217 7.1. ANTLR ............................................................................................... 218 7.2. Листинг грамматики LISMA_PDE в формате ANTLR .................. 222 7.3. FLEX & BISON ................................................................................. 226 Библиографический список ......................................................................... 229 Приложения ................................................................................................... 237 Приложение А ............................................................................................... 237 Приложение Б................................................................................................ 287 6

Стр.6