php – 为给定的正则表达式创建所有可能的匹配集

`Hello?` -> (Hell,Hello)
`[1-9][0-9]{0,3}` -> (1,2,3 ...,9998,9999)
`My (cat|dog) is awesome!` -> (My cat is awesome!,My dog is awesome!)
`1{1,10}` -> (1,11,...,111111111,1111111111)
`1*` -> //error
`1+` -> //error
`(1|11){2}` -> (1,111,1111) //notice how it doesn't repeat any of the possibilities

从正则表达式转换为DFA是非常简单的.然而,您将遇到的问题是,生成的DFA可能包含循环(例如,用于*或),这将无法完全扩展.另外,{n,n}无法在DFA中进行干净的表示,因为DFA没有“循环”多少次的“内存”.

这个问题的一个解决方案就是建立一个函数来标记和解析正则表达式,然后返回所有可能的匹配的数组.在这里使用递归将帮助你很多.

一个起点,伪码,可能看起来像：

to GenerateSolutionsFor(regeX):
    solutions = [""]
    for token in TokenizeRegex(regeX):
        if token.isConstantString:
            for sol in solutions: sol.append(token.String)
        else if token.isLeftParen:
            subregex = get content until matching right paren
            subsols = GenerateSolutionsFor(subregeX)
            for sol in solutions:
                for subsol in subsols:
                    sol.append(subsol)
        else if token.isVerticalBar:
            solutions.add(GenerateSolutionsFor(rest of the regeX))
        else if token.isLeftBrace:
            ...