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

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

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

Я использую Regex:

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

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

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

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

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

Ответы

Ответ 1

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

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

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

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

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

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

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

Предоставлено David, здесь версия, соответствующая вложенным комментариям с любым уровнем вложенности:

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

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

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

Ответ 2

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

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

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

/\*.*?\*/

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

Ответ 3

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

/\*.*?\*/

Ответ 4

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

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

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

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

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

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

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

Ответ 5

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

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