Le langage des expressions régulières a-t-il besoin d'un automate push down pour l'analyser?

Je souhaite convertir une expression régulière entrée par l'utilisateur en NFA afin de pouvoir ensuite exécuter le NFA sur une chaîne à des fins de correspondance. Quelle est la machine minimale qui peut être utilisée pour analyser des expressions régulières?

Je suppose que ce doit être un automate push down car la présence de parenthèses signifie la nécessité de compter et un DFA / NFA ne peut pas effectuer de comptage arbitraire. Cette hypothèse est-elle correcte? Par exemple, l'expression a (bc *) d nécessiterait un PDA pour que la sous-expression entre crochets soit correctement gérée.

Vous avez raison. Il est facile de montrer que la syntaxe des expressions régulières n'est pas régulière en utilisant des techniques standard .

Une possibilité est d'utiliser un homomorphisme (contre lequel est fermé) pour se débarrasser de tous les symboles sauf les parenthèses, ce qui vous laisse avec le langage Dyck qui est bien connu pour être non régulier. En cas de doute, utilisez le lemme de pompage sur .$\mathrm{REG}$$(^p)^p$

Cela dit, vous ne voulez probablement pas coder un PDA à la main. Pensez à utiliser un générateur d'analyseur comme ANTLR ou byacc . Si, d'autre part, vous souhaitez étudier l'analyse des langues en programmant vous-même les analyseurs, vous devez continuer avec d'autres algorithmes d'analyse de base tels que CYK , Earley , descendance récursive et LR .

Je vous suggère de lire également la belle réponse de Jukka à la question " Faire correspondre des expressions régulières à l'aide d'expressions régulières " sur cstheory. Un extrait:

Par exemple, nous pouvons modifier la notation standard comme suit pour obtenir des expressions régulières "compressées" :

• Vous êtes autorisé à supprimer tout préfixe composé d'une séquence de (
• Vous êtes autorisé à supprimer tout suffixe composé d'une séquence de)

Autrement dit, ((a|b)*c)de(f|g)peut être exprimé dans la notation "compressée" en utilisant, par exemple, l'une des formes suivantes: a|b)*c)de(f|gou ((a|b)*c)de(f|gou (a|b)*c)de(f|g).

[...]

La notation "compressée" (d'une expression régulière) est un langage régulier.

Ce n'est qu'un lien vers une "vue différente" intéressante (selon moi) sur le langage des expressions régulières; comme souligné dans les commentaires ci-dessous, il n'est pas utile pour construire un arbre de syntaxe. Si vous voulez coder manuellement votre analyseur, je vous proposerai cet article simple sur le projet de code " Ecrire-propre-expression-parseur ".