Posso determinar o conjunto de primeiros chars correspondidos pelo padrão regex?

Question

Eu gostaria de poder calcular o conjunto de todos os personagens que podem ser correspondidos como o primeiro personagem em uma string por uma determinada instância de java.util.regex.Pattern. Mais formalmente, dado o DFA equivalente a uma certa expressão regular, quero o conjunto de todas as transições de saída do estado de início.

Um exemplo:

Pattern p = Pattern.compile("[abc]def|daniel|chris|\\s+");
Set<Character> first = getFirstSet(p);

O conjunto first deve conter os seguintes elementos:

{ 'a', 'b', 'c', 'd', ' ', '\n', '\r', '\t' }

Alguma ideia? Estou ciente de que eu mesmo poderia construir o DFA e determinar os estados relevantes dessa maneira, mas gostaria de evitar esse tipo de aborrecimento (leia: não vale muito para mim). Observe que meu idioma host é realmente scala, então tenho acesso a todas as Libs Core Scala (pelo que vale a pena).

Answer 1

Eu acho que você poderia analisar a expressão regular e definir uma função recursiva que opera na expressão regular analisada em um gerente da esquerda para a direita, construindo um conjunto de primeiros.

Algumas coisas são simples:

• Sequência: primeiro (r1r2) = primeiro (r1) + (se '' no primeiro (r1) primeiro (r2) else o conjunto vazio)
• Alternância: primeiro (r1 | r2) = primeiro (r1) + primeiro (r2)
• Iteração: primeiro (r*) = primeiro (r) + ''
• Caracteres: primeiro (c) = c
• CaracterClasses: Primeiro ([C1-CN]) = set (C1, C2, ..., CN) ...

Estenda isso a todos os primitivos e sinalizadores especiais que seu dialeto de expressão regular sabe e você está pronto para ir.

Answer 2

Você pode resolver isso recursivamente ...

• Faixa de parênteses encerradas e chamado recursivamente.
• Divida em alternativas de Toplevel e chame recursivamente para cada parte.
• Se não houver alternativas,
  • Saia todos os símbolos que começam da esquerda até o primeiro símbolo opcional.
  • Se houver grupos Charachter, produza todos os símbolos.

Provavelmente existem muitos erros nessa idéia, mas é isso que eu tentaria. Você tem que retirar a afirmação, nomes de grupos e mil outras coisas. E se você encontrar uma classe de caracteres invertida como [^0-9], precisará gerar muitos caracteres.

Então, presumo que seja realmente um problema complexo.