СПИСОК СОКРАЩЕНИЙ

БНФ- форма Бэкуса-Наура

1. ВВЕДЕНИЕ

Эта статья представляет собой неформальное введение в написание синтаксических анализаторов на ленивом функциональном языке с использованием «комбинаторов синтаксического анализа». Большинство методов было описано Бурджем (Burge) [2], Вадлером (Wadler) [5], Хаттоном (Hutton) [3]. В последнее время в связи с комбинаторами синтаксического анализа [6, 7] стало довольно популярным использование так называемых монад. Однако мы не будем использовать их в данной статье с тем чтобы показать, что нет никакого волшебства в использовании комбинаторов синтаксического анализа. Тем не менее иногда вас будут подталкивать к изучению монад, поскольку они составляют полезное обобщение описанных здесь приёмов.

В данной статье мы придерживаемся конструкций стандартного функционального языка таких как функции высшего порядка, списки и алгебраические типы. Все программы написаны на языке Gofer [4]. В нескольких местах использованы списочные структуры, но они не являются существенными и могут быть легко заменены с помощью функций map, filter и concat. Типовые классы использованы только для перегрузки равенства и арифметических операций.

Мы начнём с объяснения определения типа функций синтаксического анализа. Используя этот тип, мы сможем построить синтаксические анализаторы для языков неоднозначных грамматик. Далее мы представим некоторые элементарные парсеры, которые могут быть использованы для синтаксического анализа терминальных символов языка.

В части 4 представлены первые комбинаторы синтаксического анализа, которые могут быть использованы для комбинирования анализаторов последовательно или параллельно. В части 5 дано определение некоторых функций, позволяющих вычислять значение в процессе синтаксического анализа. Вы можете использовать эти функции для того, что традиционно называется «определением семантических функций»: некоторый полезный смысл может быть связан с синтаксическими структурами. В качестве примера, в части 6 мы строим синтаксический анализатор для строк, состоящих из согласующихся скобок, где вычисляются разные семантические величины: дерево, описывающее структуру, и целое число, показывающее глубину вложенности.

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

В последней части комбинаторы синтаксического анализа используются для разбора строкового представления грамматики. Как семантическая величина, парсер порождается для языка грамматики, который в свою очередь, может быть применён для входной строки. Таким образом, по существу, мы получаем генератор грамматического разбора.