stringtranslate.com

История создания компилятора

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

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

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

Первые компиляторы

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

Между 1942 и 1945 годами Конрад Цузе разработал Plankalkül («плановое исчисление»), первый язык высокого уровня для компьютера, для которого он задумал Planfertigungsgerät («устройство сборки планов»), которое автоматически переводило бы математическую формулировку программы в машиночитаемую перфорированную кинопленку . [1] Однако первый реальный компилятор для этого языка был реализован лишь десятилетия спустя.

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

Первый практический компилятор был написан Коррадо Бёмом в 1951 году для его докторской диссертации [4] [5], одной из первых докторских степеней по информатике, присужденных где-либо в мире.

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

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

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

Самостоятельно размещаемые компиляторы

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

Докторская диссертация Коррадо Бёма

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

НЕЛИАК

Международный компилятор ALGOL Лаборатории электроники ВМС или NELIAC был диалектом и реализацией компилятора языка программирования ALGOL 58 , разработанным Лабораторией электроники ВМС в 1958 году. [13]

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

Лисп

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

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

—  Записка ИИ 39 [15]

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

Вперед

Forth — пример самохостингового компилятора. Возможности самокомпиляции и кросс-компиляции Forth являются синонимами метакомпиляции и метакомпиляторов . [16] [17] Как и Lisp , Forth — расширяемый язык программирования . Именно расширяемые возможности языков программирования Forth и Lisp позволяют им генерировать новые версии самих себя или переносить себя в новые среды.

Контекстно-свободные грамматики и парсеры

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

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

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

LR-анализ

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

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

Кореняк (1969) был первым, кто показал, что синтаксические анализаторы для языков программирования могут быть созданы с использованием этих методов. [20] Фрэнк ДеРемер разработал более практичные методы Simple LR (SLR) и Look-ahead LR (LALR), опубликованные в его докторской диссертации в Массачусетском технологическом институте в 1969 году. [21] [22] Это был важный прорыв, поскольку трансляторы 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 часто используются компиляторами для выполнения синтаксического анализа исходного кода.

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

Рекурсивный подъем был впервые описан Томасом Пеннелло в его статье «Очень быстрый LR-анализ» в 1986 году. [23] Позднее эта техника была подробно описана Г. Х. Робертсом [24] в 1988 году, а также в статье Лермейкерса, Аугустейна, Круземана Аретца [25] в 1992 году в журнале Theoretical Computer Science .

LL-анализ

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

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

Разработка ALGOL побудила к исследованию рекурсивного спуска, поскольку сам язык ALGOL является рекурсивным. Концепция анализа рекурсивного спуска обсуждалась в выпуске Communications of the ACM за январь 1961 года в отдельных статьях AA Grau и Edgar T. "Ned" Irons. [26] [27] Ричард Уэйчофф и его коллеги также реализовали рекурсивный спуск в компиляторе Burroughs ALGOL в марте 1961 года, [28] эти две группы использовали разные подходы, но находились, по крайней мере, в неформальном контакте. [29]

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

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

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

Ранний парсер

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

Языки описания грамматики

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

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

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

Генераторы парсеров

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

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

В начале 1960-х годов Роберт МакКлур из Texas Instruments изобрел компилятор-транслятор под названием TMG , название которого произошло от «transmogrification» (трансмогрификация). [37] [38] [39] [40] В последующие годы TMG был портирован на несколько мэйнфреймов UNIVAC и IBM.

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

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

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

XPL

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

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

Якк

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

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

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

Коко/Р

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

АНТЛР

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

Метакомпиляторы

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

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

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

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

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. [7]

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

Оптимизирующие компиляторы

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

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

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

Фрэнсис Э. Аллен , работая самостоятельно и совместно с Джоном Коком , представила многие концепции оптимизации. В статье Аллена 1966 года «Оптимизация программ» [49] было представлено использование графовых структур данных для кодирования содержимого программы для оптимизации. [50] В ее статьях 1970 года «Анализ потока управления » [51] и «Основа оптимизации программ » [52] были установлены интервалы как контекст для эффективного и действенного анализа и оптимизации потока данных. В ее статье 1971 года с Коком « Каталог оптимизирующих преобразований» [53] было дано первое описание и систематизация оптимизирующих преобразований. В ее статьях 1973 и 1974 годов по межпроцедурному анализу потока данных анализ был распространен на целые программы. [54] [55] В ее статье 1976 года с Коком описывается одна из двух основных стратегий анализа, используемых сегодня в оптимизирующих компиляторах. [56]

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

Programming Languages ​​and their Compilers Джона Кока и Джейкоба Т. Шварца , опубликованная в начале 1970 года, посвятила более 200 страниц алгоритмам оптимизации. Она включала многие из ныне известных методов, таких как устранение избыточного кода и снижение прочности . [58]

В 1972 году Гэри А. Килдалл [59] представил теорию анализа потока данных , используемую сегодня в оптимизирующих компиляторах [60] (иногда известную как метод Килдалла ).

Оптимизация глазка

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

Оптимизатор COBOL капитальных затрат

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

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

Диагностика

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

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

ПЛ/С

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

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

Компиляция точно в срок

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

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

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

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

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

Генерация кода

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

Распределение регистров

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

Известные составители

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

Ссылки

  1. ^ Хеллиге, Ганс Дитер (2004). Geschichten der Informatik - Visionen, Paradigmen, Leitmotive (на немецком языке) (1-е изд.). Берлин, Германия: Шпрингер. стр. 45, 104, 105. ISBN. 3-540-00217-0.
  2. ^ Рутисхаузер, Хайнц (1951). «Über autotische Rechenplanfertigung bei programmgesteuerten Rechenanlagen». Zeitschrift für Angewandte Mathematik und Mechanik (на немецком языке). 31 :255. дои :10.1002/замм.19510310820.
  3. ^ Фоте, Майкл; Уилке, Томас, ред. (2015) [14 ноября 2014 г.]. Написано в Йене, Германия. Келлер, Stack und autotisches Gedächtnis – eine Struktur mit Potenzial [ Подвал, стек и автоматическая память - структура с потенциалом ] (PDF) (Tagungsband zum Kolloquium, 14 ноября 2014 г., Йена). Серия GI: Конспекты лекций по информатике (LNI) - Тематика (на немецком языке). Том. Т-7. Бонн, Германия: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. стр. 20–21. ISBN 978-3-88579-426-4. ISSN  1614-3213. Архивировано (PDF) из оригинала 12 апреля 2020 г. . Получено 12 апреля 2020 г. .[1] (77 страниц)
  4. ^ Аб Бём, Коррадо (1954). Calculatrices digitales: Du déchiffrage de Formulas logomatématiques par la Machine Même dans la Conception du Program (PDF) (доктор философии) (на французском языке). Цюрих: ETH Цюрих . Проверено 27 сентября 2022 г.
  5. ^ ab Böhm, Corrado (1954). Цифровые компьютеры: О кодировании логико-математических формул с использованием самой машины во время замысла программы (PDF) (PhD). Цюрих: ETH Zurich . Получено 27 сентября 2022 г.
  6. ^ Морис В. Уилкс . 1968. Компьютеры тогда и сейчас. Журнал Ассоциации вычислительной техники, 15(1):1–7, январь. стр. 3 (комментарий в скобках добавлен редактором), «(Я не думаю, что термин компилятор был тогда [1953] общеупотребительным, хотя на самом деле он был введен Грейс Хоппер.)»
  7. ^ abc [2] Первые в мире компиляторы COBOL Архивировано 13 октября 2011 г. на Wayback Machine
  8. ^ Кнут, Дональд Э.; Пардо, Луис Трабб. «Раннее развитие языков программирования». Энциклопедия компьютерных наук и технологий . 7 : 419–493.
  9. ^ Бентли, Питер Дж. (2012). Оцифровано: Наука о компьютерах и как она формирует наш мир. Oxford University Press. стр. 87. ISBN 978-0-19-969379-5. Архивировано из оригинала 29 августа 2016 года.
  10. ^ Бэкус и др. «Автоматическая система кодирования FORTRAN», Труды AFIPS 1957 Western Joint Computer Conf., Spartan Books, Балтимор 188–198
  11. ^ [3] Розен, Сол. ALTAC, FORTRAN и совместимость . Труды 16-го национального собрания ACM 1961 г.
  12. ^ Норман, Джереми. «Грейс Хоппер и коллеги представляют COBOL». HistoryOfInformation.com . Джереми Норман . Получено 14 декабря 2022 г. .
  13. ^ «Реализации и диалекты Algol 58 — Группа сохранения программного обеспечения».
  14. ^ Т. Харт и М. Левин «Новый компилятор», AIM-39 CSAIL Цифровой архив – Серия «Лаборатория искусственного интеллекта»
  15. ^ ab Харт, Тим; Левин, Майк. "AI Memo 39-The new compiler" (PDF) . Архивировано из оригинала (PDF) 13 декабря 2020 г. . Получено 23 мая 2008 г. .
  16. ^ "Введение в метакомпиляцию в FORTH". 24 марта 2021 г.
  17. ^ Хау, Ричард Джеймс. «Мета-компилятор, реализация eForth и руководство по обоим». GitHub . Получено 27 сентября 2022 г.
  18. ^ Хомский, Ноам (сентябрь 1956 г.). «Три модели описания языка». Труды IEEE по теории информации . 2 (3): 113–124. doi :10.1109/TIT.1956.1056813. S2CID  19519474.
  19. ^ Кнут, Дональд. «О переводе языков слева направо» (PDF) . Архивировано из оригинала (PDF) 15 марта 2012 г. . Получено 29 мая 2011 г. .
  20. ^ Кореняк, А. "Практический метод построения LR(k) процессоров", Сообщения ACM , т. 12, № 11, 1969
  21. ^ ДеРемер, Ф. Практические переводчики для языков LR(k). Кандидатская диссертация, Массачусетский технологический институт, 1969.
  22. ^ ДеРемер, Ф. «Простые LR(k) грамматики», Сообщения ACM , т. 14, № 7, 1971.
  23. ^ ab Thomas J Pennello (1986). "Очень быстрый анализ LR". ACM SIGPLAN Notices . Том 21, № 7.
  24. ^ GH Roberts (1988). «Рекурсивное восхождение: аналог LR рекурсивного спуска». ACM SIGPLAN Notices . 23 (8): 23–29. doi : 10.1145/47907.47909 . S2CID  12740771.
  25. ^ Рене Леермейкерс; Лекс Огюстейн; Франс Э.Дж. Круземан Арец (1992). «Функциональный парсер LR». Теоретическая информатика . 104 (2): 313–323. дои : 10.1016/0304-3975(92)90128-3 .
  26. ^ А. А. Грау, «Рекурсивные процессы и АЛГОЛ-трансляция», Сообщения АКМ , 4, № 1, стр. 10–15. Январь 1961 г.
  27. ↑ Эдгар Т. Айронс, «Синтаксически-управляемый компилятор для ALGOL 60», Communications of the ACM , 4, № 1, январь 1961 г., стр. 51–55.
  28. ^ "Истории B5000 и людей, которые там были" (PDF) . Архивировано из оригинала (PDF) 1 марта 2021 г. . Получено 1 августа 2016 г. .
  29. ^ Уэйчофф, Ричард; Тернер, Ллойд; Розин, Роберт Ф.; Пирсон, Ральф В.; Олифинт, Г. Кларк; Маккензи, Ф. Брэд; Макдональд, Рэй В.; Макдональд, Дункан Н.; Лонерган, Уильям Д.; Крюдер, Норман Л.; Кинг, Пол Д.; Хутман, Джозеф Т.; Хаук, Эрвин А.; Хейл, Джон Э.; Галлер, Бернард А.; Форд, Джеймс; Эпперт, Рэй Р.; Дент, Бенджамин А.; Дам, Дэвид М.; Крич, Бобби А.; Коллинз, Джордж А.; Берс, Генри; Бартон, Роберт С. (6 сентября 1985 г.). «Burroughs B 5000 Conference». Университет Миннесоты . hdl :11299/107105.
  30. ^ PM Lewis, RE Stearns, «Синтаксически направленная трансдукция», focs, стр. 21–35, 7-й ежегодный симпозиум по теории коммутации и автоматов (SWAT 1966), 1966
  31. ^ Льюис, П. и Стернс, Р. «Трансдукция, направленная на синтаксис», Журнал ACM , т. 15, № 3, 1968.
  32. ^ "Компилятор/интерпретатор PL/0". Архивировано из оригинала 8 декабря 2008 г. Получено 7 июля 2011 г.
  33. ^ Дж. Эрли, «Эффективный контекстно-свободный алгоритм синтаксического анализа», Сообщения Ассоциации вычислительной техники , 13 :2:94-102, 1970.
  34. ^ Бэкус, Дж. В. (1959). «Синтаксис и семантика предложенного международного алгебраического языка Цюрихской конференции ACM-GAMM». Труды Международной конференции по обработке информации : 125–132.
  35. ^ Фаррелл, Джеймс А. (август 1995). "Расширенная форма Бэкуса-Наура". Основы компиляции . Получено 11 мая 2011 .
  36. ↑ Дональд Э. Кнут, «Нормальная форма Бэкуса против формы Бэкуса-Наура», Communications of the ACM , 7(12):735–736, 1964.
  37. ^ "TMG Meta Compiler". reocities.com . Архивировано из оригинала 4 марта 2016 года . Получено 30 июня 2011 года .
  38. ^ "Энциклопедия компьютерных языков". Архивировано из оригинала 21 сентября 2007 г. Получено 30 июня 2011 г.
  39. ^ МакКлур, Р. М. (1965). «Языки программирования для нечисловой обработки---1: ​​TMG---синтаксически направленный компилятор». Труды 20-й национальной конференции 1965 года. С. 262–274. doi :10.1145/800197.806050. ISBN 978-1-4503-7495-8. S2CID  44606611. {{cite book}}: |work=проигнорировано ( помощь )
  40. ^ RM McClure, TMG — A Syntax Directed Compiler Proc. 20th ACM National Conf. (1965), стр. 262–274.
  41. ^ "Multics PL/I". multicians.org .
  42. ^ "Chistory". Архивировано из оригинала 10 января 2015 года . Получено 3 августа 2011 года .Деннис М. Ритчи. Развитие языка Си
  43. ^ Маккиман, Уильям Маршалл; Хорнинг, Джеймс Дж.; и Вортман, Дэвид Б., Генератор компиляторов (1971), ISBN 978-0-13-155077-3 . 
  44. ^ Кафедра компьютерных наук, Университет Торонто , «Язык программирования XPL»
  45. ^ Джонсон, С.К., «Yacc – Yet Another Compiler-Compiler», Технический отчет по вычислительной технике 32, AT&T Bell Labs, 1975
  46. ^ Гамильтон, Наоми (5 октября 2023 г.). «Языки программирования от А до Я: YACC». TechWorld .
  47. ^ Шорре, Д. В. (1964). «META II — язык написания компиляторов, ориентированный на синтаксис». Труды 19-й национальной конференции ACM 1964 года . С. 41.301–41.3011. doi :10.1145/800257.808896. ISBN 978-1-4503-7918-2. S2CID  43144779. {{cite book}}: |work=проигнорировано ( помощь )
  48. ^ "Comp.compilers: Re: История и эволюция компиляторов". iecc.com .
  49. ^ Фрэнсис Э. Аллен , «Оптимизация программ» в книге Марка И. Хэлперна и Кристофера Дж. Шоу, редакторов, Annual Review in Automatic Programming , том 5, страницы 239–307. Pergamon Press, Нью-Йорк, 1969.
  50. ^ Аллен, Фрэнсис Э.; Кок, Джон (11 июля 1972 г.). Графовые конструкции для анализа потока управления программой (RC 3923) (PDF) . Yorktown Heights, NY: IBM Thomas J. Watson Research Center . Получено 6 мая 2021 г. .
  51. ^ Фрэнсис Э. Аллен. «Анализ потока управления». ACM SIGPLAN Notices , 5(7):1–19, июль 1970 г.
  52. ^ Фрэнсис Э. Аллен. «Основа оптимизации программ». В Трудах Конгресса IFIP 71 , страницы 385–390. Северная Голландия, 1972.
  53. ^ Фрэнсис Э. Аллен и Джон Кок. «Каталог оптимизирующих преобразований». В книге Р. Растина, редактора «Проектирование и оптимизация компиляторов » , страницы 1–30. Prentice-Hall, 1971.
  54. ^ Фрэнсис Э. Аллен. «Анализ межпроцедурного потока данных». В Трудах Конгресса IFIP 74, страницы 398–402. Северная Голландия, 1974.
  55. ^ Фрэнсис Э. Аллен. «Метод определения связей между данными программы». В сборнике трудов Международного симпозиума по теоретическому программированию под редакцией Андрея Ершова и Валерия А. Непомнящего , Новосибирск, СССР, август 1972 г., том 5 Lecture Notes in Computer Science, страницы 299–308. Springer-Verlag, 1974.
  56. ^ Фрэнсис Э. Аллен и Джон Кок. «Процедура анализа потока данных программы», Communications of the ACM , 19(3):137–147, март 1976 г.
  57. ^ Саркар, Вивек (1991). «PTRAN — система параллельной трансляции IBM». Параллельные функциональные языки и компиляторы. Нью-Йорк, Нью-Йорк: Ассоциация вычислительной техники. С. 309–391. doi :10.1145/107214.129260. ISBN 0-201-52243-8. Получено 6 мая 2021 г. .
  58. ^ Джон Кок и Джейкоб Т. Шварц, Языки программирования и их компиляторы . Институт математических наук Куранта, Нью-Йоркский университет, апрель 1970 г.
  59. ^ Килдалл, Гэри Арлен (май 1972). Глобальная оптимизация выражений во время компиляции (диссертация на степень доктора философии). Сиэтл, Вашингтон, США: Вашингтонский университет , Computer Science Group. Диссертация № 20506, Технический отчет № 72-06-02.
  60. ^ Kildall, Gary Arlen (1 октября 1973 г.). «Унифицированный подход к глобальной оптимизации программ» (PDF) . Труды 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (POPL) . Бостон, Массачусетс, США: 194–206. doi :10.1145/512927.512945. hdl :10945/42162. S2CID  10219496 . Получено 2 мая 2023 г. .
  61. ^ Маккиман, WM "Оптимизация через глазок". Сообщения ACM 8, 7 (июль 1965), 443–444
  62. ^ System/360 Instruction Timing Information (PDF) . IBM Systems Reference Library. Май 1964. Получено 6 мая 2021 .
  63. ^ Эванс, Майкл (1982). «Программная инженерия для среды Cobol». Сообщения ACM . 25 (12): 874–882. ​​doi : 10.1145/358728.358732 . S2CID  17268690.
  64. ↑ CACM, март 1973 г., стр. 169–179.
  65. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; Zadeck, F. Kenneth (1991). «Эффективное вычисление статической формы одиночного присваивания и графа зависимости управления» (PDF) . ACM Transactions on Programming Languages ​​and Systems . 13 (4): 451–490. CiteSeerX 10.1.1.100.6361 . doi :10.1145/115372.115320. S2CID  13243943. 

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

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