Puis-je déterminer l'ensemble de la première Chars abondés par Regex Motif?

Question

Je voudrais être en mesure de calculer l'ensemble de tous les caractères qui peuvent être assortis comme premier caractère dans une chaîne par une instance donnée de java.util.regex.Pattern. Plus formellement, étant donné l'équivalent DFA à une certaine expression régulière, je veux l'ensemble de toutes les transitions sortantes de l'état de départ.

Un exemple:

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

L'ensemble first doit contenir les éléments suivants:

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

Toutes les idées? Je suis bien conscient que je pouvais construire le DFA moi-même et déterminer les états concernés de cette façon, mais je voudrais éviter ce genre de tracas (lire: il ne vaut pas grand-chose à moi). Notez que ma langue d'accueil est en fait Scala, donc j'avoir accès à tous les libs Scala de base (pour ce que ça vaut).

Answer 1

Je pense que vous pouvez analyser l'expression régulière et définir une fonction récursive qui fonctionne sur l'expression régulière analysable en-gauche de manière à droite, la construction d'un tel ensemble de premières fois.

Certaines choses sont simples:

• Séquence: première (R1R2) = premier (r1) + (si '' en premier (r1) premier (r2) autre ensemble vide)
• Alternance: premier (r1 | r2) = premier (r1) + premier (r2)
• Itération: un premier (R *) = premier (r) + ''
• Caractères: d'abord (c) = c
• Characterclasses: premier ([c1-cn]) = ensemble (c1, c2, ..., cn) ...

étendre à toutes les primitives et des drapeaux spéciaux votre dialecte d'expression régulière et vous êtes sait bien aller.

Answer 2

Vous pouvez résoudre récursivement ...

• bande d'enfermer entre parenthèses et appeler récursivement.
• Split à des alternatives et toplevel appeler récursivement pour chaque partie.
• S'il n'y a pas d'autres solutions,
  • sortie tous les symboles à partir de la gauche au premier pas symbole en option.
  • S'il y a des groupes charachter, sortie tous les symboles.

Il y a probablement beaucoup d'erreurs dans cette idée, mais ce que je voudrais essayer. Vous devez dépouiller l'affirmation, les noms de groupe et mille autres choses. Et si vous trouvez une classe de caractère inversé comme [^ 0-9] vous avez à la sortie beaucoup de caractères.

Je suppose que c'est vraiment un problème complexe.