¿Puedo determinar el conjunto de primeros caracteres coincidentes por el patrón regex?

Question

Me gustaría poder calcular el conjunto de todos los caracteres que pueden coincidir como el primero personaje en una cadena por una instancia dada de java.util.regex.Pattern. Más formalmente, dado el DFA equivalente a una determinada expresión regular, quiero el conjunto de todas las transiciones salientes del estado de inicio.

Un ejemplo:

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

El conjunto first debe contener los siguientes elementos:

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

¿Algunas ideas? Soy muy consciente de que podría construir el DFA y determinar los estados relevantes de esa manera, pero me gustaría evitar ese tipo de problemas (léase: no vale mucho para mí). Tenga en cuenta que mi lenguaje de host es en realidad Scala, por lo que tengo acceso a todos los bibliotecas de Scala Core (por lo que vale).

Answer 1

Creo que podría analizar la expresión regular y definir una función recursiva que opera en la expresión regular analizada en un hombre de izquierda a derecha, construyendo un conjunto de primeros.

Algunas cosas son simples:

• Secuencia: primero (r1r2) = primero (r1) + (if '' en primero (r1) primero (r2) más vacío conjunto)
• Alternancia: Primero (R1 | R2) = Primero (R1) + First (R2)
• Iteración: primero (r*) = primero (r) + ''
• Caracteres: primero (c) = c
• Clases de caracteres: primero ([C1-cn]) = set (C1, C2, ..., CN) ...

Extienda esto a todas las primitivas y banderas especiales que su dialecto de expresión regular sabe y está listo para comenzar.

Answer 2

Podrías resolverlo recursivamente ...

• Franja de encerrar paréntesis y llamada recursivamente.
• Dividirse en alternativas Toplevel y llamar recursivamente para cada parte.
• Si no hay alternativas,
  • Salga todos los símbolos que comienzan desde la izquierda hasta el primer símbolo opcional ninguno.
  • Si hay grupos Charachter, envíe todos los símbolos.

Probablemente hay muchos errores en esta idea, pero esto es lo que intentaría. Tienes que eliminar la afirmación, los nombres de grupo y mil otras cosas. Y si encuentra una clase de caracteres invertida como [^0-9], debe generar muchos caracteres.

Así que supongo que es realmente un problema complejo.