Утилиты лексирования и синтаксического анализа

Я ищу утилиты для лексического анализа и создания синтаксических анализаторов, которые не являются Flex или Bison. Требования:

  • Синтаксический анализатор задается с использованием контекстно-свободной грамматики LL(*) или GLR. Я бы также рассмотрел ПЭГ.
  • Тесно интегрируется с языком программирования, который можно использовать как для написания сценариев, так и для разработки приложений. Язык также должен иметь средства для простого взаимодействия с C. Хорошими примерами являются Python, Ruby и Guile. Никаких C, Java или Perl, пожалуйста. Я хочу, чтобы язык был однородным; Я хочу, чтобы генератор парсера выводил код на том же языке.
  • Хорошо документированное и производственное качество.
  • Открытый источник. Бесплатно тоже желательно (хотя и не обязательно).
  • Совместимость с дистрибутивами Linux или одним из BSD с открытым исходным кодом. Я бы рассмотрел OpenSolaris.
  • Быстрое развитие вызывает значительно большую озабоченность, чем эффективность.
  • Подходит для анализа естественного языка, а также формальных языков. Разбор естественного языка ограничен короткими простыми предложениями с очень небольшой двусмысленностью.

Я присматриваюсь к ANTLR, хотя никогда им не пользовался. Комментарии по этому поводу приветствуются. Дайте мне знать, какие ваши любимые утилиты, отвечающие этим требованиям, и почему вы бы их порекомендовали.


python ruby parsing lexical-analysis guile
person Jerrad Genson    schedule 13.02.2011    source источник
comment
Как насчет pyparsing.wikispaces.com/Introduction или dabeaz.com/ply   -  person GWW    schedule 13.02.2011
comment
Учитывая ваши ограничения, какие возражения против flex/bison?   -  person Ira Baxter    schedule 14.02.2011
comment
Каждая грамматика LALR является грамматикой LR по определению. Более того, настаивая на генераторах синтаксических анализаторов LR, а не LALR, вы в основном получаете огромные таблицы без особой дополнительной практической выгоды. Поэтому я не уверен, почему вы настаиваете (?) на генераторах синтаксических анализаторов, отличных от LALR. Если вы сосредоточены только на создании кода для Python, Ruby, Guile, то я понимаю лучше. FWIW, я не думаю, что ANTLR генерирует что-либо из этого. Но я все еще озадачен: если выбранный вами язык легко взаимодействует с C (например, Python), bison по-прежнему является хорошим выбором: просто используйте свой язык для вызова сгенерированного Bison кода C.   -  person Ira Baxter    schedule 15.02.2011
comment
Мой опыт связан с грамматиками Bison и LALR, которых на этот раз недостаточно для удовлетворения моих потребностей; Я ищу инструмент с более выразительной грамматикой. Я полагал, что каноническая грамматика LR или LL(*) подойдет. Однако теперь кажется, что грамматика GLR может быть лучшим выбором. Что касается языков, то эти синтаксические анализаторы должны создаваться как часть каркаса расширения для базовой программы, написанной на C. Я хочу, чтобы язык расширения был однородным, и я не хочу, чтобы он был C. ANTLR способен генерации Python.   -  person Jerrad Genson    schedule 16.02.2011

Ответы (3)


arrow_upward
2
arrow_downward

здесь есть список современных парсеров Packrat.

person SK-logic    schedule 13.02.2011
comment
Я считаю, что ОП требует использования контекстно-свободной грамматики, в которую PEG, похоже, не попадают. Тем не менее, может быть, есть шанс, что ОП сочтет ПЭГ приемлемыми. - person Chris Jester-Young; 13.02.2011
comment
Любые контекстно-свободные LL(*) или LR могут быть представлены в PEG, поэтому на практике эта разница не имеет значения. Генераторы синтаксических анализаторов на основе автоматов плохо вписываются во второе требование OP, тогда как PEG можно легко интегрировать практически в любой язык. - person SK-logic; 13.02.2011

arrow_upward
1
arrow_downward

Текст NL имеет тенденцию иметь много двусмысленности. Если вы хотите анализировать естественный язык, я не думаю, что какой-либо из классических генераторов парсеров компиляторного типа (LALR, LL [включая ANTLR]) вам сильно поможет, а генераторы парсеров компилятора обычно вообще не справляются с этим.

Парсер GLR, который обрабатывает неоднозначность, может быть полезен; bison предлагает это как вариант.

person Ira Baxter    schedule 14.02.2011

arrow_upward
0
arrow_downward

Guile 2.0 (будет выпущен примерно через несколько дней) имеет Библиотека разбора LALR(1).

person Chris Jester-Young    schedule 13.02.2011