Сочетание лексера и парсера в комбинаторе парсера
Я использую uu-parsinglib, но я думаю, что следующий вопрос является универсальным синтаксического анализатора.
Давайте рассмотрим следующий пример:
У меня есть лексер с комбинатором pLex, который производит список токенов (типа MyToken). Теперь я хочу написать парсер, который будет потреблять токены и создавать AST,
Как лучше всего соединить лексер и парсер? Прямо сейчас у меня есть lex функция:
lex s = parse ( (,) <$> pLex <*> pEnd) (createStr (LineColPos 0 0 0) s)
Должен ли я создать функцию parse p = ...? Если да, как я могу построить его, чтобы отслеживать столбцы и строки от лексера? Или я должен создать parserCombinatorкоторый бы использовал pLex комбинатор как-то?
2 ответа
Анализаторы на основе таблиц требуют разделения лексического анализа и анализа из-за их ограниченной возможности просмотра. Если заглянуть в будущее достаточно далеко, чтобы объединить лексический анализ в синтаксический анализатор, взорвется пространство состояний.
Подходы, основанные на комбинаторе, обычно не страдают от этой проблемы, так как они обычно выполняют анализ рекурсивного спуска. Если автором библиотеки не указано иное, объединение фаз не принесет вреда и не принесет много пользы, разделив их.
Хотя UU-Parsinglib обеспечивает Str Класс, который абстрагируется от различных строковых входов, просматривая его определение, показывает, что он по-прежнему предполагает, что вы в конечном итоге читаете последовательность Char, будь то из String, ByteString, Text и т. д. Поэтому пытаемся заставить его анализировать Поток MyToken кажется, что это может быть сложно. Parsec может быть лучшим выбором, если вы чувствуете, что должны это сделать.
Что касается вашего вопроса о вашей строковой реализации, комбинаторы принимают строковый ввод, содержащий синтаксическую структуру, и возвращают соответствующее семантическое значение, если они совпадают. Внутри комбинатора вы можете построить это семантическое значение из того, что вы непосредственно анализируете, беря из входного потока и комбинируя семантические значения из вызываемых вами подкомбинаторов.
Таким образом, ваш комбинатор 'String match' в вашем примере будет иметь список токенов в своей области благодаря выполненному им синтаксическому анализу. Вы можете использовать всю мощь Haskell для объединения этих токенов в одно значение MyString любым способом, который имеет смысл для вашего языка: возможно, тип SplicedString, который представляет, какие значения должны быть врезаны в него.
Комбинатор строк, вероятно, был вызван комбинатором 'expression', который сможет объединить значение MyString с другими проанализированными значениями в значение MyExpression. Это комбинаторы, возвращающие семантические значения обратно!
Я думаю, что в uu-parsinglib нет ничего, что мешало бы вам использовать ввод, отличный от Text. Только для текста (и друзей) мы предоставили довольно много функций, которые вам, вероятно, понадобятся. Если вы посмотрите на старые комбинаторы парсера uulib, вы найдете подход, основанный на сканере, который также можно использовать с более новой версией uu-parsinglib.
Если вы хотите обработать много данных, возможно, лучше иметь отдельную фазу сканирования. Сообщения об ошибках имеют тенденцию быть более информативными. В uulib вы найдете некоторую поддержку для написания вашего сканера (большинство языков так или иначе накладывают некоторые особые ограничения / требования на лексическую структуру, которые довольно многие инструменты (не смогут / должны быть адаптированы) для создания вашего сканера (например, правило офсайда))