В вычислительной технике компилятор — это компьютерная программа , которая переводит компьютерный код, написанный на одном языке программирования ( исходный язык), на другой язык ( целевой язык). Название «компилятор» в основном используется для программ, которые переводят исходный код с языка программирования высокого уровня на язык программирования низкого уровня (например , язык ассемблера , объектный код или машинный код ) для создания исполняемой программы. [1] [2] : п1 [3]
Существует множество различных типов компиляторов, которые выдают выходные данные в различных полезных формах. Кросс -компилятор создает код для процессора или операционной системы , отличного от той, на которой работает сам кросс-компилятор. Загрузочный компилятор часто является временным компилятором, используемым для компиляции более постоянного или лучше оптимизированного компилятора для языка.
Сопутствующее программное обеспечение включает декомпиляторы — программы, которые переводят с языков низкого уровня на языки более высокого уровня; программы, которые переводят между языками высокого уровня, обычно называемые компиляторами исходного кода или транспиляторами ; переписчики языка , обычно программы, переводящие форму выражений без изменения языка; и компиляторы-компиляторы , компиляторы, которые создают компиляторы (или их части), часто в общем и многократно используемом виде, чтобы иметь возможность создавать множество разных компиляторов.
Компилятор, скорее всего, выполнит некоторые или все из следующих операций, часто называемых фазами: предварительная обработка , лексический анализ , синтаксический анализ , семантический анализ ( синтаксически-ориентированный перевод ), преобразование входных программ в промежуточное представление , оптимизация кода и генерация кода для конкретной машины. . Составители обычно реализуют эти этапы в виде модульных компонентов, способствуя эффективному проектированию и правильности преобразований исходных входных данных в целевые выходные данные. Ошибки программы, вызванные неправильным поведением компилятора, бывает очень сложно отследить и обойти; поэтому разработчики компилятора прилагают значительные усилия для обеспечения корректности компилятора . [4]
Компиляторы — не единственный языковой процессор, используемый для преобразования исходных программ. Интерпретатор — это компьютерное программное обеспечение, которое преобразует , а затем выполняет указанные операции. [2] : p2 Процесс перевода влияет на дизайн компьютерных языков, что приводит к предпочтению компиляции или интерпретации. Теоретически язык программирования может иметь как компилятор, так и интерпретатор. На практике языки программирования обычно связаны только с одним (компилятором или интерпретатором).
Концепции теоретических вычислений, разработанные учёными, математиками и инженерами, легли в основу развития современных цифровых вычислений во время Второй мировой войны. Примитивные двоичные языки возникли потому, что цифровые устройства понимают только единицы и нули, а также схемы в базовой архитектуре машины. В конце 1940-х годов были созданы языки ассемблера, чтобы предложить более работоспособную абстракцию компьютерных архитектур. Ограниченный объем памяти первых компьютеров привел к серьезным техническим проблемам при разработке первых компиляторов. Поэтому процесс компиляции нужно было разделить на несколько небольших программ. Внешние программы создают продукты анализа, используемые внутренними программами для генерации целевого кода. Поскольку компьютерные технологии предоставили больше ресурсов, конструкции компиляторов могли лучше согласовываться с процессом компиляции.
Программисту обычно более продуктивно использовать язык высокого уровня, поэтому разработка языков высокого уровня естественным образом вытекала из возможностей, предлагаемых цифровыми компьютерами. Языки высокого уровня — это формальные языки , строго определенные своим синтаксисом и семантикой , которые формируют архитектуру языка высокого уровня. Элементы этих формальных языков включают:
Предложения на языке могут определяться набором правил, называемых грамматикой. [5]
Форма Бэкуса-Наура (БНФ) описывает синтаксис «предложений» языка. Он был разработан Джоном Бэкусом и использовался для синтаксиса Алгола 60 . [6] Идеи взяты из концепций контекстно-свободной грамматики лингвиста Ноама Хомского . [7] «BNF и его расширения стали стандартными инструментами для описания синтаксиса программных обозначений. Во многих случаях части компиляторов генерируются автоматически на основе описания BNF». [8]
Между 1942 и 1945 годами Конрад Цузе разработал первый (алгоритмический) язык программирования для компьютеров под названием Plankalkül («Плановое исчисление»). Цузе также придумал Planfertigungsgerät («Устройство для сборки плана») для автоматического перевода математической формулировки программы в машиночитаемую перфорированную пленку . [9] Хотя фактической реализации не было до 1970-х годов, в нем были представлены концепции, позже использованные в APL , разработанном Кеном Айверсоном в конце 1950-х годов. [10] APL — язык математических вычислений.
Между 1949 и 1951 годами Хайнц Рутисхаузер предложил Superplan — язык высокого уровня и автоматический переводчик. [11] Его идеи были позже усовершенствованы Фридрихом Л. Бауэром и Клаусом Самельсоном . [12]
Разработка языков высокого уровня в годы становления цифровых вычислений предоставила полезные инструменты программирования для различных приложений:
Технология компилятора возникла из необходимости строго определенного преобразования исходной программы высокого уровня в целевую программу низкого уровня для цифрового компьютера. Компилятор можно рассматривать как интерфейсную часть для анализа исходного кода и внутреннюю часть для синтеза результатов анализа в целевой код. Оптимизация между интерфейсом и сервером может привести к более эффективному целевому коду. [16]
Некоторые ранние вехи в развитии технологии компиляторов:
Ранние операционные системы и программное обеспечение были написаны на языке ассемблера. В 1960-х и начале 1970-х годов использование языков высокого уровня для системного программирования все еще вызывало споры из-за ограниченности ресурсов. Однако некоторые исследовательские и отраслевые усилия положили начало переходу к языкам системного программирования высокого уровня, например, BCPL , BLISS , B и C.
BCPL (базовый комбинированный язык программирования), разработанный в 1966 году Мартином Ричардсом из Кембриджского университета, изначально был разработан как инструмент для написания компиляторов. [28] Было реализовано несколько компиляторов. Книга Ричардса дает представление о языке и его компиляторе. [29] BCPL был не только влиятельным языком системного программирования, который до сих пор используется в исследованиях [30] , но также послужил основой для разработки языков B и C.
BLISS (базовый язык для реализации системного программного обеспечения) был разработан для компьютера PDP-10 Digital Equipment Corporation (DEC) исследовательской группой Университета Карнеги-Меллона (CMU) В.А. Вульфа. Команда CMU продолжила разработку компилятора BLISS-11 год спустя, в 1970 году.
Multics (Мультиплексная информационная и вычислительная служба), проект операционной системы с разделением времени, в котором участвовали MIT , Bell Labs , General Electric (позже Honeywell ), а возглавлял его Фернандо Корбато из MIT. [31] Multics был написан на языке PL/I , разработанном IBM и IBM User Group. [32] Целью IBM было удовлетворение требований бизнеса, науки и системного программирования. Можно было рассмотреть и другие языки, но PL/I предложил наиболее полное решение, хотя оно и не было реализовано. [33] В течение первых нескольких лет проекта Multics подмножество языка можно было скомпилировать в ассемблер с помощью компилятора Early PL/I (EPL), созданного Дугом МакИлори и Бобом Моррисом из Bell Labs. [34] EPL поддерживала проект до тех пор, пока не был разработан компилятор начальной загрузки для полной версии PL/I. [35]
Bell Labs вышла из проекта Multics в 1969 году и разработала язык системного программирования B на основе концепций BCPL, написанных Деннисом Ритчи и Кеном Томпсоном . Ритчи создал загрузочный компилятор для B и написал операционную систему Unics (Uniplexed Information and Computing Service) для PDP-7 в B. Unics в конечном итоге стал называться Unix.
Bell Labs начала разработку и расширение C на основе B и BCPL. Компилятор BCPL был перенесен в Multics компанией Bell Labs, и BCPL был предпочтительным языком в Bell Labs. [36] Первоначально при разработке компилятора C использовалась интерфейсная программа для B-компилятора Bell Labs. В 1971 году новый PDP-11 предоставил возможность определить расширения B и переписать компилятор. К 1973 году разработка языка C была практически завершена, и ядро Unix для PDP-11 было переписано на C. Стив Джонсон начал разработку портативного компилятора C (PCC) для поддержки перенацеливания компиляторов C на новые машины. [37] [38]
Объектно-ориентированное программирование (ООП) открыло некоторые интересные возможности для разработки и сопровождения приложений. Концепции ООП уходят корнями в прошлое, но были частью науки о языках LISP и Simula . [39] Bell Labs заинтересовалась ООП с разработкой C++ . [40] C++ впервые был использован в 1980 году для системного программирования. В первоначальном проекте использовались возможности системного программирования на языке C с концепциями Simula. Объектно-ориентированные средства были добавлены в 1983 году. [41] Программа Cfront реализовала интерфейс C++ для компилятора языка C84. В последующие годы по мере роста популярности C++ было разработано несколько компиляторов C++.
Во многих областях приложений идея использования языка более высокого уровня быстро завоевала популярность. Из-за расширения функциональности, поддерживаемой новыми языками программирования , и увеличения сложности компьютерных архитектур компиляторы стали более сложными.
DARPA (Агентство перспективных оборонных исследовательских проектов) спонсировало проект компилятора совместно с исследовательской группой Вульфа CMU в 1970 году. Проект PQCC «Компилятор качества продукции » должен был создать компилятор качества продукции (PQC) на основе формальных определений исходного языка и цели. [42] PQCC без особого успеха пыталась расширить термин «компилятор-компилятор» за пределы традиционного значения генератора синтаксического анализатора (например, Yacc ). PQCC правильнее было бы называть генератором компилятора.
Исследование PQCC процесса генерации кода было направлено на создание действительно автоматической системы написания компилятора. В ходе этой работы была обнаружена и разработана фазовая структура PQC. Компилятор BLISS-11 предоставил исходную структуру. [43] Эти этапы включали анализ (передняя часть), промежуточный перевод на виртуальную машину (средний конец) и перевод на цель (внутренняя часть). TCOL был разработан для исследования PQCC для обработки специфичных для языка конструкций в промежуточном представлении. [44] Варианты TCOL поддерживают различные языки. Проект PQCC исследовал методы автоматического построения компилятора. Концепции проектирования оказались полезными при оптимизации компиляторов и компиляторов для (с 1995 года объектно-ориентированного) языка программирования Ada .
Документ Ады STONEMAN [a] формализовал среду поддержки программ (APSE), а также ядро (KAPSE) и минимум (MAPSE). Интерпретатор Ada из Нью-Йоркского университета/ED поддерживал усилия по разработке и стандартизации совместно с Американским национальным институтом стандартов (ANSI) и Международной организацией по стандартизации (ISO). Первоначальная разработка компилятора Ada Военными службами США включала компиляторы в полностью интегрированную среду проектирования в соответствии с документом STONEMAN . Армия и флот работали над проектом языковой системы Ada (ALS), ориентированным на архитектуру DEC/VAX, в то время как ВВС приступили к разработке интегрированной среды Ada (AIE), ориентированной на серию IBM 370. Хотя проекты не дали желаемых результатов, они внесли свой вклад в общие усилия по развитию Ada. [45]
Другие разработки компилятора Ada начались в Великобритании в Йоркском университете и в Германии в Университете Карлсруэ. В США компания Verdix (позже приобретенная Rational) поставила армии систему разработки Verdix Ada (VADS). VADS предоставил набор инструментов разработки, включая компилятор. Unix/VADS может размещаться на различных платформах Unix, таких как DEC Ultrix и Sun 3/60 Solaris, предназначенных для Motorola 68020, согласно оценке CECOM армии. [46] Вскоре появилось множество компиляторов Ada, прошедших тесты проверки Ada. Проект GNU Фонда свободного программного обеспечения разработал коллекцию компиляторов GNU (GCC), которая обеспечивает основные возможности для поддержки нескольких языков и целевых систем. Версия Ada GNAT — один из наиболее широко используемых компиляторов Ada. GNAT бесплатен, но существует и коммерческая поддержка, например, компания AdaCore была основана в 1994 году для предоставления коммерческих программных решений для Ada. GNAT Pro включает в себя GNAT на базе GNU GCC с набором инструментов для обеспечения интегрированной среды разработки .
Языки высокого уровня продолжали стимулировать исследования и разработки компиляторов. Основные направления включали оптимизацию и автоматическую генерацию кода. Тенденции в языках программирования и средах разработки повлияли на технологию компиляторов. Больше компиляторов стало включено в дистрибутивы языков (PERL, Java Development Kit) и в качестве компонентов IDE (VADS, Eclipse, Ada Pro). Возросла взаимосвязь и взаимозависимость технологий. Появление веб-сервисов способствовало развитию веб-языков и языков сценариев. Сценарии восходят к первым дням появления интерфейсов командной строки (CLI), где пользователь мог вводить команды, которые будут выполняться системой. Концепции пользовательской оболочки, разработанные с использованием языков для написания программ оболочки. Ранние разработки Windows предлагали простую возможность пакетного программирования. Традиционное преобразование этих языков использовало переводчик. Компиляторы Bash и Batch, хотя и не получили широкого распространения, были написаны. Совсем недавно сложные интерпретируемые языки стали частью набора инструментов разработчиков. Современные языки сценариев включают PHP, Python, Ruby и Lua. (Lua широко используется при разработке игр.) Все они имеют поддержку интерпретатора и компилятора. [47]
«Когда в конце 50-х годов возникла область компиляции, ее внимание было ограничено переводом программ на языках высокого уровня в машинный код... Область компиляции все больше переплетается с другими дисциплинами, включая компьютерную архитектуру, языки программирования, формальные методы и т. д. разработка программного обеспечения и компьютерная безопасность». [48] В статье «Исследование компиляторов: следующие 50 лет» отмечается важность объектно-ориентированных языков и Java. Среди будущих целей исследований были названы безопасность и параллельные вычисления .
Компилятор осуществляет формальное преобразование исходной программы высокого уровня в целевую программу низкого уровня. Проектирование компилятора может определять комплексное решение или охватывать определенное подмножество, которое взаимодействует с другими инструментами компиляции, например, препроцессорами, ассемблерами, компоновщиками. Требования к проектированию включают строго определенные интерфейсы как внутри между компонентами компилятора, так и снаружи между поддерживающими наборами инструментов.
Вначале на подход к проектированию компилятора напрямую влияли сложность обрабатываемого компьютерного языка, опыт человека (лиц), его проектировавшего, и доступные ресурсы. Ограничения ресурсов привели к необходимости проходить через исходный код более одного раза.
Компилятор относительно простого языка, написанный одним человеком, может представлять собой единую монолитную программу. Однако по мере усложнения исходного языка проектирование может быть разделено на ряд взаимозависимых этапов. Отдельные этапы предусматривают улучшения конструкции, которые фокусируют разработку на функциях процесса компиляции.
Классификация компиляторов по количеству проходов основана на ограничениях аппаратных ресурсов компьютеров. Компиляция требует выполнения большого количества работы, и ранние компьютеры не имели достаточно памяти для размещения одной программы, выполняющей всю эту работу. В результате компиляторы были разделены на более мелкие программы, каждая из которых просматривала исходный код (или его некоторое представление), выполняя часть необходимого анализа и переводов.
Возможность компиляции за один проход традиционно рассматривалась как преимущество, поскольку она упрощает работу по написанию компилятора, а однопроходные компиляторы обычно выполняют компиляцию быстрее, чем многопроходные компиляторы . Таким образом, отчасти из-за ограниченности ресурсов ранних систем многие ранние языки были специально разработаны так, чтобы их можно было скомпилировать за один проход (например, Pascal ).
В некоторых случаях при разработке функции языка может потребоваться, чтобы компилятор выполнил более одного прохода по исходному коду. Например, рассмотрим объявление, появляющееся в строке 20 источника, которое влияет на перевод оператора, появляющегося в строке 10. В этом случае первый проход должен собрать информацию об объявлениях, появляющихся после операторов, на которые они влияют, при этом происходит фактический перевод. во время последующего прохода.
Недостаток компиляции за один проход заключается в том, что невозможно выполнить многие сложные оптимизации , необходимые для создания высококачественного кода. Может быть сложно точно подсчитать, сколько проходов делает оптимизирующий компилятор. Например, на разных этапах оптимизации одно выражение может анализироваться много раз, а другое выражение анализироваться только один раз.
Разбиение компилятора на небольшие программы — это метод, используемый исследователями, заинтересованными в создании доказуемо правильных компиляторов. Доказательство корректности набора небольших программ часто требует меньших усилий, чем доказательство корректности более крупной, единственной эквивалентной программы.
Независимо от точного количества фаз в конструкции компилятора, фазы можно отнести к одной из трех стадий. Этапы включают в себя переднюю часть, среднюю часть и заднюю часть.
Такой подход к интерфейсу, середине и серверной части позволяет комбинировать интерфейсы для разных языков с серверами для разных процессоров , сохраняя при этом оптимизацию среднего уровня. [49] Практическими примерами этого подхода являются GNU Compiler Collection , Clang ( компилятор C/C++ на основе LLVM ), [50] и Amsterdam Compiler Kit , которые имеют несколько интерфейсов, общие оптимизации и несколько серверов.
Интерфейсная часть анализирует исходный код для создания внутреннего представления программы, называемого промежуточным представлением (IR). Он также управляет таблицей символов — структурой данных, сопоставляющей каждый символ в исходном коде со связанной информацией, такой как местоположение, тип и область действия.
Хотя внешний интерфейс может представлять собой единую монолитную функцию или программу, как в парсере без сканера , он традиционно реализовывался и анализировался как несколько этапов, которые могут выполняться последовательно или одновременно. Этот метод предпочтителен из-за его модульности и разделения задач . Чаще всего интерфейс разбивается на три этапа: лексический анализ (также известный как лексирование или сканирование), синтаксический анализ (также известный как сканирование или синтаксический анализ) и семантический анализ . Лексия и синтаксический анализ включают в себя синтаксический анализ (синтаксис слов и синтаксис фраз соответственно), и в простых случаях эти модули (лексер и синтаксический анализатор) могут быть автоматически сгенерированы из грамматики языка, хотя в более сложных случаях они требуют ручной модификации. . Лексическая грамматика и грамматика фраз обычно представляют собой контекстно-свободные грамматики , что значительно упрощает анализ, а контекстная чувствительность учитывается на этапе семантического анализа. Этап семантического анализа обычно более сложен и пишется вручную, но может быть частично или полностью автоматизирован с использованием грамматик атрибутов . Сами эти этапы можно разбить на более мелкие части: лексирование как сканирование и оценка, а синтаксический анализ как построение конкретного синтаксического дерева (CST, дерево синтаксического анализа) с последующим преобразованием его в абстрактное синтаксическое дерево (AST, синтаксическое дерево). В некоторых случаях используются дополнительные этапы, в частности реконструкция строки и предварительная обработка, но это происходит редко.
Основные этапы фронтенда включают в себя следующее:
Средний уровень, также известный как оптимизатор, выполняет оптимизацию промежуточного представления с целью повышения производительности и качества создаваемого машинного кода. [54] Средний уровень содержит те оптимизации, которые не зависят от целевой архитектуры ЦП.
К основным этапам среднего конца относятся следующие:
Анализ компилятора является предпосылкой любой оптимизации компилятора, и они тесно взаимодействуют. Например, анализ зависимостей имеет решающее значение для преобразования цикла .
Объем анализа и оптимизации компилятора сильно различается; их объем может варьироваться от работы внутри базового блока до целых процедур или даже всей программы. Существует компромисс между степенью детализации оптимизации и стоимостью компиляции. Например, оптимизация «глазок» выполняется быстро во время компиляции, но затрагивает только небольшой локальный фрагмент кода и может выполняться независимо от контекста, в котором этот фрагмент кода появляется. Напротив, межпроцедурная оптимизация требует больше времени компиляции и объема памяти, но обеспечивает оптимизацию, которая возможна только при одновременном рассмотрении поведения нескольких функций.
Межпроцедурный анализ и оптимизация широко распространены в современных коммерческих компиляторах HP , IBM , SGI , Intel , Microsoft и Sun Microsystems . Свободное программное обеспечение GCC долгое время критиковали за отсутствие мощных межпроцедурных оптимизаций, но в этом отношении оно меняется. Еще один компилятор с открытым исходным кодом с полной инфраструктурой анализа и оптимизации — Open64 , который используется многими организациями в исследовательских и коммерческих целях.
Из-за дополнительного времени и места, необходимого для анализа и оптимизации компилятора, некоторые компиляторы по умолчанию пропускают их. Пользователи должны использовать параметры компиляции, чтобы явно указать компилятору, какие оптимизации следует включить.
Серверная часть отвечает за оптимизацию архитектуры ЦП и генерацию кода [54] .
Основные этапы серверной части включают в себя следующее:
Корректность компилятора — это раздел разработки программного обеспечения, который пытается показать, что компилятор ведет себя в соответствии со спецификацией своего языка . [56] Методы включают разработку компилятора с использованием формальных методов и тщательное тестирование (часто называемое проверкой компилятора) на существующем компиляторе.
Языки программирования более высокого уровня обычно создаются с учетом типа перевода : либо компилируемого языка , либо интерпретируемого языка . Однако на практике редко что-либо в языке требует исключительной компиляции или исключительной интерпретации, хотя можно создавать языки, которые полагаются на повторную интерпретацию во время выполнения. Классификация обычно отражает наиболее популярные или распространенные реализации языка — например, BASIC иногда называют интерпретируемым языком, а C — компилируемым, несмотря на существование компиляторов BASIC и интерпретаторов C.
Интерпретация не заменяет полностью компиляцию. Он лишь скрывает это от пользователя и делает постепенным. Несмотря на то, что интерпретатор сам по себе может интерпретироваться, где-то в нижней части стека выполнения необходим набор непосредственно выполняемых машинных инструкций (см. машинный язык ).
Кроме того, для оптимизации компиляторы могут содержать функции интерпретатора, а интерпретаторы могут включать методы предварительной компиляции. Например, если выражение может быть выполнено во время компиляции, а результаты вставлены в выходную программу, это предотвращает необходимость его пересчета при каждом запуске программы, что может значительно ускорить окончательную программу. Современные тенденции к своевременной компиляции и интерпретации байт-кода порой еще больше размывают традиционную классификацию компиляторов и интерпретаторов.
В некоторых спецификациях языка указано, что реализации должны включать средства компиляции; например, Common Lisp . Однако в определении Common Lisp нет ничего, что мешало бы его интерпретации. В других языках есть функции, которые очень легко реализовать в интерпретаторе, но значительно усложняют написание компилятора; например, APL , SNOBOL4 и многие языки сценариев позволяют программам создавать произвольный исходный код во время выполнения с помощью обычных строковых операций, а затем выполнять этот код, передавая его специальной функции оценки . Чтобы реализовать эти функции на компилируемом языке, программы обычно должны поставляться с библиотекой времени выполнения , включающей версию самого компилятора.
Одна из классификаций компиляторов связана с платформой , на которой выполняется их сгенерированный код. Это называется целевой платформой.
Собственный или размещенный компилятор — это компилятор, выходные данные которого предназначены для непосредственного запуска на компьютере того же типа и в той же операционной системе, на которой работает сам компилятор . Результаты кросс-компилятора предназначены для работы на другой платформе. Кросс-компиляторы часто используются при разработке программного обеспечения для встраиваемых систем , которые не предназначены для поддержки среды разработки программного обеспечения.
Вывод компилятора, создающего код для виртуальной машины (ВМ), может выполняться или не выполняться на той же платформе, что и компилятор, создавший его. По этой причине такие компиляторы обычно не классифицируются как собственные или кросс-компиляторы.
Язык нижнего уровня, который является целью компилятора, сам может быть языком программирования высокого уровня . C, который некоторые рассматривают как своего рода переносимый язык ассемблера, часто является целевым языком таких компиляторов. Например, Cfront , оригинальный компилятор C++ , использовал C в качестве целевого языка. Код C, сгенерированный таким компилятором, обычно не предназначен для чтения и поддержки людьми, поэтому стиль отступов и создание красивого промежуточного кода C игнорируются. Некоторые из особенностей C, которые делают его хорошим целевым языком, включают директиву #line
, которая может быть сгенерирована компилятором для поддержки отладки исходного кода, а также широкую поддержку платформ, доступную компиляторам C.
Хотя общий тип компилятора выводит машинный код, существует множество других типов:
DOALL
). Другими терминами для компилятора из исходного кода являются транскомпилятор или транспилятор. [57]Компилятор — это компьютерная программа, которая переводит программу, написанную на языке высокого уровня (HLL), например C, в эквивалентную программу на языке ассемблера [2].
{{cite book}}
: |journal=
игнорируется ( помощь ){{cite book}}
: |website=
игнорируется ( помощь )Первый текст по построению компилятора.