Как я могу нормализовать / канонизировать шаблон регулярного выражения? - PullRequest
Новая
       6

Как я могу нормализовать / канонизировать шаблон регулярного выражения?

4 голосов
/ 26 июня 2010

У меня есть сложное регулярное выражение, которое я построил с помощью кода. Я хочу привести его к простейшей (канонической) форме, которая будет эквивалентным регулярному выражению, но без лишних скобок и т. Д.

Я хочу, чтобы оно было нормализовано, чтобы я мог понять, правильно ли оно, и находить в нем ошибки.

Вот пример для регулярного выражения, которое я хочу нормализовать: 

^(?:(?:(?:\r\n(?:[ \t]+))*)(<transfer-coding>(?:chunked|(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)(?:(?:;(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)=(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)|(?:"(?:(?:(?:|[^\x00-\x31\x127\"])|(?:\\[\x00-\x127]))*)))))*))))(?:(?:(?:\r\n(?:[ \t]+))*),(?:(?:\r\n(?:[ \t]+))*)(<transfer-coding>(?:chunked|(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)(?:(?:;(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)=(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)|(?:"(?:(?:(?:|[^\x00-\x31\x127\"])|(?:\\[\x00-\x127]))*)))))*))))*))$

Ответы [ 4 ]

12 голосов
/ 26 июня 2010

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

Если вы сделали хочу найти каноническую форму для регулярных выражений, я бы начал с точного определения того, что вы подразумеваете под "канонической формой".Например, предположим, что у вас есть регулярное выражение [ABCDEF-I].Является ли каноническая форма (1) [ABCDEF-I], (2) [ABCDEFGHI] или (3) [A-I]?

То есть, в целях канонизации, вы хотите (1) игнорировать это подмножество регулярных выражений для целей канонизации, (2) исключить все операторы "-", упрощая тем самым выражение, или (3) сделать его короче?

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

Однако это не обязательно будет делать то, что вы хотите.Если вам нужно реорганизовать регулярное выражение, чтобы минимизировать сложность группировки или что-то подобное, то вам может потребоваться канонизировать регулярное выражение, чтобы оно было в такой форме, чтобы оно имело только группировки, объединение и Kleene.звездные операторы.Как только он окажется в этой форме, вы можете легко перевести его в детерминированный конечный автомат, а когда он окажется в форме DFA, вы можете запустить алгоритм упрощения графиков в DFA, чтобы сформировать эквивалентный более простой DFA.Затем вы можете превратить полученный упрощенный DFA обратно в регулярное выражение.

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

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

Func<string, string> group = s=>"(?:"+s+")";
Func<string, string> capture = s=>"("+s+")";
Func<string, string> anynumberof = s=>s+"*";
Func<string, string> oneormoreof = s=>s+"+";
var beginning = "^";
var end = "$";
var newline = @"\r\n";
var tab = @"\t";
var space = " ";
var semi = ";";
var comma = ",";
var equal = "=";
var chunked = "chunked";
var transfer = "<transfer-coding>";
var backslash = @"\\";
var escape = group(backslash + @"[\x00-\x7f]");
var or = "|";
var whitespace = 
    group(
        anynumberof(
            group(
                newline +  
                group(
                    oneormoreof(@"[ \t]")))));
var legalchars = 
    group(
        oneormoreof(@"[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]"));

var re = 
    beginning + 
    group(
        whitespace + 
        capture(
            transfer + 
            group(
                chunked + 
                or + 
                group(
                    legalchars + 
                    group(
                        group(
                            semi + 
                            anynumberof(
                                group(
                                    legalchars + 
                                    equal +

...

Как только оно выглядит так, оно 'будет намного легче понять и оптимизировать.

3 голосов
/ 27 июня 2010

Я думаю, вы забегаете вперед; проблемы с этим регулярным выражением не просто косметические. Многие из скобок могут быть просто удалены, как в (?:[ \t]+), но я подозреваю, что некоторые из них изменяют значение регулярного выражения способами, которые вы не намеревались.

Например, что (?:|[^\x00-\x31\x127\"]) должно означать? С этим каналом в начале он эквивалентен [^\x00-\x31\x127\"]?? - нулю или единице, неохотно, из того, что соответствует классу персонажа. Это действительно то, что вы хотели?

Сам класс персонажа также очень подозрительный. Очевидно, что он должен совпадать с чем угодно, кроме управляющего символа ASCII или кавычки, но числа десятичные, где они должны быть шестнадцатеричными: [^\x00-\x1E\x7F\"]

2 голосов
/ 26 июня 2010

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

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

1 голос
/ 26 июня 2010

Я бы просто написал это в развернутом виде: 

^
(?:
  (?: (?: \r\n (?:[ \t]+) )* )
  (<transfer-coding>
    (?: chunked
     |  (?:
          (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)
          (?:
            (?:
              ;
              (?:
                (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)
                =
                (?: (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)
                 |  (?:
                      "
                      (?:
                        (?:
                          (?:
                           |  [^\x00-\x31\x127\"]
                           )
                         | (?:\\[\x00-\x127])
                         )*
                      )
                    )
                )
              )
            )*
          )
        )
    )
  )
  (?:
    (?: (?: \r\n (?:[ \t]+) )* )
    ,
    (?: (?: \r\n (?:[ \t]+) )* )
    (<transfer-coding>
      (?: chunked
       |  (?:
            (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)
            (?:
              (?:
                ;
                (?:
                  (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)
                  =
                  (?: (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)
                   |  (?:
                        "
                        (?:
                          (?:
                            (?:
                             |  [^\x00-\x31\x127\"]
                             )
                           | (?:\\[\x00-\x127])
                           )*
                        )
                      )
                  )
                )
              )*
            )
          )
      )
    )
  )
)
$

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

  • Отсутствует ? для именованных групп. Это должно быть (?<name> ).
  • Нет закрывающей двойной кавычки (").

Вы даже можете использовать регулярное выражение в этой форме. Если вы установите флаг RegexOptions.IgnorePatternWhitespace при создании объекта Regex, любые пробелы или комментарии (#) в шаблоне будут игнорироваться.

...