Структура компилятора. Типы транслирующих программ.

Исходная программа (написанная на каком-либо языке программирования) представляет собой последовательность символов, которая вводится в компьютер и преобразуется в форму, пригодную для непосредственного выполнения. Компилятор является программой, которая способна воспринимать строку символов определенного вида (т.е. текст программы на исходном языке) и выдавать другую строку символов (программу на машинном языке). Компиляторам присущ ряд общих черт, что упрощает процесс создания компилирующих программ. В состав любого компилятора входят три основных компонента: - лексический анализатор (блок сканирования); - синтаксический анализатор; - генератор кода машинных команд. Принцип действия анализаторов можно описать с помощью формальных моделей, в то время как для генератора кода пока не существует общепринятых четких формальных представлений. На фазе лексического анализа исходный текст программы в виде цепочки несвязанных друг с другом символов разбивается на единицы, называемые лексемами. Такими текстовыми единицами являются ключевые слова, используемые в языке (например, IF,DO и др.), имена переменных, константы и знаки операций (например,* или +). Далее эти слова рассматриваются как неделимые образования, а не как группы отдельных символов. После разбиения программы на лексемы следует фаза синтаксического анализа, называемая грамматическим разбором, на которой проверяется правильность следования операторов. Например, для предложения IF, имеющего вид IF выражение THEN предложение; грамматический разбор состоит в том, чтобы убедиться, что вслед за лексемой IF следует правильное выражение, за этим выражением следует лексема THEN, за которой в свою очередь следует правильное предложение, оканчивающееся знаком ";". Последним выполняется процесс генерации кода, который использует результаты синтаксического анализа и создает программу на машинном языке, пригодную к выполнению. Хотя в состав любого компилятора входят все три описанных выше компонента, их взаимодействие может осуществляться разнообразными способами. Рассмотрим наиболее распространенные варианты взаимосвязи между этими компонентами. Блок сканирования считывает исходную программу и представляет ее в форме файла лексем. Синтаксический анализатор читает этот файл и выдает новое представление программы, например, в постфиксной форме. Наконец, этот файл считывается генератором кода, который создает объектный код программы. Компилятор такого вида называется трехпроходным (рис.1.1), так как программа считывается трижды (исходный текст программы, файл лексем и файл в постфиксной форме). Недостаток: Невысокая скорость выполнения, так как в большинстве вычислительных систем операции, связанные с обращением к файлам, осуществляются сравнительно медленно. Преимущества: Относительная независимость каждой фазы компилирования. Так как связь между обрабатывающими блоками осуществляется только через файлы данных, любой проход может быть реализован независимо от остальных. Это обеспечивает: 1. Возможность автономной разработки различных блоков компилятора разными разработчиками, необходимо только согласовать форматы промежуточных файлов. 2. Гибкость компилятора. Например, для реализации одного и того же языка для различных типов компьютеров, возможно использовать одни и те же блоки сканирования и синтаксического анализа, но написать специальные генераторы кода для каждого типа компьютера. При реализации семейства компиляторов с различных языков для одного типа компьютеров, очевидно, потребуются различные блоки сканирования и синтаксического анализа, но возможно использование общего генератора кода. 3. Минимальные требования к объему используемой оперативной памяти (модули различных фаз компиляции можно загружать по очереди, выгружая при этом предыдущий). Для достижения высокой скорости компиляции применяется компилятор с однопроходной структурой. В этом случае синтаксический анализатор выступает в роли основной управляющей программы, вызывая блок сканирования и генератор кода, организованные в виде подпрограмм. Синтаксический анализатор постоянно обращается к блоку сканирования, получая от него лексему за лексемой из просматриваемой программы, до тех пор, пока не построит новый элемент постфиксной записи, после чего он обращается к генератору кода, который создает объектный код для этого фрагмента программы. Преимущество: Максимальная эффективность и скорость выполнения, так как программа просматривается лишь однажды, количество операций обращения к файлам минимально (только чтение из исходного и запись в объектный файлы). Недостатки: 1. Проблемы при организации переходов вперед. Например, во время обработки предложения GOTO метка; могут встретиться трудности, так как "метка" еще не встречалась в тексте программы. 2. Неоптимальность создаваемой объектной программы. Например, если встречается текст: А = (В + С); Р = (В + С) + (Е + М); компилятор мог бы построить более эффективный объектный код, трансформировав программу следующим образом: А = (В + С); Р = А + (Е + М); Однако однопроходный компилятор может утратить часть нужной информации к тому времени, когда в тексте встретится формула (Е + М). 3. Поскольку однопроходный компилятор должен полностью размещаться в памяти, его реализация сопровождается повышенными требованиями к ресурсу памяти, которые не всегда можно удовлетворить, имея систему с ограниченным объемом памяти. Для повышения эффективности выполнения объектной программы в процесс компилирования может включаться фаза оптимизации. Блок оптимизации легко встраивается в трехпроходный компилятор, где размещается, обычно, между синтаксическим анализатором и генератором кода. На этой фазе постфиксный файл используется в качестве входных данных и создается новый файл, содержащий постфиксную запись эквивалентной программы с улучшенными характеристиками. Поскольку блок оптимизации записывает свои выходные данные в формате постфиксного файла, генератор кода не нуждается в изменении. На практике возможность оптимизации предусматривается по желанию пользователя: если необходимо, чтобы время компилирования было небольшим, блок оптимизации игнорируется; если же требуется получить программу с высокой скоростью выполнения, то после работы синтаксического анализатора вызывается блок оптимизации. Возможны и другие способы структурной организации компилятора. На рис.1.3 показана структура двухпроходного компилятора, занимающая промежуточное положение между двумя описанными выше вариантами организации. В этом случае синтаксический анализатор, вызывая блок сканирования, получает лексему за лексемой и строит файл постфиксной записи программы. Генератор кода считывает этот файл и создает объектный код программы. Подобной структуре свойственно относительно небольшое время выполнения, так как программа считывается лишь дважды (исходный текст и постфиксная запись). В этом случае легко разрешается проблема с оператором перехода вперед на метку, так как эта метка считывается на фазе первого прохода, перед вызовом генератора кода. В такой компилятор при необходимости легко включить блок оптимизации. Возможны различные модификации рассмотренных схем. Ясно, что рассмотренные типы компиляторов проявляют свои достоинства в определенных условиях работы и оказываются неэффективными в других случаях. Интерпретаторы реализуют принцип, альтернативный компилированию. Компиляторы и интерпретаторы имеют много общего. Интерпретатор, тоже вначале просматривает исходную программу и выделяет в ней лексемы. Для этого используются блоки сканирования и анализаторы, аналогичные тем, которые входят в состав компилирующих программ. Однако интерпретатор вместо построения объектного кода, Достоинства интерпретатора: - относительная простота реализации; - удобство отладки программ. Достоинства компилятора: - скорость выполнения; - независимость выполняемого кода от системы программирования; - возможность передавать программы заказчикам без исходных текстов. Большинство современных интерпретаторов выполняют не исходный код, а преобразуют его в промежуточный, который затем интерпретируется. Это позволяет несколько повысить скорость исполнения и избежать передачи заказчикам исходных текстов. Для трансляции классических языков программирования (C, C++, Паскаль, Delphi и др.) обычно используются компиляторы. Как интерпретаторы выполнены большинство реализаций Бейсика и языков управления СУБД. Язык сетевого программирования Java реализован как интерпретируемый специальной виртуальной Java-машиной. Это обеспечивает возможность исполнения промежуточного кода Java на любом типе компьютера, где имеется такая виртуальная Java-машина. Поскольку компилятор преобразует исходную программу в совокупность битов, полученную строку битов можно использовать и на другой машине. Так как подготовка программы для одного типа ЭВМ осуществляется с помощью ЭВМ другого типа, соответствующие компиляторы получили название "кроссовых" (т.е. перекрестных). Конвертор – это транслятор с одного языка на другой язык того же уровня. Примером конвертора может быть программа, преобразующая код на языке Паскаль в код на С, или данные об объекте проектирования во внутреннем формате одной САПР в формат другой САПР. Уточним термины. Под транслятором понимают любую программу, которая преобразует строку символов (т.е. исходную программу) в другую строку символов (объектную программу). Результатом этого процесса может быть как программа на машинном языке для той или иной машины, так и исходный текст программы на каком-либо другом языке. Термин "компилятор" будем использовать, понимая под ним программу, которая осуществляет классическое преобразование исходной программы в программу на машинном языке. Если же будут подразумеваться все разновидности процесса трансляции, будем использовать термин "транслятор".