У меня есть простой анализатор грамматики ANTLR3, который берет короткие строки текста и преобразует их в объекты Java. Далее у меня есть большой список текстовых строк. Некоторые из них (менее 1%) могут быть преобразованы, потому что они соответствуют грамматике.
Мне нужно пропустить их все через синтаксический анализатор, чтобы понять, какие из них являются конвертируемыми, и создать коллекцию объектов Java. Очень трудоемкая операция. Гораздо эффективнее было бы передать их через регулярное выражение перед отправкой в ANTLR3.
Я могу создать такое регулярное выражение самостоятельно, но было бы гораздо лучше получить его динамически из парсера ANTLR3. Возможно ли это сделать?
Ответ 1 · рейтинг 4 · Paŭlo Ebermann
В общем, только обычные языки могут иметь описывающие их регулярные выражения. (Большинство RE-движков поддерживают функции, которые также соответствуют некоторым нерегулярным языкам (например, по обратным ссылкам), но все же не все контекстно-свободные или даже общие формальные языки.)
Я на самом деле не эксперт по antlr, но я полагаю, что его грамматика может соответствовать языкам, которые не совместимы с RE.
Так что даже теоретическая разрешимость вашей задачи на самом деле не дается, она зависит от грамматики.
Может быть, что
- ваша грамматика на самом деле является обычной грамматикой, или
- что существует обычный язык, который является небольшим надмножеством вашего языка грамматики - таким образом, RE может отфильтровать большинство несовпадающих строк, в то время как некоторые будут отфильтрованы только грамматикой/парсером.
Скорее всего, нет определенного способа убедиться, не видя вашей грамматики.
Кроме того, регулярное выражение не обязательно быстрее, чем ваш синтаксический анализатор.
