Компилятор

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

В вычислительная техника компилятор - это компьютерная программа, которая переводит компьютерный код, написанный на одном языке программирования (исходный язык) на другой язык (целевой язык). Название "компилятор" в основном используется для программ, которые переводят исходный код с языка программирования высокого уровня на язык программирования низкого уровня (например, язык ассемблера, объектный код или машинный код) для создания исполняемой программы.[1][2]:p1[3] Существует множество различных типов компиляторов, которые выдают результат в различных полезных формах. Кросс-компилятор производит код для другого центрального процессора или операционной системы, чем та, на которой работает сам кросс-компилятор. Bootstrap-компилятор часто является временным компилятором, используемым для компиляции более постоянного или лучше оптимизированного компилятора для языка. Связанное программное обеспечение включает: программу, переводящую с языка низкого уровня на язык более высокого уровня - декомпилятор'; программу, переводящую между языками высокого уровня, обычно называемую компилятор из исходного текста в исходный текст или транспилятор. Языковой переписывающий модуль - это обычно программа, которая переводит форму выражения без изменения языка. Компилятор компиляторов - это компилятор, который производит компилятор (или его часть), часто в общем и многократно используемом виде, чтобы иметь возможность производить множество различных компиляторов. Компилятор, скорее всего, будет выполнять некоторые или все из следующих операций, часто называемых фазами: препроцессирование, лексический анализ, синтаксический разбор, семантический анализ (синтаксически направленный перевод), преобразование входных программ в промежуточное представление, оптимизация кода и машинно-специфическая генерация кода. Компиляторы обычно реализуют эти фазы в виде модульных компонентов, способствуя эффективному проектированию и корректности трансформаций исходных входных данных в целевые выходные. Ошибки в программе, вызванные неправильным поведением компилятора, бывает очень трудно отследить и устранить; поэтому разработчики компиляторов прилагают значительные усилия для обеспечения корректность компилятора.[4] Компиляторы - не единственный языковой процессор, используемый для преобразования исходных программ. Интерпретатор - это компьютерное программное обеспечение, которое преобразует и затем выполняет указанные операции.[2]:p2 Процесс перевода влияет на дизайн компьютерных языков, что приводит к предпочтению компиляции или интерпретации. Теоретически, язык программирования может иметь как компилятор, так и интерпретатор. На практике языки программирования обычно ассоциируются только с одним из них (компилятором или интерпретатором).

История

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

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

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

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

Предложения в языке могут быть определены набором правил, называемых грамматикой.[5]. Компиляторы: Принципы, методы и инструменты Цзин-Шин Чанг Факультет компьютерных наук и информационной инженерии National Chi-Nan University</ref>

Форма Бэкуса-Наура (БНФ) описывает синтаксис "предложений" языка и была использована для синтаксиса Алгола 60 Джоном Бэкусом.[6] Идеи берут начало от концепций контекстно-свободной грамматики лингвиста Ноама Хомского.[7] "BNF and its extensions have become standard tools for describing the syntax of programming notations, and in many cases parts of compilers are generated automatically from a BNF description."[8]

В 1940-х годах Конрад Цузе разработал алгоритмический язык программирования под названием Планкалкюль ("Плановое исчисление"). Хотя до 1970-х годов реальной реализации не было, в нем были представлены концепции, позже увиденные в APL, разработанном Кеном Айверсоном в конце 1950-х годов.[9] APL - это язык для математических вычислений.

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

  • FORTRAN (перевод формул) для инженерных и научных приложений считается первым языком высокого уровня.[10].
  • COBOL (Common Business-Oriented Language) развился из A-0 и FLOW-MATIC и стал доминирующим языком высокого уровня для бизнес-приложений.[11].
  • LISP (List Processor) для символьных вычислений.[12].

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

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

  • 1952 год: компилятор Autocode, разработанный Аликом Гленни для компьютера Manchester Mark I в Манчестерском университете, некоторые считают первым компилируемым языком программирования.
  • 1952: Команда Грейс Хоппер в Remington Rand написала компилятор для языка программирования A-0 (и придумала термин "компилятор" для его описания),[14][15].

</ref>, хотя компилятор A-0 функционировал скорее как загрузчик или компоновщик, чем как современное понятие полного компилятора.

  • 1954-1957: Команда под руководством Джон Бэкус в IBM разработала FORTRAN, который обычно считается первым языком высокого уровня. В 1957 году они завершили компилятор FORTRAN, который обычно считается первым однозначно полным компилятором.
  • 1959 год: Конференция по языку систем данных (CODASYL) положила начало разработке COBOL. При разработке COBOL использовались A-0 и FLOW-MATIC. К началу 1960-х годов COBOL был скомпилирован на нескольких архитектурах.
  • 1958-1960: Algol 58 был предшественником ALGOL 60. В Алгол 58 были введены блоки кода, что стало ключевым шагом в развитии структурного программирования. ALGOL 60 стал первым языком, в котором были реализованы определения вложенных функций с лексической областью видимости. Он включал рекурсию. Его синтаксис был определен с помощью формы Бэкуса-Наура. АЛГОЛ 60 вдохновил многие языки, которые последовали за ним. Тони Хоар заметил: "... он был не только улучшением своих предшественников, но и почти всех своих преемников"[16][17].
  • 1958-1962: John McCarthy в MIT разработал LISP.[18] Возможности обработки символов предоставляли полезные возможности для исследований искусственного интеллекта. В 1962 году в релизе LISP 1.5 появились некоторые инструменты: интерпретатор, написанный Стивеном Расселом и Дэниелом Дж. Эдвардсом, компилятор и ассемблер, написанные Тимом Хартом и Майком Левиным.[19]

Ранние операционные системы и программное обеспечение были написаны на языке ассемблера. В 1960-х и начале 1970-х годов использование языков высокого уровня для системного программирования все еще было спорным из-за ограниченности ресурсов. Тем не менее, несколько исследовательских и промышленных проектов положили начало переходу на языки системного программирования высокого уровня, например, BCPL, BLISS, B и Си.

BCPL (Basic Combined Programming Language), разработанный в 1966 году Мартин Ричардс в Кембриджском университете, изначально разрабатывался как инструмент для написания компиляторов.[20] Было реализовано несколько компиляторов, книга Ричардса дает представление о языке и его компиляторе.[21] BCPL был не только влиятельным языком системного программирования, который до сих пор используется в исследованиях[22], но и послужил основой для разработки языков B и C.

BLISS (Basic Language for Implementation of System Software) был разработан для компьютера Digital Equipment Corporation (DEC) PDP-10 исследовательской группой В. А. Вульфа из Университета Карнеги-Меллона (CMU). Команда CMU продолжила разработку компилятора BLISS-11 годом позже, в 1970 году.

Multics (Multiplexed Information and Computing Service), проект операционной системы с разделением времени, в котором участвовали MIT, Bell Labs, General Electric (позже Honeywell) и который возглавлял Fernando Corbató из MIT.[23] Multics был написан на языке PL/I, разработанном IBM и IBM User Group.[24] Целью IBM было удовлетворение требований делового, научного и системного программирования. Были и другие языки, которые могли быть рассмотрены, но PL/I предлагал наиболее полное решение, хотя и не был реализован.[25] В течение первых нескольких лет проекта Multics подмножество языка могло быть скомпилировано в ассемблер с помощью компилятора Early PL/I (EPL) Дуга Макилори и Боба Морриса из Bell Labs. [26]

Примечания

  1. Encyclopedia: Definition of Compiler. PCMag.com. Дата обращения: 2 июля 2022.
  2. 2,0 2,1 Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman - Second Edition, 2007
  3. SUDARSANAM, ASHOK. A Retargetable Compilation Methodology for Embedded Digital Signal Processors Using a Machine-Dependent Code Optimization Library // Readings in Hardware/Software Co-Design / ASHOK SUDARSANAM, SHARAD MALIK, MASAHIRO FUJITA. — Elsevier, 2002. — P. 506–515. — «Компилятор - это компьютерная программа, которая переводит программу, написанную на языке высокого уровня (HLL), таком как C, в эквивалентную программу на языке ассемблера. [2].». — ISBN 9781558607026. — doi:10.1016/b978-155860702-6/50045-4.
  4. (2016) «Toward Understanding Compiler Bugs in GCC and LLVM». ACM: 294–305. doi:10.1145/2931037.2931074.
  5. Конспект лекций
  6. Naur, P. et al. "Report on ALGOL 60". Communications of the ACM 3 (May 1960), 299-314.
  7. Chomsky, Noam. Syntactic Structures / Noam Chomsky, David W. Lightfoot. — Walter de Gruyter, 2002. — ISBN 978-3-11-017279-9.
  8. Gries, David. Appendix 1: Backus-Naur Form // The Science of Programming. — Springer Science & Business Media, 2012. — P. 304. — ISBN 978-1461259831.
  9. Iverson, Kenneth E. org/details/programminglangu00iver_0 A Programming Language. — John Wiley & Sons, 1962. — ISBN 978-0-471430-14-8.
  10. Backus, John. The history of FORTRAN I, II and III // History of Programming Languages.
  11. Porter Adams, Vicki (5 October 1981). "Капитан Грейс М. Хоппер: мать COBOL". InfoWorld. 3 (20): 33. ISSN 0199-6649.
  12. McCarthy, J.; Brayton, R.; Edwards, D.; Fox, P.; Hodes, L.; Luckham, D.; Maling, K.; Park, D.; Russell, S. (March 1960). "Руководство программиста LISP I" (PDF). Бостон, Массачусетс: Artificial Intelligence Group, M.I.T. Computation Center and Research Laboratory.
  13. Compilers Principles, Techniques, & Tools 2nd edition by Aho, Lam, Sethi, Ullman ISBN 0-321-48681-1
  14. (1952) «The Education of a Computer». Proceedings of the 1952 ACM National Meeting (Pittsburgh): 243-249. doi:10. 1145/609784.609818.
  15. (1952) «Compiling routines». Proceedings of the 1952 ACM National Meeting (Toronto): 1-5. doi:10.1145/800259.808980.
  16. Hoare, C.A.R. umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf Hints on Programming Language Design 27 (December 1973). Архивировано 10 октября 2022 года. (Это утверждение иногда ошибочно приписывают Edsger W. Dijkstra, который также участвовал в реализации первого компилятора ALGOL 60.)
  17. Revised(3) Report on the Algorithmic Language Scheme, (Dedicated to the Memory of ALGOL 60). Дата обращения: 20 октября 2009.
  18. "Recursive Functions of Symbolic Expressions and Their Computation by Machine", Communications of ACM, April 1960
  19. McCarthy, John. Lisp 1. 5 Programmers Manual / John McCarthy, Paul W. Abrahams, Daniel J. Edwards … [и др.]. — The MIT Press, 1965. — ISBN 9780262130110.
  20. "BCPL: инструмент для написания компиляторов и системного программирования". M. Richards, University Mathematical Laboratory Cambridge, England 1969
  21. BCPL: The Language and Its Compiler, M Richards, Cambridge University Press (первая публикация 31 декабря 1981)
  22. The BCPL Cintsys and Cintpos User Guide, M. Richards, 2017
  23. Corbató, F. J.; Vyssotsky, V. A. Introduction and Overview of the MULTICS System. 1965 Fall Joint Computer Conference. Multicians.org.
  24. Report II of the SHARE Advanced Language Development Committee, 25 June 1964
  25. Multicians.org "The Choice of PL/I" article, Editor /tom Van Vleck
  26. "PL/I As a Tool for System Programming", F.J. Corbato, Datamation 6 May 1969 issue