Войти
В информатике, компилятор-компилятор или генератор компилятора - это инструмент программирования, который создает синтаксический анализатор, интерпретатор или компилятор из некоторой формы формального описания языка программирования и машина.
Наиболее распространенный тип компилятора-компилятора более точно называется генератором синтаксического анализатора и обрабатывает только синтаксический анализ: его входные данные - это грамматика, обычно записываемая в форма Бэкуса – Наура (BNF) или расширенная форма Бэкуса – Наура (EBNF), которая определяет синтаксис языка программирования; и его вывод - исходный код парсера для языка программирования. Генераторы парсеров не обрабатывают семантику языка программирования или генерацию машинного кода для целевой машины.
A метакомпилятор - это инструмент разработки программного обеспечения, используемый в основном в построение компиляторов, переводчиков и интерпретаторов для других языков программирования. Входными данными для метакомпилятора является компьютерная программа, написанная на специализированном метаязыке программирования , разработанном в основном для создания компиляторов. Язык созданного компилятора называется объектным языком. Минимальный ввод, производимый компилятором, - это метапрограмма, определяющая объектный язык грамматику и семантические преобразования в объектную программу .
Типичный генератор парсера связывает исполняемый код с каждым из правил грамматики, которые должны выполняться, когда эти правила применяются парсер. Эти фрагменты кода иногда называют подпрограммами семантических действий, поскольку они определяют семантику синтаксической структуры, которая анализируется анализатором. В зависимости от типа синтаксического анализатора, который должен быть сгенерирован, эти подпрограммы могут создавать дерево синтаксического анализа (или абстрактное синтаксическое дерево ) или напрямую генерировать исполняемый код.
Одной из первых (1964 г.), удивительно мощных версий компиляторов-компиляторов является META II, в которой была принята аналитическая грамматика со средствами вывода , которые производят стековую машину код и может компилировать собственный исходный код и другие языки.
Среди самых ранних программ исходных версий Unix, собираемых в Bell Labs, была двухчастная lex и yacc, которая обычно использовалась для вывода кода языка программирования C, но имела гибкую систему вывода, которую можно было использовать для всего, от языков программирования до преобразования текстовых файлов. Их современные версии GNU - это flex и bison.
. Некоторые экспериментальные компиляторы-компиляторы принимают в качестве входных данных формальное описание семантики языка программирования, обычно используя денотационную семантику. Этот подход часто называют «компиляцией на основе семантики», и он был впервые предложен Питером Моссесом «Система семантической реализации (SIS)» в 1978 году. Однако как сгенерированный компилятор, так и созданный им код были неэффективными по времени и Космос. В настоящее время производственные компиляторы не создаются таким образом, но исследования продолжаются.
Проект компилятора-компилятора производственного качества (PQCC ) в Университете Карнеги-Меллона не формализует семантику, но имеет полуформальную структуру для описания машины.
Компиляторы-компиляторы существуют во многих вариантах, включая восходящие машинные генераторы перезаписи (см. JBurg ), используемые для мозаичного размещения синтаксических деревьев в соответствии с грамматикой перезаписи для генерации кода, и атрибут генераторы синтаксического анализатора грамматики (например, ANTLR можно использовать для одновременной проверки типов, распространения констант и многого другого на этапе синтаксического анализа).
Метакомпиляторы уменьшают задачу написания компиляторов, автоматизируя аспекты, которые одинаковы независимо от объектного языка. Это делает возможным разработку предметно-ориентированных языков, которые подходят для спецификации конкретной проблемы. Метакомпилятор снижает стоимость производства переводчиков для таких предметных объектных языков, зависящих от предметной области, до такой степени, что становится экономически целесообразным включить в решение проблемы предметно-ориентированный язык дизайн.
метаязык метакомпилятора - это мощный язык обработки строк и символов, который также полезен для создания широкого спектра других инструментов разработки и анализа программного обеспечения.
Помимо того, что он полезен для разработки предметно-ориентированного языка, метакомпилятор является ярким примером предметно-ориентированного языка, разработанного для области написания компиляторов.
Метакомпилятор - это метапрограмма, обычно написанная на собственном метаязыке или на существующем языке компьютерного программирования. Сам процесс компиляции метакомпилятора, написанного на его собственном метаязыке, эквивалентен компилятору с собственным хостом. Наиболее распространенные компиляторы, написанные сегодня, - это компиляторы с собственным хостингом. Самостоятельный хостинг - это мощный инструмент многих метакомпиляторов, позволяющий легко расширять собственный метаязык метапрограммирования. Особенность, которая отделяет метакомпилятор от других компиляторов компилятора, заключается в том, что он принимает в качестве входных данных специализированный язык метапрограммирования, который описывает все аспекты работы компилятора. Метапрограмма, созданная метакомпилятором, представляет собой такую же полную программу, как программа, написанная на C ++, BASIC или любом другом общем языке программирования. метапрограммирование метаязык - мощный атрибут, позволяющий упростить разработку языков компьютерного программирования и других компьютерных инструментов. Процессоры командной строки, преобразование и анализ текстовых строк легко кодируются с использованием метапрограммирования метаязыков метакомпиляторов.
Полнофункциональный пакет разработки включает компоновщик и среду выполнения поддержку библиотеку. Обычно для написания библиотеки поддержки требуется машинно-ориентированный язык системного программирования, такой как C или C ++. Библиотека, состоящая из функций поддержки, необходимых для процесса компиляции, обычно завершает полный пакет метакомпилятора.
В информатике префикс мета обычно используется для обозначения примерно (его собственная категория). Например, метаданные - это данные, которые описывают другие данные. Язык, который используется для описания других языков, - это метаязык. Мета также может означать на более высоком уровне абстракции. метаязык работает на более высоком уровне абстракции, чтобы описать свойства языка. Форма Бэкуса-Наура (BNF) - это формальный метаязык, первоначально использовавшийся для определения АЛГОЛ 60. BNF - это слабый метаязык , поскольку он описывает только синтаксис и ничего не говорит о семантике или значении. Метапрограммирование - это написание компьютерных программ с возможностью обработки программ как своих данных. Метакомпилятор принимает в качестве входных данных метапрограмму, написанную на специализированных метаязыках (абстракция более высокого уровня), специально разработанных для целей метапрограммирования. На выходе получается исполняемая объектная программа.
Можно провести аналогию: поскольку компилятор C ++ принимает в качестве входных данных программу на языке программирования C ++, метакомпилятор принимает в качестве входных данных программу метапрограммирования метаязыка.
Многие сторонники языка Forth называют процесс создания новой реализации Forth мета-компиляцией, и что он составляет метакомпилятор. Четвертое определение метакомпилятора:
Это четвертое использование термина метакомпилятор оспаривается в основной информатике. См. Forth (язык программирования) и История создания компилятора. Фактический процесс компиляции Forth представляет собой комбинацию Forth, являющегося self-hosting языком расширяемого программирования, и иногда кросс-компиляцией, давно установившейся терминологией в компьютерных науках.. Метакомпиляторы - это общая система написания компиляторов. Кроме того, концепция метакомпилятора Forth неотличима от самообслуживания и расширяемого языка. Фактический процесс действует на более низком уровне, определяя минимальное подмножество четвертых слов, которые можно использовать для определения дополнительных четвертых слов. Затем можно определить полную реализацию Forth из базового набора. Это похоже на процесс начальной загрузки. Проблема в том, что почти каждый компилятор языков общего назначения также подходит под описание метакомпилятора Forth.
Просто замените X любым распространенным языком, C, C ++, Pascal, COBOL, Fortran, Ada, Modula-2 и т.д. И X будет метакомпилятором в соответствии с использованием Forth метакомпилятора. Метакомпилятор работает на уровне абстракции выше компилятора, который он компилирует. Он работает только на том же уровне (компилятор с собственным хостингом) при компиляции. Необходимо увидеть проблему с этим определением метакомпилятора. Его можно применить практически к любому языку.
Однако, при изучении концепции программирования в Forth, добавление новых слов в словарь, расширение языка таким образом - это метапрограммирование. Именно метапрограммирование в Forth делает его метакомпилятором.
Программирование на форте - это добавление новых слов в язык. Изменение языка таким образом - это метапрограммирование. Forth - это метакомпилятор, потому что Forth - это язык, специально разработанный для метапрограммирования. Программирование на Forth расширяет Forth, добавление слов в словарь Forth создает новый Forth диалект. Forth - это специализированный метакомпилятор для диалектов языка Forth.
Первый компилятор-компилятор, использующий это имя, был написан Тони Брукером в 1960 году и использовался для создания компиляторов для Атласа компьютер в Манчестерском университете, включая компилятор Atlas Autocode.
Ранняя история метакомпиляторов тесно связана с историей Рабочей группы 1 SIG / PLAN по Компиляторы, управляемые синтаксисом. Группа была основана прежде всего благодаря усилиям Говарда Меткалфа в районе Лос-Анджелеса. Осенью 1962 года Ховард Меткалф разработал два интерпретатора для написания компиляторов. Один использовал метод анализа снизу вверх, основанный на методе, описанном Ледли и Уилсоном. Другой использовал подход сверху вниз, основанный на работе Гленни, для генерации случайных английских предложений из контекстно-свободной грамматики.
В то же время Вал Шорре описал две «мета-машины». Один генеративный и один аналитический. Генеративная машина была реализована и произвела случайные алгебраические выражения. Meta I, первый метакомпилятор, был реализован Шорре на IBM 1401 в Калифорнийском университете в январе 1963 года. Его оригинальные интерпретаторы и метамашины были написаны непосредственно на псевдомашинном языке. META II, однако, была написана на метаязыке более высокого уровня, способном описывать собственную компиляцию на псевдомашинном языке.
Ли Шмидт из Болта, Беранек и Ньюман написали метакомпилятор. в марте 1963 года, который использовал ЭЛТ-дисплей на PDP-1 с разделением времени. Этот компилятор создавал реальный машинный код, а не интерпретирующий код, и был частично загружен из Meta I.
Шорре загрузил Meta II из Meta I весной 1963 года. Доклад об усовершенствованной системе метакомпилятора, представленный на конференции ACM в Филадельфии в 1964 году. конференция - это первая статья по метакомпилятору, доступная в качестве общей справочной информации. Синтаксис и техника реализации системы Шорре заложили основу для большинства последующих систем. Система была реализована на маленьком 1401 и использовалась для реализации небольшого ALGOL -подобного языка.
Немедленно последовало множество подобных систем.
Роджер Рутман из AC Delco разработал и внедрил LOGIK, язык для моделирования логического проектирования, на IBM 7090 в январе 1964 года. Этот компилятор использовал алгоритм, который производил эффективный код для логических выражений.
Еще одна статья 1964 года. В протоколе ACM описывается Meta III, разработанный Шнайдером и Джонсоном в UCLA для IBM 7090. Meta III представляет собой попытку создать эффективный машинный код для большого класса языков. Meta III была полностью реализована на ассемблере. Два компилятора были написаны на Meta III: CODOL, демонстрационный компилятор для написания компиляторов, и PUREGOL, диалект АЛГОЛА 60 (называть его АЛГОЛОМ было чистой злостью).
В конце 1964 года Ли Шмидт загрузил метакомпилятор EQGEN с PDP-1 на Beckman 420. EQGEN был языком генерации логических уравнений.
В 1964 году System Development Corporation начала серьезную работу по разработке метакомпиляторов. Это усилие включает мощные метакомпиляторы, Bookl и Book2, написанные на Lisp, которые обладают обширными возможностями поиска по дереву и резервного копирования. Результатом одной из систем Q-32 в SDC является Meta 5. Система Meta 5 включает резервное копирование входного потока и достаточно других средств для анализа любого контекстно-зависимого языка. Эта система была успешно выпущена для широкого круга пользователей и имела множество приложений для обработки строк, помимо компиляции. В нем есть много сложных «выталкивающих» стеков, средств настройки и тестирования атрибутов, а также механизмов вывода. То, что Meta 5 успешно переводит программы JOVIAL в программы PL / I, демонстрирует его мощь и гибкость.
Роберт МакКлюр из Texas Instruments изобрел компилятор-компилятор под названием TMG (представлен в 1965 году). TMG использовался для создания ранних компиляторов для таких языков программирования, как B, PL / I и ALTRAN. Вместе с метакомпилятором Вэла Шорра, он стал одним из первых источников вдохновения для последней главы книги Дональда Кнута Искусство компьютерного программирования.
Система LOT была разработана в 1966 году в Стэнфордском исследовательском институте и был очень точно смоделирован после Meta II. В нем были новые конструкции специального назначения, позволяющие создать компилятор, который, в свою очередь, мог скомпилировать подмножество PL / I. Эта система имела широкие возможности для сбора статистики и использовалась для изучения характеристик нисходящего анализа.
SIMPLE - это специализированная система транслятора, предназначенная для помощи в написании препроцессоров для PL / I. SIMPLE, написанная на PL / I, состоит из трех компонентов: исполнительного модуля, синтаксического анализатора и семантического конструктора..
Компилятор TREE-META был разработан в Стэнфордском исследовательском институте в Менло-Парке, Калифорния. Апрель 1968. Ранняя история метакомпилятора хорошо задокументирована в руководстве TREE META. TREE META шла параллельно с некоторыми разработками SDC. В отличие от более ранних метакомпиляторов, он отделял обработку семантики от обработки синтаксиса. Правила синтаксиса содержали операции построения дерева, которые объединяли распознанные языковые элементы с узлами дерева. Затем представление входных данных в виде древовидной структуры было обработано простой формой неанализируемых правил. В правилах неразборчивого анализа использовалось распознавание узлов и тестирование атрибутов, которые при сопоставлении приводили к выполнению связанного действия. Вдобавок подобный элемент дерева также может быть протестирован в неанализируемом правиле. Непроанализированные правила также были рекурсивным языком, способным вызывать непроанализированные правила, передавая элементы дерева до того, как было выполнено действие неанализируемого правила.
Концепция метармашины, первоначально выдвинутая Гленни, настолько проста, что были разработаны три версии аппаратного обеспечения и одна фактически реализована. Последний в Вашингтонском университете в Сент-Луисе. Эта машина была построена из макромодульных компонентов и имеет коды, описанные Шорре.
CWIC (компилятор для написания и реализации компиляторов) - последний известный метакомпилятор Шорре. Он был разработан в Systems Development Corporation Эрвином Буком, Дьюи Валом Шорром и Стивеном Дж. Шерманом. Используя всю мощь (lisp 2) языка обработки списков, алгоритмы оптимизации могли работать с синтаксически сгенерированными списками и деревьями до генерации кода. CWIC также имеет встроенную в язык таблицу символов.
С возрождением предметно-ориентированных языков и потребностью в генераторах парсеров, которые просты в использовании, понятны и просты в обслуживании, метакомпиляторы становятся ценным инструментом для сложных проектов разработки программного обеспечения.
Другими примерами генераторов парсеров в духе yacc являются ANTLR, Coco / R, CUP, GNU Bison, Eli, FSL, SableCC, SID (устройство для улучшения синтаксиса) и JavaCC. Хотя генераторы чистого синтаксического анализатора полезны, они решают только часть синтаксического анализа проблемы построения компилятора. Инструменты с более широким охватом, такие как PQCC, Coco / R и DMS Software Reengineering Toolkit, обеспечивают значительную поддержку для более сложных операций пост-синтаксического анализа, таких как семантический анализ, оптимизация и генерация кода.
Самые ранние метакомпиляторы Шорре, META I и META II, были разработаны Д. Вэл Шорре из Калифорнийского университета в Лос-Анджелесе. Затем последовали и другие метакомпиляторы на основе Шорре. Каждый из них добавляет улучшения в анализ языка и / или генерацию кода.
В программировании имя языка программирования обычно используется для обозначения как компилятора, так и языка программирования, причем контекст определяет значение. Программа на C ++ компилируется с помощью компилятора C ++. Это также относится к следующему. Например, META II - это и компилятор, и язык.
Метаязыки в линейке метакомпиляторов Schorre - это функциональные языки программирования, которые используют нисходящие грамматические анализирующие уравнения синтаксиса, имеющие встроенные конструкции преобразования вывода.
Синтаксическое уравнение:
= ;
- это скомпилированная тестовая функция, возвращающая успех или неудачу.
Определение языка программирования аналитически сверху вниз естественно. Например, программа может быть определена как:
program = $ декларация;
Определение программы как последовательности из нуля или более деклараций.
В языках Schorre META X есть управляющее правило. Приведенное выше правило программы является примером правила вождения. Правило программы - это тестовая функция, которая вызывает объявление, тестовое правило, которое возвращает успех или неудачу. Оператор $ loop многократно вызывает объявление, пока не будет возвращена ошибка. Оператор $ всегда успешен, даже если нет объявления. Вышеупомянутая программа всегда возвращала успех. (В CWIC длинный сбой может обходить объявление. Длительный сбой является частью системы обратного отслеживания CWIC)
Наборы символов этих ранних компиляторов были ограничены. Символ / использовался для оператора альтернативы (или). «A или B» записывается как A / B. Круглые скобки () используются для группировки.
A (B / C)
Описывает конструкцию A, за которой следует B или C. В качестве логического выражения это будет
A и (B или C)
Последовательность XY имеет подразумеваемые значения X и Y. () - группирующие, а / - оператор или . Порядок оценки всегда слева направо, так как последовательность входных символов определяется порядком проведения тестов.
Специальные операторные слова, первый символ которых - "." используются для ясности..EMPTY используется в качестве последнего альтернативного варианта, когда нет необходимости в предыдущем альтернативном варианте.
X (A / B /.EMPTY)
Указывает, что за X необязательно следует A или B. Это особая характеристика этих метаязыков как языков программирования. Вышесказанное позволяет избежать обратного отслеживания. Другие системы конструкторов компиляторов могли объявить три возможные последовательности и предоставить синтаксическому анализатору решать их.
Характеристики метапрограммных метаязыков, описанных выше, являются общими для всех метакомпиляторов Schorre и производных от них.
META I был вручную скомпилированным метакомпилятором, который использовался для компиляции META II. Мало что известно о META I, за исключением того, что первоначальная компиляция META II произвела почти идентичный код с кодом компилятора META I, написанного вручную.
Каждое правило необязательно состоит из тестов, операторов и результатов вывода. Правило соответствует некоторой части исходного потока символов входной программы, возвращающей успех или неудачу. В случае успеха ввод продвигается по совпадающим символам. В случае сбоя вход не продвигается.
Продукция вывода произвела форму ассемблерного кода непосредственно из правила синтаксиса.
TREE-META представила операторы построения дерева :
Перенос результатов вывода на неразборчивые правила сделал четкое разделение анализа грамматики и создания кода. Это сделало программирование более простым для чтения и понимания.
В 1968-1970 годах Эрвин Бук, Дьюи Вэл Шорре и Стивен Дж. Шерман разработали CWIC. (Компилятор для написания и реализации компиляторов) в System Development Corporation Центр истории информационных технологий Института Чарльза Бэббиджа (вставка 12, папка 21),
CWIC - это система разработки компиляторов, состоящая из трех специализированные, зависящие от предметной области, языки, каждый из которых предназначен для прямого описания определенных аспектов перевода. Язык синтаксиса используется для описания распознавания исходного текста и построения из него промежуточной древовидной структуры. Язык генератора используется для описания преобразования дерева в соответствующий объектный язык.
Язык синтаксиса соответствует предыдущей линии метакомпиляторов Дьюи Вэл Шорре. Он больше всего напоминает TREE-META с операторами построения tree на языке синтаксиса. Неразборчивые правила TREE-META расширены для работы с языком генератора на основе объектов на основе LISP 2.
CWIC включает три языка:
Язык генераторов имел семантику, аналогичную Lisp. Дерево синтаксического анализа рассматривалось как рекурсивный список. Общая форма функции языка генератора:
имя-функции (first-unparse_rule) =>first-production_code_generator (second-unparse_rule) =>second-production_code_generator (third-unparse_rule) =>третий-production_code_generator...
Код для обработки заданного дерева включал в себя функции языка программирования общего назначения, а также форму:
expr_gen (ADD [expr_gen (x), expr_gen (y)]) =>releasereg (y); вернуть x; (SUB [expr_gen (x), expr_gen (y)]) => releasereg (y); вернуть x; (MUL [expr_gen (x), expr_gen (y)]) =>... (х) =>r1 = getreg (); нагрузка (r1, x); return r1;...
То есть, если дерево синтаксического анализа выглядит как (ADD [
(x) =>return load (getreg (), x);
В этом случае load возвращает свой первый параметр, регистр, возвращаемый функцией getreg (). функции load и getreg - другие генераторы CWIC.
От авторов CWIC:
"Метакомпилятор помогает задаче создания компилятора, автоматизируя его не творческие аспекты, те аспекты, которые одинаковы независимо от языка, на который производимый компилятор должен переводить. Это делает возможным создание языков, соответствующих спецификации конкретная проблема. Это снижает стоимость производства процессоров для таких языков до такой степени, что становится экономически целесообразным начать решение проблемы с языкового дизайна ».
