Существуют ли генераторы Parser LL для функциональных языков, таких как Haskell или Scala?

Я заметил явное отсутствие парсеров LL, которые создают парсеры на функциональных языках. Идеальная находка для того, что я искала без успеха, - это что-то, что бы создать парсер Haskell для грамматики LL (*) в стиле ANTLR (по модулю незначительного переформатирования грамматики) и был удивлен, что каждый последний генератор синтаксического анализатора с функциональным языковая цель, которую я нашел, был своего рода парсером LR.

Я хочу перейти на синтаксический анализатор этого языка. Я работаю над тем, у которого есть функциональные функции от ANTLR до самообучения в самом языке, и это очень помогло бы, если бы я мог переносить на свой язык что-то почти наверняка правильное в другой функциональный язык (желательно, я знаком с Haskell и Scala), вместо того, чтобы полностью переписывать его с нуля, хотя в конце концов я мог бы это сделать, поскольку основной язык невелик.

В этот момент больше, чем даже решение этого, мне очень любопытно, почему нет таких генераторов пар LL (*) или даже LL (k), но многие генераторы LR, поскольку LL кажется изначально проще.

Ответы

Ответ 1

Основная причина этого заключается в том, что большинство парсеров LL (k), которые написаны на функциональных языках, просто реализованы с использованием комбинаторов-парсеров, поскольку самый простой путь для генерации библиотеки комбинаторов парсеров - рекурсивный спуск.

Haskell parsec, attoparsec и polyparse и Scala компиляторы парсера акций производят эффективные парсеры LL (*).

Как для парсека, так и для attoparsec требуется использовать явный комбинатор try для возврата, но это делается только для эффективности, а комбинаторы парсера Scala могут также обрабатывать с разбор пакетов.

Рассмотрим следующий фрагмент из анонса последнего предложения Brent Yorgey unbound:

parseAtom = parens parseTerm
    <|> var <$> ident
    <|> lam <$> brackets ident <*> parseTerm

довольно легко увидеть оригинальную грамматику.

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

Внедряя комбинаторы парсеров как EDSL, а не внешний инструмент, вы сможете использовать расширенные возможности вашего языка программирования. Вы можете сделать части более высокого порядка грамматики, построить lexer hack непосредственно в синтаксический анализатор и т.д. Типичные генераторы парсеров LR не могут делать эти вещи или могут предлагать только их в специальных случаях в ограниченном контексте из-за необходимости иметь возможность испускать таблицы в конце.

Ответ 2

Вы вдохновили меня опубликовать старый проект хобби на https://github.com/nrnrnr/ebnf. Он поддерживает генерацию парсера LL (1) для стандартного ML. Адаптация к Haskell не была бы трудной, если вы можете найти того, кто понимает Icon.

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

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

Ответ 3

SML уже несколько лет имеет ml-antlr:

http://www.classes.cs.uchicago.edu/archive/2007/winter/22610-1/docs/lpt-manual.pdf

Существует также sllgen для схемы.

В связи с тем, что существует больше генераторов парсеров LR, чем LL, сложно вручную писать парсеры LR, поэтому вам действительно нужен генератор. С помощью парсеров LL ручная реализация по-прежнему соответствует грамматике, поэтому для генератора гораздо меньше потребности.

Ответ 4

С помощью Scala вы можете использовать все существующие инструменты Java без особых накладных расходов. JavaCC - генератор парсеров LL (k). Вы можете использовать его для создания конкретного дерева синтаксиса автоматически и делать все остальное в Scala. Я на самом деле сделал это для небольшого проекта, просто потому, что уже существовала грамматика JavaCC.

Ответ 5

Прежде чем описать решение LL (k) в разработке, я объясню, почему я не использовал другие доступные параметры, которые я осознавая.

  • Библиотеки комбинаторов парсеров, то есть рекурсивные анализаторы спуска, не выполняются:

    • гарантировать контекстно-свободную грамматику (CFG), потому что они не вычисляют первые и последующие элементы.
    • делать эффективные табличные указатели k с учетом прогноза. Вместо этого они делают неэффективную обратную трассировку.
    • не используйте более эффективный алгоритм синтаксического анализа на основе стека.

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

  • JavaCC имеет следующие недостатки:

    • объединяет лексер и генератор парсера.
    • слишком подробный синтаксис грамматики BNF.
    • выводит Java, и я хочу Scala (в конечном итоге Copute).
    • afaics не делает жесткой связи имен в грамматике и в AST.
    • монолитный исходный код afaics, например. не может (легко) извлекать модули для генерации первых и последующих наборов (чтобы я мог подключить собственное генерирование парсера).

Я пытаюсь создать генератор синтаксического анализатора LL (k), который будет выводиться на Scala, а затем, надеюсь, бутстрап для вывода языка, который я разрабатываю (Copute, который будет компилироваться с Scala).

В моей текущей попытке используется подмножество синтаксиса грамматики SLK, поэтому инструмент SLK можно использовать для проверки грамматики без контекста.

Ответ 6

Вы можете использовать ANTLR, который генерирует парсер LL * в Java (среди прочих), следовательно .class resp .jar.