Эволюция компиляторов и счетчиков

Название «компилятор», похоже, было придумано в 1952 году Грейс Хоппер. Именно примерно в это время впервые реализуется то, что можно считать парсером. Однако компилятор Грейс Хоппер не имеет ничего общего с тем, что сейчас называют компилятором: инструментом, который конвертирует один язык в другой, как правило, более низкого уровня. Ассемблеры существовали до компиляторов, но ассемблер - это лишь текстовое представление двоичного кода, перевод осуществляется с простой таблицей совпадений .

Мета-круговой компилятор (1951)

Коррадо Бём в диссертации описывает программу, которая переводит компактный язык назначения и выражения в машинный код. Мета-циркуляр означает, что компилятор написан на языке, который он компилирует.

Автокод (1952)

Это набор макро-инструкций, которые переводятся на машинный язык. За этим инструментом нет особой техники.

IT (1956)

Технологический институт Карнеги обнародовал компилятор IT, работающий на IBM 650. Язык имеет арифметические выражения, но не предшествует операторам.

Иерархия Хомского и неконтактная грамматика (1956)

В монографии, опубликованной в 1956 году, Хомский представляет структуру настоящего составителя :

В то же время он изобретает неконтактный грамматический контекст: он состоит из правил, где x определяется группой элементов, и x не зависит от контекста, в котором он появляется. Такая грамматика легко пишется в BNF, формате, который появится позже .

Фортран (1957)

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

Лисп (1958)

Первый компилятор Lisp не более продуман, чем компилятор Fortran, так как программист сам должен добавить скобки, чтобы указать ему, как трансформировать код.

БНФ (1958)

Джон Бэкус и Питер Наур используют оригинальную нотацию, которую они будут использовать для описания грамматики языка Алгол 58: Форма Бэкус-Наур, или BNF.

Пример грамматики BNF:

<ifelse> ::= <if> [ { else <if> } ]

<if> ::= if "(" <condition> ")" ( <instruction> | "{" { <insttuction> } "}" )

Прецедент (1959)

Теоретическая реализация предрасположенности операторов демонстрируется Самуэльсоном и Бауэром с помощью стека.

Алгол (1960)

Первый структурированный язык, основанный на грамматике, описанной в BNF. Описание парсера ALGOL публикует Ned Irons.
Algo 60 имеет блоки инструкций и поддерживает рекурсивность, тогда новые концепции. Он также содержит динамические таблицы, поэтому C и Паскаль были регрессиями в этом плане.

Рекурсивный парсер вниз (1961)

Питер Лукас и Нэд Айронс оба описывают рекурсивный потомственный парсер. Оно состоит из первоначального правила, которое ссылается на другие правила и таким образом интерпретирует язык, следуя иерархии их компостирования. Кроме того, правило может ссылаться на себя и быть рекурсивным, как это имеет место в описании BNF выше, когда инструкция, являющаяся частью правила «if», также является правилом «if».

Алгоритм Шаттинга-Ярда Дейкштры (1961)

Из артитметического выражения с скобками или нет (и, следовательно, по распознаванию прецедента) этот алгоритм выдает абстрактное синтаксическое дерево. Он использует стек и производит неверную (так называемую польскую) нотацию или оператор следует за парой операндов с операндами с более высоким приоритетом в конце строки.

Парсер ЛР (1965) и ЛАЛР (1971)

Придуманный Дональдом Кнутом, ЛР-парнер читает неконтактную грамматику левой части в правую.

Можно получить SLR (Simple Left-Right), изобретённый в 1969 году Фрэнком ДеРемером, или LALR (Look-Ahead Left-Right), придуманный тем же в 1971 году. Во втором случае пытается совпадение правила грамматики с инструкцией исходного кода и в случае неудачи возвращается к первому элементу и пробует альтернативу. Сообщение об ошибке выдается, когда альтернативы не соответствуют.
LR (k) или k означает количество «lookaheads», уровней, которые анализатор исследует в исходном коде, прежде чем принять решение о применении правила к инструкции.

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

Парсер LL (1968) и LR

Принцип LL, предложенный Льюисом и Стёрнсом, применяется к грамматике, предназначенной для анализа упрощенным парнером и написания вручную.

Анализатор LL анализирует инструкцию слева и справа и сверху вниз, он строит представление инструкции, заменяя каждый узел группой узлов, которые его определяют.

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

Алгоритм CYK (1960 +

)

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

Парсер Эрли (1970)

Джей Эрли в 1968 году изобрел алгоритм, способный анализировать большинство неконтактных грамм, которые он упростил в 1970 году. Однако он был медленным на исполнение и другие приемы навязывались популярным составителям. Более быстрая версия была найдена позже.

Парсер ГЛР (1974)

Парсер GLR (Generalized LR) - расширение LR для двусмысленных грамматик, подобных грамматике C. Алгоритм, реализующий его, был описан Бернардом Лангом и улучшен с 1974 года.
Языки C, C++ и т. Д. управляются версией этого алгоритма большинством компиляторов.

Якк (1975)

На основе LALR это первый автоматический генератор парсера, снятый Стивеном Джонсоном на ATT для Unix.
Компилятор C переключается с простого рекурсивного парсера вниз на LALR. Но Yacc будет доступен публике только в 1979 году.

Yacc был использован GCC, затем для Awk, R, Ruby и т. Д.

GCC и CLang

GCC давно использует Yacc, но в 2004 году компиляторы C и Objective-C заменяют Yacc на рекурсивный потомственный парсер, написанный вручную. Она обеспечивает минимальный прирост скорости в 1,5%. Затем последовал компилятор C++ .
CLang использует аналогичный парсер для всех языков.

АНТЛР (1989)

Основываясь на алгоритме LL (k), ANTLR, созданном Теренсом Парром, вероятно, является наиболее часто используемым инструментом формирования парнеров. Версия 4, называющая себя ALL (k), и представляющая собой сочетание LL (k) и GLR, работает либо с прослушивателями, либо с посетителями, и позволяет анализировать практически любую грамматику. Написание компилятора становится намного проще и в читательской версии также облегчает множественные целевые языки.

Читайте также:

Автор: Денис Суро, создатель языков Script и Cryonie.