Извлечение информации с помощью грамматик BNF
Я хотел бы извлечь информацию из текста и иметь возможность запрашивать ее.
Структура этого текста будет определяться грамматикой БНФ (или ее вариантом), а извлекаемая информация будет указываться во время выполнения (синтаксис запроса на данный момент не имеет значения).
Таким образом, требования на самом деле просты:
- Получить некоторый структурированный текст
- Загрузить его в пригодной для использования форме, используя грамматику для его анализа
- Запустить запрос, чтобы выбрать некоторые его части
Чтобы проиллюстрировать пример, предположим, что у нас есть такая грамматика (в настроенном формате BNF):
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<id> ::= 15 * digit
<hex> ::= 10 * (<digit> | a | b | c | d | e | f)
<anything> ::= <digit> | .... (all characters)
<match> ::= <id> (" " <hex>)*
<nomatch> ::= "." <anything>*
<line> ::= (<match> | <nomatch> | "") [<CR>] <LF>
<text> ::= <line>+
Для которой такой текст будет соответствовать:
012345678901234
012345678901234 abcdef0123
Nor the previous line nor this one would match
И затем я хотел бы перечислить все теги, которые появляются в правиле, поэтому например, используя синтаксис, подобный XPath:
match//id
, который вернет список.
Это звучит относительно просто, за исключением того, что у меня есть два больших ограничения:
- грамматика BNF должна считываться во время выполнения (из структуры, подобной строке/вектору)
- запросы также будут считываться во время выполнения
Некоторые уточнения:
- предполагается, что грамматика не будет часто меняться, поэтому шаг "компиляции" для создания структуры в памяти приемлем (и, возможно, необходим для достижения хорошей скорости)
- скорость имеет существенное значение, бонусные баллы за оперативный сбор нужных фрагментов
- бонусные баллы за возможность использования обратных вызовов для устранения неоднозначности (иногда необходимая информация по устранению неоднозначности может потребовать, например, доступа к БД)
- бонусные баллы за составные грамматики (в пользу модульности и повторного использования элементы грамматики)
Я знаю, например, lex/yacc и flex/bison, однако они, похоже, только создают код C/C++ для компиляции, а это не то, чем я занимаюсь.
Знаете ли вы о надежной библиотеке (желательно бесплатной и с открытым исходным кодом), которая может преобразовать грамматику BNF в синтаксический анализатор «на лету» и создать структурированный вывод в памяти из основного текста с помощью этого синтаксического анализатора? ?
РЕДАКТИРОВАТЬ:Я открыт для альтернатив. На данный момент идея заключалась в том, что, возможно, регулярные выражения могли бы позволить такое извлечение, однако, учитывая сложность вовлеченных грамматик, это могло бы быстро стать безобразным, и, таким образом, поддержка регулярных выражений была бы довольно ужасной задачей. Кроме того, разделяя грамматики и извлечение, я надеюсь, что смогу повторно использовать одну и ту же грамматику для разных нужд извлечения, вместо того, чтобы каждый раз иметь немного разные регулярные выражения.