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

Question

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

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

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

Answer 1

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

* Haskell парсек , attoparsec и polyparse и комбинаторы парсера стокового кода Scala - все, что фактически является парсерами LL (*).

И parsec, и attoparsec требуют, чтобы вы использовали явный комбинатор try для возврата назад, но это делается только для повышения эффективности, и комбинаторы синтаксического анализа scala также могут работать с синтаксическим анализом пакетов.1016 *.

Рассмотрим следующий фрагмент из анонса недавнего несвязанного пакета Брента Йорги:

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

это довольно легко увидетьисходная грамматика.

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

1. Библиотеки комбинаторов синтаксического анализа, то есть синтаксические анализаторы с рекурсивным спуском, не:

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

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

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

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

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

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

Answer 6

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