В информатике компилятор -компилятор или генератор компиляторов — это программный инструмент, который создает синтаксический анализатор , интерпретатор или компилятор из некоторой формы формального описания языка программирования и машины.
Наиболее распространенный тип компилятора-транслятора называется генератором синтаксического анализатора . [1] Он обрабатывает только синтаксический анализ .
Формальное описание языка обычно представляет собой грамматику, используемую в качестве входных данных для генератора парсера. Она часто напоминает форму Бэкуса–Наура (BNF), расширенную форму Бэкуса–Наура (EBNF) или имеет свой собственный синтаксис. Файлы грамматики описывают синтаксис целевого языка программирования сгенерированного компилятора и действия, которые следует выполнять в отношении его конкретных конструкций.
Исходный код для парсера языка программирования возвращается как выход генератора парсера. Затем этот исходный код может быть скомпилирован в парсер, который может быть как автономным, так и встроенным. Затем скомпилированный парсер принимает исходный код целевого языка программирования в качестве входных данных и выполняет действие или выводит абстрактное синтаксическое дерево (AST).
Генераторы парсеров не обрабатывают семантику AST или генерацию машинного кода для целевой машины. [2]
Метакомпилятор — это инструмент разработки программного обеспечения, используемый в основном для создания компиляторов , трансляторов и интерпретаторов для других языков программирования. [3] Входные данные для метакомпилятора — это компьютерная программа , написанная на специализированном метаязыке программирования, разработанном в основном для создания компиляторов. [3] [4] Язык, создаваемый компилятором, называется объектным языком. Минимальные входные данные, создающие компилятор, — это метапрограмма, определяющая грамматику объектного языка и семантические преобразования в объектную программу . [4] [5]
Типичный генератор парсера связывает исполняемый код с каждым из правил грамматики, которые должны быть выполнены, когда эти правила применяются парсером. Эти фрагменты кода иногда называют семантическими подпрограммами действий, поскольку они определяют семантику синтаксической структуры, которая анализируется парсером. В зависимости от типа парсера, который должен быть сгенерирован, эти подпрограммы могут строить дерево синтаксического анализа (или абстрактное синтаксическое дерево ) или генерировать исполняемый код напрямую.
Одной из самых ранних (1964) и удивительно мощных версий компиляторов-компиляторов является META II , которая принимала аналитическую грамматику с выходными средствами , создающими стековый машинный код, и могла компилировать свой собственный исходный код и другие языки.
Среди самых ранних программ оригинальных версий Unix , созданных в Bell Labs, была двухкомпонентная система lex и yacc , которая обычно использовалась для вывода кода языка программирования C , но имела гибкую систему вывода, которую можно было использовать для всего: от языков программирования до преобразования текстовых файлов. Их современные версии GNU — flex и bison .
Некоторые экспериментальные компиляторы-компиляторы принимают в качестве входных данных формальное описание семантики языка программирования, обычно с использованием денотационной семантики . Этот подход часто называют «компиляцией на основе семантики», и он был впервые предложен Питером Моссесом в 1978 году в Semantic Implementation System (SIS). [6] Однако и сгенерированный компилятор, и созданный им код были неэффективны во времени и пространстве. В настоящее время ни один производственный компилятор не построен таким образом, но исследования продолжаются.
Проект Production Quality Compiler-Compiler ( PQCC ) в Университете Карнеги-Меллона не формализует семантику, но имеет полуформальную структуру для описания машины.
Существует множество разновидностей компиляторов-компиляторов, включая восходящие генераторы машин переписывания (см. JBurg), используемые для разбиения синтаксических деревьев в соответствии с грамматикой переписывания для генерации кода, а также генераторы парсеров атрибутной грамматики (например, ANTLR можно использовать для одновременной проверки типов, распространения констант и многого другого на этапе синтаксического анализа).
Метакомпиляторы сокращают задачу написания компиляторов, автоматизируя аспекты, которые одинаковы независимо от языка объекта. Это делает возможным проектирование доменно-специфичных языков , которые соответствуют спецификации конкретной проблемы. Метакомпилятор снижает стоимость производства трансляторов для таких доменно-специфичных языков объектов до точки, где становится экономически целесообразным включить в решение проблемы проектирование доменно-специфичного языка . [4]
Поскольку метаязык метакомпилятора обычно представляет собой мощный язык обработки строк и символов, они часто находят широкое применение в приложениях общего назначения, включая создание широкого спектра других инструментов разработки и анализа программного обеспечения. [4] [7]
Помимо того, что метакомпилятор полезен для разработки предметно-ориентированных языков , он является ярким примером предметно-ориентированного языка, предназначенного для написания компиляторов.
Метакомпилятор — это метапрограмма , обычно написанная на собственном метаязыке или существующем языке программирования. Процесс компиляции самого себя метакомпилятором, написанным на собственном метаязыке, эквивалентен саморазмещающемуся компилятору . Наиболее распространенные компиляторы, написанные сегодня, являются саморазмещающимися компиляторами. Саморазмещаемость — это мощный инструмент многих метакомпиляторов, позволяющий легко расширять их собственный метаязык метапрограммирования. Особенность, которая отличает метакомпилятор от других компиляторов-компиляторов, заключается в том, что он принимает в качестве входных данных специализированный язык метапрограммирования , описывающий все аспекты работы компилятора. Метапрограмма, созданная метакомпилятором, является такой же полной программой, как и программа, написанная на C++ , BASIC или любом другом общем языке программирования . Метаязык метапрограммирования — это мощный атрибут, позволяющий упростить разработку языков программирования и других компьютерных инструментов. Процессоры командной строки, преобразование и анализ текстовых строк легко кодируются с использованием метаязыков метапрограммирования метакомпиляторов.
Полнофункциональный пакет разработки включает в себя компоновщик и библиотеку поддержки времени выполнения . Обычно для написания библиотеки поддержки требуется машинно-ориентированный язык программирования , такой как C или C++. Библиотека, состоящая из функций поддержки, необходимых для процесса компиляции, обычно дополняет полный пакет метакомпилятора.
В информатике префикс meta обычно используется для обозначения (его собственной категории) . Например, метаданные — это данные, которые описывают другие данные. Язык, который используется для описания других языков, является метаязыком . Meta может также означать на более высоком уровне абстракции . Метаязык работает на более высоком уровне абстракции для описания свойств языка. Форма Бэкуса–Наура (БНФ) — это формальный метаязык, первоначально использовавшийся для определения АЛГОЛа 60. БНФ — это слабый метаязык , поскольку он описывает только синтаксис и ничего не говорит о семантике или значении. Метапрограммирование — это написание компьютерных программ с возможностью рассматривать программы как свои данные. Метакомпилятор принимает в качестве входных данных метапрограмму, написанную на специализированном метаязыке (более высоком уровне абстракции), специально разработанном для целей метапрограммирования. [4] [5] Выходными данными является исполняемая объектная программа.
Можно провести аналогию: как компилятор C++ принимает в качестве входных данных программу на языке программирования C++ , так и метакомпилятор принимает в качестве входных данных программу на метаязыке метапрограммирования .
Многие сторонники языка Forth называют процесс создания новой реализации Forth метакомпиляцией и что он представляет собой метакомпилятор. Определение метакомпилятора в Forth следующее:
Это использование термина метакомпилятор Forth оспаривается в основной компьютерной науке. См. Forth (язык программирования) и История построения компиляторов . Фактический процесс компиляции Forth сам по себе является комбинацией Forth, являющегося саморасширяемым языком программирования , и иногда кросс-компиляции , давно устоявшейся терминологии в компьютерной науке. Метакомпиляторы являются общей системой написания компиляторов. Помимо того, что концепция метакомпилятора Forth неотличима от саморасширяемого и расширяемого языка. Фактический процесс действует на более низком уровне, определяя минимальное подмножество слов Forth , которое может использоваться для определения дополнительных слов Forth, затем из базового набора может быть определена полная реализация Forth. Это звучит как процесс самозагрузки. Проблема в том, что почти каждый компилятор языка общего назначения также соответствует описанию метакомпилятора Forth.
Просто замените X на любой распространенный язык, C, C++, Pascal , COBOL , Fortran , Ada , Modula-2 и т. д. И X будет метакомпилятором в соответствии с использованием метакомпилятора в Forth. Метакомпилятор работает на уровне абстракции выше компилятора, который он компилирует. Он работает на том же уровне (самостоятельно размещающий компилятор) только при компиляции самого себя. Нужно увидеть проблему с этим определением метакомпилятора. Его можно применить к большинству языков.
Однако, рассматривая концепцию программирования в Forth, добавление новых слов в словарь, расширение языка таким образом — это метапрограммирование. Именно это метапрограммирование в Forth делает его метакомпилятором.
Программирование на Forth — это добавление новых слов в язык. Изменение языка таким образом — это метапрограммирование . Forth — это метакомпилятор, потому что Forth — это язык, специально разработанный для метапрограммирования. Программирование на Forth — это расширение Forth путем добавления слов в словарь Forth, что создает новый диалект Forth . Forth — это специализированный метакомпилятор для диалектов языка Forth.
Разработка оригинального компилятора-компилятора была начата Тони Брукером и Дерриком Моррисом в 1959 году, а первоначальное тестирование началось в марте 1962 года. [8] Компилятор Brooker Morris Compiler (BMCC) использовался для создания компиляторов для нового компьютера Atlas в Манчестерском университете для нескольких языков: Mercury Autocode , Extended Mercury Autocode, Atlas Autocode , ALGOL 60 и ASA Fortran . Примерно в то же время смежная работа велась ET (Ned) Irons в Принстоне и Alick Glennie в Atomic Weapons Research Establishment в Олдермастоне, чья статья "Syntax Machine" (рассекреченная в 1977 году) вдохновила серию систем письменного перевода META, упомянутых ниже.
Ранняя история метакомпиляторов тесно связана с историей рабочей группы 1 SIG/PLAN по компиляторам, управляемым синтаксисом. Группа была основана в первую очередь усилиями Говарда Меткалфа в районе Лос-Анджелеса. [9] Осенью 1962 года Говард Меткалф разработал два интерпретатора, пишущих компиляторы. Один использовал метод анализа снизу вверх, основанный на методе, описанном Ледли и Уилсоном. [10] Другой использовал подход сверху вниз, основанный на работе Гленни, для генерации случайных английских предложений из контекстно-свободной грамматики. [11]
В то же время Вал Шорре описал две «метамашины», одну генеративную и одну аналитическую. Генеративная машина была реализована и производила случайные алгебраические выражения. Meta I, первый метакомпилятор, был реализован Шорре на IBM 1401 в Калифорнийском университете в Лос-Анджелесе в январе 1963 года. Его оригинальные интерпретаторы и метамашины были написаны непосредственно на псевдомашинном языке. META II , однако, был написан на метаязыке более высокого уровня, способном описывать свою собственную компиляцию в псевдомашинный язык. [12] [13] [14]
Ли Шмидт из Bolt, Beranek и Newman написал метакомпилятор в марте 1963 года, который использовал дисплей CRT на PDP-1 с разделением времени. [15] Этот компилятор создавал фактический машинный код, а не интерпретируемый код, и был частично скопирован с Meta I. [ требуется ссылка ]
Шорре создал Meta II из Meta I весной 1963 года. Статья об усовершенствованной системе метакомпилятора, представленная на конференции ACM в Филадельфии в 1964 году, является первой статьей о метакомпиляторе, доступной в качестве общего справочника. Синтаксис и метод реализации системы Шорре заложили основу для большинства последующих систем. Система была реализована на небольшом 1401 и использовалась для реализации небольшого языка типа ALGOL . [ необходима цитата ]
Сразу же появилось много подобных систем. [ необходима цитата ]
Роджер Ратман из AC Delco разработал и реализовал LOGIK, язык для моделирования логического проектирования, на IBM 7090 в январе 1964 года. [16] Этот компилятор использовал алгоритм, который создавал эффективный код для булевых выражений. [ необходима ссылка ]
Другая статья в трудах ACM 1964 года описывает Meta III, разработанный Шнайдером и Джонсоном в Калифорнийском университете в Лос-Анджелесе для IBM 7090. [17] Meta III представляет собой попытку создания эффективного машинного кода для большого класса языков. Meta III был полностью реализован на языке ассемблера. На Meta III были написаны два компилятора: CODOL, демонстрационный компилятор для написания компиляторов, и PUREGOL, диалект ALGOL 60. (Называть его ALGOL было чистой наглостью).
В конце 1964 года Ли Шмидт скопировал метакомпилятор EQGEN с PDP-1 на Beckman 420. EQGEN был языком генерации логических уравнений.
В 1964 году System Development Corporation начала масштабную работу по разработке метакомпиляторов. Эта работа включает в себя мощные метакомпиляторы Bookl и Book2, написанные на Lisp , которые обладают обширными возможностями поиска по дереву и резервного копирования. Meta 5 является результатом развития одной из систем Q-32 в SDC. [18] Система Meta 5 включает в себя резервное копирование входного потока и достаточно других возможностей для анализа любого контекстно-зависимого языка. Эта система была успешно выпущена для широкого круга пользователей и имела множество приложений для работы со строками, помимо компиляции. Она имеет множество сложных стеков push-down, возможностей настройки и тестирования атрибутов, а также механизмов вывода. То, что Meta 5 успешно транслирует программы JOVIAL в программы PL/I, демонстрирует ее мощь и гибкость.
Роберт МакКлур из Texas Instruments изобрел компилятор-компилятор под названием TMG (представлен в 1965 году). TMG использовался для создания ранних компиляторов для языков программирования, таких как B , PL/I и ALTRAN . Вместе с метакомпилятором Вэла Шорре он стал ранним источником вдохновения для последней главы книги Дональда Кнута « Искусство программирования» . [19]
Система LOT была разработана в 1966 году в Стэнфордском исследовательском институте и была смоделирована очень близко к Meta II. [20] Она имела новые специализированные конструкции, позволяющие ей генерировать компилятор, который, в свою очередь, мог компилировать подмножество PL/I. Эта система имела обширные возможности сбора статистики и использовалась для изучения характеристик анализа сверху вниз.
SIMPLE — это специализированная система трансляции, разработанная для помощи в написании препроцессоров для PL/I. SIMPLE, написанная на PL/I, состоит из трех компонентов: исполнительной части, синтаксического анализатора и семантического конструктора. [21]
Компилятор TREE-META был разработан в Стэнфордском исследовательском институте в Менло-Парке, Калифорния. Апрель 1968 г. Ранняя история метакомпиляторов хорошо документирована в руководстве TREE META. TREE META параллельна некоторым разработкам SDC. В отличие от более ранних метакомпиляторов, он разделил обработку семантики и обработку синтаксиса. Правила синтаксиса содержали операции построения дерева , которые объединяли распознанные элементы языка с узлами дерева. Затем представление древовидной структуры входных данных обрабатывалось простой формой правил неразбора. Правила неразбора использовали распознавание узлов и проверку атрибутов, которые при сопоставлении приводили к выполнению соответствующего действия. Кроме того, подобный элемент дерева также можно было проверить в правиле неразбора. Правила неразбора также были рекурсивным языком, способным вызывать правила неразбора, передавая элементы дерева до того, как выполнялось действие правила неразбора.
Концепция метамашины, изначально предложенная Гленни, настолько проста, что было разработано три версии оборудования, и одна из них была фактически реализована. Последняя в Университете Вашингтона в Сент-Луисе. Эта машина была построена из макромодульных компонентов и имеет в качестве инструкций коды, описанные Шорре.
CWIC (Compiler for Writing and Implementing Compilers) — последний известный метакомпилятор Шорре. Он был разработан в Systems Development Corporation Эрвином Буком, Дьюи Валом Шорре и Стивеном Дж. Шерманом. Благодаря полной мощи (lisp 2) алгоритмы оптимизации языка обработки списков могли работать с сгенерированными синтаксисом списками и деревьями до генерации кода. В CWIC также была встроена таблица символов.
С возрождением предметно-ориентированных языков и потребностью в генераторах синтаксических анализаторов, которые просты в использовании, понимании и обслуживании, метакомпиляторы становятся ценным инструментом для сложных проектов по разработке программного обеспечения.
Другие примеры генераторов парсеров в духе yacc: ANTLR , Coco/R , [22] CUP, [ требуется цитата ] GNU Bison , Eli, [23] FSL, [ требуется цитата ] SableCC , SID (Syntax Improving Device), [24] и JavaCC . Хотя генераторы чистых парсеров полезны, они решают только часть проблемы парсинга при построении компилятора. Инструменты с более широкой областью применения, такие как PQCC , Coco/R и DMS Software Reengineering Toolkit, обеспечивают значительную поддержку для более сложных действий после парсинга, таких как семантический анализ, оптимизация кода и генерация.
Самые ранние метакомпиляторы Шорре, META I и META II, были разработаны Д. Валом Шорре в Калифорнийском университете в Лос-Анджелесе. Затем последовали другие метакомпиляторы на основе Шорре. Каждый из них добавлял улучшения в анализ языка и/или генерацию кода.
В программировании принято использовать название языка программирования для обозначения как компилятора, так и языка программирования, контекст различает значение. Программа на C++ компилируется с помощью компилятора C++. Это также применимо в следующем. Например, META II — это и компилятор, и язык.
Метаязыки в линейке метакомпиляторов Шорре представляют собой функциональные языки программирования, использующие грамматический анализ сверху вниз, синтаксические уравнения со встроенными конструкциями преобразования выходных данных.
Синтаксическое уравнение:
<имя> = <тело>;
— это скомпилированная тестовая функция, возвращающая success или failure . <name> — это имя функции. <body> — это форма логического выражения, состоящая из тестов, которые могут быть сгруппированы, иметь альтернативы и выводить продукции. Тест похож на bool в других языках, success — true , а failure — false .
Аналитическое определение языка программирования сверху вниз является естественным. Например, программа может быть определена как:
программа = $декларация;
Определение программы как последовательности из нуля или более объявлений.
В языках Schorre META X есть управляющее правило. Правило программы выше является примером управляющего правила. Правило программы является тестовой функцией, которая вызывает объявление, тестовое правило, которое возвращает успех или неудачу . Оператор цикла $ многократно вызывает объявление, пока не будет возвращена неудача . Оператор $ всегда успешен, даже если объявлений нет. Вышеприведенная программа всегда будет возвращать успех. (В CWIC длинный сбой может обойти объявление. Длинный сбой является частью системы обратного отслеживания CWIC)
Наборы символов этих ранних компиляторов были ограничены. Символ / использовался для альтернативного (или) оператора. «A или B» записывается как A / B. Скобки ( ) используются для группировки.
А (Б/В)
Описывает конструкцию A, за которой следует B или C. Как логическое выражение это будет
А и (Б или В)
Последовательность XY подразумевает значение X и Y. ( ) — это группировка и / оператор or . Порядок оценки всегда слева направо, поскольку последовательность входных символов определяется порядком тестов.
Для ясности используются специальные операторные слова, первым символом которых является «.». .EMPTY используется в качестве последней альтернативы, когда предыдущая альтернатива не требуется.
X (A / B / .ПУСТО)
Указывает, что за X необязательно следует A или B. Это специфическая характеристика этих метаязыков как языков программирования. Возврат к предыдущему варианту исключается выше. Другие системы конструкторов компиляторов могли объявить три возможные последовательности и оставить это на усмотрение синтаксического анализатора.
Характеристики метаязыков метапрограммирования, описанные выше, являются общими для всех метакомпиляторов Шорре и производных от них.
META I был вручную скомпилированным метакомпилятором, использовавшимся для компиляции META II. О META I известно немного, за исключением того, что первоначальная компиляция META II производила почти идентичный код, что и вручную закодированный компилятор META I.
Каждое правило может состоять из тестов, операторов и выходных производств. Правило пытается сопоставить некоторую часть потока исходных символов входной программы, возвращая успех или неудачу. При успехе ввод продвигается по совпавшим символам. При неудаче ввод не продвигается.
Выходные продукты создавали форму ассемблерного кода непосредственно из синтаксического правила.
TREE-META представила операторы построения дерева : < node_name > и [ < number > ], перемещающие выходные производственные преобразования в неразобранные правила. Операторы построения дерева использовались в правилах грамматики, напрямую преобразуя входные данные в абстрактное синтаксическое дерево . Правила неразбора также являются тестовыми функциями, которые соответствуют шаблонам деревьев. Правила неразбора вызываются из правила грамматики, когда абстрактное синтаксическое дерево должно быть преобразовано в выходной код. Построение абстрактного синтаксического дерева и правил неразбора позволяло выполнять локальные оптимизации путем анализа дерева разбора.
Перемещение выходных производств в правила unparse сделало четкое разделение анализа грамматики и производства кода. Это сделало программирование более простым для чтения и понимания.
В 1968–1970 годах Эрвин Бук, Дьюи Вал Шорре и Стивен Дж. Шерман разработали CWIC. [4] (Компилятор для написания и реализации компиляторов) в Центре истории информационных технологий Института Чарльза Бэббиджа корпорации System Development Corporation (вставка 12, папка 21),
CWIC — это система разработки компиляторов, состоящая из трех специализированных, предметно-ориентированных языков, каждый из которых предназначен для описания определенных аспектов перевода в прямолинейной манере. Язык синтаксиса используется для описания распознавания исходного текста и построения из него промежуточной древовидной структуры. Язык генератора используется для описания преобразования дерева в соответствующий объектный язык.
Синтаксис языка следует предыдущей линейке метакомпиляторов Dewey Val Schorre. Он больше всего напоминает TREE-META, имея операторы построения деревьев в синтаксическом языке. Правила unparse TREE-META расширены для работы с объектно-ориентированным генераторным языком на основе LISP 2 .
CWIC включает три языка:
Generators Language имел семантику, похожую на Lisp . Дерево разбора рассматривалось как рекурсивный список. Общая форма функции Generator Language:
имя-функции(первое-правило_разбора) => первый-генератор_кода_производства (second-unparse_rule) => second-production_code_generator (третье-правило_разбора) => третий_генератор_кода_производства ...
Код для обработки данного дерева включал функции языка программирования общего назначения, а также форму: <stuff>, которая выдавала бы (stuff) в выходной файл. Вызов генератора может использоваться в unparse_rule. Генератору передается элемент шаблона unparse_rule, в который он помещен, и его возвращаемые значения перечислены в (). Например:
expr_gen(ADD[expr_gen(x),expr_gen(y)]) => <АР + (х*16)+у;> релизрег(y); вернуть х; (SUB[expr_gen(x),expr_gen(y)])=> <СР + (х*16)+у;> релизрег(y); вернуть х; (MUL[expr_gen(x),expr_gen(y)])=> . . . (x)=> r1 = getreg(); нагрузка(r1, x); вернуть r1;...
То есть, если дерево разбора выглядит как (ADD[<something1>,<something2>]), expr_gen(x) будет вызвано с <something1> и вернет x. Переменная в правиле unparse является локальной переменной, которая может использоваться в production_code_generator. expr_gen(y) вызывается с <something2> и возвращает y. Вот вызов генератора в правиле unparse, которому передается элемент в позиции, которую он занимает. Надеемся, в приведенном выше x и y будут регистрами при возврате. Последнее преобразование предназначено для загрузки атомарного объекта в регистр и возврата регистра. Первое производство будет использоваться для генерации инструкции 360 "AR" (Add Register) с соответствующими значениями в общих регистрах. Приведенный выше пример является только частью генератора. Каждое выражение генератора вычисляется в значение, которое затем может быть дополнительно обработано. Последнее преобразование можно было бы также записать как:
(x)=> вернуть загрузку(getreg(), x);
В этом случае load возвращает свой первый параметр — регистр, возвращаемый getreg(). Функции load и getreg — это другие генераторы CWIC.
От авторов CWIC:
«Метакомпилятор помогает задаче построения компилятора, автоматизируя его нетворческие аспекты, те аспекты, которые одинаковы независимо от языка, который созданный компилятор должен транслировать. Это делает возможным проектирование языков, которые соответствуют спецификации конкретной проблемы. Это снижает стоимость производства процессоров для таких языков до точки, когда становится экономически целесообразным начинать решение проблемы с проектирования языка». [4]
{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)