М.М.Гавриков,А.Н.Иванченко,

Д.В.Гринченков

ТеореТические основы

разрабоТки и реализации

языков программирования

Под редакцией проф. А.Н.Иванченко

Допущено Министерством образования и науки Российской Федерации

в качестве учебногопособия

для студентов вузов, обучающихся

по специальности «Программное обеспечение

вычислительной техники и автоматизированных систем»

направления подготовки дипломированных специалистов «Информатика и вычислительная техника»

УДК681.3(075.8) ББК32.973я73 Г23 Рецензенты:

Н.Б.Толпинская, доц. кафедры ПОВТ и АС Донского государственного технического университета, канд. техн. наук, Ю.М.Вишняков, проф. кафедры «Математическое обеспечение и применения ЭВМ», д-р техн. наук ГавриковМ.М.

Г23 Теоретические основы разработки и реализации языков программирования : учебное пособие / М.М. Гавриков, А.Н. Иванченко, Д.В. Гринченков ; под ред. А.Н. Иванченко. — М. : КНОРУС, 2013. — 178 с.

ISBN978-5-406-02430- Изложен широкий круг вопросов, касающихся теоретических основ разработки и реализации языков программирования: теория перевода и ее применение к синтаксическому анализу; конструирование сканеров и однопроходных анализаторов; свойства языков и грамматик и др.

Соответствует Федеральному государственному образовательному стандарту высшего профессионального образования третьего поколения.

Для студентов высших учебных заведений. Может быть полезно для разработчиков программного обеспечения вычислительной техники и автоматизированных систем.

УДК681.3(075.8) ББК32.973я Гавриков Михаил Михайлович Иванченко Александр Николаевич Гринченков Дмитрий Валерьевич

ТЕОРЕТИЧЕСКИЕОСНОВЫРАЗРАБОТКИИРЕАЛИЗАЦИИ

ЯЗЫКОВПРОГРАММИРОВАНИЯ

Изд. № 5140. Формат 6090/16.

Гарнитура «NewtonC». Печать офсетная.

Усл. печ. л. 11,5. Уч.изд. л. 10,0. Тираж 500 экз. Заказ № ООО «КноРус».

129085, Москва, проспект Мира, 105, стр. 1.

Тел.: (495) 741-46-28.

E-mail: [email protected] http://www.knorus.ru Отпечатано в ГУП «Брянское областное полиграфическое объединение».

241019, г. Брянск, пр-т Ст. Димитрова, 40.

© Гавриков М.М., Иванченко А.Н., Гринченков Д.В., ISBN978-5-406-02430-0 © ООО «КноРус», оглавление Предисловие.................................. Глава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 • Оглавление Глава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, ЮРГТУ (НПИ).

Хорошо известно, что традиционно сложившиеся принципы обучения студентов по специальности «Программное обеспечение вычислительной техники и автоматизированных систем» подразумевают не только освоение навыков программирования на различных языках, но и глубокое освоение математических основ, на которых базируются модели и процедурная семантика языков. Эта позиция нашла отражение как в российском государственном образовательном стандарте, так и в образовательных программах ведущих стран мира для специальностей и направлений, связанных с изучением информационных технологий. Учитывая это, можно уверенно сказать, что изучение теории, методологии и принципов разработки языков программирования и построения трансляторов является одной из существенных составляющих в подготовке специалистов в области программного обеспечения.

Особо следует отметить, что на протяжении более чем пятнадцати лет в стране практически не издавалось специальной литературы по вышеназванному направлению, вышедшие ранее книги давно стали библиографической редкостью и недоступны широкому кругу читателей. Ситуация в последнее время несколько улучшилась, было издано несколько новых книг, вышли переработанные и дополненные редакции классических изданий. Однако недостаток литературы продолжает ощущаться. Поэтому авторы надеются, что их издание может внести свою достойную лепту в обеспечение учебного процесса соответствующей литературой, тем более что их пособие специально ориентировано на обучение студентов.

Содержание книги во многом перекрывает разделы для обязательного изучения из образовательного стандарта по дисциплине «Теория языков программирования и методы трансляции» специальности «Программное обеспечение вычислительной техники и автоматизированных систем». Авторы стремились четко выдержать направленность на обучение, в первую очередь неподготовленного читателя, для чего в книге приведено значительное количество примеров, упражнений и заданий по всем темам, которые могут использоваться на практических и лабораторных занятиях.

Учитывая, что сама по себе описываемая дисциплина использует сложный математический аппарат с большим количеством теорем, лемм, специфических формул и доказательств авторы старались, сохранив достаточно высокий научный уровень, уйти от излишнего увлечения сложными, практически нечитаемыми конструкциями, что позволило сделать текст книги более понятным и лучше усваиваемым. Цель авторов была не «напугать» читателя обилием сложных формализмов, доступных пониманию лишь профильных специалистов, а постепенно, шаг за шагом, ввести обучаемого в сложный мир разработки языков программирования и трансляторов. При этом следовало избежать и другой крайности — чрезмерного упрощения.

Учебное пособие хотя и предназначено для студентов, но авторы надеются, что оно может оказаться полезным и для разработчиков программного обеспечения, сталкивающихся с проблемами и задачами из данной прикладной области.