Трансляция, компиляция и интерпретация программ

3 ТРАНСЛЯЦИЯ, КОМПИЛЯЦИЯ И ИНТЕРПРЕТАЦИЯ ПРОГРАММ. Основные понятия Транслятором называется программа, которая переводит программу с некоторого входного языка в программу на выходном языке. Кроме понятия «транслятор» имеется термин «компилятор». Компилятором называется транслятор, который переводит программу на входном языке в программу на ассемблере или в машинных кодах. Полученная компилятором программа не может быть непосредственно выполнена, так как для этого необходима работа программы-загрузчика, загружающего программу в память. Процесс компиляции состоит из двух этапов – анализа и синтеза. Рис. 4.1 - Схема работы компилятора На этапе анализа осуществляется распознавание языка исходной программы и проверка правильности конструкций и смысловых особенностей языка. Выделяют этапы лексического, синтаксического и семантического анализа. На этапе лексического анализа осуществляется чтение символов входного языка и построение элементарных слов (лексем) входного языка. Примерами лексем ЯП являются константы, идентификаторы, ключевые слова. Выделенные на этапе лексического анализа идентификаторы заносятся в специальные служебные таблицы компилятора. Модуль компилятора, выполняющий лексический анализ, называется сканером. При синтаксическом анализе выполняется проверка правильности конструкций исходной программы в соответствии с правилами грамматики, описывающей входной язык компилятора. Терминалами в такой грамматике являются лексемы. В качестве примера рассмотрим построение КС-грамматики для выражений. Для этого применим следующий алгоритм: 1) все допустимые операции в выражении упорядочим в порядке возрастания приоритета. 2) Каждому уровню приоритета i поставим соответствие нетерминал Аi, причем нетерминалу А0 («выражение») соответствует самый низкий уровень приоритета 0. Тогда получим нетерминалы А0…Аn. 3) Добавим нетерминал Аn+1, соответствующий понятию «элементарное выражение». 4) Для каждого нетерминала Аi (0<=i<=n) запишем правила: - для бинарной операции, выполняющейся слева направо Аi->Ai+Ai+1 - для бинарной операции, выполняющейся справа налево Аi->Ai+1+Ai - для унарной префиксной операции, используем. однократно Ai->+Ai+1 - для унарной префикс.операции, используем. многократно Ai->+ Ai - для унарной постфиксной операции, использ. однократно Ai->Ai+1+ - для унарной постфикс.операции, используем. многократно Ai->Ai+ 5) Для каждого нетерминала Аi (0<=i<=n) добавим правило Ai->Ai+1 6) Для Аn+1 записываются правила двух типов: Аn+1-> <идентификатор>  <константа>  <вызов ф-ции> … Аn+1-> (А0) Унарные операции «+» и «-« поднимают в таблице приоритетов до верхнего уровня, соответствующего А0. Например, пусть выражение состоит из идентификаторов, целых констант, связанных знаками «+», «-«, «*», «/». КС-грамматика, описывающая синтаксис выражения, имеет вид: А0 -> +A1  –A1  A0+A1  A0-A1  A1 А1 -> A1*A2  A1/A2  A2 А2 -> <идентификатор> <константа>  (A0) Существуют различные подходы при построении блока синтаксического анализа, зависящие от метода грамматического разбора исходной программы и от особенностей входного языка. Семантический анализ отвечает за проверку соответствия текста программы смысловым особенностям языка, например, правильности использования идентификаторов с точки зрения обязательности их описания и области видимости, проверку корректности обращений к функциям, элементам массивов. Результатом работы блока анализа является внутренняя форма представления исходной программы, являющаяся промежуточной для этапа синтеза объектного кода. На этапе генерации кода осуществляется формирование конструкций программы на выходном языке. Генерация включает в себя оптимизацию кода, необходимую для улучшения его эффективности. Процесс компиляции состоит из нескольких этапов, причем для различных компиляторов некоторые из них могут быть объединены. Процесс обработки исходной программы может быть выполнен за один ее просмотр или проход, тогда говорят об однопроходном компиляторе. На практике же современные компиляторы выполняют несколько проходов, на каждом из которых формируются промежуточные данные, необходимые для последующих проходов. При выполнении каждого последующего прохода компилятору доступны результаты более ранних проходов, и текст исходной программы. Результаты проходов являются данными, недоступными пользователю, как правило, они хранятся в оперативной памяти или во временных файлах на диске. Идеал – это однопроходные компиляторы, однако они реальны только для очень простых языков с жестким синтаксисом и семантикой. Обычно компиляторы имеют от 2 до 5 проходов. Интерпретатор – это программа. которая осуществляет проверку правильности синтаксических конструкций входного языка и организует их выполнение. Результирующую программу интерпретатор не порождает. Это означает, что оптимизация исходной программы для интерпретатора, в отличие от компилятора, отсутствует. Преимуществом интерпретатора перед компилятором является относительная простота его реализации и независимость от архитектуры вычислительной системы, где будет выполняться программа. Примером интерпретируемого языка является HTML. Примером простейшего компилятора является компилятор с языка Ассемблер, где один оператор исходного языка транслируется в одну машинную команду. Синтаксис языка описывается простой КС-грамматикой, а семантический анализ необходим для проверки правильности типов операндов для команд, проверки описания идентификаторов и меток и правильного употребления ключевых слов ассемблера. Рассмотрим алгоритмы построения блоков компилятора более подробно. Сначала рассмотрим пример описания с помощью КС-грамматики модельного языка. Программа: главная программа языка VMKS. Допускается описание функций с параметрами, тип void. Типы данных: integer, symbol Операции: арифметические (+-*/), сравнения (==,<>) Операторы: присваивания, if Операнды: простые переменные, константы Константы: целые, символьные Грамматика имеет вид: S -> <описание функции>S | <описание переменных>S | -> general <блок> <описание функции> -> void <идентификатор> (<список параметров>) <блок> <описание переменных> -> integer <список переменных>; | symbol <список переменных>; <список параметров> -> <список параметров>,<элемент списка параметров>|<элемент списка параметров> <элемент списка параметров> -> <тип параметра> <идентификатор> <тип параметра> -> integer | symbol <список переменных> -> <элемент списка>,<список переменных> | <элемент списка> <элемент списка> -> <идентификатор> | <идентификатор> = <константа> <константа> -> <целая константа> | <символьная константа> <идентификатор> -> <буква><символы> <символы> -> <буква><символы>|<цифра><символы>| <блок> -> begin<операторы>end <операторы> -> <один оператор><операторы> |  <один оператор> -> <присваивание> | | <описание переменных> | <блок> | <вызов функции> <присваивание> -> <идентификатор>=<выражение>; <выражение> -> <выражение>==<слагаемое> | <выражение> <> < слагаемое > | +<слагаемое > | -< слагаемое > | <слагаемое> <слагаемое> -> <слагаемое> + <множитель> | <слагаемое> - <множитель> | <множитель> <множитель> -> <множитель> * <элементарное выражение> | <множитель> / <элементарное выражение> | <элементарное выражение> -> if <выражение> then <один оператор> <продолжение> <продолжение> -> otherwise <один оператор> |  <вызов функции> -> <идентификатор> (<фактические параметры>); <фактические параметры> -> <выражение>, <фактические параметры> | <выражение> <элементарное выражение> -> <идентификатор>| <целая константа> |(<выражение>)| <символьная константа> <целая константа> -> 0| <цифра не ноль><цифры> <символьная константа> -> ‘<один символ>’ <цифры> -> <цифры><цифра> |  <один символ> -> <буква>|<цифра>|… <буква> -> a|b|c|…|z|A|B|C|…|Z <цифра> -> 0|1|2|…|9 <цифра не ноль> -> 1|2|…|9 4 Лексический анализ Лексема – это структурная единица языка, которая состоит из символов языка и не содержит в себе других лексем. Лексемами языков программирования являются идентификаторы, константы, ключевые слова, знаки операций. Лексический анализатор (сканер) – это часть компилятора, выполняющая чтение исходной программы и выделение в ее тексте лексем. Теоретически лексический анализ можно совмещать с синтаксическим, однако это совмещение практически отсутствует в современных компиляторах из-за следующих причин: - сканер упрощает анализ исходного текста, позволяя отбросить комментарии и незначащие элементы входного текста, например, пробелы; - сканер работает по простым алгоритмам, а синтаксический анализатор – по достаточно сложным, поэтому их целесообразно не смешивать вместе; - изменение синтаксиса языка не повлечет изменения сканера, так как лексический уровень языка при этом останется без изменений. Возможны два метода связи лексического и синтаксического анализаторов. При первом методе сканер анализирует всю исходную программу и формирует последовательность лексем, которая затем поступает на вход синтаксическому анализатору. При втором методе синтаксический анализатор вызывает сканер по мере необходимости получения очередной лексемы из текста программы. Так как сканер выделяет такие лексемы, как идентификаторы и константы, описываемые регулярными выражениями, то распознавать эти выражения возможно с помощью конечных недетерминированных автоматов-распознавателей. Конечный автомат-распознаватель для цепочки входного языка определяет ее принадлежность языку, поэтому в основе алгоритма работы сканера лежит алгоритм работы конечного автомата. Сканер должен определять границы лексем, формировать лексему и выдавать сообщение об ошибке в лексеме, если текущий входной символ не соответствует ожидаемому для конечного автомата. Как правило, границами лексем являются такие терминальные символы, как пробелы, специальные символы. Перед программированием сканера строится таблица лексем языка, в которой для каждой лексемы указывается ее изображение, тип и символ-ограничитель. Тип каждой лексемы должен быть уникален и кодироваться целым числом. В таблицу лексем вводятся специальный символ конца исходного модуля и тип, соответствующий ошибочному символу. ПРИМЕР. Для выделения лексем языка строится конечный автомат, детерминируется, в его заключительных состояниях отмечается тип лексемы, распознанной в этом состоянии. Так как ключевые слова языка представляют собой идентификаторы, то для простоты конечный автомат выделяет идентификатор, а в программе сканера осуществляется его сравнение со множеством ключевых слов, после чего устанавливается тип выделенной лексемы. Рассмотрим практическую реализацию сканера. Сканер – это функция, которая при одном обращении к ней выделяет одну лексему и возвращает изображение лексемы и ее тип. В своей работе сканер использует следующие глобальные данные: #define MaxText 100000 // макс. длина текста #define MaxLex 25 // макс. длина одной лексемы char t[MaxText]; //текст исходной программы int uk; // указатель на текущий символ в тексте int str, stolb; // строка и столбец в тексте Изображение и тип лексемы определяются как typedef char LEX[MaxLex]; LEX l; // изображение лексемы int typ; // тип лексемы Перед программированием сканера определяется, какие комментарии предусмотрены в тексте исходного модуля. Это необходимо для организации пропуска комментариев в тексте. Также пропускаются пробелы, символы перевода строки, комментарии. Программа сканера имеет вид: int skaner(LEX l) { int typ; // тип лексемы int i; // текущая длина лексемы for(i=0;i;} else { реализация модели КА и возврат типа лексемы} } Конечный автомат распознает лексемы и возвращает их тип. Различают явный и неявный способы программирования сканера. При явном способе сканер является универсальной программой, работающей с последовательностью правил автомата в соответствии со значением текущего состояния и символа на входе автомата. При неявном способе программирования сканера понятие текущего состояния отсутствует, и код сканера для каждого состояния осуществляет проверки, необходимые в этом состоянии. Каждому состоянию ставится в соответствие метка и сканер имеет вид: Met1: обработка состояния 1 … Metn: обработка состояния N Метка Met1 при этом должна соответствовать начальному состоянию. Обработка состояния зависит от типа состояния (начальное, заключительное, обычное): 1. Если состояние ни начальное, ни заключительное: Metk: if (t[uk]==’a’) {l[i++]=t[uk++]; goto Metm;} else if (t[uk]==’b’) {l[i++]=t[uk++]; goto Metn;} else {PrintError(…); return <тип ошибки>;} Программа выдачи текста ошибки работает с передаваемым в функцию номером ошибки, сообщая номер строки и столбца текста, где она находится. Ошибка выдается сканером, если обнаружен недопустимый символ, или найдена ошибка в структуре лексемы. Для лексем, фактическая длина которых превышает зарезервированную возможную длину, можно выдавать предупреждение и «урезать» лексему, либо сообщать об ошибке. Для проверки символа на букву или цифру осуществляется его сравнение с границами их возможных диапазонов: (t[uk]>=’0’)&&(t[uk]<=’9’). 2. Если состояние k – начальное, то после PrintError() надо выполнить увеличение указателя uk++, чтобы не было зацикливания, и последующие обращения к сканеру были возможны. 3. Если переход в заключительное состояние, из которого больше нет переходов, то нужно добавить символ в лексему и выполнить возврат return <тип лексемы>, Если распознан идентификатор, то для корректного возврата типа надо проверить, не ключевое ли это слово. 4. Если состояние k – заключительное, то Metk: if (t[uk]==’a’) {l[i++]=t[uk++]; goto Metm;} else if (t[uk]==’b’) {l[i++]=t[uk++]; goto Metn;} else {return <тип лексемы для состояния k>;} Например, пусть сканер распознает целые константы, знаки «+», «=», «==». Конечный автомат: q0 Тогда фрагмент сканера для конечного автомата имеет вид: q0: if ((t[uk]<=’9’)&&(t[uk]>=’0’) {l[i++]=t[uk++]; goto q1;} else if (t[uk]==’+’) {l[i++]=t[uk++]; return t_plus;} else if (t[uk]==’=’) {l[i++]=t[uk++]; goto q3;} else {PrintError(…); return t_error;} q1: while((t[uk]<=’9’)&&(t[uk]>=’0’) l[i++]=t[uk++]; return t_const; q3: if (t[uk]==’=’) {l[i++]=t[uk++]; return t_twoequal;} else return t_oneequal; При программировании сканера целесообразно запрограммировать модули defs.h, scaner.hpp, scaner.cpp. Кроме функции выдачи ошибки предусмотреть функции int GetUk(void) и void SetUk(int uk1).