- •Понятие транслятора. Структура транслятора. Фазы трансляции. Основные блоки транслятора.
- •Понятие транслятора. Многопроходная организация взаимодействия блоков транслятора.
- •Понятие транслятора. Однопроходная организация взаимодействия блоков транслятора.
- •Понятие транслятора. Комбинированные взаимодействия блоков транслятора.
- •Способы определения языков. Механизмы порождения и распознавания.
- •Формальные грамматики. Порождающие грамматики Хомского.
- •Конечные автоматы. Детерминированные конечные автоматы.
- •Конечные автоматы. Недетерминированные конечные автоматы.
- •Автоматы с магазинной памятью. Устройство автомата с магазинной памятью.
- •Автоматы с магазинной памятью. Детерминированные и недетерминированные автоматы с магазинной памятью.
- •Машина Тьюринга. Устройство машины Тьюринга. Отличия конечного автомата от машины Тьюринга.
- •Машина Тьюринга. Линейно-ограниченные автоматы.
- •Системы Линденмайера (l-системы). Внутреннее устройство l-систем.
- •Системы автоматической генерации компиляторов. Основные спецификации и идеологии.
- •Системы автоматической генерации компиляторов. Проект Coco/r.
- •Системы автоматической генерации компиляторов. Проект Yacc.
- •Системы автоматической генерации компиляторов. Генерация лексического анализатора.
- •Системы автоматической генерации компиляторов. Генерация синтаксического анализатора.
- •Понятие компилятора. Этапы анализа исходной программы.
- •Понятие компилятора. Лексический анализ.
- •Понятие компилятора. Синтаксический анализ.
- •Понятие компилятора. Семантический анализ.
- •Понятие компилятора. Основные фазы компиляции.
- •Понятие компилятора. Генерация кода. Основные подходы к генерации кода. Понятие целевой машины.
- •Понятие компилятора. Оптимизация кода. Основные источники оптимизации.
Понятие транслятора. Комбинированные взаимодействия блоков транслятора.
Сочетания многопроходной и однопроходной схем трансляции порождают разнообразные комбинированные варианты, многие из которых успешно используются. В качестве примера можно рассмотреть некоторые из них.
На рис. 1.11 представлена схема взаимодействия блоков транслятора, разбивающая весь процесс на два прохода. На первом проходе порождается полное промежуточное представление программы, а на втором осуществляется генерация кода. Использование такой схемы позволяет легко переносить транслятор с одной вычислительной системы на другую путем переписывания генератора кода.
Кроме этого, вместо генератора кода легко подключить эмулятор промежуточного представления, что достаточно просто позволяет разработать систему программирования на некотором языке, ориентированную на различные среды исполнения. Пример подобной организации взаимодействия блоков транслятора представлен на рис. 1.12.
Наряду со схемами, предполагающими замену генератора кода на эмулятор, существуют трансляторы, допускающие их совместное использование. Одна из таких схем представлена на рис. 1.13.
Процесс трансляции, включая и генерацию кода, может быть выполнен за любое число проходов (в примере используется однопроходная трансляция, представленная ранее на рис 1.9). Однако сформированный объектный код не исполняется на соответствующей ему вычислительной системе, а эмулируется на компьютере с другой архитектурой. Такая схема применяется в среде построенной вокруг языка программировании Java. Сам транслятор генерирует код виртуальной Java-машины, эмуляция которого осуществляется специальными средствами как автономно, так и в среде Internet браузера.
Представленная схема может иметь и более широкое толкование применительно к любому компилятору, порождающему машинный код. Все дело в том, что большинство современных вычислительных машин реализованы с использованием микропрограммного управления. А микропрограммное устройство управления можно рассматривать как программу, эмулирующую машинный код. Это позволяет говорить о повсеместном использовании последней представленной схемы.
Способы определения языков. Механизмы порождения и распознавания.
Существует два основных способа определения языков:
механизм порождения или генератор;
механизм распознавания или распознаватель.
Они тесно связаны. Первый обычно используется для описания языков, а второй для их реализации. Оба способа позволяют описать языки конечным образом, несмотря на бесконечное число порождаемых ими цепочек.
Неформально язык L - это множество цепочек конечной длины в алфавите T. Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой. Цепочки (предложения) языка строятся в соответствии с этими правилами. Достоинство определения языка с помощью грамматик в том, что операции, производимые в ходе синтаксического анализа и перевода, можно делать проще, если воспользоваться структурой, предписываемой цепочкам с помощью этих грамматик.
Механизм распознавания использует алгоритм, который для произвольной входной цепочки остановится и ответит "да" после конечного числа шагов, если эта цепочка принадлежит языку. Если цепочка не принадлежит языку, алгоритм ответит "нет". Распознаватели используются непосредственно при построении синтаксических анализаторов и являются как бы их формальной моделью. Распознаватели строятся на основе теорий конечных автоматов и автоматов с магазинной памятью.