Компилятор — это программа, осуществляющая перевод исходной программы, написанной на входном языке, в эквивалентную ей объектную программу на языке машинных команд или языке ассемблера.
Общие сведения о компиляторах
Компилятором является программный продукт, предназначенный для перевода программы, которая написана на каком-либо языке программирования (исходном языке) в программу на язык ассемблера или в машинные команды. Практически все компиляторы выполняют перевод программы с некоторого высокоуровневого языка программирования в машинные коды, которые могут быть непосредственно исполнены компьютерным оборудованием.
При осуществлении семантического анализа, генерации кода и оптимизации сформированной программы, компилятор обязан пользоваться параметрами главных компонентов исходной программы, то есть, использовать переменные, константы, функции и другие лексические единицы входного языка. Эти параметры компилятор может получить при выполнении синтаксического анализа входной программы (наиболее часто при изучении структуры блоков описаний переменных и констант), а также может их дополнить при подготовке к генерации кода (к примеру, при выделении памяти).
Статья: Проектирование компилятора
Совокупность характеристик, соответствующих всем компонентам исходной программы, зависит от типа каждого компонента, от его смысла (семантики) и, естественно, от той роли, которую он выполняет в исходной и конечной программах. В каждом конкретном случае эта совокупность характеристик может быть своя, и она зависит от синтаксиса и семантики входного языка, от архитектуры целевой вычислительной системы и от структуры компилятора. Однако существуют стандартные характеристики, присущие некоторым компонентам исходной программы. К примеру, для переменных стандартными характеристиками являются их тип и адрес ячейки памяти, для констант это их значение, для функций это количество и типы формальных аргументов, тип возвращаемого результата, адрес вызова кода функции.
Основной характеристикой каждого компонента исходной программы считается его имя. Именно с именами переменных, констант, функций и других компонентов входного языка работает программист. Это означает, что и компилятор обязан обладать умением выполнять анализ этих компонентов по их именам. Имена всех компонентов должны являться уникальными. Некоторые современные языки программирования могут допускать отсутствие уникальности имен переменных, и функций в зависимости от их области видимости и иных параметров исходной программы.
То есть, задачей компилятора является сохранение некоторой информации, связанной с каждым компонентом исходной программы, и организация доступа к этой информации по имени компонента. Для решения данной задачи компилятор должен организовать специализированные хранилища данных, именуемые таблицами идентификаторов, или таблицами символов. Таблица идентификаторов должна состоять из набора полей данных (записей), каждое из которых должно соответствовать одному компоненту исходной программы. Запись должна содержать всю требуемую компилятору информацию об этом компоненте и может быть пополнена в процессе работы компилятора.
Проектирование компилятора
Компилятор может пополнять записи в таблице идентификаторов при выполнении анализа исходной программы и нахождении в ней новых компонентов, которые требуют помещения в таблицу. Процесс поиска информации в таблице должен выполняться всегда, когда компилятору нужны данные о каком-либо компоненте программы. При этом необходимо отметить, что поиск компонента в таблице осуществляется компилятором значительно чаще, чем размещение в ней новых компонентов. Это объясняется тем, что описания новых компонентов в исходной программе, обычно, попадаются существенно более редко, чем данные компоненты используются. Помимо этого, всем операциям добавления компонентов в таблицу идентификаторов всегда должна предшествовать операция поиска, которая позволяет проверить, что такого компонента в таблице нет.
На любую операцию поиска компонента в таблице компилятор должен затратить время, и, так как, число компонентов в исходной программе может быть достаточно большим (от единиц до сотен тысяч в зависимости от объема программы), то это время способно оказать существенное влияние на общее время компиляции. По этой причине таблицы идентификаторов необходимо организовать таким образом, чтобы у компилятора была возможность максимально оперативно осуществлять поиск требуемой ему записи таблицы по имени компонента, с которым сопряжена данная запись.
Необходимо отметить следующий набор способов организации таблиц идентификаторов:
- Способ простых и упорядоченных списков.
- Способ бинарного дерева.
- Способ хэш - адресации с рехэшированием.
- Способ хэш - адресации по методу цепочек.
- Комбинированный способ хэш - адресации с ее списком или бинарным деревом.
В самом простом случае таблица идентификаторов выступает в качестве линейного неупорядоченного списка, или массива, все ячейки которого несут информацию о соответствующем компоненте таблицы. Помещение новых компонентов в такую таблицу осуществляется записью информации в очередную ячейку массива или списка по мере нахождения новых компонентов в исходной программе.
Поиск требуемого компонента в таблице будет в таком варианте исполняться путем последовательного перебора всех компонентов и сравнения их имен с именем требуемого компонента, пока не будет обнаружен компонент, имеющий такое же имя. То есть, если за единицу времени будет принято время, которое затрачивается компилятором на операцию сравнения двух строк (в современных вычислительных системах такое сравнение наиболее часто исполняется при помощи одной командой), то для таблицы, имеющей в своем составе N компонентов, в среднем должно исполняться N/2 сравнений. А время, которое необходимо для добавления нового компонента в таблицу, не зависит от количества компонентов в таблице (N).
