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

Изменить 2: Для практической демонстрации того, почему это остается важным, смотрите не далее, чем stackoverflow, вызванное регулярным выражением (2016-07-20)!

Изменить: Этот вопрос значительно изменился с тех пор, как я впервые спросил его. См. Ниже для двух быстрых + совместимых, но не полностью полнофункциональных реализаций. Если вы знаете больше или лучше реализаций, пожалуйста, укажите их, но пока еще не идеальная реализация!

Где можно найти надежную реализацию Regex?

Знает ли кто-нибудь о нормальной линейной реализации регулярного выражения без обратного отслеживания (System.Text.RegularExpressions) для .NET или родной и разумно используемой из .NET? Чтобы быть полезным, ему нужно было бы:

  • имеет временную сложность наихудшего вычисления регулярных выражений O (m * n), где m - длина регулярного выражения, а n - длина ввода.
  • имеют нормальную временную сложность O (n), так как почти никакие регулярные выражения фактически не вызывают экспоненциальное состояние-пространство, или, если они могут, делают это только на минутном подмножестве вход.
  • имеют разумную скорость построения (т.е. потенциально экспоненциальные DFA)
  • предназначено для использования людьми, а не математиками - например, Я не хочу переопределять классы символов юникода: Символьные классы стиля .NET или PCRE являются плюсом.

Бонусные баллы:

  • бонусные баллы для практичности, если он реализует функции на основе стека, которые позволяют обрабатывать вложенность за счет потребления памяти O (n + m), а не O (m).
  • бонусные баллы для или для захвата подвыражений или (если есть экспоненциальное число возможных совпадений подвыражения, то перечисление всех из них по своей сути экспоненциально - но перечисление первого малое не должно быть и аналогично для замены). Вы можете обходиться без какой-либо функции, используя другую, поэтому достаточно одного из них.
  • лот-бонусные баллы для обработки регулярных выражений как значений первого класса (так что вы можете принять объединение, пересечение, конкатенацию, отрицание - в частности, отрицание и пересечение, так как очень сложно выполнять строковые манипуляции определение регулярного выражения)
  • ленивое соответствие, т.е. совпадение в неограниченных потоках без помещения всего в память - плюс. Если потоки не поддерживают поиск, захват подвыражений и/или замены не могут (в общем) возможны за один проход.
  • Backreferences вне, они фундаментально ненадежны; то есть всегда могут экспоненциально воздействовать на случаи патологического ввода.

Такие алгоритмы существуют (это основная теория автоматов...) - но существуют ли практически доступные реализации, доступные из .NET?

Фон: (вы можете пропустить это)

Мне нравится использовать Regex для быстрого и грязного очищения текста, но я неоднократно сталкивался с проблемами, когда общее использование NFA, используемое perl/java/python/.NET, демонстрирует экспоненциальное поведение. К сожалению, эти случаи довольно легко вызвать, как только вы начнете автоматически генерировать регулярные выражения. Даже неэкспоненциальная производительность может стать чрезвычайно низкой при чередовании регулярных выражений, которые соответствуют одному и тому же префиксу - например, в действительно базовом примере, если вы возьмете словарь и превратите его в регулярное выражение, ожидайте ужасную производительность.

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

Не совсем практичные варианты:

  • Почти идеальный: Инструментарий FSA. Может компилировать регулярные выражения для быстрых реализаций C в DFA + NFA, также позволяет датчикам (!), Иметь регулярные выражения первого класса (инкапсуляция yay!), Включая синтаксис для пересечения и параметризации. Но это в прологе... (почему что-то с такими практическими функциями недоступно на основном языке?)
  • Быстрый, но непрактичный: полный парсер, например отличный ANTLRобычно поддерживает надежные быстрые регулярные выражения. Однако синтаксис antlr гораздо более подробен и, конечно же, позволяет создавать конструкции, которые не могут генерировать действительные парсеры, поэтому вам нужно найти некоторое безопасное подмножество.

Хорошие реализации:

  • RE2 - библиотека с открытым исходным кодом google, нацеленная на разумную совместимость с PCRE минус обратные ссылки. Я думаю, что это преемник unix-порта plan9 regex lib, данный автору.
  • TRE - также в основном совместим с PCRE и даже делает обратные ссылки, хотя с помощью тех, которые вы теряете гарантии скорости. И он имеет мега-отличный примерный режим соответствия!

К сожалению, обе реализации - это С++, и для взаимодействия с .NET требуется взаимодействие.

Ответы

Ответ 1

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

Единственное, о чем я буду комментировать, прежде чем продолжить, - это то, что я рекомендую вам задать вопрос о выборе использования RegEx. Вы явно более знакомы с вашей конкретной проблемой и тем, что пытаетесь решить, так что вы можете ответить на этот вопрос. Я не думаю, что ANTLR станет хорошей альтернативой; Тем не менее, механизм правил home- brew (если ограниченный по объему) может быть сильно настроен на ваши конкретные потребности. Все зависит от вашей конкретной проблемы.

Для тех, кто читает это и "отсутствует точка", вот несколько фоновых чтений:

На том же сайте существует ряд реализаций связанных на этой странице.

Суть всего обсуждения вышеприведенной статьи заключается в том, что лучшим ответом является использование обоих. С этой целью единственная широко используемая реализация, о которой я знаю, - это та, которая используется языком TCL. Насколько я понимаю, он был первоначально написан Генри Спенсером, и он использует этот гибридный подход. Было предпринято несколько попыток портировать его в библиотеку c, хотя я не знаю ни одного, широко используемого. Уолтер Уолдо и упоминаются Томас Лакнер и здесь. Также упоминается boost library, хотя я не уверен в реализации. Вы также можете посмотреть сам код TCL (связанный с их сайт) и работать оттуда.

Короче говоря, я бы пошел с TRE или Plan 9, поскольку они активно поддерживаются.

Очевидно, что ни один из них не является С#/. Net, и я не знаю того, что есть.

Ответ 2

Если вы можете обращаться с небезопасным кодом (и проблемой лицензирования), вы можете выполнить реализацию из этого окна TRE windows.

Возможно, вы сможете использовать это непосредственно с P/Invoke и явными структурами компоновки для следующего:

typedef int regoff_t;
typedef struct {
  size_t re_nsub;  /* Number of parenthesized subexpressions. */
  void *value;     /* For internal use only. */
} regex_t;

typedef struct {
  regoff_t rm_so;
  regoff_t rm_eo;
} regmatch_t;


typedef enum {
  REG_OK = 0,       /* No error. */
  /* POSIX regcomp() return error codes.  (In the order listed in the
     standard.)  */
  REG_NOMATCH,      /* No match. */
  REG_BADPAT,       /* Invalid regexp. */
  REG_ECOLLATE,     /* Unknown collating element. */
  REG_ECTYPE,       /* Unknown character class name. */
  REG_EESCAPE,      /* Trailing backslash. */
  REG_ESUBREG,      /* Invalid back reference. */
  REG_EBRACK,       /* "[]" imbalance */
  REG_EPAREN,       /* "\(\)" or "()" imbalance */
  REG_EBRACE,       /* "\{\}" or "{}" imbalance */
  REG_BADBR,        /* Invalid content of {} */
  REG_ERANGE,       /* Invalid use of range operator */
  REG_ESPACE,       /* Out of memory.  */
  REG_BADRPT            /* Invalid use of repetition operators. */
} reg_errcode_t;

Затем используйте экспорт, способный обрабатывать строки со встроенными нулями (с широкой поддержкой символов)

/* Versions with a maximum length argument and therefore the capability to
   handle null characters in the middle of the strings (not in POSIX.2). */
int regwncomp(regex_t *preg, const wchar_t *regex, size_t len, int cflags);

int regwnexec(const regex_t *preg, const wchar_t *string, size_t len,
      size_t nmatch, regmatch_t pmatch[], int eflags);

Альтернативно оберните его с помощью решения С++/CLI для упрощения перевода и большей гибкости (я бы, конечно, предложил, чтобы это было разумно, если вам было удобно с С++/CLI).

Ответ 3

Где я могу найти надежную реализацию Regex?

Вы не можете.

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

Btw, я уверен, что вы уже так пробовали, но вы скомпилировали регулярное выражение (с возможностью вывода на сборку) - я говорю, потому что:

если у вас есть сложное Regex и миллионы коротких строк для тестирования

Ответ 4

Рассмотрим, как DFAs создаются из регулярных выражений:

Вы начинаете с регулярного выражения. Каждая операция (concat, union, Kleene clos) представляет собой переход между состояниями в NFA. Результирующие состояния DFA представляют собой силовые наборы состояний в NFA. Состояния в NFA линейны по размеру регулярного выражения, поэтому состояния DFA экспоненциальны по размеру регулярного выражения.

Итак, ваше первое ограничение,

имеют худшую временную сложность оценки регулярных выражений O (m * n), где m - длина регулярного выражения, n - длина ввода

Невозможно. Регулярное выражение должно быть скомпилировано в DFA (в худшем случае) 2 ^ m-состояния, которое не будет выполняться в линейном времени.

Это всегда относится ко всем, кроме простейших регулярных выражений. Вы так просто можете просто написать быстрое выражение .contains.

Ответ 5

Быстрый комментарий: Просто потому, что вы можете имитировать конструкцию DFA путем моделирования с несколькими состояниями, не означает, что вы не выполняете работу преобразования NFA-DFA. Разница в том, что вы распространяете усилия над самим поиском. I.e., наихудшая производительность не изменилась.