Парсер-комбинатор

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

Парсеры, использующие комбинаторы, широко использовались при создании прототипов компиляторов и процессоров для предметно-ориентированных языков, таких как интерфейсы естественного языка к базам данных, где сложные и разнообразные семантические действия тесно интегрированы с синтаксической обработкой. В 1989 году Ричард Фрост и Джон Лаунбери продемонстрировали использование комбинаторов парсеров для создания интерпретаторов естественного языка . Грэм Хаттон также использовал функции высшего порядка для базового синтаксического анализа в 1992 году. и монадический анализ в 1996 году. С.Д. Свирстра также продемонстрировал практические аспекты синтаксических комбинаторов в 2001 году. В 2008 году Фрост, Хафиз и Каллаган описал набор комбинаторов парсеров в Haskell , которые решают давнюю проблему размещения левой рекурсии и работают как полноценный инструмент нисходящего синтаксического анализа в полиномиальном времени и пространстве.

Основная идея

В любом языке программирования, который имеет первоклассные функции , комбинаторы синтаксических анализаторов могут использоваться для объединения базовых анализаторов для создания анализаторов для более сложных правил. Например, правило продукции контекстно -свободной грамматики (CFG) может иметь одну или несколько альтернатив, и каждая альтернатива может состоять из последовательности нетерминалов и/или терминалов, или альтернатива может состоять из один нетерминал или терминал или пустая строка. Если для каждой из этих альтернатив доступен простой анализатор, можно использовать комбинатор анализаторов для объединения каждого из этих анализаторов, возвращая новый анализатор, который может распознавать любую или все альтернативы.

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

Комбинаторы

Чтобы обсуждение было относительно простым, мы обсуждаем комбинаторы синтаксических анализаторов только с точки зрения распознавателей . Если входная строка имеет длину #input и доступ к его членам осуществляется через индекс jраспознаватель — это анализатор, который возвращает на выходе набор индексов, представляющих индексы, на которых анализатор успешно завершил распознавание последовательности токенов, начинающихся с индекса j. Пустой набор результатов указывает на то, что распознавателю не удалось распознать какую-либо последовательность, начинающуюся с индекса. j.

• The empty Распознаватель распознает пустую строку. Этот анализатор всегда завершается успешно, возвращая одноэлементный набор, содержащий входной индекс:

$empty(j)=\{j\}$

• Распознаватель term x распознает терминал x. Если токен по индексу j во входной строке есть x, этот синтаксический анализатор возвращает одноэлементный набор, содержащий j + 1; в противном случае он возвращает пустой набор.

$term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ element of }}input=x\\\left\{\right\},&{\mbox{otherwise}}\end{cases}}$

Даны два распознавателя p и q, мы можем определить два основных комбинатора синтаксического анализатора: один для сопоставления альтернативных правил и один для правил упорядочивания:

• «Альтернативный» комбинатор синтаксического анализатора ⊕ применяет каждый из распознавателей к одному и тому же индексу. j и возвращает объединение конечных индексов распознавателей:

$(p\oplus q)(j)=p(j)\cup q(j)$

• Комбинатор «последовательность» ⊛ применяет первый распознаватель. p к входному индексу j, и для каждого конечного индекса применяется второй распознаватель q с этим в качестве стартового индекса. Он возвращает объединение индексов завершения, возвращаемых всеми вызовами q:

$(p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}$

Может существовать несколько различных способов анализа строки с завершением по одному и тому же индексу, что указывает на неоднозначную грамматику . Простые распознаватели не признают этих двусмысленностей; каждый возможный индекс окончания указывается в наборе результатов только один раз. Для получения более полного набора результатов более сложный объект, например дерево разбора необходимо вернуть .

Примеры

Рассмотрим весьма неоднозначную контекстно-свободную грамматику , s ::= ‘x’ s s | ε. Используя определенные ранее комбинаторы, мы можем модульно определить исполняемые обозначения этой грамматики на современном функциональном языке (например, Haskell ) как s = term ‘x’ <*> s <*> s <+> empty. Когда распознаватель s применяется по индексу 2 входной последовательности x x x x x он вернет набор результатов {2,3,4,5}, что указывает на наличие совпадений, начинающихся с индекса 2 и заканчивающихся любым индексом от 2 до 5 включительно.

Недостатки и решения

Комбинаторы синтаксических анализаторов, как и все анализаторы рекурсивного спуска , не ограничиваются контекстно-свободными грамматиками и, таким образом, не выполняют глобального поиска неоднозначностей в LL( k ) синтаксическом анализе First _k и Follow _k наборов . Таким образом, неоднозначности не известны до момента выполнения, если и до тех пор, пока входные данные не вызовут их. В таких случаях анализатор рекурсивного спуска может по умолчанию (возможно, неизвестный разработчику грамматики) выбрать один из возможных неоднозначных путей, что приводит к семантической путанице (алиасингу) при использовании языка. Это приводит к ошибкам пользователей неоднозначных языков программирования, о которых не сообщается во время компиляции и которые возникают не в результате человеческой ошибки, а из-за неоднозначной грамматики. Единственное решение, которое устраняет эти ошибки, — это устранить двусмысленности и использовать контекстно-свободную грамматику.

Простые реализации комбинаторов синтаксического анализатора имеют некоторые недостатки, которые характерны для синтаксического анализа сверху вниз. Наивный комбинаторный анализ требует экспоненциального времени и пространства при анализе неоднозначной контекстно-свободной грамматики. В 1996 году Фрост и Шидловски продемонстрировали, как мемоизацию с комбинаторами синтаксического анализатора, чтобы уменьшить временную сложность до полиномиальной. можно использовать Позже Фрост использовал монады для создания комбинаторов для систематического и правильного объединения мемо-таблиц в ходе вычислений.

сверху вниз Как и любой рекурсивный анализ спуска , обычные комбинаторы синтаксического анализатора (например, комбинаторы, описанные выше) не завершаются при обработке леворекурсивной грамматики (например, s ::= s <*> term ‘x’|empty). Алгоритм распознавания, который учитывает неоднозначные грамматики с помощью прямых леворекурсивных правил, описан Фростом и Хафизом в 2006 году. Алгоритм ограничивает постоянно растущий леворекурсивный анализ, налагая ограничения на глубину. Этот алгоритм был расширен до полного алгоритма синтаксического анализа для обеспечения как косвенной, так и прямой левой рекурсии за полиномиальное время , а также для создания компактных представлений полиномиального размера потенциально экспоненциального числа деревьев синтаксического анализа для весьма неоднозначных грамматик Фростом, Хафизом и Каллаганом в 2007. Этот расширенный алгоритм учитывает косвенную левую рекурсию, сравнивая ее «вычисленный контекст» с «текущим контекстом». Те же авторы также описали свою реализацию набора комбинаторов парсеров, написанных на языке программирования Haskell и основанных на том же алгоритме.

Ссылки

• Бердж, Уильям Х. (1975). Методы рекурсивного программирования . Серия «Системное программирование». Аддисон-Уэсли. ISBN  978-0201144505 .
• Фрост, Ричард; Лаунбери, Джон (1989). «Создание интерпретаторов естественного языка на ленивом функциональном языке» (PDF) . Компьютерный журнал . Специальное издание о ленивом функциональном программировании. 32 (2): 108–121. дои : 10.1093/comjnl/32.2.108 . Архивировано из оригинала 6 июня 2013 г. {{cite journal}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
• Фрост, Ричард А.; Шидловски, Барбара (1996). «Запоминание чисто функциональных языковых процессоров с нисходящим обратным отслеживанием» (PDF) . наук. Вычислить. Программа . 27 (3): 263–288. дои : 10.1016/0167-6423(96)00014-7 .
• Фрост, Ричард А. (2003). Монадическая мемоизация для сокращения поиска, сохраняющего корректность (PDF) . стр. 66–80. ISBN  978-3-540-40300-5 . {{cite book}}: |journal= игнорируется ( помогите )
• Фрост, Ричард А.; Хафиз, Рахматулла (2006). «Новый алгоритм синтаксического анализа сверху вниз для устранения неоднозначности и левой рекурсии за полиномиальное время» (PDF) . Уведомления ACM SIGPLAN . 41 (5): 46–54. дои : 10.1145/1149982.1149988 . S2CID   8006549 .
• Фрост, Ричард А.; Хафиз, Рахматулла; Каллаган, Пол (2007). «Модульный и эффективный нисходящий анализ неоднозначных леворекурсивных грамматик». Материалы 10-го Международного семинара по технологиям синтаксического анализа (IWPT), ACL-SIGPARSE : 109–120. CiteSeerX   10.1.1.97.8915 .
• Фрост, Ричард А.; Хафиз, Рахматулла; Каллаган, Пол (2008). «Парсер-комбинаторы неоднозначных леворекурсивных грамматик». Практические аспекты декларативных языков . ACM-SIGPLAN. Том. 4902. стр. 167–181. CiteSeerX   10.1.1.89.2132 . дои : 10.1007/978-3-540-77442-6_12 . ISBN  978-3-540-77441-9 .
• Хаттон, Грэм (1992). «Функции высшего порядка для синтаксического анализа». Журнал функционального программирования . 2 (3): 323–343. CiteSeerX   10.1.1.34.1287 . дои : 10.1017/s0956796800000411 . S2CID   31067887 .
• Окасаки, Крис (1998). «Даже функции высшего порядка для синтаксического анализа, или Зачем кому-то вообще использовать функцию шестого порядка?» . Журнал функционального программирования . 8 (2): 195–199. дои : 10.1017/S0956796898003001 . S2CID   59694674 .
• Свирстра, С. Доайтсе (2001). «Комбинаторные парсеры: от игрушек к инструментам» . Электронные заметки по теоретической информатике . 41 : 38–59. дои : 10.1016/S1571-0661(05)80545-6 .
• Уодлер, Филип (1985). «Как заменить неудачу списком успехов — метод обработки исключений, возврата и сопоставления с образцом в ленивых функциональных языках». Функциональные языки программирования и архитектура компьютеров . Конспекты лекций по информатике. Том. 201. С. 113–128. дои : 10.1007/3-540-15975-4_33 . ISBN  978-0-387-15975-1 . {{cite book}}: |journal= игнорируется ( помогите )