Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

История вычислительной техники
Аппаратное обеспечение
Программное обеспечение
Информатика
Современные концепции
По стране
Хронология вычислений
Глоссарий информатики

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

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

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

Первые компиляторы [ править ]

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

Первый практический компилятор был написан Коррадо Бемом в 1951 году для его докторской диссертации . Первый реализованный компилятор был написан Грейс Хоппер , которая также ввела термин «компилятор» [1] [2], имея в виду ее систему A-0, которая функционировала как загрузчик или компоновщик , а не современное понятие компилятора. Первый автокод и компилятор в современном понимании были разработаны Аликом Гленни в 1952 году в Манчестерском университете для компьютера Mark 1 . [3] [4] Команда FORTRAN под руководством Джона Бэкусав IBM представила первый коммерчески доступный компилятор в 1957 году, на создание которого ушло 18 человеко-лет. [5]

Первый компилятор ALGOL 58 был завершен к концу 1958 года Фридрихом Л. Бауэром , Германом Боттенбрухом, Хайнцем Рутисхаузером и Клаусом Самельсоном для компьютера Z22 . Bauer et al. в предыдущие годы работал над технологией компилятора для Sequentielle Formelübersetzung (т. е. последовательного перевода формул ).

К 1960 году расширенный компилятор Fortran, ALTAC, был доступен на Philco 2000, поэтому вполне вероятно, что программа Fortran была скомпилирована для компьютерных архитектур IBM и Philco в середине 1960 года. [6] Первым известным продемонстрированным кроссплатформенным языком высокого уровня был COBOL . Во время демонстрации в декабре 1960 года программа COBOL была скомпилирована и реализована как на UNIVAC II, так и на RCA 501. [2]

Самостоятельные компиляторы [ править ]

Не путать с компилятором компилятора .

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

Докторская диссертация Коррадо Бема [ править ]

Коррадо Бём разработал язык, машину и метод перевода для компиляции этого языка на машине в своей докторской диссертации 1951 года. Он не только описал полный компилятор, но и впервые определил этот компилятор на его собственном языке. Язык был интересен сам по себе, потому что каждый оператор (включая операторы ввода, операторы вывода и операторы управления) был частным случаем оператора присваивания [ необходима цитата ] .

NELIAC [ править ]

Navy Electronics Laboratory International Алгол Compiler или NELIAC был говор и составитель реализация Алгол 58 языка программирования , разработанного Военно - морской электроники лаборатории в 1958 году.

NELIAC был детищем Гарри Хаски - тогдашнего председателя ACM и известного компьютерного ученого (а затем научного руководителя Никлауса Вирта ) при поддержке Мори Холстеда, главы вычислительного центра NEL. Самая ранняя версия была реализована на прототипе компьютера USQ-17 (названного «Графиня») в лаборатории. Это был первый в мире самокомпилирующийся компилятор - компилятор сначала был написан в упрощенной форме на языке ассемблера ( начальная загрузка ), затем переписан на своем собственном языке и скомпилирован с помощью начальной загрузки и, наконец, перекомпилирован сам по себе, что бутстрап устарел.

Лисп [ править ]

Другой ранний компилятор с собственным хостом был написан для Лиспа Тимом Хартом и Майком Левиным из Массачусетского технологического института в 1962 году. [7] Они написали компилятор Лиспа на Лиспе, тестируя его внутри существующего интерпретатора Лиспа. Как только они улучшили компилятор до такой степени, что он мог компилировать свой собственный исходный код, он стал самостоятельным хостингом. [8]

Компилятор в том виде, в каком он существует на стандартной ленте компилятора, представляет собой программу на машинном языке, которая была получена благодаря тому, что определение S-выражения компилятора работает над собой через интерпретатор. (AI Memo 39) [8]

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

Forth [ править ]

Forth - это пример компилятора с собственным хостом. Функции самокомпиляции и кросс-компиляции Forth обычно путают с метакомпиляцией и метакомпиляторами . [ необходима цитата ] Как и Lisp , Forth является расширяемым языком программирования . Это возможности расширяемого языка программирования Forth и Lisp, которые позволяют им создавать новые версии самих себя или переносить себя в новые среды.

Бесконтекстные грамматики и парсеры [ править ]

Анализатор является важным компонентом компилятора. Он анализирует исходный код языка программирования для создания некоторой формы внутреннего представления. Языки программирования, как правило, определяются в терминах контекстно-свободной грамматики, потому что для них могут быть написаны быстрые и эффективные синтаксические анализаторы. Парсеры могут быть написаны вручную или сгенерированы генератором парсеров . Грамматика, не зависящая от контекста, обеспечивает простой и точный механизм для описания того, как конструкции языка программирования строятся из более мелких блоков . Формализм контекстно-свободных грамматик был разработан в середине 1950-х годов Ноамом Хомским . [9]

Блочная структура была введена в языки программирования в рамках проекта ALGOL (1957–1960), который, как следствие, также включал контекстно-свободную грамматику для описания синтаксиса ALGOL.

Грамматики без контекста достаточно просты, чтобы позволить создавать эффективные алгоритмы синтаксического анализа, которые для заданной строки определяют, можно ли и как ее сгенерировать из грамматики. Если разработчик языка программирования желает работать с некоторыми ограниченными подмножествами контекстно-свободных грамматик, возможны более эффективные синтаксические анализаторы.

Разбор LR [ править ]

Основная статья: парсер LR

LR - парсер (слева направо) был изобретен Дональдом Кнутом в 1965 году в статье «О переводе языков слева направо». LR анализатор представляет собой анализатор , который считывает входные данные из L EFT направо (как это будет выглядеть , если визуально отображается) и производит R ightmost вывод . Также используется термин синтаксический анализатор LR ( k ) , где k относится к количеству неиспользованных входных символов предварительного просмотра , которые используются при принятии решений синтаксического анализа.

Кнут доказал, что грамматики LR ( k ) могут быть проанализированы со временем выполнения, по существу пропорциональным длине программы, и что каждая грамматика LR ( k ) для k  > 1 может быть механически преобразована в грамматику LR (1) для того же язык. Другими словами, для анализа любой детерминированной контекстно-свободной грамматики (DCFG) необходимо иметь опережающий просмотр только на один символ . [10]

Кореняк (1969) был первым, кто показал, что синтаксические анализаторы для языков программирования могут быть созданы с использованием этих методов. [11] Франк Де Ремер разработал более практичные методы Simple LR (SLR) и Look-Ahead LR (LALR), опубликованные в его докторской диссертации в Массачусетском технологическом институте в 1969 году. [12] [13] Это был важный прорыв, поскольку LR (k ) переводчики, по определению Дональда Кнута, были слишком большими для внедрения в компьютерные системы в 1960-х и 1970-х годах.

На практике LALR предлагает хорошее решение; дополнительная мощность парсеров LALR (1) по сравнению с парсерами SLR (1) (то есть LALR (1) может анализировать более сложные грамматики, чем SLR (1)) полезна, и, хотя LALR (1) не сравним с LL ( 1) (См. Ниже) (LALR (1) не может анализировать все грамматики LL (1)), большинство грамматик LL (1), встречающихся на практике, может быть проанализировано LALR (1). LR (1) грамматики снова более мощные, чем LALR (1); однако грамматика LR (1) требует канонического синтаксического анализатора LR, который был бы чрезвычайно большим по размеру и не считается практичным. Синтаксис многих языков программирования определяется грамматиками, которые можно анализировать с помощью анализатора LALR (1), и по этой причине анализаторы LALR часто используются компиляторами для выполнения синтаксического анализа исходного кода.

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

Рекурсивное восхождение было впервые описано Томасом Пеннелло в его статье «Очень быстрый LR-синтаксический анализ» в 1986 году. [14] Техника позже была изложена GH Roberts [15] в 1988 году, а также в статье Leermakers, Augusteijn, Kruseman Aretz [16] в 1992 г. в журнале « Теоретическая информатика» .

Разбор LL [ править ]

Основная статья: парсер LL

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

Грамматики LL (k) могут быть проанализированы рекурсивным анализатором спуска, который обычно кодируется вручную, хотя в качестве альтернативы можно использовать нотацию, такую ​​как META II .

Дизайн ALGOL вызвал исследование рекурсивного спуска, поскольку сам язык ALGOL является рекурсивным. Концепция рекурсивного анализа спуска обсуждалась в выпуске CACM за январь 1961 г. в отдельных статьях А. А. Грау и Эдгара Т. "Неда" Айронса .[17] [18] Ричард Уэйчофф и его коллеги также реализовали рекурсивный спуск в компиляторе Burroughs ALGOL в марте 1961 года, [19] обе группы использовали разные подходы, но поддерживали, по крайней мере, неформальный контакт. [20]

Идея грамматик LL (1) была введена Льюисом и Стернсом (1968). [21] [22]

Рекурсивный спуск был популяризирован Никлаусом Виртом с PL / 0 , образовательным языком программирования, который использовался для обучения построению компиляторов в 1970-х годах. [23]

LR разбор может обрабатывать больший диапазон языков , чем LL разбор , а также лучше при передаче сообщений об ошибках (это спорно, требуется ССЫЛКА), т.е. обнаруживает синтаксические ошибки , когда вход не соответствует грамматике , как можно скорее.

Парсер Эрли [ править ]

В 1970 году Джей Эрли изобрел то, что стало известно как синтаксический анализатор Эрли . Парсеры Earley привлекательны тем, что могут достаточно эффективно анализировать все контекстно-свободные языки . [24]

Языки описания грамматики [ править ]

Джон Бэкус предложил «металингвистические формулы» [25] [26] для описания синтаксиса нового языка программирования IAL, известного сегодня как АЛГОЛ 58 (1959). Работа Бэкуса была основана на канонической системе Поста, разработанной Эмилем Постом .

Дальнейшее развитие АЛГОЛА привело к АЛГОЛу 60 ; в своем отчете (1963) Питер Наур назвал нотацию Бэкуса нормальной формой Бэкуса (BNF) и упростил ее, чтобы минимизировать используемый набор символов. Однако Дональд Кнут утверждал , что BNF скорее следует читать как Backus-Наура , [27] и что стало общепринятым использование.

Никлаус Вирт определил расширенную форму Бэкуса – Наура (EBNF), усовершенствованную версию BNF, в начале 1970-х годов для PL / 0. Другой вариант - расширенная форма Бэкуса – Наура (ABNF). И EBNF, и ABNF широко используются для определения грамматики языков программирования в качестве входных данных для генераторов синтаксического анализатора и в других областях, таких как определение протоколов связи.

Генераторы парсеров [ править ]

Более полный список, который также включает генераторы парсеров LL, SLR, GLR и LR, см. В разделе Сравнение генераторов парсеров.

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

Первый компилятор-компилятор, использующий это имя, был написан Тони Брукером в 1960 году и использовался для создания компиляторов для компьютера Atlas в Университете Манчестера, включая компилятор Atlas Autocode . Однако он сильно отличался от современных компиляторов-компиляторов, и сегодня его, вероятно, можно было бы описать как нечто среднее между универсальным компилятором с широкими возможностями настройки и языком с расширяемым синтаксисом . Название «компилятор-компилятор» было гораздо более подходящим для системы Брукера, чем для большинства современных компиляторов-компиляторов, которые более точно описываются как генераторы синтаксического анализатора. Почти наверняка название "Compiler Compiler" вошло в широкое употребление благодаря Yacc.а не о работе Брукера. [ необходима цитата ]

В начале 1960-х Роберт МакКлюр из Texas Instruments изобрел компилятор-компилятор под названием TMG , название взято из «трансмогрификации». [28] [29] [30] [31] В последующие годы TMG был перенесен на несколько мэйнфреймов UNIVAC и IBM.

Проект Multics , совместное предприятие MIT и Bell Labs , был одним из первых, кто разработал операционную систему на языке высокого уровня. В качестве языка был выбран PL / I , но внешний поставщик не смог предоставить работающий компилятор. [32] Команда Multics разработала собственное подмножество диалекта PL / I, известное как Early PL / I (EPL) в качестве языка реализации в 1964 году. TMG был перенесен на серию GE-600 и использовался для разработки EPL Дугласом Макилроем , Робертом Моррисом. , и другие.

Вскоре после того, как Кен Томпсон написал первую версию Unix для PDP-7 в 1969 году, Дуг Макилрой создал первый язык более высокого уровня для новой системы: реализацию TMG МакКлюра. [33] TMG также инструмент определения компилятора используется Кен Томпсон , чтобы написать компилятор для языка B на его PDP-7 в 1970 году B был непосредственный предок C .

Один из первых генераторов парсеров LALR назывался TWS и был создан Фрэнком Де Ремером и Томом Пеннелло.

XPL [ править ]

XPL является диалектом PL / I языка программирования , используемым для разработки компиляторов для языков программирования . Он был разработан и реализован в 1967 году командой с Уильямом М. МакКиманом , Джеймсом Дж. Хорнингом и Дэвидом Б. Вортманом из Стэнфордского университета и Калифорнийского университета в Санта-Круз . Впервые об этом было объявлено на Осенней компьютерной конференции 1968 года в Сан-Франциско. [34] [35]

В XPL была относительно простая система записи переводчика, получившая название ANALYZER , основанная на методе восходящего анализа приоритета компилятора , называемом MSP (приоритет смешанной стратегии). XPL был загружен через Burroughs Algol на компьютер IBM System / 360 . (В некоторых последующих версиях XPL, используемых во внутренних проектах Университета Торонто, использовался синтаксический анализатор SLR (1), но эти реализации никогда не распространялись).

Yacc [ править ]

Yacc - это генератор синтаксического анализатора (свободно, компилятор-компилятор ), не путать с lex , который является лексическим анализатором, часто используемым Yacc в качестве первого этапа. Yacc был разработан Стивеном Джонсоном в AT&T для операционной системы Unix . [36] Название является аббревиатурой от « Еще один компилятор компилятора ». Он генерирует компилятор LALR (1) на основе грамматики, записанной в нотации, аналогичной форме Бэкуса – Наура.

Джонсон работал над Yacc в начале 1970-х в Bell Labs . [37] Он был знаком с TMG, и его влияние можно увидеть в Yacc и дизайне языка программирования C. Поскольку Yacc был генератором компилятора по умолчанию в большинстве систем Unix, он был широко распространен и использовался. Производные, такие как GNU Bison , все еще используются.

Компилятор, сгенерированный Yacc, требует лексического анализатора . Генераторы лексических анализаторов, такие как lex или flex , широко доступны. Стандарт IEEE POSIX P1003.2 определяет функциональные возможности и требования как для Lex, так и для Yacc.

Coco / R [ править ]

Coco / R - это генератор парсеров, который генерирует парсеры LL (1) в Modula-2 (с плагинами для других языков) из входных грамматик, написанных в варианте EBNF. Он был разработан Ханспетером Мёссенбёком в Швейцарском федеральном технологическом институте в Цюрихе (ETHZ) в 1985 году.

ANTLR [ править ]

ANTLR - это генератор парсеров, который генерирует парсеры LL (*) в Java из входных грамматик, написанных в варианте EBNF. Он был разработан Теренсом Парром из Университета Сан-Франциско в начале 1990-х годов как преемник более раннего генератора под названием PCCTS.

Метакомпиляторы [ править ]

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

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

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

Многие метакомпиляторы основаны на работе Дьюи Вэл Шорре . Его компилятор META II , впервые выпущенный в 1964 году, был первым документированным метакомпилятором. Имея возможность определять свой собственный язык и другие языки, META II приняла синтаксическую формулу со встроенным выводом (производство кода) . Он также был переведен на один из самых ранних экземпляров виртуальной машины . Лексический анализ проводился с помощью встроенных функций распознавания токенов: .ID, .STRING и .NUMBER. Строки в кавычках в синтаксической формуле распознают несохраняемые лексемы. [38]

TREE-META , метакомпилятор Шорре второго поколения, появился примерно в 1968 году. Он расширил возможности META II, добавив неанализируемые правила, отделяющие создание кода от анализа грамматики. Операции преобразования дерева в синтаксической формуле создают абстрактные синтаксические деревья , над которыми работают неанализируемые правила. Неразборчивое сопоставление с образцом дерева обеспечивало возможность оптимизации глазком .

CWIC , описанный в публикации ACM 1970 года, представляет собой метакомпилятор Шорре третьего поколения, который добавил к грамматическому анализу правила лексирования и операторы поиска с возвратом. LISP 2 был связан с нечеткими правилами TREEMETA на языке генератора CWIC. Благодаря обработке LISP 2 CWIC может генерировать полностью оптимизированный код. CWIC также обеспечил генерацию двоичного кода в разделах именованного кода. Одно- и многопроходные компиляции могут быть реализованы с использованием CWIC.

CWIC скомпилирован в 8-битные инструкции машинного кода с адресацией байтов, в первую очередь предназначенные для создания кода IBM System / 360.

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

Кросс-компиляция [ править ]

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

Ранним примером кросс-компиляции была AIMICO, где программа FLOW-MATIC на UNIVAC II использовалась для создания языка ассемблера для IBM 705 , который затем был собран на компьютере IBM. [2]

68C алгол компилятор ZCODE выход, который может быть затем либо компилируется в локальный код с помощью машинного ZCODE переводчика или запустить интерпретирован. ZCODE - это промежуточный язык на основе регистров. Эта способность интерпретировать или компилировать ZCODE способствовала переносу ALGOL 68C на множество различных компьютерных платформ.

Оптимизация компиляторов [ править ]

Оптимизация компилятора - это процесс улучшения качества объектного кода без изменения получаемых им результатов.

Разработчики первого компилятора FORTRAN стремились сгенерировать код, который был бы лучше, чем средний ручной ассемблер, чтобы клиенты действительно могли использовать их продукт. В одном из первых настоящих компиляторов им часто это удавалось. [39]

Более поздние компиляторы, такие как компилятор IBM Fortran IV, уделяли больше внимания хорошей диагностике и более быстрому выполнению за счет оптимизации объектного кода. Только в серии IBM System / 360 IBM предоставила два отдельных компилятора: быстро выполняющийся модуль проверки кода и более медленный оптимизирующий.

Фрэнсис Э. Аллен , работая самостоятельно и совместно с Джоном Коке , представила многие концепции оптимизации. В статье Аллена 1966 года « Оптимизация программ» [40] было введено использование структур данных графа для кодирования содержимого программы с целью оптимизации. [41] В ее статьях 1970 года « Анализ потока управления» [42] и «Основа для оптимизации программ» [43] установлены интервалы как контекст для эффективного и действенного анализа и оптимизации потока данных. Ее статья 1971 года с Коке, Каталог оптимизации преобразований , [44]дано первое описание и систематизация оптимизирующих преобразований. Ее статьи 1973 и 1974 годов по анализу межпроцедурных потоков данных распространили анализ на целые программы. [45] [46] Ее статья 1976 года с Коке описывает одну из двух основных стратегий анализа, используемых сегодня при оптимизации компиляторов. [47]

Аллен разработала и реализовала свои методы как часть компиляторов для IBM 7030 Stretch - Harvest и экспериментальной системы Advanced Computing System . Эта работа позволила установить возможности и структуру современных машинно-независимых оптимизаторов. Затем она основала и возглавила проект PTRAN по автоматическому параллельному выполнению программ FORTRAN. [48] Ее команда PTRAN разработала новые схемы обнаружения параллелизма и создала концепцию графа зависимости программы, основного метода структурирования, используемого большинством распараллеливающих компиляторов.

«Языки программирования и их компиляторы » Джона Кока и Джейкоба Шварца , опубликованные в начале 1970 года, посвятили алгоритмам оптимизации более 200 страниц. Он включал многие из уже знакомых нам техник, таких как устранение избыточного кода и снижение стойкости . [49]

Оптимизация глазка [ править ]

Оптимизация с помощью глазка - очень простой, но эффективный метод оптимизации. Он был изобретен Уильямом М. МакКиманом и опубликован в 1965 году в CACM. [50] Он использовался в компиляторе XPL, который помог разработать МакКиман.

Оптимизатор COBOL Capex [ править ]

Корпорация Capex разработала «Оптимизатор COBOL» в середине 1970-х годов для COBOL . В данном случае оптимизатор этого типа зависел от знания «слабых мест» стандартного компилятора IBM COBOL и фактически заменял (или исправлял ) разделы объектного кода более эффективным кодом. Код замены может заменить линейный поиск в таблице с помощью бинарного поиска , например , или иногда просто заменить относительно «медленный» команду с известной быстрее той , которая была в противном случае функционально эквивалентны в его контексте. Эта техника теперь известна как « Снижение силы ». Например, на оборудовании IBM System / 360 интерфейс командной строкиинструкция была, в зависимости от конкретной модели, в два-пять раз быстрее, чем инструкция CLC для однобайтовых сравнений. [51] [52]

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

Диагностика [ править ]

Когда компилятору предоставляется синтаксически неправильная программа, полезно четкое и четкое сообщение об ошибке. С точки зрения разработчика компилятора, этого часто бывает трудно достичь.

WATFIV компилятор Fortran был разработан в Университете Ватерлоо , Канада , в конце 1960 - х годов. Он был разработан, чтобы выдавать лучшие сообщения об ошибках, чем компиляторы Fortran от IBM того времени. Кроме того, WATFIV был гораздо более удобным в использовании, потому что он объединял компиляцию, компоновку и выполнение в один этап, тогда как компиляторы IBM имели три отдельных компонента для запуска.

PL / C [ править ]

PL / C - язык компьютерного программирования, разработанный в Корнельском университете в начале 1970-х годов. Хотя PL / C был подмножеством языка PL / I IBM, он был разработан с конкретной целью - использовать его для обучения программированию. Двумя исследователями и преподавателями, разработавшими PL / C, были Ричард В. Конвей и Томас Р. Уилкокс. Они представили знаменитую статью «Разработка и реализация диагностического компилятора для PL / I», опубликованную в «Коммуникациях ACM» в марте 1973 г. [53]

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

Сборник Just in Time [ править ]

Основная статья: Своевременная компиляция

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

Промежуточное представление [ править ]

Основная статья: Промежуточное представление

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

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

Статическое однократное присвоение (SSA) было разработано Роном Цитроном , Жанной Ферранте , Барри К. Розеном , Марком Н. Вегманом и Ф. Кеннетом Задеком , исследователями из IBM в 1980-х годах. [54] В SSA переменной присваивается значение только один раз. Вместо изменения существующей создается новая переменная. SSA упрощает оптимизацию и генерацию кода.

Генерация кода [ править ]

Основная статья: Генерация кода (компилятор)

Генератор кода генерирует инструкции на машинном языке для целевого процессора.

Размещение регистра [ править ]

Алгоритм Сетхи-Уллмана или нумерация Сетхи-Уллмана - это метод минимизации количества регистров, необходимых для хранения переменных.

Известные компиляторы [ править ]

См. Также: АЛГОЛ 60: Хронология реализаций АЛГОЛА 60 и Список компиляторов.
  • Комплект компилятора Amsterdam от Эндрю Таненбаума и Кериэль Джейкобс
  • Беркли Паскаль, написанный Кеном Томпсоном в 1975 году. Билл Джой и другие из Калифорнийского университета в Беркли добавили улучшения
  • Коллекция компиляторов GNU , ранее называвшаяся компилятором C GNU. Первоначально созданный Ричардом Столлманом в 1987 году, GCC является крупным современным компилятором, который используется для компиляции многих проектов свободного программного обеспечения , особенно Linux .
  • LLVM , ранее известная как виртуальная машина низкого уровня
  • Small-C от Рона Кейна и Джеймса Э. Хендрикса
  • Turbo Pascal , созданный Андерсом Хейлсбергом , впервые выпущен в 1983 году.
  • WATFOR , созданный в Университете Ватерлоо . Один из первых популярных образовательных компиляторов, хотя сейчас в значительной степени устарел.
Этот список неполный ; вы можете помочь, добавив недостающие элементы из надежных источников .

См. Также [ править ]

  • История языков программирования
  • Lex (и лексический анализатор Flex ), синтаксический анализатор токенов, обычно используемый вместе с yacc (и Bison).
  • BNF , метасинтаксис, используемый для выражения контекстно-свободной грамматики : то есть формальный способ описания формальных языков.
  • Самоинтерпретатор, переводчик , написанный на языке, который он может интерпретировать.

Ссылки [ править ]

  1. ^ Морис В. Уилкс . 1968. Компьютеры тогда и сейчас. Журнал Ассоциации вычислительной техники, 15 (1): 1–7, январь. п. 3 (комментарий в скобках, добавленный редактором), «(я не думаю, что термин« компилятор »был тогда [1953] в общем употреблении, хотя на самом деле он был введен Грейс Хоппер.)»
  2. ^ a b c [1] Первые в мире компиляторы COBOL. Архивировано 13 октября 2011 г. на Wayback Machine.
  3. ^ Кнут, Дональд Э .; Пардо, Луис Трабб. «Раннее развитие языков программирования». Энциклопедия компьютерных наук и технологий . 7 : 419–493.
  4. ^ Питер Дж. Бентли (2012). Оцифровано: Наука о компьютерах и как она формирует наш мир . Издательство Оксфордского университета. п. 87. ISBN 9780199693795. Архивировано 29 августа 2016 года.
  5. ^ Backus et al. «Система автоматического кодирования FORTRAN», Учеб. AFIPS 1957 г. Совместная западная компьютерная конференция, Spartan Books, Балтимор 188–198
  6. ^ [2] Розен, Саул. АЛЬТАК, ФОРТРАН и совместимость . Материалы 16-го национального собрания ACM 1961 г.
  7. ^ Т. Харт и М. Левин "Новый компилятор", AIM-39 [ постоянная мертвая ссылка ] Цифровой архив CSAIL - Лаборатория искусственного интеллекта.
  8. ^ а б Тим Харт; Майк Левин. «AI Memo 39-Новый компилятор» (PDF) . Проверено 23 мая 2008 года . [ постоянная мертвая ссылка ]
  9. ↑ Хомский, Ноам (сентябрь 1956 г.). «Три модели для описания языка». IEEE Transactions по теории информации . 2 (3): 113–124. DOI : 10.1109 / TIT.1956.1056813 . S2CID 19519474 . 
  10. ^ Кнут, Дональд. «О переводе языков слева направо» (PDF) . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
  11. ^ Кореняк, А. «Практический метод построения процессоров LR (k)», Сообщения ACM, Vol. 12, No. 11, 1969 г.
  12. ^ ДеРемер, Ф. Практические переводчики для языков LR (k). Кандидатская диссертация, Массачусетский технологический институт, 1969.
  13. ^ DeRemer, F. "Простые LR (k) грамматики", Сообщения ACM, Vol. 14, № 7, 1971.
  14. ^ a b Томас Дж. Пеннелло (1986). «Очень быстрый парсинг LR» . Уведомления ACM SIGPLAN . 21 (7).
  15. ^ GH Робертс (1988). «Рекурсивный подъем: аналог LR рекурсивного спуска» .
  16. ^ Leermakers, Augusteijn, Kruseman Арец (1992). «Функциональный парсер LR» .CS1 maint: несколько имен: список авторов ( ссылка )
  17. ^ А. А. Грау, "Рекурсивные процессы и перевод АЛГОЛОВ", Commun. АКМ, 4, № 1, с. 10–15. Январь 1961 г.
  18. ^ Эдгар Т. Айронс , "Синтаксически управляемый компилятор для АЛГОЛА 60", Commun. АКМ, 4, № 1, январь 1961 г., стр. 51–55.
  19. ^ «Истории о B5000 и людях, которые там были» (PDF) .
  20. ^ "Конференция Берроуза B5000, Институт Чарльза Бэббиджа". ЛВП : 11299/107105 . Цитировать журнал требует |journal=( помощь )
  21. ↑ PM Lewis, RE Stearns, «Syntax-direction transduction», фокусы, стр. 21–35, 7-й ежегодный симпозиум по теории коммутации и автоматов (SWAT 1966), 1966
  22. ^ Льюис, П. и Стернс, Р. «Синтаксически-управляемое преобразование», Журнал ACM, Vol. 15, № 3, 1968.
  23. ^ "Компилятор / интерпретатор PL / 0" . Архивировано из оригинала 8 декабря 2008 года . Проверено 7 июля 2011 года .
  24. ^ Дж. Эрли, «Эффективный контекстно-свободный алгоритм синтаксического анализа» , Коммуникации Ассоциации вычислительной техники , 13 : 2: 94-102, 1970.
  25. Перейти ↑ Backus, JW (1959). «Синтаксис и семантика предложенного международного алгебраического языка Цюрихской конференции ACM-GAMM» . Труды Международной конференции по обработке информации : 125–132.
  26. ↑ Фаррелл, Джеймс А. (август 1995 г.). «Расширенная форма Бэкус Наур» . Основы компилятора . Проверено 11 мая 2011 года .
  27. ^ Дональд Э. Кнут, "Нормальная форма Бэкуса против формы Бэкуса Наура", Commun. АКМ, 7 (12): 735–736, 1964.
  28. ^ "Мета-компилятор TMG" . reocities.com . Архивировано из оригинала 4 марта 2016 года . Проверено 30 июня 2011 года .
  29. ^ "Архивная копия" . Архивировано из оригинального 21 сентября 2007 года . Проверено 30 июня 2011 года .CS1 maint: заархивированная копия как заголовок ( ссылка )
  30. ^ «Языки программирования для нечисловой обработки - 1» . acm.org .
  31. ^ RM McClure, TMG - Синтаксически управляемый компилятор . 20-я Национальная конференция ACM. (1965), стр. 262–274.
  32. ^ "Multics PL / I" . multicans.org .
  33. ^ "Архивная копия" . Архивировано из оригинала на 10 января 2015 года . Проверено 3 августа 2011 года .CS1 maint: заархивированная копия как заголовок ( ссылка )Деннис М. Ричи. Развитие языка C
  34. ^ МакКиман, Уильям Маршалл; Хорнинг, Джеймс Дж .; и Уортман, Дэвид Б., Генератор компилятора (1971), ISBN 978-0-13-155077-3 . 
  35. ^ Департамент компьютерных наук, Университет Торонто , "Язык программирования XPL"
  36. ^ Джонсон, SC, «Yacc - еще один компилятор компилятора», Технический отчет 32 по вычислительной науке, AT&T Bell Labs, 1975
  37. ^ Гамильтон, Наоми. «Азия языков программирования: YACC» . TechWorld .
  38. ^ «META II - синтаксически ориентированный язык написания компиляторов» . acm.org .
  39. ^ "Comp.compilers: Re: История и эволюция компиляторов" . iecc.com .
  40. ^ FE Аллен. Оптимизация программы. В: Марк И. Халперн и Кристофер Дж. Шоу, редакторы, Ежегодный обзор автоматического программирования, том 5, страницы 239–307. Pergamon Press, Нью-Йорк, 1969.
  41. ^ Фрэнсис Э. Аллен и Джон Кок. Теоретико-графические конструкции для анализа потока управления программой. Технический отчет IBM Res. Представитель RC 3923, IBM TJ Watson Research Center, Yorktown Heights, NY, 1972.
  42. ^ Фрэнсис Э. Аллен. Анализ потока управления. Уведомления ACM SIGPLAN, 5 (7): 1–19, июль 1970 г.
  43. ^ Фрэнсис Э. Аллен. Основа для оптимизации программы. В Proc. Конгресс ИФИП 71, страницы 385–390. Северная Голландия, 1972 год.
  44. ^ Фрэнсис Э. Аллен и Джон Кок. Каталог оптимизирующих преобразований. В Р. Растин, редактор, Дизайн и оптимизация компиляторов, страницы 1–30. Прентис-Холл, 1971.
  45. ^ Фрэнсис Э. Аллен. Анализ межпроцедурного потока данных. В Proc. Конгресс ИФИП 74, страницы 398–402. Северная Голландия, 1974.
  46. ^ Фрэнсис Э. Аллен. Метод определения отношений данных программы. В редакции Андрея Ершова и Валерия А. Непомнящего, Proc. Международный симпозиум по теоретическому программированию, Новосибирск, СССР, август 1972 г., том 5 конспектов лекций по информатике, стр. 299–308. Спрингер-Верлаг, 1974.
  47. ^ Фрэнсис Э. Аллен и Джон Кок. Процедура анализа потока данных программы. Сообщения ACM, 19 (3): 137–147, март 1976 г.
  48. ↑ Вивек Саркар. Система параллельного программирования PTRAN. В языках параллельного функционального программирования и компиляторах, под редакцией Б. Шимански, ACM Press Frontier Series, страницы 309–391, 1991.
  49. ^ Джон Кок и Джейкоб Т. Шварц, Языки программирования и их компиляторы. Курантский институт математических наук Нью-Йоркского университета, апрель 1970 г.
  50. ^ МакКиман, WM Оптимизация глазка . Commun. ACM 8, 7 (июль 1965 г.), 443–444
  51. ^ http://www.bitsavers.org/pdf/ibm/360/A22_6825-1_360instrTiming.pdf
  52. ^ "Программная инженерия для среды Cobol" . acm.org .
  53. ^ CACM марта 1973 С. 169-179.
  54. ^ Cytron, Рон; Ферранте, Жанна; Розен, Барри К .; Wegman, Mark N .; Задек, Ф. Кеннет (1991). «Эффективное вычисление статической формы единого назначения и графика зависимости управления» (PDF) . Транзакции ACM по языкам и системам программирования . 13 (4): 451–490. CiteSeerX 10.1.1.100.6361 . DOI : 10.1145 / 115372.115320 . S2CID 13243943 .   

Дальнейшее чтение [ править ]

  • Бэкус, Джон и др., «Система автоматического кодирования FORTRAN» , Труды Западной совместной компьютерной конференции, Лос-Анджелес, Калифорния, февраль 1957. Описывает разработку и реализацию первого компилятора FORTRAN командой IBM.
  • Кнут, Д.Е. , RUNCIBLE-алгебраический перевод на ограниченном компьютере , Коммуникации ACM, Vol. 2, стр. 18 (ноябрь 1959 г.).
  • Айронс, Эдгар Т., Компилятор, управляемый синтаксисом для АЛГОЛА 60 , Сообщения ACM, Vol. 4, стр. 51. (январь 1961 г.).
  • Дейкстра, Эдсгер В. (1961). «Перевод ALGOL 60: переводчик ALGOL 60 для X1 и создание переводчика для ALGOL 60 (PDF) (технический отчет). Амстердам: Mathematisch Centrum. 35.
  • Конвей, Мелвин Э. , Дизайн разделимого компилятора диаграмм переходов , Коммуникации ACM, том 6, выпуск 7 (июль 1963 г.)
  • Флойд, Р. У. , Синтаксический анализ и приоритет операторов , Журнал ACM, Vol. 10, стр. 316. (июль 1963 г.).
  • Cheatham, TE, и Sattley, K., Компиляция , управляемая синтаксисом , SJCC, стр. 31. (1964).
  • Рэнделл, Брайан ; Рассел, Лоуфорд Джон, Реализация Алгола 60: перевод и использование программ Алгола 60 на компьютере , Academic Press, 1964
  • Кнут, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
  • Кок, Джон ; Шварц, Джейкоб Т. , Языки программирования и их компиляторы: предварительные замечания , технический отчет Института математических наук Куранта , Нью-Йоркский университет , 1969.
  • Бауэр, Фридрих Л .; Эйкель, Юрген (ред.), Конструирование компилятора, Продвинутый курс , 2-е изд. Лекционные заметки по информатике 21, Springer 1976, ISBN 3-540-07542-9 
  • Грис, Дэвид , Конструирование компиляторов для цифровых компьютеров , Нью-Йорк: Wiley, 1971. ISBN 0-471-32776-X 

Внешние ссылки [ править ]

  • Конструирование компилятора до 1980 года - аннотированный список литературы Дика Грюна
  • «История написания компиляторов» (PDF) . Компьютеры и автоматика . XI (12): 8–10, 12, 14, 24–25. Декабрь 1962 г.