nC1DMY1V3A
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ МУРМАНСКИЙ АРКТИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
И. М. Лазарева
ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
И МЕТОДЫ ТРАНСЛЯЦИИ
Учебное пособие
МУРМАНСК
2018
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ МУРМАНСКИЙ АРКТИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
И. М. Лазарева
ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
И МЕТОДЫ ТРАНСЛЯЦИИ
Учебное пособие
Рекомендовано учебно-методическим советом университета в качестве учебного пособия по дисциплине
«Теория языков программирования и методы трансляции» по направлению подготовки
01.03.02 «Прикладная математика и информатика: Системное программирование и компьютерные технологии»
МУРМАНСК
2018
1
УДК 004 (075.8) ББК 32.97я73
Л17
Печатается по решению Совета по научно-исследовательской работе и редакционно-издательской деятельности Мурманского арктического государственного университета
Рекомендовано учебно-методическим советом Мурманского арктического государственного университета к использованию в учебном процессе (протокол № 1 от 14.09.2017)
Автор: И. М. Лазарева, кандидат физико-математических наук, доцент, зав. кафедрой математики, физики и информационных технологий Мурманского арктического государственного университета
Рецензенты: В. Я. Беляев, кандидат физико-математических наук, доцент, доцент кафедры математики, физики и информационных технологий Мурманского арктического государственного университета; Ю. В. Романовская, кандидат физико-математических наук, заведующая кафедрой математики, информационных систем и программного обеспечения Мурманского государственного технического университета (протокол № 10 от 25.04.2018)
Лазарева И. М.
Л17 Теория языков программирования и методы трансляции : учебное пособие / И. М. Лазарева. – Мурманск : МАГУ, 2018. – 97 с.
В учебном пособии рассмотрена теория, образующая фундамент, необходимый для корректной постановки и решения проблем в области информатики. Отражены базовые сведения о формальных грамматиках, наиболее часто применяемых для описания, анализа и трансляции языков программирования высокого уровня. Изложены основные алгоритмы нисходящего и восходящего синтаксического анализа текстов программ.
Предназначено для студентов высших учебных заведений, обучающихся по направлению подготовки «Прикладная математика и информатика».
Печатается в авторской редакции.
ISBN 978-5-4222-0362-8 |
Лазарева И. М., 2018 |
|
ФГБОУ ВО «Мурманский арктический |
|
государственный университет», 2018 |
|
2 |
Оглавление
Введение........................................................................................................................ |
4 |
Тема 1. Теоретические основы построения компиляторов................................ |
6 |
Упрощенная модель компилятора ............................................................................ |
6 |
Формальное описание языка. Понятие метаязыка .................................................. |
9 |
Вопросы и задания для контроля к теме 1 ............................................................. |
11 |
Тема 2. Основы теории формальных языков и грамматик ............................. |
12 |
Порождающая грамматика ...................................................................................... |
14 |
Классификация по Хомскому.................................................................................. |
16 |
Вопросы и задания для контроля к теме 2 ............................................................. |
17 |
Тема 3. Контекстно-свободные грамматики ....................................................... |
19 |
Эквивалентные преобразования КС-грамматик.................................................... |
23 |
Нормальные формы Хомского и Грейбах .............................................................. |
30 |
Вопросы и задания для контроля к теме 3 ............................................................. |
31 |
Тема 4. Автоматы и преобразователи................................................................... |
33 |
Конечный автомат .................................................................................................... |
33 |
Приведение конечного автомата ............................................................................. |
36 |
Конечные автоматы и автоматные грамматики .................................................... |
40 |
Недетерминированные и детерминированные конечные автоматы ................... |
42 |
Автоматы с магазинной памятью............................................................................ |
45 |
Расширенные МП-автоматы .................................................................................... |
49 |
Преобразователи с магазинной памятью ............................................................... |
52 |
Вопросы и задания для контроля к теме 4 ............................................................. |
54 |
Тема 5. Нисходящие методы синтаксического анализа.................................... |
56 |
S-грамматика ............................................................................................................. |
60 |
Q-грамматика ............................................................................................................ |
61 |
LL(1)-грамматика...................................................................................................... |
64 |
Метод рекурсивного спуска .................................................................................... |
67 |
Вопросы и задания для контроля к теме 5 ............................................................. |
69 |
Тема 6. Формальные методы описания перевода .............................................. |
71 |
Транслирующая грамматика ................................................................................... |
71 |
Синтаксически управляемый перевод .................................................................... |
74 |
Понятие атрибута. Синтезированные и наследуемые атрибуты ......................... |
76 |
Атрибутные транслирующие грамматики и перевод ........................................... |
80 |
Вопросы и задания для контроля к теме 6 ............................................................. |
82 |
Тема 7. Восходящие методы обработки языков ................................................. |
83 |
Метод «Перенос-свертка»........................................................................................ |
86 |
Метод «Перенос-опознание»................................................................................... |
88 |
Бессуффиксные ПО-грамматики............................................................................. |
94 |
Вопросы и задания для контроля к теме 7 ............................................................. |
96 |
Литература ................................................................................................................. |
97 |
3 |
|
Введение
Пособие написано в соответствии с государственным образовательным стандартом и рабочей программой по дисциплине «Теория языков программирования и методы трансляции», которая входит в цикл вариативных дисциплин по направлению подготовки бакалавров «Прикладная математика и информатика».
Решение многих современных научных и прикладных задач часто требуют использования вычислительных машин и написания для них программ на соответствующих языках программирования. Несмотря на то, что к настоящему времени разработаны тысячи различных языков и их трансляторов, процесс создания новых продуктов в этой области не прекращается. Это связно как с развитием технологии производства вычислительных систем, так и с необходимостью решения все более сложных прикладных задач. Кроме того, элементы данной теории применимы и в других областях, например, при описании структур данных, в частности регулярных выражений.
Воснове методов, используемых для создания, анализа и преобразования языков программирования, лежит теория формальных языков и грамматик, а также теория автоматов. Поэтому, теория языков программирования, а также практические методы разработки трансляторов обязательно входят в стандарт высшего образования по направлениям, связанным с информатикой и программированием.
Впособие включен базовый объем теоретического материала по дисциплине «Теория языков программирования и методы трансляции». Введены основные понятия теории формальных языков и грамматик, теории автоматов. Описаны основные алгоритмы синтаксического анализа и схемы синтаксически управляемого перевода. Использован математический аппарат теории множеств, теории графов и математической логики.
Начинается изложение с описания упрощенной схемы организации работы компилятора для демонстрации основной области приложения изучаемых понятий и алгоритмов (тема 1). В качестве базовых выделяются блоки лексического и синтаксического анализа, блок генератора кода. Описываются различные способы взаимодействия этих блоков.
Для описания языка, на котором будут создавать программы, подлежащие обработке с помощью компилятора, вводится понятие порождающей грамматики. Основные положения теории порождающих грамматик изложены в теме 2. Формальные грамматики позволяют создать математическое описание различных языков. Благодаря такому описанию появляется возможность создавать программные средства, работающие с данными языками – языковые процессоры. И это не только компиляторы, но и различные переводчики для естественных языков или средства обработки символьных выражений.
4
В теме 3 более подробно рассмотрен отдельный класс порождающих грамматик – контекстно-свободных грамматик (КС-грамматик), который специально предназначен для описания языков программирования. КСграмматики позволяют описать язык программирования с помощью порождающей процедуры.
Другой способ описания языка – использование распознающей процедуры. Для ее реализации используются специальные автоматные модели: конечные автоматы и автоматы с магазинной памятью. Описание данных моделей приводится в теме 4. Автоматные модели позволяют не только распознавать принадлежность цепочек символов заданному языку, но и преобразовывать (или транслировать) их на другой язык.
Темы 5 и 7 содержат описание методов синтаксического анализа построенных языков – нисходящих и восходящих, соответственно. В основе этих методов лежат правила соответствующей формальной грамматики, а алгоритм их работы строится на базе автоматных механизмов.
Тема 6 посвящена методам синтаксически управляемого перевода, основой которого является транслирующая грамматика. Вводится математическое понятие перевода и описываются базовые алгоритмы преобразования языков программирования.
Таким образом, в результате изучения дисциплины «Теория языков программирования и методы трансляции» студенты должны знать и уметь использовать основные положения теории формальных языков и грамматик, прикладную теорию конечных автоматов и автоматов с магазинной памятью, методы синтаксического анализа и перевода для классов формальных грамматик, используемых для описания основных конструкций языков программирования, а так же уметь самостоятельно формально описывать синтаксис и семантику несложных языков программирования, разрабатывать алгоритмы синтаксического анализа для наиболее часто используемых классов формальных грамматик.
5
Тема 1. Теоретические основы построения компиляторов
Упрощенная модель компилятора
Как известно, программы для вычислительных машин представляют собой тексты, написанные на специальных языках, называемых языками программирования. Различают языки программирования высокого и низкого уровня.
Язык программирования высокого уровня позволяет создавать программы наиболее удобным для программиста образом. Написанная программа непосредственно реализовывает алгоритм решения поставленной задачи. Основой алфавита такого языка обычно является латинский алфавит, а ключевые слова имеют понятный смысл.
Язык программирования низкого уровня – это язык, реализующий алгоритм поставленной задачи с помощью простейших команд, своей структурой и содержанием ориентированных на конкретную вычислительную систему.
Однако исходную программу, написанную как на языке высокого уровня, так и на языке низкого уровня непосредственно ЭВМ не может выполнить. В любом случае такая программа должна быть переведена на язык машинных кодов – в объектную программу.
Обработку исходной программы с целью ее проверки на правильность написания и дальнейшей трансляции в объектную программу осуществляют специальные программы-трансляторы, являющиеся элементами системного программного обеспечения вычислительных систем.
Трансляторы для программ, написанных на языках низкого уровня называются ассемблерами.
Трансляторы для программ, написанных на языках высокого уровня называются – компиляторами. Далее будем рассматривать принципы построения именно компиляторов.
Современные языки программирования, обладающие определенными различиями, при этом строятся по схожим принципам, что проводит и к схожим процессам, реализуемым в компиляторах программ, написанных на различных языках. Данные процессы можно представить последовательностью фаз, которые сменяют друг друга, выдавая нужный результат, что в конце концов приводит к преобразованию программы, написанной на исходном языке в объектный код.
Кроме этого выделяется единый для всех фаз процесс анализа и исправление ошибок, которые могут быть обнаружены в обрабатываемом исходном тексте программы, а также специальное хранилище – таблицы имен, содержащие информацию о внутренних объектах программ.
Обобщенная структура компилятора, учитывающая существующие в нем фазы [3], представлена на рис. 1.1.
6
Рис. 1.1. Обобщенная структура компилятора
Таким образом, основными блоками компилятора являются лексический анализатор, синтаксический анализатор и генератор кода.
Лексический анализатор
Всоответствии с представленной выше структурой входная программа сначала подвергается лексической обработке.
Цель лексического анализа – разбиение исходной программы, представляющей цепочку символов, на известные лексемы, приведение их к одному формату и замена их условными кодами, которые называются дескрипторами. Каждый дескриптор состоит из двух частей: класса (типа) лексемы и указателя на адрес в памяти, где находится информация о конкретной лексеме. Эта информация организуется и хранится в таблицах имен.
Влюбом языке программирования имеется ограниченный набор лексемами, например, служебное слово, идентификатор, действительное число, разделитель, знак операции, комментарий.
Рассмотрим пример лексической обработки следующей строки:
IFА1=5
Лексический блок устанавливает, что данная цепочка символов представляет служебное слово IF, переменную А1, знак равенства и константу 5. Таким образом, шесть входящих символов преобразуются в поток образов четырех лексем-дескрипторов.
Переменная А1 как лексема принадлежит классу «переменная» и имеет значение, которое служит указателем на элемент таблицы имен переменных. Этот указатель на таблицу имен фактически является внутренним именем переменной А1.
Если представить таблицы имён как словарь, то лексическая обработка в какой-то степени аналогична группировке букв в слова и нахождению этих слов в словаре.
7
Синтаксический анализатор
Этот блок переводит последовательность лексем, построенную лексическим анализатором, в другую последовательность, которая непосредственно отражает порядок, в котором должны выполнятся операции в программе.
Например, С+А*В можно перевести так: УМНОЖ(А, В, R1) СЛОЖ(С, R1, R2).
Таким образом, пять лексем, полученные на выходе лексического анализатора, преобразуются в две новые единицы, которые описывают необходимые действия.
Эти новые единицы называются атомами, и образуют выход синтаксического анализатора.
Каждый атом состоит из класса и значения. Тогда атом УМНОЖ (А, В, R1) может принадлежать классу «умнож» и иметь значение в таблице имен переменных для А, В, R1 соответственно.
Внутри компилятора атом будет представлен целым числом, обозначающим «умнож», и тремя указателями, обозначающими его значение.
Выполняя необходимые преобразования, синтаксический анализатор учитывает структуру языка, и поэтому имеет название «синтаксический».
Генератор кода
Этот блок «развёртывает» атомы, построенные синтаксическим анализатором, в последовательность команд вычислительной машины, которые выполняют соответствующие действия.
Точный характер этого развёртывания может зависеть от элементов таблицы, на которые ссылаются атомы, и от ожидаемого состояния вычислительной машины в момент фактического выполнения команд.
Чтобы порождаемый код был эффективным, часто требуется, чтобы генератор кода основательно анализировал содержимое различных реестров машины в период выполнения программы – это позволяет избежать повторной загрузки уже доступной информации и выбрать наиболее подходящие регистры для хранения переменных, промежуточных результатов и др.
Та часть работы компилятора, которая позволяет получать более эффективное представление объектной программы называется оптимизацией. Иногда в компиляторах присутствует специальный блок оптимизации перед генератором кода.
Эффект оптимизации часто состоит в переупорядочивании атомов.
Варианты взаимодействия блоков транслятора
Организация процесса трансляции может осуществляться различным образом. Это определяется различными вариантами взаимодействия блоков транслятора: лексического анализатора, синтаксического анализатора
8
и генератора кода. Несмотря на одинаковый конечный результат, различные варианты взаимодействия блоков транслятора обеспечивают различные варианты хранения промежуточных данных. Можно выделить два основных варианта взаимодействия блоков транслятора:
многопроходную организацию, при которой каждая из фаз является независимым процессом, передающим управление следующей фазе только после окончания полной обработки своих данных;
однопроходную организацию, при которой все фазы представляют единый процесс и передают друг другу данные небольшими фрагментами.
На основе двух основных вариантов можно также создавать их разнообразные сочетания.
Разбиение на проходы приводит к дополнительным затратам ресурсов вычислительной системы, но есть объективные причины необходимости этого:
логика языка; оптимизация кода; экономия памяти.
Каждый проход компилятора можно организовать в виде отдельного блока или комбинации нескольких блоков.
Для того, чтобы понять, как строятся и функционируют компиляторы необходимо знать теорию построения языков программирования и существующие теоретические методы трансляции. Таким образом, излагаемая далее теория имеет непосредственное приложение в разработке современного программного обеспечения вычислительных систем.
Формальное описание языка. Понятие метаязыка
Разработка нового языка программирования начинается с определения его синтаксиса и семантики [5].
Определение 1.1. Правила, определяющие структуру предложений языка, образуют его синтаксис.
Определение 1.2. Семантика языка – это описание множества смыслов и соответствия между смыслами и предложениями.
Семантика языка зависит от характера объектов, описываемых языком, и средства ее изучения различны для различных типов языков. Синтаксис же языка в меньшей степени зависит от назначения языка и может изучаться методами, не зависящими от содержания и назначения языка.
Для описания синтаксиса языка программирования, в свою очередь, нужен также некоторый класс языков. Язык, предназначенный для описания другого языка, называют метаязыком.
Исторически первым метаязыком, который использовался на практике для описания синтаксиса языков программирования (в частности Ал-
9