Рекомендации по реализации C синтаксического анализатора регулярных выражений

Question

Я думаю о реализации парсера регулярных выражений в библиотеке C, которую я разрабатываю. Теперь возникает вопрос: есть ли какой-нибудь открытый исходный код, который я мог бы использовать дословно или с как можно меньшим количеством изменений? Мои ожидания в отношении кода:

• это должно быть написано на C (не C ++)
• нужно скомпилировать под gcc, mingw, M $ VC
• он не должен зависеть от каких-либо сторонних или специфических для ОС заголовков / библиотек (т. Е. Все, что нужно для его компиляции, должно быть легко доступно при базовой установке gcc, mingw, M $ VC
• было бы неплохо, если бы он использовал Perl-совместимый синтаксис регулярных выражений (как PCRE в PHP).
• в идеале код должен быть максимально компактным

Есть ли готовые решения, которые вы могли бы порекомендовать? Я смотрел на PCRE для C, и похоже, что в нем есть все, что доступно в PHP (какие правила), но размер (1.4MB DL) немного пугающий. Как вы думаете, это надежная ставка? Или есть другие варианты, которые стоит рассмотреть?

[EDIT]

Библиотека, которую я разрабатываю, имеет открытый исходный код, лицензия BSD.

Answer 1

PCRE такой большой, потому что регулярные выражения hard .В большинстве случаев это в основном документация и код поддержки;намного меньше при компиляции в объектный код.

Answer 2

RE2 , реализация регулярного выражения Google выполняет сопоставление по линейному времени (O(n), если n - длина строки), PCRE и большинство других механизмов регулярного выражения в худшем случае работают экспоненциально , Еще один заслуживающий внимания O(n) сопоставитель регулярных выражений - flex , но для него нужны все возможные регулярные выражения во время компиляции. Если вы ищете что-то меньшее, чем PCRE, посмотрите сопоставление регулярных выражений в busybox или сопоставление шаблонов в lua .

Answer 3

Вы можете попробовать TRE, если вас устраивает синтаксис регулярных выражений POSIX. Если вы хотите использовать синтаксис Perl, у Google есть новая реализация, которую стоит проверить.

Answer 4

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