КОНСПЕКТ ОБЗОРНОЙ ЛЕКЦИИ

 

Для студентов специальности
Т1002 «Программное обеспечение информационных технологий»

(А.М.Кадан, к.т.н., доцент)

 

Вопрос №44.
ЭЛЕМЕНТЫ ТЕОРИИ ТРАНСЛЯЦИИ

 

1.      Общие схемы трансляции

2.      Фазы лексического, синтаксического семантического анализа

3.      Таблицы идентификаторов

4.      Классификация распознавателей

5.      Языки и автоматы

 

Общие схемы трансляции

 

Практически во всех трансляторах (и в компиляторах, и в интерпретаторах) в том или ином виде присутствует большая часть перечисленных ниже процессов:

§         лексический анализ

§         синтаксический анализ

§         семантический анализ

§         генерация внутреннего представления программы

§         оптимизация

§         генерация объектной программы.

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

 

Транслятор — это программа, которая переводит входную программу на исход­ном (входном) языке в эквивалентную ей выходную программу на результирую­щем (выходном) языке. В этом определении слово «программа» встречается три раза, и это не ошибка и не тавтология. В работе транслятора, действительно, уча­ствуют всегда три программы.

 

Компилятор — это транслятор, который осуществляет перевод исходной програм­мы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера.

Таким образом, компилятор отличается от транслятора лишь тем, что его ре­зультирующая программа всегда должна быть написана на языке машинных ко­дов или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке — возможен, например, транслятор программ с языка Pascal на язык С. Соответственно, всякий компилятор являет­ся транслятором, но не наоборот — не всякий транслятор будет компилятором

 

Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и выполняет ее.

В отличие от трансляторов интерпретаторы не порождают результирующую про­грамму (и вообще какого-либо результирующего кода) — и в этом принципиаль­ная разница между ними. Интерпретатор, так же как и транслятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семанти­кой входного языка.

 

Этапы трансляции. Общая схема работы транслятора

 

На рисунке представлена общая схема работы компилятора. Из нее видно, что в целом процесс компиляции состоит из двух основных этапов — синтеза и анализа.

На этапе анализа выполняется распознавание текста исходной программы, соз­дание и заполнение таблиц идентификаторов. Результатом его работы служит некое внутреннее представление программы, понятное компилятору.

На этапе синтеза на основании внутреннего представления программы и инфор­мации, содержащейся в таблице (таблицах) идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код.

 

Далее дается перечень основных фаз (частей) компиляции и краткое описание их функций. Более подробная информация дана в подразделах, соответствую­щих этим фазам.

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

·         применение лексического анализатора упрощает работу с текстом исходной программы на этапе синтаксического разбора и сокращает объем обрабаты­ваемой информации, так как лексический анализатор структурирует посту­пающий на вход исходный текст программы и выкидывает всю незначащую информацию;

·         для выделения в тексте и разбора лексем возможно применять простую, эф­фективную и теоретически хорошо проработанную технику анализа, в то вре­мя как на этапе синтаксического анализа конструкций исходного языка ис­пользуются достаточно сложные алгоритмы разбора;

·         сканер отделяет сложный по конструкции синтаксический анализатор от ра­боты непосредственно с текстом исходной программы, структура которого может варьироваться в зависимости от версии входного языка — при такой конструкции компилятора для перехода от одной версии языка к другой дос­таточно только перестроить относительно простой лексический анализатор.

В основ­ном лексические анализаторы выполняют исключение из текста исходной про­граммы комментариев, незначащих пробелов, символов табуляции и перевода строки, а также выделение лексем следующих типов: идентификаторов, строко­вых, символьных и числовых констант, ключевых (служебных) слов входного языка, знаков операций и разделителей.

 

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

 

Семантический анализ — это часть компилятора, проверяющая правильность текста исходной программы с точки зрения семантики входного языка. Кроме непосредственно проверки, семантический анализ должен выполнять преобра­зования текста, требуемые семантикой входного языка (такие, как добавление функций неявного преобразования типов). В различных реализациях компиля­торов семантический анализ может частично входить в фазу синтаксического разбора, частично — в фазу подготовки к генерации кода.

 

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

 

Генерация кода — это фаза, непосредственно связанная с порождением команд, составляющих предложения выходного языка и в целом текст результирующей программы. Это основная фаза на этапе синтеза результирующей программы. Кроме непосредственного порождения текста результирующей программы, гене­рация обычно включает в себя также оптимизацию — процесс, связанный с обра­боткой уже порожденного текста. Иногда оптимизацию выделяют в отдельную фазу компиляции, так как она оказывает существенное влияние на качество и эффективность результирующей программы (см. разделы «Генерация кода. Ме­тоды генерации кода» и « Оптимизация кода. Основные методы оптимизации»).

Таблицы идентификаторов

 

Таблицы идентификаторов (иногда - «таблицы символов») — это специальным образом организованные наборы данных, служащие для хранения информации об элементах исходной программы, которые затем используются для порожде­ния текста результирующей программы. Таблица идентификаторов в конкрет­ной реализации компилятора может быть одна, или же таких таблиц может быть несколько. Элементами исходной программы, информацию о которых нужно хра­нить в процессе компиляции, являются переменные, константы, функции и т. п. — конкретный состав набора элементов зависит от используемого входного языка программирования. Понятие «таблицы» вовсе не предполагает, что это хранилище данных должно быть организовано именно в виде таблиц. Оно может быть организовано в виде списков, деревьев и т.д.

Построение дерева вывода и генерация кода

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

Первым шагом общего алгоритма анализа должно являться построение таблицы лексем, выполняемое лексическим анализатором (сканером). Входной информацией для сканера является исходная программа, воспринимаемая как последовательность символов.

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

По последовательности лексем, таблице идентификаторов и матрице предшествования (которая задает структуру языка, т.е. как бы выполняет роль грамматики) выполняется разбор цепочки. Результатом разбора является проверка цепочки на синтаксическую правильность и для правильных цепочек - построение последовательности правил вывода (для неправильных цепочек выдается сообщение об ошибке). Таким образом, получение последовательности правил вывода – это второй шаг общего алгоритма анализа.

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

Например. Пусть правила грамматики имеют следующий вид:

P: E ® -E (правило 1)
E ® E | E&E (правила 2 и 3)
E ® E | E^E (правила 4 и 5)
E ® (E) | p (правила 6 и 7)

Пусть входная цепочка имеет вид -p^p&p.

Вывод ее в грамматике имеет вид

E ® -E ® -E&E ® -E&p ® -E^E&p ® -E^p&p ® -p^p&p

Или пусть входная цепочка -p&p^p.

Вывод ее:

E ® -E ® -E&E ® -E&E^E ® -E&E^p ® -E&p^p ® -p&p^p

Деревья вывода для этих двух примеров приведены ниже


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

Построенное дерево и будет деревом синтаксического разбора предложения грамматики.

Генерация объектного кода - это перевод компилятором внутреннего представления исходной программы в результирующую объектную программу на языке ассемблера или непосредственно на машинном языке (машинных кодах).

Генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые действия по подготовке к генерации кода: распределено адресное пространство под функции и переменные, проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной программы и т.д.

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

Примерами таких форм записи являются:

·         обратная польская запись операций;

·         тетрады операций;

·         триады операций;

·         собственно команды ассемблера.

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

Тетрады представляют собой запись операций в форме из четырех составляющих:
<операция>(<операнд1>,<операнд2>,<результат>). Тетрады используются редко, так как требуют больше памяти для своего представления, чем триады, не отражают взаимосвязи операций и, кроме того, плохо отображаются в команды ассемблера и машинные коды, так как в наборах команд большинства современных машин не встречаются операции с тремя операндами.

Триады представляют собой запись операций в форме из трех составляющих: <операция>(<операнд1>,<операнд2>), при этом один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно номеруют для удобства указания ссылок одних триад на другие. Например, выражение A := B*C + D - B*10, записанное в виде триад будет иметь вид:

1) * ( B, C )
2) + ( ^1, D )
3) * ( B, 10 )
4) - ( ^2, ^3 )
5) := ( A, ^4 )

Здесь операции обозначены соответствующим знаком (при этом присвоение также является операцией), а знак ^ означает ссылку операнда одной триады на результат другой.

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