Компилятор - Compiler

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

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

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

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

История

Схема работы типичного многоязычного многоцелевого компилятора

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

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

  • Алфавит , любой конечный набор символов;
  • Строка , конечная последовательность символов;
  • Язык , любой набор строк в алфавите.

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

Форма Бэкуса-Наура (BNF) описывает синтаксис «предложений» языка и использовалась для синтаксиса Algol 60 Джоном Бэкусом . Идеи взяты из концепции контекстно-свободной грамматики , разработанной лингвистом Ноамом Хомски . «BNF и его расширения стали стандартными инструментами для описания синтаксиса программных обозначений, и во многих случаях части компиляторов генерируются автоматически из описания BNF».

В 1940-х годах Конрад Цузе разработал язык алгоритмического программирования под названием Plankalkül («Расчет плана»). Хотя фактической реализации не было до 1970-х годов, в нем были представлены концепции, которые позже были замечены в APL, разработанном Кеном Айверсоном в конце 1950-х годов. APL - это язык математических вычислений.

Дизайн языков высокого уровня в годы становления цифровых вычислений предоставил полезные инструменты программирования для множества приложений:

  • FORTRAN (перевод формул) для инженерных и научных приложений считается первым языком высокого уровня.
  • COBOL (Common Business-Oriented Language) превратился из A-0 и FLOW-MATIC в доминирующий язык высокого уровня для бизнес-приложений.
  • LISP (List Processor) для символьных вычислений.

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

Некоторые ранние вехи в развитии технологии компиляторов:

  • 1952 : Компилятор автокода, разработанный Аликом Гленни для компьютера Manchester Mark I в Манчестерском университете, считается некоторыми первым скомпилированным языком программирования.
  • 1952 : Команда Грейс Хоппер в Remington Rand написала компилятор для языка программирования A-0 (и придумала термин компилятор для его описания), хотя компилятор A-0 функционировал больше как загрузчик или компоновщик, чем современное понятие полный компилятор.
  • 1954–1957 : Группа под руководством Джона Бэкуса из IBM разработала FORTRAN, который обычно считается первым языком высокого уровня. В 1957 году они завершили компилятор FORTRAN, который, как принято считать, представил первый однозначно завершенный компилятор.
  • 1959 : Конференция по языку систем данных (CODASYL) инициировала разработку COBOL . В дизайне COBOL использовались A-0 и FLOW-MATIC. К началу 1960-х COBOL был скомпилирован на нескольких архитектурах.
  • 1958–1962 : Джон Маккарти из Массачусетского технологического института разработал LISP . Возможности обработки символов предоставили полезные функции для исследований искусственного интеллекта. В 1962 году в выпуске LISP 1.5 были отмечены некоторые инструменты: интерпретатор, написанный Стивеном Расселом, и Дэниел Дж. Эдвардс, компилятор и ассемблер, написанный Тимом Хартом и Майком Левином.

Ранние операционные системы и программное обеспечение были написаны на ассемблере. В 1960-х и начале 1970-х годов использование языков высокого уровня для системного программирования все еще оставалось спорным из-за ограниченности ресурсов. Тем не менее, несколько научно - исследовательских и промышленных усилия начали переход к системам высокого уровня языков программирования, например, BCPL , BLISS , B и C .

BCPL (базовый комбинированный язык программирования), разработанный в 1966 году Мартином Ричардсом из Кембриджского университета, изначально разрабатывался как инструмент для написания компиляторов. Было реализовано несколько компиляторов, книга Ричардса дает представление о языке и его компиляторе. BCPL был не только влиятельным языком системного программирования, который до сих пор используется в исследованиях, но и послужил основой для разработки языков B и C.

BLISS (базовый язык для реализации системного программного обеспечения) был разработан для компьютера PDP-10 Digital Equipment Corporation (DEC) исследовательской группой Университета Карнеги-Меллона (CMU) У. А. Вульфа. Группа CMU продолжила разработку компилятора BLISS-11 год спустя, в 1970 году.

Multics (Multiplexed Information and Computing Service), проект операционной системы с разделением времени, в котором участвовали MIT , Bell Labs , General Electric (позже Honeywell ) и возглавлялся Фернандо Корбато из Массачусетского технологического института. Multics была написана на языке PL / I, разработанном IBM и IBM User Group. Целью IBM было удовлетворение требований бизнеса, науки и системного программирования. Могли быть рассмотрены и другие языки, но PL / I предложил наиболее полное решение, хотя оно и не было реализовано. В течение первых нескольких лет проекта Multics подмножество языка могло быть скомпилировано на язык ассемблера с помощью компилятора Early PL / I (EPL) Дугом Макилори и Бобом Моррисом из Bell Labs. EPL поддерживала проект до тех пор, пока не был разработан компилятор для полной загрузки PL / I.

Bell Labs покинула проект Multics в 1969 году: «Со временем надежда сменилась разочарованием, поскольку изначально групповые усилия не привели к созданию экономически полезной системы». Продолжение участия увеличит расходы на поддержку проекта. Поэтому исследователи обратились к другим разработкам. Язык системного программирования B, основанный на концепциях BCPL, был написан Деннисом Ричи и Кеном Томпсоном . Ритчи создал загрузочную-обвязки компилятор для B и написал УНИКС (Uniplexed информационной и вычислительной службы) операционной системы для PDP-7 в Б. УНИКС в конце концов стал буквам Unix.

Bell Labs начала разработку и расширение C на основе B и BCPL. Компилятор BCPL был перенесен в Multics компанией Bell Labs, и BCPL был предпочтительным языком в Bell Labs. Первоначально использовалась интерфейсная программа для компилятора B Bell Labs, пока разрабатывался компилятор C. В 1971 году новый PDP-11 предоставил ресурсы для определения расширений B и перезаписи компилятора. К 1973 году разработка языка C была практически завершена, и ядро ​​Unix для PDP-11 было переписано на C. Стив Джонсон начал разработку Portable C Compiler (PCC) для поддержки перенацеливания компиляторов C на новые машины.

Объектно-ориентированное программирование (ООП) предлагает некоторые интересные возможности для разработки и сопровождения приложений. Концепции ООП уходят корнями в прошлое, но они были частью LISP и языковой науки Simula . В Bell Labs разработкой C ++ заинтересовалось ООП. C ++ впервые был использован в 1980 году для системного программирования. Первоначальный дизайн использовал возможности системного программирования на языке C с концепциями Simula. Объектно-ориентированные средства были добавлены в 1983 году. Программа Cfront реализовала интерфейс C ++ для компилятора языка C84. В последующие годы по мере роста популярности C ++ было разработано несколько компиляторов C ++.

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

DARPA (Агентство перспективных оборонных исследовательских проектов) спонсировало проект компилятора с исследовательской группой CMU Вульфа в 1970 году. Конструкция компилятора-компилятора производственного качества PQCC должна была создать компилятор производственного качества (PQC) на основе формальных определений исходного языка и цели. PQCC без особого успеха попытался расширить термин «компилятор-компилятор» за пределы традиционного значения «генератор синтаксического анализа» (например, Yacc ). PQCC правильнее было бы называть генератором компилятора.

Исследование PQCC по процессу генерации кода было направлено на создание действительно автоматической системы написания компилятора. Эти усилия обнаружили и разработали фазовую структуру PQC. Компилятор BLISS-11 предоставил исходную структуру. Этапы включали в себя анализ (внешний интерфейс), промежуточный перевод на виртуальную машину (средний этап) и перевод в целевой объект (серверная часть). TCOL был разработан для исследования PQCC для обработки языковых конструкций в промежуточном представлении. Варианты TCOL поддерживают разные языки. В рамках проекта PQCC изучались методы построения автоматизированных компиляторов. Концепции дизайна оказались полезными при оптимизации компиляторов и компиляторов для объектно-ориентированного языка программирования Ada .

Документ Ады Стоунман формализовал среду поддержки программ (APSE) вместе с ядром (KAPSE) и минимальным (MAPSE). Переводчик Ada NYU / ED поддерживал разработку и стандартизацию усилий Американского национального института стандартов (ANSI) и Международной организации по стандартизации (ISO). Первоначальная разработка компилятора Ada Военными службами США включала компиляторы в полную интегрированную среду проектирования в соответствии с положениями документа Stoneman Document. Армия и флот работали над проектом Ada Language System (ALS), ориентированным на архитектуру DEC / VAX, в то время как ВВС начали работу над интегрированной средой Ada (AIE), ориентированной на серию IBM 370. Хотя проекты не принесли желаемых результатов, они внесли свой вклад в общие усилия по разработке Ada.

Другие разработки компилятора Ada были предприняты в Великобритании в Йоркском университете и в Германии в университете Карлсруэ. В США компания Verdix (позже приобретенная Rational) предоставила армии Verdix Ada Development System (VADS). VADS предоставил набор инструментов разработки, включая компилятор. Unix / VADS может быть размещен на различных платформах Unix, таких как DEC Ultrix и Sun 3/60 Solaris, предназначенных для Motorola 68020 в оценке Army CECOM. Вскоре появилось много компиляторов Ada, которые прошли проверку Ada Validation. В рамках проекта Free Software Foundation GNU была разработана коллекция компиляторов GNU (GCC), которая предоставляет базовые возможности для поддержки нескольких языков и целевых приложений. Версия Ada GNAT - один из наиболее широко используемых компиляторов Ada. GNAT бесплатен, но есть также коммерческая поддержка, например, AdaCore была основана в 1994 году для предоставления коммерческих программных решений для Ada. GNAT Pro включает GNU на основе GNU GCC с набором инструментов для обеспечения интегрированной среды разработки .

Языки высокого уровня продолжали стимулировать исследования и разработки компиляторов. Основные области включали оптимизацию и автоматическую генерацию кода. Тенденции в языках программирования и средах разработки повлияли на технологию компиляторов. Больше компиляторов стало включено в языковые дистрибутивы (PERL, Java Development Kit) и как компонент IDE (VADS, Eclipse, Ada Pro). Взаимосвязь и взаимозависимость технологий росли. Появление веб-сервисов способствовало развитию веб-языков и языков сценариев. Сценарии восходят к ранним дням появления интерфейсов командной строки (CLI), когда пользователь мог вводить команды для выполнения системой. Концепции пользовательской оболочки, разработанные с использованием языков для написания программ оболочки. Ранние разработки Windows предлагали простую возможность пакетного программирования. При обычном преобразовании этих языков использовался интерпретатор. Компиляторы Bash и Batch были написаны, хотя и не получили широкого распространения. Совсем недавно сложные интерпретируемые языки стали частью набора инструментов разработчиков. Современные языки сценариев включают PHP, Python, Ruby и Lua. (Lua широко используется при разработке игр.) Все они имеют поддержку интерпретатора и компилятора.

«Когда область компиляции началась в конце 50-х годов, ее внимание было ограничено переводом программ на языке высокого уровня в машинный код ... Сфера компиляции все больше переплетается с другими дисциплинами, включая компьютерную архитектуру, языки программирования, формальные методы, программная инженерия и компьютерная безопасность ". В статье "Compiler Research: The Next 50 Years" отмечена важность объектно-ориентированных языков и Java. Безопасность и параллельные вычисления были названы среди целей будущих исследований.

Конструкция компилятора

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

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

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

Сравнение однопроходных и многопроходных компиляторов

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

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

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

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

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

Трехступенчатая структура компилятора

Дизайн компилятора

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

  • Внешний интерфейс сканирует ввод и проверяет синтаксис и семантику в соответствии с определенным исходным языком. Для языков со статической типизацией он выполняет проверку типа путем сбора информации о типе. Если входная программа синтаксически неверна или имеет ошибку типа, она генерирует сообщения об ошибках и / или предупреждения, обычно идентифицируя место в исходном коде, где была обнаружена проблема; в некоторых случаях фактическая ошибка может быть (намного) раньше в программе. Аспекты внешнего интерфейса включают лексический анализ, синтаксический анализ и семантический анализ. Внешний интерфейс преобразует входную программу в промежуточное представление (IR) для дальнейшей обработки средним концом. Этот IR обычно является представлением программы более низкого уровня по отношению к исходному коду.
  • В средней конечных выполняет оптимизацию по IR , которые не зависят от архитектуры процессора мишени. Эта независимость исходного кода / машинного кода предназначена для обеспечения возможности совместной оптимизации между версиями компилятора, поддерживающими разные языки и целевые процессоры. Примерами оптимизации среднего уровня являются удаление бесполезного ( устранение мертвого кода ) или недоступного кода ( анализ достижимости ), обнаружение и распространение постоянных значений ( распространение констант ), перемещение вычислений в менее часто выполняемое место (например, вне цикла). , или специализация вычислений в зависимости от контекста. В конечном итоге создание «оптимизированного» IR, используемого серверной частью.
  • Конец обратно принимает оптимизированный IR от среднего конца. Он может выполнять больше анализа, преобразований и оптимизаций, специфичных для целевой архитектуры ЦП. Серверная часть генерирует зависимый от цели ассемблерный код, выполняя выделение регистров в процессе. Серверная часть выполняет планирование инструкций , которое переупорядочивает инструкции, чтобы держать блоки параллельного выполнения занятыми, заполняя интервалы задержки . Хотя большинство задач оптимизации являются NP-трудными , эвристические методы их решения хорошо разработаны и в настоящее время реализованы в компиляторах производственного качества. Обычно выходные данные серверной части представляют собой машинный код, специализированный для конкретного процессора и операционной системы.

Этот внешний / средний / внутренний подход позволяет комбинировать внешние интерфейсы для разных языков с внутренними интерфейсами для разных процессоров , разделяя оптимизацию среднего уровня. Практическими примерами этого подхода являются GNU Compiler Collection , Clang ( компилятор C / C ++ на основе LLVM ) и Amsterdam Compiler Kit , которые имеют несколько внешних интерфейсов, общую оптимизацию и несколько внутренних интерфейсов.

Внешний интерфейс

Лексер и парсер пример C . Начиная с последовательности символов " if(net>0.0)total+=net*(1.0+tax/100.0);", сканер составляет последовательность токенов и классифицирует каждый из них, например, как идентификатор , зарезервированное слово , числовой литерал или оператор . Последняя последовательность преобразуется синтаксическим анализатором в синтаксическое дерево , которое затем обрабатывается оставшимися фазами компилятора. Сканер и синтаксический анализатор обрабатывают обычные и должным образом контекстно-свободные части грамматики для C соответственно.

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

Хотя интерфейс может быть отдельной монолитной функцией или программой, как в парсере без сканирования , он традиционно реализовывался и анализировался как несколько этапов, которые могут выполняться последовательно или одновременно. Этому методу отдают предпочтение из-за его модульности и разделения задач . Чаще всего сегодня интерфейс разбивается на три этапа: лексический анализ (также известный как лексирование или сканирование), синтаксический анализ (также известный как сканирование или синтаксический анализ) и семантический анализ . Лексирование и синтаксический анализ включают синтаксический анализ (синтаксис слов и синтаксис фраз соответственно), и в простых случаях эти модули (лексический анализатор и синтаксический анализатор) могут быть автоматически сгенерированы из грамматики языка, хотя в более сложных случаях они требуют ручной модификации. . Лексическая грамматика и фразовая грамматика обычно являются контекстно-независимыми грамматиками , что значительно упрощает анализ, а контекстная чувствительность обрабатывается на этапе семантического анализа. Этап семантического анализа, как правило, более сложен и написан вручную, но может быть частично или полностью автоматизирован с использованием грамматик атрибутов . Сами эти фазы могут быть далее разбиты: лексирование как сканирование и оценка и анализ как построение конкретного синтаксического дерева (CST, дерево синтаксического анализа) с последующим преобразованием его в абстрактное синтаксическое дерево (AST, синтаксическое дерево). В некоторых случаях используются дополнительные фазы, в частности реконструкция линии и предварительная обработка, но это случается редко.

Основные этапы фронтенда включают следующее:

  • Реконструкция строки преобразует входную последовательность символов в каноническую форму, готовую для синтаксического анализа. Языки, которыеограничиваютсвои ключевые слова или допускают произвольные пробелы в идентификаторах, требуют этой фазы. Втопе-вниз,рекурсивный спуск, таблично ориентированные парсерыиспользуемые в 1960х годахправилочитать исходный один символ за один раз и не требуют отдельной фазы tokenizing. Atlas AutocodeиImp(а также некоторые реализацииALGOLиCoral 66) являются примерами стропированных языков, компиляторы которых будут иметьфазуреконструкции строки.
  • Предварительная обработка поддерживаетподстановку макросов и условную компиляцию . Обычно этап предварительной обработки происходит перед синтаксическим или семантическим анализом; например, в случае C препроцессор манипулирует лексическими токенами, а не синтаксическими формами. Однако некоторые языки, такие как Scheme, поддерживают макрозамены на основе синтаксических форм.
  • Лексический анализ (также известный как лексирование или токенизация ) разбивает текст исходного кода на последовательность небольших фрагментов, называемых лексическими токенами . Этот этап можно разделить на два этапа: сканирование , во время которого вводимый текст сегментируется на синтаксические единицы, называемые лексемами, и присваивается им категория; и оценка , которая преобразует лексемы в обработанное значение. Токен - это пара, состоящая из имени токена и необязательного значения токена . Общие категории токенов могут включать идентификаторы, ключевые слова, разделители, операторы, литералы и комментарии, хотя набор категорий токенов различается в разных языках программирования . Синтаксис лексемы обычно является регулярным языком , поэтомудля его распознавания можно использовать конечный автомат, построенный на основе регулярного выражения . Программа, выполняющая лексический анализ, называется лексическим анализатором . Это не может быть отдельным этапом - его можно объединить с этапом синтаксического анализа без сканирования , и в этом случае синтаксический анализ выполняется на уровне символа, а не на уровне токена.
  • Синтаксический анализ (также известный как синтаксический анализ ) включает синтаксический анализ последовательности токенов для определения синтаксической структуры программы. На этом этапе обычно строится дерево синтаксического анализа , которое заменяет линейную последовательность токенов древовидной структурой, построенной в соответствии с правилами формальной грамматики, которые определяют синтаксис языка. Дерево синтаксического анализа часто анализируется, дополняется и трансформируется на более поздних этапах работы компилятора.
  • Семантический анализ добавляет семантическую информацию в дерево синтаксического анализа и строит таблицу символов . На этом этапе выполняются семантические проверки, такие как проверка типа (проверка ошибок типа) или привязка объекта ( связывание ссылок на переменные и функции с их определениями) или определенное присвоение (требование инициализации всех локальных переменных перед использованием), отклонение неверных программ или выдача предупреждения. Для семантического анализа обычно требуется полное дерево синтаксического анализа, а это означает, что эта фаза логически следует зафазой синтаксического анализа и логически предшествуетфазе генерации кода , хотя часто можно объединить несколько фаз в один проход по коду в реализации компилятора.

Средний конец

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

Основные этапы среднего конца включают следующее:

Анализ компилятора является предпосылкой для любой оптимизации компилятора, и они тесно взаимодействуют друг с другом. Например, анализ зависимостей имеет решающее значение для преобразования цикла .

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

Межпроцедурный анализ и оптимизация распространены в современных коммерческих компиляторах от HP , IBM , SGI , Intel , Microsoft и Sun Microsystems . Свободное программное обеспечение GCC был подвергнут критике в течение длительного времени не хватает мощных межпроцедурные оптимизаций, но она меняется в этом отношении. Другой компилятор с открытым исходным кодом с полной инфраструктурой анализа и оптимизации - Open64 , который используется многими организациями в исследовательских и коммерческих целях.

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

Бэк-энд

Серверная часть отвечает за оптимизацию архитектуры ЦП и генерацию кода .

Основные этапы бэкенда включают следующее:

  • Машинно-зависимые оптимизации : оптимизации, зависящие от деталей архитектуры ЦП, на которые нацелен компилятор. Ярким примером является оптимизация с глазком , которая переписывает короткие последовательности инструкций ассемблера в более эффективные инструкции.
  • Генерация кода : преобразованный промежуточный язык переводится на выходной язык, обычно на собственный машинный язык системы. Это включает в себя решения о ресурсах и хранении, такие как решение, какие переменные помещать в регистры и память, а также выбор и планирование соответствующих машинных инструкций вместе с соответствующими режимами адресации (см. Также алгоритм Сетхи – Уллмана ). Также может потребоваться сгенерировать данные отладки для облегчения отладки .

Корректность компилятора

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

Скомпилированные и интерпретируемые языки

Языки программирования более высокого уровня обычно появляются с учетом типа перевода : либо разработанные как компилируемый язык, либо как интерпретируемый язык . Однако на практике в языке редко бывает что-то, что требует его исключительной компиляции или эксклюзивной интерпретации, хотя можно разрабатывать языки, которые полагаются на повторную интерпретацию во время выполнения. Категоризация обычно отражает наиболее популярные или широко распространенные реализации языка - например, BASIC иногда называют интерпретируемым языком, а C - скомпилированным, несмотря на существование компиляторов BASIC и интерпретаторов C.

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

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

В некоторых спецификациях языка указано, что реализации должны включать средства компиляции; например, Common Lisp . Однако в определении Common Lisp нет ничего, что мешало бы его интерпретации. В других языках есть функции, которые очень легко реализовать в интерпретаторе, но значительно усложняют написание компилятора; например, APL , SNOBOL4 и многие языки сценариев позволяют программам создавать произвольный исходный код во время выполнения с помощью обычных строковых операций, а затем выполнять этот код, передавая его специальной функции оценки . Чтобы реализовать эти функции на скомпилированном языке, программы обычно должны поставляться с библиотекой времени выполнения, которая включает версию самого компилятора.

Типы

Одна классификация компиляторов - это платформа, на которой выполняется их сгенерированный код. Это называется целевой платформой.

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

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

Язык нижнего уровня, который является целью компилятора, может сам быть языком программирования высокого уровня . C, рассматриваемый некоторыми как своего рода переносимый язык ассемблера, часто является целевым языком таких компиляторов. Например, Cfront , исходный компилятор для C ++ , использовал C в качестве целевого языка. Код C, сгенерированный таким компилятором, обычно не предназначен для чтения и обслуживания людьми, поэтому стиль отступа и создание красивого промежуточного кода C игнорируются. Некоторые из функций C, которые делают его хорошим целевым языком, включают #lineдирективу, которая может быть сгенерирована компилятором для поддержки отладки исходного источника, и широкую поддержку платформы, доступную с помощью компиляторов C.

Хотя общий тип компилятора выводит машинный код, существует много других типов:

  • Компиляторы «исходный код» - это тип компилятора, который принимает язык высокого уровня в качестве входных данных и выводит язык высокого уровня. Например, компилятор с автоматическим распараллеливанием часто принимает программу на языке высокого уровня в качестве входных данных, а затем преобразует код и аннотирует его с помощью аннотаций параллельного кода (например, OpenMP ) или языковых конструкций (например, DOALLоператоров Fortran ). Другими терминами для компиляторов «исходный код» являются языковой переводчик, языковой преобразователь или языковой перезаписчик . Последний термин обычно применяется к переводам, которые не предполагают смены языка.
  • Компиляторы байт-кода компилируются на язык ассемблера теоретической машины, как некоторые реализации Prolog
  • Оперативные компиляторы (JIT-компилятор) откладывают компиляцию до времени выполнения. Существуют JIT компиляторы для многих современных языков , включая Python , JavaScript , Smalltalk , Java , Microsoft .NET «s Common Intermediate Language (CIL) и другие. Компилятор JIT обычно работает внутри интерпретатора. Когда интерпретатор обнаруживает, что путь кода «горячий», то есть он часто выполняется, будет вызван JIT-компилятор и скомпилировать «горячий» код для повышения производительности.
    • Для некоторых языков, таких как Java, приложения сначала компилируются с помощью компилятора байт-кода и доставляются в машинно-независимом промежуточном представлении . Интерпретатор байт-кода выполняет байт-код, но JIT-компилятор преобразует байт-код в машинный код, когда требуется повышенная производительность.
  • Компиляторы оборудования (также известные как инструменты синтеза) - это компиляторы, входными данными которых является язык описания оборудования, а выходными данными - описание конфигурации оборудования в форме списка соединений или иным образом.
  • Ассемблер это программа , которая собирает читаемый человеческий язык ассемблера в машинный код , фактические команд , выполняемых с помощью аппаратных средств. Обратная программа, переводящая машинный код на язык ассемблера, называется дизассемблером .
  • Программа, которая переводит с языка низкого уровня на язык более высокого уровня, является декомпилятором .
  • Программа, которая переводит в формат объектного кода, который не поддерживается на машине компиляции, называется кросс-компилятором и обычно используется для подготовки кода для встроенных приложений.
  • Программа, которая переписывает объектный код обратно в объектный код того же типа, применяя оптимизацию и преобразования, представляет собой двоичный рекомпилятор .

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

использованная литература

дальнейшее чтение

внешние ссылки