- •Часть 1
- •Лекция №1 Предисловие п.1. Место системного программного обеспечения в компьютерной системе
- •П.2. Структура спо
- •П.3. Хакеры как движущая сила развития спо
- •Лекция №2
- •1. Формальные языки и грамматики в системе программирования
- •1.1. Структура систем программирования
- •1.2. Языки и цепочки символов. Способы задания языков
- •1.2.1. Общие представления о языках
- •1.2.2. Цепочки символов. Операции над цепочками символов
- •1.2.3. Формальное определение языка
- •1.2.4. Способы задания языков
- •Лекция №3
- •1.3. Грамматики и распознаватели
- •1.3.1. Порождающая грамматика
- •1.3.2. Запись правил грамматики с использованием метасимволов
- •Лекция №4
- •1.3.3. Распознаватели
- •1.3.4. Классификация распознавателей
- •1.3.4.1. Классификация распознавателей по компонентам
- •1.3.4.2. Классификация распознавателей по типу языков
- •Лекция №4
- •Лекция №5
- •1.3.5. Примеры классификации языков и грамматик
- •Лекция № 6
- •1.4. Технология формирования предложений языка
- •1.4.1. Выводимость цепочек
- •1.4.2. Сентенциальная форма грамматики
- •1.4.3. Левосторонний и правосторонний выводы
- •1.4.4. Дерево вывода и методы его построения
- •1.4.5. Проблема однозначности грамматик
- •2.1.2. Формальное определение компилятора
- •2.1.3. Интерпретаторы
- •2.2. Общая схема работы компилятора
- •2.3. Варианты построения компиляторов
- •2.3.1. Общие подходы в построении компиляторов
- •2.3.2. Понятие прохода
- •2.3.3. Однопроходные и многопроходные компиляторы
- •2.4. Особенности построения интерпретаторов и их взаимодействие с компиляторами
- •3.1.2. Принципы построения сканеров
- •Лекция 9
- •3.1.3. Сканер как конечный автомат
- •Лекция 10
- •3.2. Взаимодействие сканера с таблицей идентификаторов
- •3.2.1.Назначение и особенности построения таблиц идентификаторов
- •3.2.2. Простейшие методы построения таблиц идентификаторов
- •3.2.3. Построение таблиц идентификаторов по методу бинарного дерева
- •Список литературы
2.3. Варианты построения компиляторов
2.3.1. Общие подходы в построении компиляторов
В реальных компиляторах некоторые фазы компиляции могут быть разбиты на более мелкие составляющие, другие, напротив, объединены в одну фазу. Порядок выполнения фаз компиляции также может меняться в разных вариантов компиляторов.
В одном случае компилятор просматривает текст исходной программы, сразу выполняет все фазы компиляции и получает результат – объектный код. В другом случае над исходным текстом выполняются только некоторые из фаз компиляции, и получается не конечный результат, а набор некоторых промежуточных данных. Эти данные затем снова подвергаются обработке, причем этот процесс может повторяться несколько раз, т. е. в реальных компиляторах трансляция текста исходной программы выполняется как правило за несколько проходов.
2.3.2. Понятие прохода
Проходом называется процесс последовательного чтения компилятором данных из внешней памяти, их обработка и помещение результата работы во внешнюю память. Чаще всего один проход включает в себя выполнение одной или нескольких фаз компиляции. Результатом промежуточных проходов является внутреннее представление исходной программы, а результатом последнего прохода – объектная программа. В качестве памяти могут выступать различные носители информации (оперативная память компьютера, накопители на магнитных дисках и т. д.). Современные компиляторы используют, как правило, для хранения данных оперативную память компьютера и только в редких случаях, при больших размерах компилируемой программы (когда недостаточно оперативной памяти) используют внешнюю память на жестких магнитных дисках. При выполнении каждого прохода компилятору доступна информация, полученная в результате всех предыдущих проходов, и исходный текст программы. Но, как правило, в первую очередь используется та информация, которая получена на предыдущем проходе. Следует иметь в виду, что информация, обычно полученная компилятором при выполнении проходов не доступна пользователю. Эта информация хранится либо в оперативной памяти, которая освобождается после процедуры компилирования, либо во внешних временных файлах на диске, которые также удаляются по завершению работы компилятора, таким образом, пользователь, в принципе, не знает, за сколько именно проходов выполнена компиляция. Он всегда видит только текст исходной программы и результирующую объектную программу. Так как количество выполняемых проходов – это важная техническая характеристика компилятора, то солидные фирмы-разработчики компиляторов обычно указывают ее в описании своего продукта.
2.3.3. Однопроходные и многопроходные компиляторы
Поскольку сокращение количества проходов приводит к увеличению скорости работы компилятора, сокращению объема необходимой памяти, то разработчики стремятся сократить количество проходов, выполняемых компилятором.
Различают две основные схемы построения компиляторов: однопроходные и многопроходные.
Однопроходной компилятор, получающий на вход исходную программу и сразу же порождающий результирующую объектную программу – это идеальный вариант. Однако сократить количество проходов удается не всегда. Количество проходов определяется, прежде всего, грамматическими и семантическими правилами исходного языка. Чем сложнее грамматика, и чем больше вариантов предполагают семантические правила, тем больше проходов требуется для получения объектного кода. Именно поэтому компиляторы с языка Pascal работают быстрее, чем компиляторы с языка С, т. к. грамматика Pascal более проста, а семантические правила более жесткие. Однопроходные компиляторы – редкость, они возможны только для очень простых языков. Реальные компиляторы – это двух-, трех- или более проходные. Например, трехпроходной компилятор: при первом проходе – лексический анализ, при втором – синтаксический разбор и семантический анализ, при третьем – генерации и оптимизация кода.