Компилятор

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

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

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

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

Редактировать

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DARPA (Defense Advanced Research Projects Agency) спонсировало проект компилятора с исследовательской группой CMU Вульфа в 1970 году. Проект PQCC производственного компилятора-компилятора должен был создать производственный качественный компилятор (PQC) на основе формальных определений исходного языка и цели. [32] PQCC без особого успеха попытался расширить термин «компилятор-компилятор» за пределы традиционного значения как генератор синтаксического анализатора (например, Yacc ). PQCC правильнее было бы называть генератором компилятора.

Исследование PQCC по процессу генерации кода было направлено на создание действительно автоматической системы написания компилятора. Эти усилия обнаружили и разработали фазовую структуру PQC. Компилятор BLISS-11 предоставил исходную структуру. [33] Этапы включали анализ (внешний интерфейс), промежуточный перевод в виртуальную машину (средний этап) и перевод в целевой объект (серверная часть). TCOL был разработан для исследования PQCC для обработки языковых конструкций в промежуточном представлении. [34] Варианты 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. [35]

Другие разработки компилятора Ada были предприняты в Великобритании в Йоркском университете и в Германии в университете Карлсруэ. В США компания Verdix (позже приобретенная Rational) предоставила армии Verdix Ada Development System (VADS). VADS предоставил набор инструментов разработки, включая компилятор. Unix / VADS может быть размещен на различных платформах Unix, таких как DEC Ultrix и Sun 3/60 Solaris, предназначенных для Motorola 68020 в оценке Army CECOM. [36] Вскоре появилось много компиляторов 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 широко используется при разработке игр.) Все они имеют поддержку интерпретатора и компилятора. [37]

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

Редактировать

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

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

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

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

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

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

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

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

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

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

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

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

Этот внешний / средний / внутренний подход позволяет комбинировать внешние интерфейсы для разных языков с внутренними интерфейсами для разных процессоров , разделяя оптимизацию среднего уровня. [39] Практическими примерами этого подхода являются GNU Compiler Collection , Clang ( компилятор C / C ++ на основе LLVM ), [40] и 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, поддерживают макрозамены на основе синтаксических форм.
  • Лексический анализ (также известный как лексирование или токенизация ) разбивает текст исходного кода на последовательность небольших фрагментов, называемых лексическими токенами . [41] Этот этап можно разделить на два этапа: сканирование , которое сегментирует входной текст на синтаксические единицы, называемые лексемами, и присваивает им категорию; и оценка , которая преобразует лексемы в обработанное значение. Токен - это пара, состоящая из имени токена и необязательного значения токена . [42] Общие категории токенов могут включать идентификаторы, ключевые слова, разделители, операторы, литералы и комментарии, хотя набор категорий токенов различается в зависимости от языков программирования . Синтаксис лексемы обычно является регулярным языком , поэтомудля его распознавания можно использовать конечный автомат, построенный на основе регулярного выражения . Программа, выполняющая лексический анализ, называется лексическим анализатором . Это не может быть отдельным этапом - его можно объединить с этапом синтаксического анализа без сканирования , и в этом случае синтаксический анализ выполняется на уровне символа, а не на уровне токена.
  • Синтаксический анализ (также известный как синтаксический анализ ) включает синтаксический анализ последовательности токенов для определения синтаксической структуры программы. На этом этапе обычно строится дерево синтаксического анализа , которое заменяет линейную последовательность токенов древовидной структурой, построенной в соответствии с правилами формальной грамматики, которые определяют синтаксис языка. Дерево синтаксического анализа часто анализируется, дополняется и трансформируется на более поздних этапах работы компилятора. [43]
  • Семантический анализ добавляет семантическую информацию в дерево синтаксического анализа и строит таблицу символов . На этом этапе выполняются семантические проверки, такие как проверка типа (проверка ошибок типа) или привязка объекта ( связывание ссылок на переменные и функции с их определениями) или определенное присваивание (требование инициализации всех локальных переменных перед использованием), отклонение неверных программ или выдача предупреждения. Для семантического анализа обычно требуется полное дерево синтаксического анализа, а это означает, что эта фаза логически следует зафазой синтаксического анализа и логически предшествуетфазе генерации кода , хотя часто можно объединить несколько фаз в один проход по коду в реализации компилятора.

Средний конецРедактировать

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

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

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

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

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

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

Бэк-эндРедактировать

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

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

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

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

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

Редактировать

Языки программирования более высокого уровня обычно появляются с учетом типа перевода : либо разработанные как компилируемый язык, либо как интерпретируемый язык . Однако на практике в языке редко бывает что-то, что требует его исключительной компиляции или эксклюзивной интерпретации, хотя можно разрабатывать языки, которые полагаются на повторную интерпретацию во время выполнения. Категоризация обычно отражает наиболее популярные или широко распространенные реализации языка - например, 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-компилятор преобразует байт-код в машинный код, когда требуется повышенная производительность. [46] [необходим неосновной источник ]
  • Аппаратные компиляторы (также известные как инструменты синтеза) - это компиляторы, вывод которых представляет собой описание аппаратной конфигурации, а не последовательность инструкций.
  • Ассемблер это программа , которая собирает читаемый человеческий язык ассемблера в машинный код , фактические команд , выполняемых с помощью аппаратных средств. Обратная программа, переводящая машинный код на язык ассемблера, называется дизассемблером .
  • Программа, которая переводит с языка низкого уровня на язык более высокого уровня, является декомпилятором . [ необходима цитата ]
  • Программа, осуществляющая перевод между языками высокого уровня, обычно называется языковым переводчиком, компилятором исходного кода , языковым конвертером или языковым перезаписчиком . [ необходима цитата ] Последний термин обычно применяется к переводам, которые не предполагают смены языка. [50]
  • Программа, которая переводит в формат объектного кода, который не поддерживается на машине компиляции, называется кросс-компилятором и обычно используется для подготовки кода для встроенных приложений. [ необходима цитата ] [ требуется пояснение ]
  • Программа, которая переписывает объектный код обратно в объектный код того же типа, применяя оптимизацию и преобразования, представляет собой двоичный рекомпилятор .

Редактировать

Редактировать

  1. ^ PC Mag персонал (28 февраля 2019). «Энциклопедия: определение компилятора» . PCMag.com . Проверено 28 февраля 2017 года .
  2. ^ a b Компиляторы: принципы, методы и инструменты Альфреда В. Ахо, Рави Сетхи, Джеффри Д. Ульмана - второе издание, 2007 г.
  3. ^ Солнце, Ченгнянь; Ле, Ву; Чжан, Цирунь; Су, Чжендун (2016). «На пути к пониманию ошибок компилятора в GCC и LLVM» . ACM .
  4. ^ конспекты лекций Компиляторы: принципы, методы и инструменты Цзин-Шин Чанг Департамент компьютерных наук и информационной инженерии Национальный университет Чи-Нан
  5. ^ Наур, П. и др. «Отчет по АЛГОЛу 60». Сообщения ACM 3 (май 1960 г.), 299–314.
  6. ^ Хомский, Ноам; Лайтфут, Дэвид В. (2002). Синтаксические структуры . Вальтер де Грюйтер. ISBN 978-3-11-017279-9.
  7. ^ Грис, Дэвид (2012). «Приложение 1: Форма Бэкуса-Наура» . Наука программирования . Springer Science & Business Media. стр. 304. ISBN 978-1461259831.
  8. ^ Айверсон, Кеннет Э. (1962). Язык программирования . Джон Вили и сыновья. ISBN 978-0-471430-14-8.
  9. ^ Бэкус, Джон. «История FORTRAN I, II и III» (PDF) . История языков программирования . Softwarepreservation.org .
  10. Портер Адамс, Вики (5 октября 1981 г.). «Капитан Грейс М. Хоппер: мать КОБОЛА». InfoWorld. 3 (20): 33. ISSN 0199-6649.
  11. ^ Маккарти, J .; Brayton, R .; Эдвардс, Д .; Fox, P .; Hodes, L .; Luckham, D .; Maling, K .; Парк, Д .; Рассел, С. (март 1960). "Руководство программиста LISP I" (PDF). Бостон, Массачусетс: Группа искусственного интеллекта, Вычислительный центр Массачусетского технологического института и исследовательская лаборатория.
  12. ^ Принципы компиляции, методы и инструменты 2-е издание Ахо, Лам, Сетхи, Ульман ISBN  0-321-48681-1
  13. ^ Хоппер, Грейс Мюррей (1952). «Компьютерное образование». Протоколы Национального собрания ACM 1952 г. (Питтсбург) : 243–249. DOI : 10.1145 / 609784.609818 . S2CID  10081016 .
  14. ^ Риджуэй, Ричард К. (1952). «Составление программ». Материалы Национального собрания ACM 1952 г. (Торонто) : 1–5. DOI : 10.1145 / 800259.808980 . S2CID  14878552 .
  15. ^ " Рекурсивные функции символьных выражений и их вычисление машиной ", Сообщения ACM, апрель 1960
  16. ^ Маккарти, Джон; Abrahams, Paul W .; Эдвардс, Дэниел Дж .; Харт, Тимоти П .; Левин, Михаил Иванович (1965). Руководство программиста на Лисп 1.5 . MIT Press. ISBN 9780262130110.
  17. ^ " BCPL: инструмент для написания компилятора и системного программирования " М. Ричардс, Университетская математическая лаборатория Кембриджа, Англия, 1969
  18. ^ BCPL: Язык и Его компилятор, M Richards, Cambridge University Press (первая опубликована 31 декабря 1981)
  19. ^ Руководство пользователя BCPL Cintsys и Cintpos, М. Ричардс, 2017
  20. ^ Corbató, FJ; Высоцкий В.А. "Введение и обзор системы MULTICS" . 1965 г. Осенняя компьютерная конференция . MultICAL.org.
  21. ^ Отчет II комитета SHARE Advanced Language Development, 25 июня 1964 г.
  22. ^ Multicians.org «Выбор PL / I» статьи, редактор / Том Ван Флек
  23. ^ "PL / I как инструмент для системного программирования", FJ Corbato, Datamation 6 мая 1969 г.
  24. ^ " Компилятор Multics PL / 1 ", RA Freiburghouse, GE, Fall Joint Computer Conference 1969
  25. ^ Datamation колонка, 1969
  26. ^ Деннис М. Ричи, " Развитие языка C ", Вторая конференция ACM по истории языков программирования, апрель 1993 г.
  27. ^ С. К. Джонсон, "Портативный компилятор C: теория и практика", 5-й симпозиум ACM POPL, январь 1978 г.
  28. ^ А. Снайдер, Портативный компилятор для языка C , Массачусетский технологический институт, 1974.
  29. ^ К. Нигарард, Университет Осло, Норвегия, « Основные концепции объектно-ориентированного программирования », SIGPLAN Notices V21, 1986
  30. ^ Б. Страуструп: "Что такое объектно-ориентированное программирование?" Материалы 14-й конференции АГУ, 1986.
  31. ^ Бьярн Страуструп, "Обзор языка программирования C ++", Справочник по объектной технологии (редактор: Саба Замир, ISBN  0-8493-3135-8 )
  32. ^ Leverett, Cattell, Hobbs, Newcomer, Reiner, Schatz, Wulf: "Обзор проекта компилятора-компилятора производственного качества", CMU-CS-89-105, 1979
  33. ^ В. Вульф, К. Нори, " Отложенное связывание в компиляторах, созданных PQCC ", CMU Research Showcase Report, CMU-CS-82-138, 1982
  34. Джозеф М. Ньюкомер, Дэвид Алекс Лэмб, Брюс В. Леверетт, Майкл Тай, Уильям А. Вульф - Университет Карнеги-Меллона и Дэвид Левин, Эндрю Х. Райнерит - Интерметрики: «TCOL Ada: Пересмотренный отчет о промежуточном представлении для Стандартный язык программирования Министерства обороны США », 1979 г.
  35. Уильям А. Уитакер, «Ада - проект: рабочая группа высшего порядка Министерства обороны США», ACM SIGPLAN Notices (том 28, № 3, март 1991 г.)
  36. ^ Центр CECOM для разработки программного обеспечения Advanced Software Technology, "Итоговый отчет - оценка набора тестов ACEC для приложений реального времени", AD-A231 968, 1990
  37. ^ П. Биггар, Э. де Фрис, Д. Грегг, "Практическое решение для компиляторов языка сценариев", представление в Science of Computer Programming, 2009
  38. ^ М.Холл, Д. Падуя, К. Пингали, «Исследование компиляторов: следующие 50 лет», ACM Communications 2009 Vol 54 # 2
  39. ^ Купер и Torczon 2012, стр. 8
  40. ^ Латтнер, Крис (2017). «ЛЛВМ» . В Брауне, Эми; Уилсон, Грег (ред.). Архитектура приложений с открытым исходным кодом . Архивировано 2 декабря 2016 года . Проверено 28 февраля 2017 года .
  41. Перейти ↑ Aho, Lam, Sethi, Ullman 2007, p. 5-6, 109-189
  42. Перейти ↑ Aho, Lam, Sethi, Ullman 2007, p. 111
  43. Перейти ↑ Aho, Lam, Sethi, Ullman 2007, p. 8, 191-300
  44. ^ а б Блинделл, Габриэль Хьорт (3 июня 2016 г.). Подбор инструкций: принципы, методы и приложения . Швейцария. ISBN 9783319340197. OCLC  951745657 .
  45. ^ Купер и Toczon (2012), стр. 540
  46. ^ Эйкок, Джон (2003). «Краткая история точно в срок». ACM Comput. Surv . 35 (2, июнь): 93–113. DOI : 10.1145 / 857076.857077 . S2CID  15345671 .[необходим неосновной источник ]
  47. ^ Swartz, Jordan S .; Бец, Во; Роуз, Джонатан (22–25 февраля 1998 г.). «Маршрутизатор на основе быстрой маршрутизации для ПЛИС» (PDF) . FPGA '98 Труды Шестого международного симпозиума ACM / SIGDA 1998 г. по программируемым вентильным массивам . Монтерей, Калифорния: ACM : 140–149. DOI : 10.1145 / 275107.275134 . ISBN 978-0897919784. S2CID  7128364 . Архивировано (PDF) из оригинала 9 августа 2017 года.
  48. ^ Посох Xilinx (2009). «Обзор синтеза XST» . Xilinx, Inc. Архивировано 2 ноября 2016 года . Проверено 28 февраля 2017 года .[необходим неосновной источник ]
  49. ^ Посох Альтера (2017). «Двигатель Spectra-Q ™» . Altera.com. Архивировано из оригинального 10 -го октября 2016 года . Проверено 28 февраля 2017 года .[необходим неосновной источник ]
  50. ^ «Учебник языкового переводчика» (PDF) . Вашингтонский университет .

Редактировать

Редактировать