Je ne comprends pas bien encore ... En gros ce que tu dis c'est que tu as un arbre dans lequel les informations peuvent faire référence à des objets éloignés dans l'arbre ?
Si tu veux vérifier que l'expression est valide (ne fait référence qu'à des noeuds qui existent), ta sémantique c'est « l'expression est valide » (un booléen). Seulement, comme tu peux faire référence à des objets éloignés, cette information est contextuelle. La solution pour faire un unique parcours est de dé-contextualiser cette information en ajoutant plus de choses. Par exemple, un Set représentant tous les noms accessibles dans le sous arbre (ce qui change la complexité du parcours). Tu ne peux pas dire si une expression est correcte, mais tu peux dire à qui elle fait référence. Ainsi, ta sémantique serait un couple (variable_referencees, variables_declarees).
À la fin du calcul, on peut regarder si les variables référencées sont incluses dans les variables déclarées. Ce qui détermine si c'est bien typé ou non.
L'idée c'est d'ajouter suffisamment d'information dans le domaine de sortie pour construire l'information qui nous intéresse après en une seule étape et de manière indépendante de la structure qui l'a engendrée.
Si l'insertion dans ton set est en log n, comme tu fais autant d'insertions (dans le pire des cas) que la taille de l'arbre tu obtiens un truc dans le style du O( n log n) où n est le nombre de noeuds dans l'arbre. Ensuite une petite inclusion d'ensembles ce qui n'est normalement pas trop méchant (un peu plus que linéaire ?).
[^] # Re: Dans l'art voluptueuse de ne rien comprendre
Posté par Aluminium95 . En réponse au journal EDSL et F-algèbres. Évalué à 2.
Je ne comprends pas bien encore ... En gros ce que tu dis c'est que tu as un arbre dans lequel les informations peuvent faire référence à des objets éloignés dans l'arbre ?
Si tu veux vérifier que l'expression est valide (ne fait référence qu'à des noeuds qui existent), ta sémantique c'est « l'expression est valide » (un booléen). Seulement, comme tu peux faire référence à des objets éloignés, cette information est contextuelle. La solution pour faire un unique parcours est de dé-contextualiser cette information en ajoutant plus de choses. Par exemple, un
Setreprésentant tous les noms accessibles dans le sous arbre (ce qui change la complexité du parcours). Tu ne peux pas dire si une expression est correcte, mais tu peux dire à qui elle fait référence. Ainsi, ta sémantique serait un couple(variable_referencees, variables_declarees).À la fin du calcul, on peut regarder si les variables référencées sont incluses dans les variables déclarées. Ce qui détermine si c'est bien typé ou non.
L'idée c'est d'ajouter suffisamment d'information dans le domaine de sortie pour construire l'information qui nous intéresse après en une seule étape et de manière indépendante de la structure qui l'a engendrée.
Si l'insertion dans ton set est en
log n, comme tu fais autant d'insertions (dans le pire des cas) que la taille de l'arbre tu obtiens un truc dans le style duO( n log n)oùnest le nombre de noeuds dans l'arbre. Ensuite une petite inclusion d'ensembles ce qui n'est normalement pas trop méchant (un peu plus que linéaire ?).