Генерация кода (компилятор) - Code generation (compiler)

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

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

Вход в генератор кода обычно состоит из дерево синтаксического анализа или абстрактное синтаксическое дерево.[1] Дерево преобразуется в линейную последовательность инструкций, обычно в промежуточный язык такие как трехадресный код. Дальнейшие этапы компиляции могут или не могут называться «генерацией кода», в зависимости от того, включают ли они значительные изменения в представлении программы. (Например, оптимизация глазка проход вряд ли будет называться «генерацией кода», хотя генератор кода может включать проход оптимизации с глазком.)

Основные задачи

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

Задачи, которые обычно являются частью фазы «генерации кода» сложного компилятора, включают:

Выбор инструкций обычно осуществляется путем рекурсивный обход послепорядка в абстрактном синтаксическом дереве сопоставление конкретных конфигураций дерева с шаблонами; например, дерево W: = ДОБАВИТЬ (X; MUL (Y; Z)) могут быть преобразованы в линейную последовательность инструкций путем рекурсивной генерации последовательностей для t1: = X и t2: = MUL (Y; Z), а затем выпустить инструкцию ДОБАВИТЬ W, t1, t2.

В компиляторе, который использует промежуточный язык, может быть два этапа выбора инструкций - один для преобразования дерева синтаксического анализа в промежуточный код, а второй этап намного позже для преобразования промежуточного кода в инструкции из Набор инструкций целевой машины. Эта вторая фаза не требует обхода дерева; это может быть выполнено линейно и обычно включает простую замену операций промежуточного языка их соответствующими коды операций. Однако, если компилятор на самом деле Переводчик языков (например, тот, который преобразует Эйфель к C ), то вторая фаза генерации кода может включать строительство дерево из линейного промежуточного кода.

Генерация кода времени выполнения

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

Связанные понятия

Фундаментальную задачу ввода ввода на одном языке и вывода вывода на нетривиально другом языке можно понять с точки зрения ядра трансформационный операции формальная теория языка. Следовательно, некоторые методы, которые изначально были разработаны для использования в компиляторах, стали использоваться и другими способами. Например, YACC (Еще один Компилятор компилятор ) принимает участие в Форма Бэкуса-Наура и преобразует его в парсер в C. Хотя изначально он был создан для автоматического создания парсера для компилятора, yacc также часто используется для автоматизации написания кода, который необходимо изменять каждый раз при изменении спецификаций.[3]

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

Отражение

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

Смотрите также

Рекомендации

  1. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Расширенная реализация проекта компилятора. Морган Кауфманн. ISBN  978-1-55860-320-2. генерация кода.
  2. ^ Ахо, Альфред V .; Рави Сетхи; Джеффри Д. Ульман (1987). Компиляторы: принципы, методы и инструменты. Эддисон-Уэсли. п. 15. ISBN  0-201-10088-6.
  3. ^ Генерация кода: настоящий урок Rails. Artima.com (16 марта 2006 г.). Проверено 10 августа 2013.