Улучшение / Исправление регулярных выражений для комментариев в стиле C

Question

Я пишу (в C #) простой синтаксический анализатор для обработки языка сценариев, который очень похож на классический C.

В одном имеющемся у меня файле сценария регулярное выражение, которое я использую для распознавания / * блочных комментариев * /, входит в какой-то бесконечный цикл, принимая 100% CPU на века.

Используемое мной регулярное выражение:

/\*([^*]|[\r\n]|(\*+([^*/]|[\r\n])))*\*+/

Любые предложения о том, почему это может быть заблокировано?

В качестве альтернативы, какое еще регулярное выражение я мог бы использовать вместо этого?

Дополнительная информация:

• Работа в C # 3.0 с ориентацией на .NET 3.5;
• Я использую метод Regex.Match (string, int), чтобы начать сопоставление с определенным индексом строки;
• Я оставил программу работающей более часа, но матч не завершен;
• Опции, передаваемые в конструктор Regex: RegexOptions.Multiline и RegexOptions.IgnorePatternWhitespace;
• Регулярное выражение правильно работает для 452 моих 453 тестовых файлов.

Answer 1

Некоторые проблемы, которые я вижу с вашим регулярным выражением:

Нет необходимости в последовательностях |[\r\n] в вашем регулярном выражении; класс отрицанных символов, такой как [^*], соответствует всему, кроме *, включая разделители строк. Только метасимвол . (точка) не соответствует им.

Как только вы окажетесь внутри комментария, единственный символ, который вам нужно искать, это звездочка; если вы не видите ни одного из них, вы можете сожрать столько символов, сколько захотите. Это означает, что нет смысла использовать [^*], когда вместо него можно использовать [^*]+. На самом деле, вы могли бы также поместить это в атомарную группу - (?>[^*]+) - потому что у вас никогда не будет причин отказаться от каких-либо звездочек, как только вы их сопоставите.

Отфильтровывая посторонние ненужные вещи, последняя альтернатива внутри ваших крайних парней - \*+[^*/], что означает «одну или несколько звездочек, за которыми следует символ, который не является звездочкой или косой чертой». Это всегда будет совпадать со звездочкой в ​​конце комментария, и ему всегда придется снова отказываться от него, потому что следующий символ - косая черта. Фактически, если до финального слеша есть двадцать звездочек, эта часть вашего регулярного выражения будет соответствовать всем им, тогда она откажется от всех по очереди. Тогда последняя часть - \*+/ - будет соответствовать им по крепости.

Для максимальной производительности я бы использовал это регулярное выражение:

/\*(?>(?:(?>[^*]+)|\*(?!/))*)\*/

Это будет соответствовать правильно сформированному комментарию очень быстро, но что более важно, если оно начинает совпадать с чем-то, что не является действительным комментарием, оно потерпит неудачу как можно быстрее.

---

Предоставлено Дэвид , вот версия, которая соответствует вложенным комментариям с любым уровнем вложенности:

(?s)/\*(?>/\*(?<LEVEL>)|\*/(?<-LEVEL>)|(?!/\*|\*/).)+(?(LEVEL)(?!))\*/

Он использует балансировочные группы .NET, поэтому он не будет работать ни в каком другом варианте. Для полноты приведем еще одну версию (из библиотеки RegexBuddy), в которой используется синтаксис рекурсивных групп, поддерживаемый Perl, PCRE и Oniguruma / Onigmo:

/\*(?>[^*/]+|\*[^/]|/[^*])*(?>(?R)(?>[^*/]+|\*[^/]|/[^*])*)*\*/

Answer 2

Нет, нет, нет! Разве никто не читал «Освоение регулярных выражений» (3-е издание) !? В этом Джеффри Фридл исследует эту проблему и использует ее в качестве примера (стр. 272-276), чтобы проиллюстрировать свою технику «раскручивания петли». Его решение для большинства двигателей регулярных выражений выглядит так:

/\*[^*]*\*+(?:[^*/][^*]*\*+)*/

Однако, если механизм регулярных выражений оптимизирован для обработки ленивых квантификаторов (как это делает Perl), то наиболее эффективное выражение намного проще (как предложено выше):

/\*.*?\*/

(Конечно, с примененным модификатором '' точка соответствует всем ''). Обратите внимание, что я не использую .NET, поэтому я не могу сказать, какая версия быстрее для этого движка.

Answer 3

Возможно, вы захотите попробовать опцию Singleline, а не Multiline, тогда вам не нужно беспокоиться о \ r \ n. С этим включением у меня сработало следующее простое испытание, включавшее комментарии, которые занимали более одной строки:

/\*.*?\*/

Answer 4

Я использую это в данный момент

\/\*[\s\S]*?\*\/

Answer 5

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

Если основное предположение состоит в том, чтобы соответствовать всему от "/*" до первого "*/", то один из способов сделать это - это (как обычно, регулярное выражение не подходит для вложенных структур, поэтому комментарии вложенного блока не работает):

/\*(.(?!\*/))*.?\*/             // run this in single line (dotall) mode

По сути, это говорит: "/*", за которым следует все, что само по себе не сопровождается "*/", за которым следует "*/".

В качестве альтернативы вы можете использовать более простое:

/\*.*?\*/                       // run this in single line (dotall) mode

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