Функциональные парсеры: различия между версиями

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

В данной статье мы придерживаемся конструкций стандартного функционального языка таких как [[w:Функция высшего порядка|функции высшего порядка]], [[w:Линейный список|списки]] и [[w:Тип данных|алгебраические типы]]. Все программы написаны на языке Gofer &nbsp;[4]. В нескольких местах использованы списочные структуры, но они не являются существенными и могут быть легко заменены с помощью функций <tt>map</tt>, <tt>filter</tt> и <tt>concat</tt>. Типовые [[w:Класс (программирование)|классы]] использованы только для [[w:Полиморфизм в языках программирования|перегрузки]] равенства и арифметических операций.

Мы начнём с объяснения определения типа [[w:Функция (программирование)|функций]] синтаксического анализа. Используя этот тип, мы сможем построить синтаксические анализаторы для языков неоднозначных [[w:Грамматика|грамматик]]. Далее мы представим некоторые элементарные [[w:парсер|парсеры]], которые могут быть использованы для синтаксического анализа терминальных символов [[w:Язык (система знаков)|языка]].

В части &nbsp;4 представлены первые комбинаторы синтаксического анализа, которые могут быть использованы для комбинирования анализаторов последовательно или параллельно. В части &nbsp;5 дано определение некоторых функций, позволяющих [[w:Вычисление|вычислять]] значение в процессе синтаксического анализа. Вы можете использовать эти функции для того, что традиционно называется «определением [[w:Семантика|семантических]] функций»: некоторый полезный смысл может быть связан с синтаксическими структурами. В качестве примера, в части &nbsp;6 мы строим синтаксический анализатор для [[w:Строковый тип|строк]], состоящих из согласующихся скобок, где вычисляются разные семантические величины: [[w:Дерево (теория графов)|дерево]], описывающее структуру, и [[w:Целое число|целое число]], показывающее глубину вложенности.

В частях &nbsp;7 &nbsp;и &nbsp;8 мы рассматриваем некоторые новые комбинаторы синтаксического анализа. Не только они сами облегчат жизнь в будущем, но и их определения также являются хорошими примерами использования комбинаторов синтаксического анализа. Реальное приложение — разработанный парсер [[w:Арифметика|арифметических выражений]] — приведено в части &nbsp;9. Далее приведено обобщение парсера для случая произвольного числа уровней старшинства. Это сделано без программирования приоритетов операторов как целых чисел и мы избежим использования индексов и эллипсисов.