✖


Jump to content

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

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

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

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

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

[ редактировать ]
Не путать с компилятором-компилятором .

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

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

[ редактировать ]

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

НЕЛИАК

[ редактировать ]

Лаборатории электроники ВМФ Международный АЛГОЛ компилятор или NELIAC представлял собой диалект и реализацию компилятора АЛГОЛ 58, языка программирования разработанного Лабораторией военно-морской электроники в 1958 году. [13]

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

Лисп

[ редактировать ]

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

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

— Памятка ИИ 39 [15]

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

Форт

[ редактировать ]

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

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

[ редактировать ]

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

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

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

LR-парсинг

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

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

Разработка АЛГОЛА вызвала исследование рекурсивного спуска, поскольку сам язык АЛГОЛ рекурсивен. Концепция анализа рекурсивного спуска обсуждалась в январском выпуске журнала Communications of ACM за 1961 год в отдельных статьях А. А. Грау и Эдгара Т. «Неда» Айронса . [26] [27] Ричард Вейчофф и его коллеги также реализовали рекурсивный спуск в компиляторе АЛГОЛА Берроуза в марте 1961 года. [28] обе группы использовали разные подходы, но поддерживали, по крайней мере, неформальный контакт. [29]

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

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

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

Парсер Эрли

[ редактировать ]

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

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

[ редактировать ]

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

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

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

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

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

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

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

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

Проект Multics , совместное предприятие Массачусетского технологического института и 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 B был непосредственным предком C. на своем PDP-7 в 1970 году .

Ранний генератор синтаксического анализатора 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] Название является аббревиатурой от « Еще один компилятор-компилятор ». Он генерирует компилятор 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) в Модуле-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, отделяющие создание кода от анализа грамматики. Операции преобразования дерева в синтаксической формуле создают абстрактные синтаксические деревья , над которыми работают правила разбора. Сопоставление с образцом дерева неразбора обеспечило возможность оптимизации в виде глазка .

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 способствовала портированию АЛГОЛА 68C на множество различных компьютерных платформ.

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

[ редактировать ]

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

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

от IBM Более поздние компиляторы, такие как компилятор Fortran IV , уделяли больше внимания хорошей диагностике и более быстрому выполнению за счет объектного кода оптимизации . Лишь в серии 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 разработала новые схемы обнаружения параллелизма и создала концепцию графа зависимости программы — основного метода структурирования, используемого большинством распараллеливающих компиляторов.

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

Диагностика

[ редактировать ]

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

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

ПЛ/К

[ редактировать ]

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

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

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

[ редактировать ]
Основная статья: Сборка точно в срок

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

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

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

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

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

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

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]
См. Также: АЛГОЛ 60: график реализации АЛГОЛ 60 и список компиляторов.

См. также

[ редактировать ]

Ссылки

[ редактировать ]
  1. ^ Хеллиге, Ганс Дитер (2004). Истории информатики - видения, парадигмы, лейтмотивы (на немецком языке) (1-е изд.). Берлин, Германия: Шпрингер. стр. 45, 104, 105. ISBN.  3-540-00217-0 .
  2. ^ Рутисхаузер, Хайнц (1951). «Об автоматическом составлении расчетных планов в вычислительных системах с программным управлением». Журнал прикладной математики и механики (на немецком языке). 31 :255. дои : 10.1002/zamm.19510310820 .
  3. ^ Фоте, Майкл; Уилке, Томас, ред. (2015) [14 ноября 2014 г.]. Написано в Йене, Германия. Подвал, стек и автоматическая память — структура с потенциалом [ Подвал, стек и автоматическая память — структура с потенциалом ] (PDF) (Материалы коллоквиума 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. ^ Jump up to: а б Бём, Коррадо (1954). Цифровые калькуляторы: От расшифровки логико-математических формул самой машиной в разработке программы (PDF) (PhD) (на французском языке). Цюрих: ETH Цюрих . Проверено 27 сентября 2022 г.
  5. ^ Jump up to: а б Бём, Коррадо (1954). Цифровые компьютеры: О кодировании логико-математических формул с использованием самой машины во время разработки программы (PDF) (доктор философии). Цюрих: ETH Цюрих . Проверено 27 сентября 2022 г.
  6. ^ Морис В. Уилкс . 1968. Компьютеры тогда и сейчас. Журнал Ассоциации вычислительной техники, 15 (1): 1–7, январь. п. 3 (комментарий в скобках добавлен редактором): «(Я не думаю, что термин «компилятор» тогда [1953] широко использовался, хотя на самом деле он был введен Грейс Хоппер.)»
  7. ^ Jump up to: а б с [2] Первые в мире компиляторы COBOL. Архивировано 13 октября 2011 года в Wayback Machine.
  8. ^ Кнут, Дональд Э.; Пардо, Луис Трабб. «Раннее развитие языков программирования». Энциклопедия компьютерных наук и технологий . 7 : 419–493.
  9. ^ Бентли, Питер Дж. (2012). Оцифровка: компьютерная наука и как она формирует наш мир . Издательство Оксфордского университета. п. 87. ИСБН  978-0-19-969379-5 . Архивировано из оригинала 29 августа 2016 года.
  10. ^ Бэкус и др. «Система автоматического кодирования FORTRAN», Учеб. AFIPS, 1957 г., Западная объединенная компьютерная конференция, 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. ^ Jump up to: а б Харт, Тим; Левин, Майк. «AI Memo 39-Новый компилятор» (PDF) . Архивировано из оригинала (PDF) 13 декабря 2020 года . Проверено 23 мая 2008 г.
  16. ^ «Введение в метакомпиляцию в FORTH» . 24 марта 2021 г.
  17. ^ Хау, Ричард Джеймс. «Метакомпилятор, реализация eForth и руководство по обоим» . Гитхаб . Проверено 27 сентября 2022 г.
  18. ^ Хомский, Ноам (сентябрь 1956 г.). «Три модели описания языка». Транзакции IEEE по теории информации . 2 (3): 113–124. дои : 10.1109/TIT.1956.1056813 . S2CID   19519474 .
  19. ^ Кнут, Дональд. «О переводе языков слева направо» (PDF) . Архивировано из оригинала (PDF) 15 марта 2012 года . Проверено 29 мая 2011 г.
  20. ^ Кореняк, А. «Практический метод построения процессоров LR (k)», Communications of the ACM , Vol. 12, № 11, 1969 г.
  21. ^ ДеРемер, Ф. Практические переводчики для языков LR (k). Кандидатская диссертация, Массачусетский технологический институт, 1969.
  22. ^ ДеРемер, Ф. «Простые LR(k) грамматики», Communications of the ACM , Vol. 14, № 7, 1971.
  23. ^ Jump up to: а б Томас Дж. Пеннелло (1986). «Очень быстрый анализ LR» . Уведомления ACM SIGPLAN . Том. 21, нет. 7.
  24. ^ Г.Х. Робертс (1988). «Рекурсивный подъем: LR-аналог рекурсивного спуска» . Уведомления ACM SIGPLAN . 23 (8): 23–29. дои : 10.1145/47907.47909 . S2CID   12740771 .
  25. ^ Рене Леермейкерс; Лекс Огюстейн; Французский Э.Дж. Круземан Арец (1992). «Функциональный парсер LR» . Теоретическая информатика . 104 (2): 313–323. дои : 10.1016/0304-3975(92)90128-3 .
  26. ^ А. А. Грау, «Рекурсивные процессы и перевод АЛГОЛА», Сообщения ACM , 4, № 1, стр. 10–15. Январь 1961 г.
  27. ^ Эдгар Т. Айронс , «Стаксисно-управляемый компилятор для АЛГОЛа 60», Communications of the ACM , 4, № 1, январь 1961, стр. 51–55.
  28. ^ «Истории о B5000 и людях, которые там были» (PDF) .
  29. ^ Уэйчофф, Ричард; Тернер, Ллойд; Розин, Роберт Ф.; Пирсон, Ральф В.; Олифинт, Дж. Кларк; Маккензи, Ф. Брэд; Макдональд, Рэй В.; Макдональд, Дункан Н.; Лонерган, Уильям Д.; Кройдер, Норман Л.; Кинг, Пол Д.; Хутман, Джозеф Т.; Хаук, Эрвин А.; Хейл, Джон Э.; Галлер, Бернард А.; Форд, Джеймс; Эпперт, Рэй Р.; Дент, Бенджамин А.; Дам, Дэвид М.; Крич, Бобби А.; Коллинз, Джордж А.; Берс, Анри; Бартон, Роберт С. (6 сентября 1985 г.). «Конференция Берроуза B 5000» . Университет Миннесоты . hdl : 11299/107105 .
  30. ^ П. М. Льюис, Р. Э. Стернс, «Синтаксиально-направленная трансдукция», focs, стр. 21–35, 7-й ежегодный симпозиум по теории коммутации и автоматов (SWAT 1966), 1966
  31. ^ Льюис, П. и Стернс, Р. «Синтаксиально-направленная трансдукция», Журнал ACM , Vol. 15, № 3, 1968.
  32. ^ «Компилятор/интерпретатор PL/0» . Архивировано из оригинала 8 декабря 2008 года . Проверено 7 июля 2011 г.
  33. ^ Дж. Эрли, «Эффективный алгоритм контекстно-свободного анализа» , Сообщения Ассоциации вычислительной техники , 13 :2:94-102, 1970.
  34. ^ Бэкус, JW (1959). «Синтаксис и семантика предложенного международного алгебраического языка Цюрихской конференции ACM-GAMM» . Материалы Международной конференции по обработке информации : 125–132.
  35. ^ Фаррелл, Джеймс А. (август 1995 г.). «Расширенная форма Бэкуса-Наура» . Основы компиляции . Проверено 11 мая 2011 г.
  36. ^ Дональд Э. Кнут, «Нормальная форма Бэкуса против формы Бэкуса-Наура», Communications of the ACM , 7 (12): 735–736, 1964.
  37. ^ «Метакомпилятор TMG» . reocities.com . Архивировано из оригинала 4 марта 2016 года . Проверено 30 июня 2011 г.
  38. ^ «Энциклопедия компьютерных языков» . Архивировано из оригинала 21 сентября 2007 года . Проверено 30 июня 2011 г.
  39. ^ МакКлюр, Р.М. (1965). «Языки программирования для нечисловой обработки --- 1: TMG --- синтаксически управляемый компилятор». Материалы 20-й национальной конференции 1965 года . стр. 262–274. дои : 10.1145/800197.806050 . ISBN  978-1-4503-7495-8 . S2CID   44606611 . {{cite book}}: |work= игнорируется ( помогите )
  40. ^ RM McClure, TMG - Синтаксически управляемый компилятор, Proc. 20-я Национальная конференция ACM. (1965), стр. 262–274.
  41. ^ «Мультикс ПЛ/И» . multicians.org .
  42. ^ «Чистория» . Архивировано из оригинала 10 января 2015 года . Проверено 3 августа 2011 г. Деннис М. Ричи. Развитие языка Си
  43. ^ Маккиман, Уильям Маршалл; Хорнинг, Джеймс Дж.; и Вортман, Дэвид Б., Генератор компилятора (1971), ISBN   978-0-13-155077-3 .
  44. ^ Факультет компьютерных наук Университета Торонто , «Язык программирования XPL»
  45. ^ Джонсон, SC, «Yacc - еще один компилятор-компилятор», Технический отчет по информатике 32, AT&T Bell Labs, 1975
  46. ^ Гамильтон, Наоми (5 октября 2023 г.). «А-Я языков программирования: YACC» . ТехМир .
  47. ^ Шорре, Д.В. (1964). «META II — синтаксически-ориентированный язык написания компиляторов» . Материалы 19-й национальной конференции ACM 1964 года . С. 41.301–41.3011. дои : 10.1145/800257.808896 . ISBN  978-1-4503-7918-2 . S2CID   43144779 . {{cite book}}: |work= игнорируется ( помогите )
  48. ^ «Comp.compilers: Re: История и эволюция компиляторов» . iecc.com .
  49. ^ Фрэнсис Э. Аллен , «Оптимизация программы» В книге Марка И. Халперна и Кристофера Дж. Шоу, редакторов, « Ежегодный обзор автоматического программирования» , том 5, страницы 239–307. Пергамон Пресс, Нью-Йорк, 1969.
  50. ^ Аллен, Фрэнсис Э.; Кок, Джон (11 июля 1972 г.). Теоретико-графовые конструкции для анализа потока управления программой (RC 3923) (PDF) . Йорктаун-Хайтс, штат Нью-Йорк: Исследовательский центр IBM Томаса Дж. Уотсона . Проверено 6 мая 2021 г.
  51. ^ Фрэнсис Э. Аллен. «Анализ потока управления». Уведомления ACM SIGPLAN , 5(7):1–19, июль 1970 г.
  52. ^ Фрэнсис Э. Аллен. «Основы оптимизации программ».В Proc. Конгресс ИФИП 71 , стр. 385–390. Северная Голландия, 1972 год.
  53. ^ Фрэнсис Э. Аллен и Джон Кок. «Каталог оптимизирующих преобразований». В Р. Растине, редакторе, «Проектирование и оптимизация компиляторов» , страницы 1–30. Прентис-Холл, 1971 год.
  54. ^ Фрэнсис Э. Аллен. «Межпроцедурный анализ потоков данных». В Proc. Конгресс ИФИП 74, страницы 398–402. Северная Голландия, 1974 год.
  55. ^ Фрэнсис Э. Аллен. «Метод определения взаимосвязей данных программы». В соавторстве редакторов Тр. А. Ершова и В. А. Непомнящего . Международный симпозиум по теоретическому программированию , Новосибирск, СССР, август 1972 г., том 5 конспектов лекций по информатике, страницы 299–308. Спрингер-Верлаг, 1974.
  56. ^ Фрэнсис Э. Аллен и Джон Кок. «Процедура анализа потока данных программы», Communications of ACM , 19(3):137–147, март 1976 г.
  57. ^ Саркар, Вивек (1991). «PTRAN — система параллельного перевода IBM». Параллельные функциональные языки и компиляторы . Нью-Йорк, штат Нью-Йорк: Ассоциация вычислительной техники. стр. 309–391. дои : 10.1145/107214.129260 . ISBN  0-201-52243-8 . Проверено 6 мая 2021 г.
  58. ^ Джон Кок и Джейкоб Т. Шварц, Языки программирования и их компиляторы . Институт математических наук Куранта, Нью-Йоркский университет, апрель 1970 г.
  59. ^ Килдалл, Гэри Арлен (май 1972 г.). Глобальная оптимизация выражений во время компиляции (кандидатская диссертация). Сиэтл, Вашингтон, США: Вашингтонский университет , Группа компьютерных наук. Диссертация №20506, Технический отчет №72-06-02.
  60. ^ Килдалл, Гэри Арлен (1 октября 1973 г.). «Единый подход к глобальной оптимизации программ» (PDF) . Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (POPL) . Бостон, Массачусетс, США: 194–206. дои : 10.1145/512927.512945 . hdl : 10945/42162 . S2CID   10219496 . Проверено 2 мая 2023 г.
  61. ^ Маккиман, WM «Оптимизация глазка». Сообщения ACM 8, 7 (июль 1965 г.), 443–444.
  62. ^ Информация о времени выполнения инструкций System/360 (PDF) . Справочная библиотека по системам IBM. Май 1964 года . Проверено 6 мая 2021 г.
  63. ^ Эванс, Майкл (1982). «Программное обеспечение для среды Cobol» . Коммуникации АКМ . 25 (12): 874–882. дои : 10.1145/358728.358732 . S2CID   17268690 .
  64. ^ CACM, март 1973 г., стр. 169–179.
  65. ^ Сайтрон, Рон; Ферранте, Жанна; Розен, Барри К.; Вегман, Марк Н.; Задек, Ф. Кеннет (1991). «Эффективное вычисление статической формы одиночного назначения и графика зависимости управления» (PDF) . Транзакции ACM в языках и системах программирования . 13 (4): 451–490. CiteSeerX   10.1.1.100.6361 . дои : 10.1145/115372.115320 . S2CID   13243943 .

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

[ редактировать ]
[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=History_of_compiler_construction&oldid=1234630604"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 380e44a23fd6ff50b4a8a1e98ee3bd16__1721025540
URL1:https://arc.ask3.ru/arc/aa/38/16/380e44a23fd6ff50b4a8a1e98ee3bd16.html
Заголовок, (Title) документа по адресу, URL1:
History of compiler construction - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)