История синтаксического анализа

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

В этой статье мы в хронологическом порядке перечислим важнейшие этапы развития парсеров как инструмента анализа данных.

1960

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

 1961

Нед Айронс выпускает свой парсер ALGOL. Фактически, алгоритм Айронса является первым подобным анализатором, который был описан в печати. Парсер Неда является лево-рекурсивным (форма рекурсивного спуска) парсером . В отличие от современного рекурсивного спуска, алгоритм Айронса носит общий характер и является синтаксически-управляемым. «Общий» означает, что они могут разобрать что написано в БНФ (форма Бэкуса – Наура — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории). «Синтаксически-управляемый» (декларативный) означает, что анализатор фактически создается из БНФ — парсер не нужно создавать самому.

1961

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

•  В 1960-х память и CPU очень ограничены. Ручное кодирование (hand-coding) окупается даже тогда, когда выигрыш от его применения мал.
• Чистый леворекурсивный анализ — очень слабый метод синтаксического анализа. Ручному кодированию часто приходится преодолевать эти ограничения. Это утверждение верно как в 1961, так и в наши дни.
• Леворекурсивный анализ хорошо работает в сочетании с ручным кодированием — они дополняют друг друга.

1965

Дональд Кнут (Don Knuth) изобретает алгоритм LR. Ученый в первую очередь заинтересован в математической стороне задачи. Кнут описывает алгоритм анализа, но его подход считается непрактичным.

1968

Джей Эрли (Jay Earley) изобретает алгоритм, названный в его честь. Как и алгоритм Irons, алгоритм Эрли является синтаксически-управляемым и носит общий характер. В отличие от алгоритма Irons, не использует метод поиска с возвратом. Основная идея Эрли состоит в том, чтобы отслеживать этапы работы алгоритма в таблицах. Алгоритм Эрли заманчив, но имеет три основных недостатка:

• Во-первых, есть ошибка в обработке правил нулевой длины.
• Во-вторых, при право-сторонней рекурсии необходимо применять алгоритм дважды.
• В-третьих, чтобы создать таблицы, необходимо вести учёт системных ресурсов, что, по меркам аппаратных средств 1968 года, является довольно сложной задачей.

1969

Фрэнк ДеРемер (Frank DeRemer) описывает новый вариант LR Кнута. Для алгоритма LALR ДеРемера необходим только стек и таблица состояний, размер которой можно легко изменить.

1972

Ахо (Aho) и Алманн (Ullmann) описали простой способ исправить ошибку правила нулевой длины в оригинальном алгоритме Эрли. К сожалению, это исправление требует даже больше системных ресурсов, чем алгоритм Эрли.

1975

Белл Лэбс (Bell Labs) преобразует свой компилятор языка C из самокодируемого рекурсивного спуска в алгоритм LALR ДеРемера.

 1977

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

1979

Bell Labs выпустила новую версию UNIX — седьмую. V7 включает в себя безусловно наиболее полный, полезный и доступный инструментарий для разработки компиляторов. Центральное место занимает инструментарий Yacc, генератор синтаксических анализаторов на основе LALR. С небольшим трудом Yacc парсит свой собственный язык ввода, а также язык основного компилятора V7 — переносимого компилятора языка C. Кажется, что после двух десятилетий исследований, проблема синтаксического анализа наконец решается.

1987

Ларри Уолл (Larry Wall) представляет Perl 1. Perl позволяет решать более сложные задачи, чем отличается от уже существующих языков. Ларри активно использует LALR — насколько известно автору, чаще, чем кто-либо до или после него.

 1991

Джуп Лео (Joop Leo) обнаруживает способ ускорить правосторонние рекурсии в алгоритме Эрли. Алгоритм Лео является линейным практически для любой: как однозначной, так и неоднозначной грамматики, представляющей практический интерес. Аппаратное обеспечение в 1991 на шесть порядков быстрее, чем в 1968 году, так что вопрос учёта системных ресурсов стал не столь важен. Однако, если дело касается скорости, то выигрывает алгоритм Эрли. Алгоритм Лео оказался важным открытием, но его практическая реализация появится лишь через 20 лет.

1990-е

Алгоритм Эрли забыт. Все приверженцы LALR довольны, не так ли? Нет. Пользователи LALR делают неприятные открытия. В то время как LALR автоматически генерирует свои анализаторы, их отладка настолько трудна, что проще написать парсер самому. После отладки их LALR анализаторы при правильных входных данных работают быстро. Но почти все, что они говорят пользователям о некорректных входных данных — лишь сообщение о неверном формате без указания дополнительной информации. По словам Ларри, LALR «быстр, но глуп».

2000

Ларри Уолл принимает решение о радикальном переопределении Perl — издании Perl 6. Он даже не рассматривает вопрос о повторном использовании LALR.

2002

Эйкок (Aycock) и Хоспул (Horspool) опубликовали результаты своих опытов по созданию быстрого, практичного парсера Эрли. Однако при этом не использовалось улучшение, предложенное Джупом Лео — они, кажется, не знают о нем. Их собственный метод ускорения ограничен в своих показателях и сложности, которые он несет с собой, они могут быть даже контрпродуктивными при оценке времени. Но в этой работе ценным оказалось решение ошибки правила нулевой длины. И на этот раз оно не требует никакого дополнительного учета системных ресурсов.

2006

GNU объявляет, что был переписан парсер компилятора GCC. В течение трех десятилетий, компиляторы языка C промышленного флагмана использовали LALR в качестве парсера — доказательство утверждения, что LALR и серьезный алгоритм эквивалентны. Теперь GNU заменяет LALR технологией, которую тот заменил четверть века назад: рекурсивным спуском.

 С 2000 и до сегодняшнего дня

С отступлением от LALR приходит крах престижа теории синтаксического анализа. Спустя полтора века, мы пришли к тому, с чего начали. Если вы возьмете оригинальный алгоритм Ned Irons 1961 года, измените имена и даты и переведете код из смеси ассемблера и ALGOL в Haskell, то вы бы легко смогли выпустить его в наши дни и представить как новый и революционный подход.

Парсер Marpa

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

Эйкок и Хоспул решили проблему правила нулевой длины. Джуп Лео разработал ускорение для правосторонней рекурсии. И вопрос учета системных ресурсов разрешился сам по себе: машинные операции в настоящее время в миллиард раз быстрее, чем в 1968 году, и скорость, вероятно, уже не столь значима — в настоящее время главной проблемой стали кэш-промахи.

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

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

Перевод статьи «Parsing: a timeline»