如何将字符串列表编译为紧凑的正则表达式？

先举几个例子说明需求：

基础场景 #

• 输入字符串：'Example', 'DOMNode', 'DOMText', 'DOMElement'
• 期望输出：(Example|DOM(Node|Text|Element))

进阶场景（两端匹配公共部分） #

• 输入字符串：'Example', 'ArrayIterator', 'RecursiveArrayIterator', 'DirectoryIterator', 'RecursiveDirectoryIterator'
• 期望输出：(Example|(Recursive)?(Array|Directory)Iterator)

我有一组需要匹配的目标字符串，目前是直接用交替符|拼接成正则表达式，但希望能提取公共前缀/后缀，合并成更简洁的分组结构。这只是练手项目，但卡壳好久了。

我试过拆分字符、匹配各种组合，熬了好几天夜，记不清所有尝试过的方法了，就是找不到能提取公共部分并重建正则的正确思路。

我有个处理下划线分隔字符串的函数，按下划线拆分前缀时效果不错：

<?php
/**
 * separates snake case names into nested hierarchies.
 */
function processArray(array $funcs): array
 {
    $loop = false;
    $current = false;
    $newFuncs = [];
    foreach ($funcs as $name)
     {
        $pos = strpos($name, '_');
        if ($current and !str_starts_with($name, $current))
         {
            if ($loop || $pos)
             {
                $newFuncs[$current] = processArray($newFuncs[$current]);
                $loop = false;
             }
            $current = false;
         }
        if ($pos)
         {
            $current = substr($name, 0, $pos + 1);
            $newFuncs[$current] ??= [];
            $subName = substr($name, $pos + 1);
            $newFuncs[$current][] = $subName;
            if (strpos($subName, '_'))
             {
                $loop = true;
             }
         }
        else
         {
            if ($loop)
             {
                $newFuncs[$current] = processArray($newFuncs[$current]);
                $loop = false;
             }
            $current = false;
            $newFuncs[] = $name;
         }
     }
    return $newFuncs;
 }

function getRegex(array $strs): string
 {
    static $level = 0;
    $ret = '(';
    foreach ($strs as $key => $value)
     {
        if (is_array($value))
         {
            $strs[$key] = (is_string($key)?$key:'').getRegex($value);
         }
     }
    $ret.= implode('|', $strs);
    $ret.= ')';
    return $ret;
 }


$funcs = get_defined_functions()['internal'];
sort($funcs);

$funcs = processArray($funcs);
$getRegex = getRegex($funcs);

//remove isolated groups (groups with only one alternation)
do
 {
    $getRegex = preg_replace('~\(([a-zA-Z_0-9]+?)\)~', '$1', $getRegex, -1, $count);
 } 
while ($count);

var_dump($getRegex);

我已经接近解决问题，但遇到了新情况：当存在可选部分时，会在可选字符串前生成空交替项，导致正则优先匹配空值，无法正确匹配带可选内容的字符串。比如生成的My(|Opt)无法匹配MyOpt。

以下是当前的实现代码：

function processRegexArray(array $funcs): array
 {
    $loop = false;
    $current = false;
    $newFuncs = [];
    foreach ($funcs as $name)
     {
        preg_match('~^([A-Z]+(?=[A-Z])|[A-Z0-9_]*[a-z]+)~', $name, $matches);
        $pos = strlen($matches[0]??='') -1;
        if ($current and !str_starts_with($name, $current))
         {
            if ($loop || $pos)
             {
                $newFuncs[$current] = processRegexArray($newFuncs[$current]);
                $loop = false;
             }
            $current = false;
         }
        if ($pos)
         {
            $current = substr($name, 0, $pos + 1);
            $newFuncs[$current] ??= [];
            $subName = substr($name, $pos + 1);
            $newFuncs[$current][] = $subName;
            preg_match('~^([A-Z]+(?=[A-Z])|[A-Z0-9_]*[a-z]+)~', $subName, $matches);
            if ($matches)
             {
                $loop = true;
             }
         }
        else
         {
            if ($loop)
             {
                $newFuncs[$current] = processRegexArray($newFuncs[$current]);
                $loop = false;
             }
            $current = false;
            $newFuncs[] = $name;
         }
     }
    return $newFuncs;
 }

function getRegex(array $strs): string
 {
    if (count($strs) === 0)
        return '';
    static $level = 0;
    $ret = '(';
    foreach ($strs as $key => $value)
     {
        if (is_array($value))
         {
            $strs[$key] = (is_string($key)?$key:'').getRegex($value);
         }
     }
    $ret.= implode('|', $strs);
    $ret.= ')';
    return $ret;
 }

$members = [...get_declared_classes(), ...get_declared_interfaces(), ...get_declared_traits()];
sort($members);

// remove namespaced names for now
foreach ($members as $key => $value)
 {
    if (strpos($value, '\\') !== false)
     {
        unset($members[$key]);
     }
 }
$members = processRegexArray($members);

$getRegex = getRegex($members);
do
 {
    $getRegex = preg_replace('~\(([^|()]*?)\)~', '$1', $getRegex, -1, $count);
 } 
while ($count);
var_dump($getRegex);

预期输出 #

string(2302) "(AllowDynamicProperties|AppendIterator|ArgumentCountError|ArithmeticError|Array(Access|Iterator|Object)|AssertionError|Attribute|BackedEnum|Bad(FunctionCallException|MethodCallException)|CURL(File|StringFile)|CachingIterator|CallbackFilterIterator|ClosedGeneratorException|Closure|CompileError|Countable|Curl(Handle|MultiHandle|ShareHandle)|DOM(Attr|CdataSection|CharacterData|ChildNode|Comment|Document|DocumentFragment|DocumentType|Element|Entity|EntityReference|Exception|Implementation|NameSpaceNode|NamedNodeMap|Node|NodeList|Notation|ParentNode|ProcessingInstruction|Text)|DOMXPath|Date(Interval|Period|Time(|Immutable|Interface|Zone))|DeflateContext|Directory(|Iterator)|DivisionByZeroError|DomainException|EmptyIterator|Error(|Exception)|Exception|Fiber(|Error)|FilesystemIterator|FilterIterator|Generator|GlobIterator|HashContext|InfiniteIterator|InflateContext|InternalIterator|InvalidArgumentException|Iterator(|Aggregate|Iterator)|Json(Exception|Serializable)|LengthException|LibXMLError|LimitIterator|LogicException|MultipleIterator|NoRewindIterator|Open(SSL(AsymmetricKey|Certificate|CertificateSigningRequest))|Out(OfBoundsException|OfRangeException)|OuterIterator|OverflowException|PDO|PDO(Exception|Row|Statement)|ParentIterator|ParseError|Phar(|Data|Exception|FileInfo)|PhpToken|RangeException|Rar(Archive|Entry|Exception)|Recursive(ArrayIterator|CachingIterator|CallbackFilterIterator|DirectoryIterator|FilterIterator|Iterator(|Iterator)|RegexIterator|TreeIterator)|Reflection(|Attribute|Class(|Constant)|Enum(|BackedCase|UnitCase)|Exception|Extension|Fiber|Function(|Abstract)|Generator|IntersectionType|Method|NamedType|Object|Parameter|Property|Reference|Type|UnionType|ZendExtension)|Reflector|RegexIterator|ReturnTypeWillChange|RuntimeException|SeekableIterator|Sensitive(Parameter(|Value))|Serializable|Session(Handler(|Interface)|IdInterface|UpdateTimestampHandlerInterface)|Simple(XML(Element|Iterator))|Spl(DoublyLinkedList|File(Info|Object)|FixedArray|Heap|MaxHeap|MinHeap|ObjectStorage|Observer|PriorityQueue|Queue|Stack|Subject|TempFileObject)|Stringable|Throwable|Traversable|TypeError|UnderflowException|UnexpectedValueException|UnhandledMatchError|UnitEnum|ValueError|Weak(Map|Reference)|XML(Parser|Reader|Writer)|__PHP_Incomplete_Class|finfo|php_user_filter|stdClass)"

内容的提问来源于stack exchange，提问作者yarns