Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎Тип <tt>Parser</tt>: Идентификаторы заключены в <tt>
Строка 128:
Используя элементарные парсеры из предыдущей части, можно сконструировать парсеры для терминальных символов грамматики. Более интересными являются синтаксические анализаторы для нетерминальных символов. Конечно, их можно написать вручную, но более удобно сконструировать их путём частичной параметризации функций высшего порядка.
 
Важными операциями над парсерами являются последовательное и параллельное соединение. Мы создадим для них две функции, которые для удобства обозначения определены как операторы: <tt><*></tt> для последовательного соединения и <tt><|></tt> для параллельного соединения. Приоритеты этих операторов определены таким образом, чтобы минимизировать использование скобок в практических ситуациях:
 
infixr 6 <*>
Строка 135:
Оба оператора имеют два парсера в качестве параметров, и возвращают парсер в качестве результата. Снова соединяя результат с другими парсерами, можно создать даже ещё более сложные парсеры.
 
В определениях, приведённых ниже, функции действуют на парсеры <tt>p1</tt> и <tt>p2</tt>. Кроме параметров <tt>p1</tt> и <tt>p2</tt>, функция действует на строку, которую можно рассматривать как строку, разбираемую парсером, являющимся результатом комбинирования <tt>p1</tt> и <tt>p2</tt>.
 
Для начала напишем определение оператора <tt><*></tt>. Для последовательного соединения сначала к входным данным должен быть применён <tt>р1</tt>. После этого <tt>р2</tt> применяется к оставшейся части строки, указанной в результате. Поскольку <tt>р1</tt> возвращает список решений, мы используем списочную запись, согласно которой <tt>р2</tt> применяется ко всем остаточным строкам в списке:
 
(<*>) :: Parser s a -> Parser s b -> Parser s (a, b)
(p1 <*> p2) xs = [(xs2, (v1, v2)) | (xs1, v1) <- p1 xs, (xs2, v2) <- p2 xs1]
(xs2, v2) <- p2 xs1]
 
Результатом функции является список всех возможных кортежей <tt>(v1, v2)</tt> с оставшейся строкой <tt>xs2</tt>, где <tt>v1</tt> — это дерево разбора, полученное с помощью <tt>p1</tt>, и где остаток строки <tt>xs1</tt> используется в качестве входных данных для <tt>p2</tt>, в результате работы которого получаются <tt>v2</tt> и <tt>xs2</tt>.
 
Кроме «последовательного соединения» нам необходим комбинатор синтаксического разбора для представления «выбора». Для этого у нас есть оператор комбинатора синтаксического анализа <tt><|></tt>:
 
(<|>) :: Parser s a -> Parser s a -> Parser s a
(p1 <|> p2) xs = p1 xs ++ p2 xs
 
Благодаря использованию списка благоприятных исходов и <tt>p1</tt> и <tt>p2</tt> возвращают списки возможных вариантов разбора. Для того, чтобы получить все возможные благоприятные исходы, полученные путём выбора из <tt>p1</tt> и <tt>p2</tt>, нам нужно лишь конкатенировать эти два списка.
Упражнение 2. Определяя приоритет оператора <|>, с использованием ключевого слова infixr мы также указали, что оператор является правоассоциативным. Почему это более удачное решение по сравнению с левой ассоциативностью? ▼
 
▲Упражнение 2. Определяя приоритет оператора <tt><|></tt>, с использованием ключевого слова <tt>infixr</tt> мы также указали, что оператор является правоассоциативным. Почему это более удачное решение по сравнению с левой ассоциативностью?
Результатом применения комбинаторов синтаксического анализа является снова парсер, который может быть соединён с другими парсерами. Деревья разбора, получаемые в результате, представляют собой сложные кортежи, отражающие способ, которым были соединены парсеры. Таким образом, термин «дерево разбора» является действительно подходящим. Например парсер р, где▼
 
▲Результатом применения комбинаторов синтаксического анализа является снова парсер, который может быть соединён с другими парсерами. Деревья разбора, получаемые в результате, представляют собой сложные кортежи, отражающие способ, которым были соединены парсеры. Таким образом, термин «дерево разбора» является действительно подходящим. Например парсер <tt>р</tt>, где
 
p = symbol 'a' <*> symbol 'b' <*> symbol 'c'
 
имеет тип <tt>Parser Char (Char, (Char, Char))</tt>.
 
Несмотря на то, что кортежи ясно описывают структуру дерева разбора, существует трудность, заключающаяся в том, что мы не можем соединять парсеры случайным образом. Например, мы не можем последовательно соединить парсер <tt>p</tt>, описанный ранее и <tt>symbol ‘a’’a’</tt>, поскольку последний имеет тип <tt>Parser Char Char</tt>, а параллельно можно соединять только парсеры одного типа. Хуже того, невозможно рекурсивно соединить парсер с самим собой, так как это приведёт к возникновению типов, представляющих собой бесконечно вложенные кортежи. Нам необходимо иметь способ изменения структуры дерева разбора, возвращаемого данным парсером.
 
== Преобразователи парсеров ==
Источник — https://ru.wikibooks.org/wiki/Функциональные_парсеры