библиотека для преобразования регулярных выражений в NFAs?

Question

Есть ли хорошая библиотека для преобразования регулярных выражений в NFAs ? Я вижу много научных работ по этому предмету, которые полезны, но не так трудоемки в коде.

Мой вопрос частично связан с любопытством, а частично с реальной необходимостью ускорить сопоставление регулярных выражений в производственной системе, над которой я работаю. Хотя было бы интересно изучить этот предмет для изучения, я не уверен, что это «практическое» решение для ускорения нашего сопоставления с образцом. Мы являемся магазином Java, но с радостью примем указатели на хороший код на любом языке.

Редактировать

Интересно, я не знал, что регулярные выражения Java уже были NFA. Название этой статьи заставило меня поверить в обратное. Кстати, в настоящее время мы выполняем сопоставление регулярных выражений в Postgres; если простое решение - переместить сопоставление в код Java, это было бы здорово.

Answer 1

Решение вашей задачи по ускорению регулярных выражений:

Реализация Java своего механизма регулярных выражений основана на NFA. Таким образом, чтобы настроить ваши регулярные выражения, я бы сказал, что вам будет полезно более глубокое понимание того, как реализован движок.

И поэтому я советую вам: Освоение регулярных выражений В книге подробно рассматривается механизм NFA и способы его сопоставления, включая настройку регулярного выражения, специфичного для механизма NFA.

Кроме того, посмотрите Атомная группировка для настройки вашего регулярного выражения.

Answer 2

Отказ от ответственности: я не эксперт по Java + регулярные выражения. Но, если я правильно понимаю ...

Если средство сопоставления регулярных выражений в Java похоже на большинство других, оно использует NFA, но не так, как вы могли бы ожидать. Вместо реализации только для пересылки, о которой вы, возможно, слышали, она использует решение обратного отслеживания, которое упрощает сопоставление подвыражений и, вероятно, требуется для использования обратных ссылок. Тем не менее, он выполняет чередование плохо.

Вы хотите увидеть: http://swtch.com/~rsc/regexp/regexp1.html (относительно граничных случаев, которые плохо работают на этой измененной архитектуре).

Я также написал вопрос, который, как мне кажется, сводится к тому же:

Реализация регулярного выражения, которая может обрабатывать машинные регулярные выражения: * без возврата *, O (n)?

Но, по сути, похоже, по какой-то очень странной причине, что все распространенные реализации регулярных выражений основных поставщиков имеют ужасную производительность при использовании на определенных регулярных выражениях, даже если это не является необходимым.

Answer 3

Отказ от ответственности: я гугл, а не эксперт по регулярным выражениям.

Существует множество библиотек регулярных выражений, превышающих JDK, одна из которых dk.brics.automaton . Согласно тесту, указанному в статье , он примерно в 20 раз быстрее, чем реализация JDK.

Эта библиотека была написана Андерсом Мёллером, а также mavenized .