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

'''Ерон Фоккер (Jeroen Fokker)'''<br />

Факультет вычислительной техники, Университет Утрехта

 

Ключевые слова: парсер, список благоприятных исходов, синтаксический анализ, денотационная семантика.

 

 

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

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

 

 

Задачей синтаксического анализа является построение дерева, описывающего структуру заданной строки. В функциональном языке мы можем определить тип данных Tree (дерево). Парсер может быть реализован посредством функции следующего типа:

Мы будем использовать это определение типа в оставшейся части данной статьи.

 

 

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

Позже нам понадобится этот тривиальный парсер в качестве нейтрального элемента для функции foldr. Обратите внимание на отличие от функции epsilon, которая имеет один элемент в своём списке благоприятных исходов (хотя и пустой).

 

 

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

Несмотря на то, что кортежи ясно описывают структуру дерева разбора, существует трудность, заключающаяся в том, что мы не можем соединять парсеры случайным образом. Например, мы не можем последовательно соединить парсер p, описанный ранее и symbol ‘a’, поскольку последний имеет тип Parser Char Char, а параллельно можно соединять только парсеры одного типа. Хуже того, невозможно рекурсивно соединить парсер с самим собой, так как это приведёт к возникновению типов, представляющих собой бесконечно вложенные кортежи. Нам необходимо иметь способ изменения структуры дерева разбора, возвращаемого данным парсером.

 

 

Помимо операторов <*> и <|>, которые комбинируют парсеры, мы можем определить некоторые функции, которые модифицируют или преобразуют существующие парсеры. Мы создадим три из них: sp позволяет данному парсеру игнорировать начальные пробелы, just преобразует парсер таким образом, что он требует, чтобы остаток строки был пустым, и <@ применяет заданную функцию к деревьям разбора, получающимся в результате разбора.

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

 

 

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

Упражнение 8. Что случится, если мы опустим преобразователь just в этих примерах?

 

 

Несмотря на то, что в принципе вы можете построить парсеры для любого контекстно-свободного языка используя комбинаторы <*> и <|>, на практике проще иметь в распоряжении несколько дополнительных комбинаторов синтаксического анализа. В традиционных грамматических формализмах для описания, например, необязательных или повторяющихся конструкций также используются дополнительные символы. Например рассмотрим формализм БНФ, в котором изначально могли быть использованы только последовательное и параллельное соединения (обозначаемые размещение рядом и вертикальными линиями соответственно), а позже он был расширен таким образом, чтобы учитывать также повторение, обозначаемое звёздочками.

Упражнение 14. Попробуйте определить chainr. Определение изумительно симметрично по отношению к chainl. Но ощутить его красоту вы сможете лишь открыв её самостоятельно...

 

 

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

мы получим парсер, который предполагает наличие структуры, но не завершается с ошибкой в случае её отсутствия.

 

 

В этой части мы будем использовать комбинаторы синтаксического анализа в конкретном приложении. Мы разработаем парсер арифметических выражений, деревья разбора которого имеют тип Expr:

На этом примере ясно видно достоинство данного метода. Нет никакой необходимости в отдельных формализмах для грамматик; продукции грамматики объединены с использованием функций высокого порядка. Также не нужен отдельный генератор парсеров (как «yacc»); функции могут быть рассмотрены и как описание грамматики и как выполняемый анализатор.

 

 

Арифметические выражения, в которых операторы имеют более двух уровней приоритета, могут быть разобраны путём написания дополнительных вспомогательных функций, промежуточных между term и expr. Функция chainr, имеющая в качестве первого параметра функцию с приоритетом на один уровень ниже, чем у chainr, используется в каждом определении.

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

 

 

Не смотря на то, что в предыдущих частях показано, что отдельные формализмы для грамматик не нужны, пользователи могут захотеть придерживаться, например, нотации БНФ для написания грамматик. Поэтому в этой части мы напишем функцию, преобразующую БНФ-грамматику в парсер. БНФ-грамматика задается в виде строки и подвергается анализу конечно же с помощью парсера. Этот парсер такой, что возвращаемое им «дерево» разбора также является парсером! Так что название этой части является обоснованным.

Упражнение 20. Сделайте парсер для вашего любимого языка.

 

 

Я бы хотел поблагодарить Doaitse Swierstra и Erik Meijer за их комментарии к наброску данной статьи и стимулирующие идеи.

 

 

#R. Bird and P. Wadler, Introduction to Functional Programming. Prentice Hall, 1988.

#Philip Wadler, `Monads for functional programming'. In Lecture notes of the First International Spring School on Advanced Programming Techniques, (J. Jeuring, ed.) Springer, 1995.

 

 

#Символ равный а удовлетворяет условию равенства а: