Компилятор

Эта статья о программном обеспечении для перевода компьютерных языков. Чтобы узнать о манге, см. Компилятор (манга) .

«Компиляция» и «Компиляция» перенаправляются сюда. Чтобы узнать о компании-разработчике программного обеспечения, см. Compile (компания) . Чтобы узнать о других целях, см. Компиляция .

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

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

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

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

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

История

Основная статья: История создания компилятора

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

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

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

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

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

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

Между 1942 и 1945 годами Конрад Цузе разработал первый (алгоритмический) язык программирования для компьютеров под названием Plankalkül («Плановое исчисление»). Цузе также задумал Planfertigungsgerät («Устройство сборки плана») для автоматического перевода математической формулировки программы в машиночитаемую перфорированную пленку . Хотя фактической реализации не произошло до 1970-х годов, в нем были представлены концепции, позже использованные в APL , разработанном Кеном Айверсоном в конце 1950-х годов. APL — язык математических вычислений.

Между 1949 и 1951 годами Хайнц Рутисхаузер предложил Superplan — язык высокого уровня и автоматический переводчик. Его идеи позже были усовершенствованы Фридрихом Л. Бауэром и Клаусом Самельсоном .

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

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

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

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

• Май 1952 : Грейс Хоппер команда из Remington Rand написала компилятор для языка программирования A-0 (и ввела термин «компилятор» для его описания). хотя компилятор A-0 функционировал скорее как загрузчик или компоновщик, чем современное понятие полного компилятора.
• 1952, до сентября : Компилятор Autocode, разработанный Аликом Гленни для компьютера Manchester Mark I в Манчестерском университете, считается некоторыми первым компилируемым языком программирования.
• 1954–1957 : Группа под руководством Джона Бэкуса из IBM разработала FORTRAN , который обычно считается первым языком высокого уровня. В 1957 году они завершили работу над компилятором FORTRAN, который обычно считается создателем первого однозначно полного компилятора.
• 1959 : Конференция по языку систем данных (CODASYL) инициировала разработку COBOL . Дизайн COBOL основан на A-0 и FLOW-MATIC. К началу 1960-х годов COBOL был скомпилирован для нескольких архитектур.
• 1958–1960 : Алгол 58 был предшественником АЛГОЛА 60 . Он представил блоки кода , что стало ключевым достижением в развитии структурного программирования . АЛГОЛ 60 был первым языком, реализовавшим определения вложенных функций с лексической областью действия . Это включало рекурсию . Его синтаксис был определен с использованием BNF . АЛГОЛ 60 вдохновил множество последовавших за ним языков. Тони Хоар заметил: «... это было усовершенствование не только своих предшественников, но и почти всех их преемников».
• 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 (Мультиплексная информационная и вычислительная служба), проект операционной системы с разделением времени, в котором участвовали MIT , Bell Labs , General Electric (позже Honeywell ), а возглавлял его Фернандо Корбато из MIT. 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 и написал операционную систему Unics (Uniplexed Information and Computing Service) для PDP-7 на B. Unics в конечном итоге стал называться Unix.

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

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

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

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

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

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

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

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

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

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

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

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

Однопроходные и многопроходные компиляторы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К основным этапам среднего конца относятся следующие:

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

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

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

Межпроцедурный анализ и оптимизация широко распространены в современных коммерческих компиляторах 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 ) или языковыми конструкциями (например, Fortran's DOALL заявления). Другими терминами для компилятора из исходного кода являются транскомпилятор или транспилятор.
• Компиляторы байт-кода компилируются в язык ассемблера теоретической машины, как некоторые Пролога реализации .
  • Эта машина Пролога также известна как абстрактная машина Уоррена (или WAM).
  • Компиляторы байт-кода для Java , Python также являются примерами этой категории.
• JIT-компиляторы (JIT-компиляторы) откладывают компиляцию до времени выполнения. JIT-компиляторы существуют для многих современных языков, включая Python , JavaScript , Smalltalk , Java , Common Intermediate Language (CIL) Microsoft других .NET и . JIT-компилятор обычно работает внутри интерпретатора. Когда интерпретатор обнаруживает, что путь кода является «горячим», то есть он выполняется часто, JIT-компилятор будет вызван и скомпилирует «горячий» код для повышения производительности.
  • Для некоторых языков, таких как Java, приложения сначала компилируются с использованием компилятора байт-кода и доставляются в машинно-независимом промежуточном представлении . Интерпретатор байт-кода выполняет байт-код, но JIT-компилятор преобразует байт-код в машинный код, когда требуется повышение производительности.
• Аппаратные компиляторы (также известные как инструменты синтеза) — это компиляторы, входные данные которых представляют собой язык описания аппаратного обеспечения в форме списка соединений , а выходные данные — описание конфигурации аппаратного обеспечения или иным образом.
  • Выходные данные этих компиляторов нацелены на компьютерное оборудование на очень низком уровне, например, на программируемую вентильную матрицу (FPGA) или структурированную интегральную схему специального назначения (ASIC). Такие компиляторы называются аппаратными, поскольку компилируемый ими исходный код эффективно контролирует окончательную конфигурацию оборудования и его работу. Результатом компиляции является лишь соединение транзисторов или справочных таблиц .
  • Примером аппаратного компилятора является XST, инструмент синтеза Xilinx, используемый для настройки FPGA. Подобные инструменты доступны от Altera, Synplicity, Synopsys и другие производители оборудования.
• Программа, которая переводит с языка низкого уровня на язык более высокого уровня, называется декомпилятором .
• Программа, которая преобразуется в формат объектного кода, который не поддерживается на машине компиляции, называется кросс-компилятором и обычно используется для подготовки кода для выполнения во встроенных программных приложениях.
• Программа, которая переписывает объектный код обратно в объектный код того же типа, применяя оптимизации и преобразования, является двоичным перекомпилятором .

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

См. также

• Абстрактная интерпретация
• Анализ снизу вверх
• Скомпилируйте и запустите систему
• Компилировать ферму
• Список компиляторов
• Список важных публикаций по информатике § Составители
• Метакомпиляция
• Трансформация программы

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

• Ахо, Альфред В .; Сетхи, Рави ; Уллман, Джеффри Д. (1986). Составители: принципы, методы и инструменты (1-е изд.). Аддисон-Уэсли . ISBN  9780201100884 .
• Аллен, Фрэнсис Э. (сентябрь 1981 г.). «История технологии языковых процессоров в IBM». Журнал исследований и разработок IBM . 25 (5). ИБМ : 535–548. дои : 10.1147/rd.255.0535 .
• Аллен, Рэнди; Кеннеди, Кен (2001). Оптимизация компиляторов для современных архитектур . Издательство Морган Кауфманн . ISBN  978-1-55860-286-1 .
• Аппель, Эндрю Уилсон (2002). Современная реализация компилятора на Java (2-е изд.). Издательство Кембриджского университета . ISBN  978-0-521-82060-8 .
• Аппель, Эндрю Уилсон (1998). Современная реализация компилятора в ML . Издательство Кембриджского университета . ISBN  978-0-521-58274-2 .
• Борнат, Ричард (1979). Понимание и написание компиляторов: Руководство «Сделай сам» (PDF) . Издательство Макмиллан . ISBN  978-0-333-21732-0 . Архивировано из оригинала (PDF) 15 июня 2007 года . Проверено 11 апреля 2007 г.
• Калингарт, Питер (1979). Горовиц, Эллис (ред.). Ассемблер, компилятор и трансляция программ . Серия «Разработка компьютерного программного обеспечения» (1-е издание, 1-е изд.). Потомак, Мэриленд: Computer Science Press, Inc. ISBN  0-914894-23-4 . ISSN   0888-2088 . LCCN   78-21905 . Проверено 20 марта 2020 г. (2+xiv+270+6 страниц)
• Купер, Кейт Дэниел; Торчон, Линда (2012). Разработка компилятора (2-е изд.). Амстердам, Нидерланды: Эльзевир/Морган Кауфманн. п. 8. ISBN  978-0-12088478-0 . OCLC   714113472 .
• Грис, Дэвид (1971). Создание компилятора для цифровых компьютеров (на английском, испанском, японском, китайском, итальянском и русском языках). Нью-Йорк: Джон Уайли и сыновья. ISBN  0-471-32776-Х . Первый текст по построению компилятора.
• Маккиман, Уильям Маршалл ; Хорнинг, Джеймс Дж .; Вортман, Дэвид Б. (1970). Генератор компилятора . Энглвуд Клиффс, Нью-Джерси : Прентис-Холл . ISBN  978-0-13-155077-3 .
• Мучник, Стивен (1997). Расширенное проектирование и реализация компилятора . Издательство Морган Кауфманн . ISBN  978-1-55860-320-2 .
• Скотт, Майкл Ли (2005). Прагматика языков программирования (2-е изд.). Морган Кауфманн . ISBN  978-0-12-633951-2 .
• Шрикант, Ю.Н.; Шанкар, Прити (2003). Справочник по проектированию компиляторов: оптимизации и генерация машинного кода . ЦРК Пресс . ISBN  978-0-8493-1240-3 .
• Терри, Патрик Д. (1997). Компиляторы и генераторы компиляторов: введение в C++ . Международная компьютерная пресса Thomson. ISBN  978-1-85032-298-6 .
• Вирт, Никлаус (1996). Конструкция компилятора (PDF) . Аддисон-Уэсли . ISBN  978-0-201-40353-4 . Архивировано из оригинала (PDF) 17 февраля 2017 года . Проверено 24 апреля 2012 г.
• Сообщество LLVM. «Генератор кода LLVM, независимый от цели» . Документация ЛЛВМ . Проверено 17 июня 2016 г.
• Ссылки на учебники по компиляторам. Коллекция ссылок на основные учебники по построению компиляторов.

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

• Компиляторы в Curlie
• Инкрементальный подход к построению компилятора – учебное пособие в формате PDF
• Основы проектирования компилятора на Wayback Machine (архивировано 15 мая 2018 г.)
• Короткая анимация на YouTube, объясняющая ключевое концептуальное различие между компиляторами и интерпретаторами.
• Синтаксический анализ и синтаксический анализ LL1 на YouTube
• Давайте построим компилятор , Джек Креншоу
• Форум о разработке компиляторов на Wayback Machine (архив от 10 октября 2014 г.)