ГЛАВА 2. БАЗОВЫЕ ПОНЯТИЯ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК
Глава 1. место трансляторов в системном программном обеспечении. основные фазы процесса трансляции
РАЗДЕЛ I. ЭЛЕМЕНТЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК. ОСНОВНЫЕ МЕТОДЫ И СРЕДСТВА ТРАНСЛЯЦИИ
Основы построения трансляторов
Им. академика М.ф. решетнева
Сибирский государственный аэрокосмический университет
Курс лекций по дисциплине «Системное программное обеспечение»
Красноярск 2011 г.
В данной главе излагаются некоторые основные сведения о месте, занимаемом трансляторами в системном программном обеспечении ЭВМ, а также приводится информация о видах и функциях трансляторов. Размещенная в данной главе обобщенная схема компилятора позволяет ознакомиться с сущностью и назначением основных фаз процесса трансляции.
Системное программное обеспечение – совокупность программных и языковых средств, предназначенных для поддержания функционирования ЭВМ и наиболее эффективного выполнения ею целевого назначения. Системные программы осуществляют организацию вычислительного процесса и управление ресурсами ЭВМ. Вследствие этого они обычно тесно связаны со структурой машины, для которой созданы.
По функциональному назначению в системном программном обеспечении можно выделить две системы: операционную систему и систему программирования.
Операционная система – комплекс программ, которые обеспечивают управление аппаратурой ЭВМ, планирование эффективного использования ее ресурсов, автоматизацию процесса подготовки программ и прохождения их в ЭВМ, взаимодействие между пользователем и вычислительной машиной.
Система программирования – совокупность программных средств, обеспечивающих автоматизацию разработки и отладки пользовательских программ.
Понятие системы программирования возникло с появлением языков программирования более высокого по сравнению с машинным уровня, что повлекло за собой разработку специальных программных средств, которые должны обеспечивать перевод программ, записанных в терминах входного языка, на внутренний язык вычислительной машины. Таким образом, система программирования включает в себя, по крайней мере, два компонента: входной язык системы и транслятор с этого языка.
Система программирования тесно связана с операционной системой. Все трансляторы, входящие в состав систем программирования, работают под управлением операционной системы, являясь одновременно составной частью последней (функционально трансляторы принадлежат к группе системных обрабатывающих программ операционной системы).
Таким образом,основные функции системы программирования следующие:
- трансляция (перевод) программ пользователей с языка программирования в машинные коды команд;
- регистрация синтаксических и логических ошибок в программах.
Средства системы программирования, выполняющие эти функции, включают в себя ассемблеры, компиляторы и интерпретаторы.
Трансляторы, которые используются для программ, написанных на языке Ассемблера, называются ассемблеры.
Для трансляции программ с языков высокого уровня используются компиляторы или интерпретаторы.
Компиляторы – преобразуют операторы языка в машинные коды целиком для всей программы. В результате обработки исходного текста программы формируется объектный модуль, который затем может многократно выполняться после его загрузки в оперативную память.
Интерпретаторы – осуществляют преобразование операторов в машинные коды во время выполнения программы. После запуска программы в оперативную память одновременно загружаются исходный текст программы, написанный на языке высокого уровня, и интерпретатор, который последовательно транслирует операторы программы и сразу же их выполняет.
В современных ЭВМ одни и те же языки программирования могут быть представлены как компилирующие или интерпретирующие системы программирования.
Интерпретирующие системы программирования эффективны на этапе разработки программ, так как минимизируют время на отладку. Применение режима интерпретации для многократного выполнения отлаженных программ нецелесообразно, так как интерпретатор занимает дополнительный объем оперативной памяти, а также из-за трансляции замедляется выполнение программы.
Компилирующие СП эффективны при регулярной эксплуатации программ, так как имеется уже готовый к выполнению объектный модуль, что экономит время, затрачиваемое на трансляцию, и место в оперативной памяти. Разработка и отладка программ с использованием компилятора связаны с дополнительными временными затратами на трансляцию всего текста при определении ошибки.
Рассмотрим обобщенную структуру компилятора и основные фазы процесса компиляции (рис. 1.1).
На фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы – слова в соответствии с определениями языка. Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором для получения очередной лексемы, либо как полный проход, результатом которого является файл лексем.
В процессе выделения лексем лексический анализатор может как самостоятельно строить таблицы объектов (идентификаторов, строк, чисел и т.д.), так и выдавать значения для каждой лексемы при очередном к нему обращении. В этом случае таблицы объектов строятся в последующих фазах (например, в процессе синтаксического анализа).
Рис. 1.1. Структурная схема компилятора
На этапе лексического анализа обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.).
Основная задача синтаксического анализа – разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)анализ (и его вариант – рекурсивный спуск), либо LR(1) анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) – при использовании систем автоматического построения синтаксических анализаторов.
Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицы объектов. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.
На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи «описание-использование», в частности, анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа таблицы объектов пополняются информацией об описаниях (свойствах) объектов.
Основным формализмом, использующимся при контекстном анализе, является аппарат атрибутных грамматик. Результатом контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть рассредоточена в самом дереве или сосредоточена в отдельных таблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.
Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие.
Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная – только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д.
Наконец, генерация кода – последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различные синтаксические методы. Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.
В этой главе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков - грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования.
Алфавит (или словарь) - это конечное множество символов.
Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.
Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Синонимы цепочки – предложение, строка или слово.
Цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ e.
Более формально цепочка символов в алфавите V определяется следующим образом:
1) e - цепочка в алфавите V;
2) если a - цепочка в алфавите V и a - символ этого алфавита,
то aa - цепочка в алфавите V;
3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).
Если a и b - цепочки, то цепочка ab называется конкатенацией (илисцеплением) цепочек a и b.
Например, если a = ab и b = cd, то ab = abcd.
Для любой цепочки a всегда ae = ea = a.
Обращением (илиреверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке.
Обращение цепочки a будем обозначать aR.
Например, если a = abcdef, то aR = fedcba.
Для пустой цепочки: e = eR.
Длина цепочки- это число составляющих ее символов.
Например, если a = abcdefg, то длина a равна 7.
Длину цепочки a будем обозначать | a |. Длина e равна 0.
n-ой степенью цепочки a(будем обозначать an) называется конкатенация n цепочек a.
a0 = e; an = aan-1 = an-1a.
Язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.
