М.М.Гавриков,А.Н.Иванченко,
Д.В.Гринченков
ТеореТические основы
разрабоТки и реализации
языков программирования
Под редакцией проф. А.Н. Иванченко
Допущено Министерством образования Российской Федерации
в качестве учебногопособия
для студентов высших учебных заведений, обучающихся
по специальности «Программное обеспечение
вычислительной техники и автоматизированных систем»
направления подготовки дипломированных специалистов «Информатика и вычислительная техника»
УДК 681.3(075.8) ББК 32.973я73 Г23 Рецензенты:
Н. Б. Толпинская, доц. кафедры ПОВТ и АС Донского государственного технического университета, канд. техн. наук, Ю. М. Вишняков, проф. кафедры «Математическое обеспечение и применения ЭВМ», д-р техн. наук Гавриков М. М.
Г23 Теоретические основы разработки и реализации языков программирования : учебное пособие / М.М. Гавриков, А.Н. Иванченко, Д.В. Гринченков; под ред. А.Н. Иванченко. — М. : КНОРУС, 2010. — 184 с.
ISBN Изложен широкий круг вопросов, касающихся теоретических основ разработки и реализации языков программирования: теория перевода и ее применение к синтаксическому анализу; кон струирование сканеров и однопроходных анализаторов; свойства языков и грамматик и др.
Для студентов высших учебных заведений, а также может быть полезно для разработчиков программного обеспечения вычислительной техники и автоматизированных систем.
УДК 681.3(075.8) ББК 32.973я Гавриков Михаил Михайлович Иванченко Александр Николаевич Гринченков Дмитрий Валерьевич
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАЗРАБОТКИ И РЕАЛИЗАЦИИ
ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
Санитарно-эпидемиологическое заключение № 77.99.60.953.Д.003365.04.09 от 01.04.2009 г.Изд. № 1747. Подписано в печать 08.09.2009. Формат 6090/16.
Гарнитура «NewtonC». Печать офсетная.
Усл. печ. л. 11,5. Уч.-изд. л. 10,0. Тираж 2000 экз. Заказ № ООО «Издательство КноРус».
129110, Москва, ул. Большая Переяславская, 46, стр. 7.
Тел.: (495) 680-7254, 680-0671, 680-1278.
E-mail: [email protected] http://www.knorus.ru Отпечатано в ГУП «Брянское областное полиграфическое объединение».
241019, г. Брянск, пр-т Ст. Димитрова, 40.
© Гавриков М.М., Иванченко А.Н., Гринченков Д.В., © ЗАО «МЦФЭР», ISBN 9785406001219 © ООО «Издательство КноРус», оглавление Предисловие.................................. Глава1.Введениевпроблематикуразработкииреализации языковпрограммирования 1.1. Языки программирования и формальные языки............ 1.2. Понятие транслятора и компилятора. Фазы компиляции...... 1.3. Инструменты и технологии разработки и реализации языков программирования............................. Глава2.Способызаданияформальныхязыков 2.1. Математический аппарат теории формальных языков........ 2.2. Цепочки и языки.............................. 2.3. Грамматики................................. 2.4. Распознаватели............................... 2.5. Регулярные выражения и синтаксические диаграммы........ 2.6. Соответствия между способами описания языков........... 2.7. Упражнения и задания........................... Глава3.Основытеориипереводаиееприменение ксинтаксическомуанализу 3.1. Определение перевода........................... 3.2. Схемы синтаксически управляемых переводов............ 3.3. Модели простейших трансляторов.................... 3.4. Определение синтаксического разбора................. 3.5. Модели анализаторов........................... 3.6. Модели синтаксически управляемой трансляции........... 3.7. Упражнения и задания........................... Глава4.Конструированиесканеров 4.1. Общая характеристика процесса сканирования............ 4.2. Описание лексем в языке расширенных регулярных выражений.......................... 4.3. Построение недетерминированного конечного автомата по расширенному регулярному выражению.............. 4.4. Преобразование синтаксической диаграммы в конечный автомат............................ 4.5. Преобразование недетерминированного конечного автомата в детерминированный........................... 4.6. Представление результатов сканирования............... 4.7. Методики конструирования сканеров.................. 4.8. Упражнения и задания........................... 4 • Оглавление Глава5.ПрименениеКСязыковиграмматиквразработкеязыков программирования Глава6.Конструированиеоднопроходныханализаторов 6.1. Общая характеристика моделей и методов 6.3. Алгоритмы построения управляющих 6.6. Конструирование алгоритмов типа «перенос — свертка»
Глава7.Семантическийанализисинтезвнутреннего представленияпрограммы 7.1. Общие замечания о семантическом анализе 7.3. Интерпретация промежуточной программы Изучение теории и освоение методологии разработки языков программирования и построения трансляторов — важнейшие составляющие в профессиональной подготовке специалистов в области программного обеспечения. С середины 80-x гг. XX в. в нашей стране почти не выпускалось научной и учебной литературы по этой тематике, доступной широкому кругу читателей, а вышедшее ранее издание известных авторов (А. Ахо и Дж. Ульман [1, 2], Д. Грис [4], Р. Хантер [5] и др.) стало библиографической редкостью даже для библиотек технических вузов. В последние 10 лет опубликовано немало новых книг отечественных и зарубежных авторов. Среди них — фундаментальная монография А. Ахо, М. Лам, Р. Сети и Дж. Ульмана [3], которую можно рассматривать как блестящий образец справочного руководства по разработке компиляторов. Материал этой книги может использоваться как читателями, только приступающими к изучению данной области, так и специалистами-практиками. Однако стиль изложения, формат и, главное, объем книги (1184 с.) представляют некоторые сложности в использовании ее в качестве учебника. Все это побудило авторов к созданию настоящего пособия, цели которого состоят в следующем:
— краткое, но систематическое изложение методологии, инструментов и технологий разработки языков программирования и построения трансляторов;
— рассмотрение основных положений и моделей теории формальных языков, синтаксического анализа и перевода, составляющих теоретическую базу разработки и реализации языков программирования;
— изложение методик и формальных методов синтеза основных элементов трансляторов;
— иллюстрация применения излагаемых методов путем их проецирования на реальные задачи, связанные с разработкой и реализацией как универсальных, так и проблемно-ориентированных языков программирования.
Материал учебного пособия в значительной степени превосходит содержание требований государственного образовательного стандарта к дисциплине «Теория языков программирования и методы трансляции» специальности «Программное обеспечение вычислительной техники и автоматизированных систем».
6 • Предисловие Отличия настоящего учебного пособия от других, посвященных этой тематике, носят методологический и структурный характер.
Во многих книгах методология разработки языков программирования и сам язык как объект разработки и исследования (свойства классов грамматик и языков, соотношения между ними, инвариантность некоторых классов грамматик к методам синтаксического анализа и др.) затмеваются изложением методов построения элементов трансляторов. На практике процессы разработки языка и построения транслятора действительно тесно связаны. В то же время наш опыт преподавания вышеупомянутой и родственных дисциплин показывает, что слабым местом в знаниях и представлениях студентов являются именно вопросы разработки языков. Это обусловлено еще и тем, что большую часть методов и алгоритмов формального синтеза элементов транслятора можно программно реализовать и интегрировать в систему (или, по крайней мере, в среду) построения трансляторов, с чем они успешно справляются. Разработка и исследование нового языка (например, проблемно-ориентированного), а не использование подмножеств известных языков, требует значительных аналитических усилий.
В настоящем пособии мы постарались выделить вопросы, связанные с разработкой языков программирования, придать им больший вес и уделить больше внимания их изложению. Кроме того, в пособии сделано некоторое смещение акцентов на применение методологии в разработке интерпретаторов для проблемно-ориентированных языков (примеры, упражнения и задания главы 7 на построение синтаксически-управляемых схем трансляции для языков описания принципиальных и функциональных схем).
Теоретический материал пособия почти целиком опирается на фундаментальную, получившую всеобщее признание монографию А. Ахо и Дж. Ульмана [1, 2]. Это, как нам представляется, позволило выдержать единые стиль, терминологию и систему обозначений и обеспечить достаточно высокий научный уровень представления материала.
Изложенный в пособии материал апробирован на лекционных, практических и лабораторных занятиях по курсам «Конструирование компиляторов», «Лингвистическое обеспечение САПР» и «Теория языков программирования и методы трансляции», которые в течение ряда лет преподаются авторами на кафедре «Программное обеспечение вычислительной техники» Южно-Российского государственного технического университета (Новочеркасского политехнического института).
Учебное пособие предназначено для студентов вузов, обучающихся по специальности «Программное обеспечение вычислительной техники и автоматизированных систем», а также может быть рекомендовано для студентов специальности «Математическое обеспечение и администрирование информационных систем» и специальностей направления «Информатика и вычислительная техника». Мы надеемся, что оно окажется полезным и для разработчиков программного обеспечения, сталкивающихся с проблемами и задачами из данной прикладной области. Материал пособия содержит большое количество примеров, упражнений и заданий, которые могут использоваться на практических и лабораторных занятиях.
Авторы выражают благодарность своим коллегам и студентам за помощь в отладке примеров программ и подготовке рукописи.
Все замечания и предложения по содержанию учебного пособия можно направлять по адресу: 346428, г. Новочеркасск Ростовской обл., ул. Просвещения, д. 132, ЮРГТУ (НПИ).