Создание синтаксического анализатора (парсера) по контекстно-свободным грамматикам

Пару лет назад я собирался написать интерпретатор Пролога на Delphi. Я решил начать с создания парсера. Написание анализатора специально под Пролог показалось мне жутко сложным, казалось, легче будет написать универсальный анализатор и синтаксис Пролога к нему. Ну, так как это все безумно сложно и долго, я забросил эту задумку. А вот парсер остался. Здесь я расскажу про его написание.

Цель: написать синтаксический анализатор, поддерживающий контекстно-свободные грамматики. Также парсер может выполнять какие-то действия (связанные, например, с интерпретацией) в процессе анализа — т. н. «пользовательская часть» парсера.

Пусть синтаксис хранится в памяти таким образом: имеется начальный синтаксический нетерминал, с которого начинается синтаксический анализ; пусть также у каждого символа* имеется список символов, с которых следует продолжать анализ после данного символа. Если список пуст, то анализ можно считать успешно завершённым.
*синтаксические символы бывает двух типов — терминал и нетерминал

Рис. 1

Алгоритм рекурсивный, каждая итерация работает не с одним термом, а с текущим списком термов:

подпрограмма ПРОПАРСИТЬ ПО СПИСКУ ТЕРМОВ:

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

(тут использован интуитивно понятный человеческий язык… или импровизация на его тему)

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

Поподробнее о пользовательской части:

1. Бывает так, что нужно сделать такой символ, который представляет собой любую строку из английских символов или цифр. Такое придётся кодировать тридцатью различными термами (а это сложно/долго). Чтобы избежать этого, достаточно сделать простую проверку строки в «пользовательской части» парсера и изменить предварительный результат парсинга на результат проверки.
2. Также в пользовательской части можно предусмотреть выполнение системных команд языка (при интерпретации), например, если смоделирован синтаксис языка Brainfuck и в тексте встречается символ '+', то пользовательская часть увеличивает значение текущей ячейки на единицу.

Вот и всё с написанием, осталось реализовать этот алгоритм и опробовать его.

Также об этом можно почитать в статье Википедии Синтаксический анализ.

P. S. Вот здесь есть архив с исходниками (на Delphi) и DLL парсера, его импорт в виде проекта на Delphi и тут же тест-программа. Можно записывать синтаксис в текстовой форме (как это делать, написано в readme.txt) и аналиировать входные строки по нему. Появляющиеся окна ввода имитируют пользовательскую часть парсера: текст в поле — остаток анализируемого текста (его можно модифицировать в пользовательской части), в надписи над текстом указан литерал (если это он), в заголовке — True или False — предположительные (т. е. до пользовательской части) результаты анализа по текущему терму — соответственно Успех или Провал, и кнопки Ok и Cancel — будущий результат анализа по терму, возвращённый пользовательской частью. В конце будет проигран звук — звук ошибки или окна информации, свидетельствующий о результате парсинга. Входная строка в поле ввода также будет изменена.

EDIT: Отредактировал статью в соответствии с действительностью.