如何规范化/规范化正则表达式模式？

Question

我有一个复杂的正则表达式,我用代码构建.我想将它规范化为最简单(规范)的形式,它将是一个等价的正则表达式但没有额外的括号等等.

我希望它被规范化,这样我就可以理解它是否正确并找到它中的错误.

以下是我想要规范化的正则表达式的示例:

^(?:(?:(?:\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]))*)))))*))))*))$

Answer 1

到目前为止,我正在接受其他答案和评论.即使您可以定义缩小形式,缩小形式也不太可能比这个更容易理解,这类似于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 +

...

一旦看起来它将更容易理解和优化.