Je développe un programme qui extrait du texte d'autres programmes. L'une des fonctionnalités est que les utilisateurs peuvent spécifier des "scripts de remplacement" pour traiter le texte. Exemple de script de rechange:
|ORIG|a|BECOMES|bb|END| |ORIG|b|BECOMES|aa|END|
3 Réponses :
Vous pouvez essayer de créer un graphique avec les nœuds représentant vos scripts et des bords de remplacement connectant un script avec un autre si le premier script fait partie du devient du second script.
Ensuite, vous pouvez rechercher des boucles dans ce graphique, vous indiquant que votre peut être indéfiniment appliquer les règles de cette boucle.
Qui échoue sur un script comme celui-ci: | Orig | A | devient | B | Fin || Orig | C | devient | b | bb | devient | ACAC | FIN | depuis No devient a bb .
Avec vos scripts de remplacement, vous pouvez efficacement modéliser une grammaire de type-0 pour laquelle vous avez dû décider si la langue générée est finie (c'est-à-dire que vous ne pouvez faire que de nombreuses étapes pour atteindre chaque résultat de remplacement possible), ce qui est, autant que je sache , non décritable.
Si une origine est égale ou une sous-chaîne de tout devient alors que vous pourriez avoir des problèmes.
Mais le premier script de remplacement de la question a cela, et il ne peut clairement pas boucler infiniment. Je suppose que je pourrais jeter beaucoup d'avertissements faux positifs, mais j'aimerais vraiment faire mieux.
Comme mentionné dans un commentaire, mes scripts de remplacement sont réellement complètes. Ainsi, la question réduit le problème d'arrêt et est insoluble.
Je ne suis pas un scientifique informatique, mais j'ai un sentiment que cela n'est pas possible. La détection d'une boucle en cours d'exécution ne serait possible que si vous pouvez stocker chaque version de la sortie lors de l'exécution, nécessitant un stockage infini. Détecter une boucle potentielle en analysant le script ne me semble tout simplement pas possible. Vous pouvez détecter des négatifs, mais pas tous les positifs, je pense. Cela rappelle le problème d'arrêt.
Pourquoi avez-vous besoin de gérer les règles tout le temps? Je penserais que c'est plus naturel pour que l'utilisateur exécute les règles de remplacement une fois dans l'ordre de leur définition.