Библиотека Parser, которая может обрабатывать двусмысленность

Я ищу зрелую парсерную библиотеку, либо для Scala, либо для Haskell. Самое главное, что библиотека может обрабатывать двусмысленность. Если выражение неоднозначно, я хочу всевозможное абстрактное синтаксическое дерево, соответствующее выражению. Простой пример: выражение a ⊗ b ⊗ c можно рассматривать как (a ⊗ b) ⊗ c или a ⊗ (b ⊗ c), и мне нужны оба варианта. Спасибо!

Ответ 1

В конечном итоге выбор упал на формализм определения синтаксиса (SDF2) с генератором таблицы sdf здесь и JSGLR в качестве генератора синтаксического анализатора.

Ответ 2

Мне кажется, что старый парень помнит, когда бумаги Уолдера, такие как Comprehending Monads (предшественник обозначений), были захватывающими и новыми. Идея состоит в том, что вы (цитируя) заменяете неудачу списком успехов, то есть поддерживаете список всех возможных анализов. В конце вы обычно просто принимаете первый матч, но с этой настройкой вы можете взять все из них.

Это не все, что эффективно для детерминированного парсера, поэтому они меньше в моде, но они то, что вам нужно.

Посмотрите polyparse и, в частности, Text.ParserCombinators.HuttonMeijer и Text.ParserCombinators.HuttonMeijerWallace.

(Хаттон и Мейджер перевели библиотеку парсеров в Haskell (от Gofer), и Уоллес добавил дополнительные возможности.)

Удостоверьтесь, что вы проверяете это на простых примерах, таких как синтаксический анализ "aaaa" с помощью

testP = do
   a <- many $ char 'a'
   b <- many $ char 'a'
   return (a,b)

чтобы увидеть, есть ли у него семантика, которую вы ищете.

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

(Спекуляция: я не думаю, что parsec может делать то, что вы хотите. Его стандартный комбинатор выбора детерминирован. Я не искал настройки или замены этого поведения, и я бы не хотел, чтобы я боялся.)

Ответ 3

Этот вопрос сразу напомнил мне о Yacc мертв/Нет, это не обсуждение с конца 2010 года. Авторы Yacc - это мертвая бумага, которая предоставляет библиотеку в Scala (не поддерживается), Haskell и Racket. В Yacc - живой ответ, Russ Cox указывает, что код работает в экспоненциальном времени для двусмысленных грамматик.

Хорошо известно, что в O(n^3) можно анализировать неоднозначные грамматики, хотя, очевидно, может потребоваться экспоненциальное время для перечисления всех деревьев разбора в случае, когда их экспоненциально много, и будет случай x1 + x2 + x3 ... + xn. bison реализует алгоритм GLR, который делает это; к сожалению, в то время как bison, безусловно, зрелый (если не совсем умирающий), он не написан ни в Haskell, ни в Scala.

Даниэль Спивак реализовал парсер GLL в Scala IIRC, но в прошлый раз, когда я посмотрел на него, он столкнулся с некоторыми проблемами производительности. Поэтому я не уверен, что его можно было бы назвать зрелым.

Ответ 4

Я не могу говорить о том, насколько это зрело или дает вам примеры использования, но у меня был scala gll-combinators библиотека открывается на вкладке в течение нескольких дней. Он обрабатывает неоднозначные грамматики и выглядит довольно элегантно.