Построить парсер из грамматики во время выполнения

Ответ 1

Довольно легко построить рекурсивный спуск, парсер обратной связи, который принимает грамматику в качестве входных данных. Вы можете уменьшить все свои правила до следующей формы (или действовать так, как если бы у вас есть):

 A = B C D ;

Анализ такого правила путем рекурсивного спуска очень просто: вызовите процедуру, которая соответствует нахождению B, затем тот, который находит C, а затем тот, который находит D. Учитывая, что вы выполняете общий синтаксический анализатор, вы всегда можете вызвать "parse_next_sentential_form (x)" и передать имя желаемой формы (терминальный или нетерминальный токен) как x (например, "B", "C", "D" ).

При обработке такого правила парсер хочет создать A, найдя B, затем C, затем D. Чтобы найти B (или C или D), вы хотели бы иметь индексированный набор правил в которые все левые стороны одинаковы, поэтому можно легко перечислить правила производства B и рекурсивно обрабатывать их содержимое. Если ваш парсер получает сбой, он просто отступает.

Это не будет сильным сильным парсером, но не должен быть ужасным, если он будет хорошо реализован.

Можно также использовать анализатор Эрли, который анализирует, создавая состояния частично обработанных правил.

Если вы хотите, чтобы это было быстро, я полагаю, вы могли бы просто взять кишки Бизона и превратить его в библиотеку. Тогда, если у вас есть грамматический текст или правила грамматики (разные точки входа в Bison), вы можете запустить его и заставить его создавать свои таблицы в памяти (что он должен делать в той или иной форме). Не выплюньте их; просто создайте механизм анализа LR, который их использует. Voila, эффективное генерирование парсера на лету. Вы должны беспокоиться о двусмысленности и ЛАЛРЕ (1) вашей грамматики, если вы это сделаете; предыдущие два решения работают с любой контекстной свободной грамматикой.

Ответ 2

Я не знаю об этой существующей библиотеке. Однако, если производительность и надежность не являются критическими, тогда вы можете открутить бизон или любой другой инструмент, который генерирует код C (через popen (3) или аналогичный), отжимает gcc на сгенерированном коде, связывает его с общей библиотекой и загружает библиотеку через dlopen (3)/dlsym (3). В Windows - DLL и LoadLibrary().

Ответ 3

Самый простой вариант - встроить некоторый язык сценариев или даже полномасштабную виртуальную машину (например, Mono) и запустить сгенерированные синтаксические анализаторы поверх нее. У Lua есть довольно мощный JIT-компилятор, достойные возможности метапрограммирования и несколько реализаций Packrat, готовых к использованию, поэтому, вероятно, это был бы самый медленный способ.

Ответ 4

Я только что наткнулся на это http://cocom.sourceforge.net/ammunition++-13.html
Последний - Эрли Парсер, и он, кажется, берет грамматику как строку.
Одна из функций:

Открытая функция `parse_grammar '

         `int parse_grammar (int strict_p, const char *description)'

- еще одна функция, которая настраивает парсер на заданную грамматику.   Грамматика задается строкой `description '.   Описание аналогично YACC.

Фактический код находится в http://sourceforge.net/projects/cocom/

ИЗМЕНИТЬ

Более новая версия находится в https://github.com/vnmakarov/yaep

Ответ 5

boost:: spirit - это синтаксический анализ С++, который можно использовать для динамического создания парсеров во время выполнения.