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

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

В данной статье мы придерживаемся таких конструкций стандартного функционального языка таких как [[w:Функция высшего порядка|функции высшего порядка]], [[w:Линейный список|списки]] и [[w:Тип данных|алгебраические типы]]. Все программы написаны на языке Gofer&nbsp;[4]. В нескольких местах использованывстречаются списочные структуры (list comprehensions), но ониих использование не являютсяявляется существенными и они могут быть легко заменены с помощью функций <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. Далее приведено обобщение парсера для случая произвольного числа уровней старшинства (precedence level). Это сделано без программированияуказания приоритетов операторов какс целыхпомощью чисел, и мы избежимбез использования индексов и эллипсисовмноготочий.