Мысли о синтаксическом анализе. Часть 0

Решил вот начать цикл статей о серьёзном изучении контекстно-свободных языков, грамматик, описывающих эти языки, и универсальных алгоритмов парсинга. Раньше почти не писал, но, чувствую, надо. И первым делом хотелось бы обозначить темы, которые я могу затронуть в следующих статьях:

• Классический LR(1) разбор [Donald Knuth, 1965]. Сейчас он начинает набирать популярность в связи с возрастающей мощностью любительских компьютеров. Избавляет от конфликтов грамматик, с которыми не могут справиться традиционные инструменты построения парсеров (yacc, bison), использующих LALR [Frank DeRemer, 1969] подход. Но не все КС-грамматики поддаются такому разбору. GLR [Masaru Tomita, 1984] позволяет полностью избежать конфликты, обойдя все варианты разбора. Поделюсь реализацией программы-анализатора грамматик. (Я его делаю на досуге. Спрошу сразу у хабрасоощества: нужны ли вообще подобные инструменты?)
• Алгоритм Кока-Янгера-Касами [Cocke-Younger-Kasami (CYK), 1965-70]. Требует соответствия грамматики нормальной форме Хомского [Chomsky normal form]. Является действительно универсальным и легко реализуемым. Для него существуют расширения, с которыми мне хотелось бы разобраться.
• Алгоритм Эрли [Jay Earley, 1970]. Не накладывает ограничений на используемую для анализа контекстно-свободную грамматику. Работает по нисходящему принципу, в отличие от предыдущих алгоритмов. LRE тоже интересно описать.

Видно, что меня интересуют универсальные алгоритмы создания разборщиков и самого разбора, нюансы их реализации, используемые технологии программирования.
Ну и чтобы придать веса топику…

Немного теории...

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

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

Парсинг применяется прежде всего:

• для регулярных выражений;
• для разбора математических выражений, ЯП, структурированных форматов данных;
• для анализа естественных языков – орфография, пунктуация, грамматика, машинный перевод;
• ...

Типы парсеров:

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

Порождающие грамматики(один из способов описания языка)

Термины:

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

Типы грамматик

По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):

• тип 0. неограниченные грамматики – возможны любые правила
• тип 1. контекстно-зависимые грамматики – левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
• тип 2. контекстно-свободные грамматики – левая часть состоит из одного нетерминала.
• тип 3. регулярные грамматики – более простые, эквивалентны конечным автоматам.

Пример

Приведу пример самой большой грамматики, которую мы разбирали вручную(строили всякие автоматы) на занятиях компиляторами:
E::=E + T
E::=T
T::=T * F
T::=F
F::=( E )
F::=t
Терминалы: +, *, (, ), t.
Нетерминалы: E(начальный), T, F.
Грамматика, собственно, описывает язык арифметических выражений с операциями сложения и умножения и скобками(t – число) и показывает, как раскрываются или сворачиваются символы грамматики.

Пока всё.
Спасибо, что дочитали этот сумбурный, написанный на ночь(эх, нужно было дождаться утра) текст до конца. Просто нужно было выговориться. Буду благодарен всем, кто напишет любой критический комментарий. Именно чтобы поспорить я сюда и пришел.