Online PHP editor | output for BY44p

<?php class Element { const TYPE_LITERAL = 0; const TYPE_GROUP = 1; const END_OF_STRING = 2; public $type; public $value; public $next = self::END_OF_STRING; } function buildGraph($tokens) { $root = new Element; $root->type = Element::TYPE_GROUP; while ( $tokens->valid() ) { $token = $tokens->current(); $tokens->next(); switch ($token) { case '(': if ( isset($current) ) { $current->next = buildGraph($tokens); $current = $current->next; } else { $root->value[] = buildGraph($tokens); $current = end($root->value); } break; case ')': $current->next = &$root->next; return $root; case '|': $current->next = &$root->next; unset($current); break; default: if ( isset($current) ) { $current->next = new Element; $current = $current->next; } else { $root->value[] = new Element; $current = end($root->value); } $current->type = Element::TYPE_LITERAL; $current->value = $token; } } $root->next = Element::END_OF_STRING; return $root; } function getPaths($elt, $prefix = '') { if ( $elt === Element::END_OF_STRING ) { yield $prefix; return; } switch($elt->type) { case Element::TYPE_LITERAL: $prefix .= $elt->value; yield from getPaths($elt->next, $prefix); break; case Element::TYPE_GROUP: foreach ($elt->value as $value) { yield from getPaths($value, $prefix); } break; } } $pattern = 'chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a)'; // validation $validationPattern = '~ \A ( [^()]+ | $ (?1)* $ )* \z ~x'; if ( !preg_match($validationPattern, $pattern) ) throw new Exception('invalid pattern.'); // tokenization $tokens = (function ($regex) { if ( preg_match_all('~ [^()|]+ | (?<![^(|]) (?![^|)]) | [()|] ~x', $regex, $matches) ) yield from $matches[0]; })($pattern); $graph = buildGraph($tokens); foreach (getPaths($graph) as $path) { echo $path, PHP_EOL; }