Comment détecter une logique circulaire ou une récursivité dans un évaluateur d'expressions personnalisées?

Question

J'ai écrit un évaluateur de fonction expérimental qui me permet de lier des fonctions simples de telle sorte que lorsque les variables changent, toutes les fonctions qui dépendent de ces variables (et les fonctions qui dépendent de ces fonctions, etc.) sont mises à jour simultanément. Pour ce faire, au lieu d'évaluer la fonction immédiatement telle qu'elle est entrée, je la stocke. Seulement quand une valeur de sortie est demandée, j’évalue la fonction et chaque fois qu’une valeur de sortie est demandée.

Par exemple:

pi = 3.14159
rad = 5
area = pi * rad * rad
perim = 2 * pi * rad

Je définis «pi» et «rad» comme variables (enfin, les fonctions qui retournent une constante), et «aire» et «périm» comme fonctions. Chaque fois que «pi» ou «rad» change, je m'attends à ce que les résultats de «area» et de «perim» changent en nature. De même, s’il existait des fonctions dépendant de la "zone" ou du "périm", les résultats seraient également différents.

Tout cela fonctionne comme prévu. Le problème ici est lorsque l'utilisateur introduit une récursivité - accidentelle ou intentionnelle. Il n'y a pas de logique dans ma grammaire - il s'agit simplement d'un évaluateur - je ne peux donc pas fournir à l'utilisateur un moyen de "rompre" la récursion. Je voudrais éviter que cela se produise, ce qui signifie que j'ai besoin d'un moyen de le détecter et de déclarer l'entrée en cause invalide.

Par exemple:

a = b
b = c
c = a

À l’heure actuelle, l’évaluation de la dernière ligne entraîne une exception StackOverflowException (alors que les deux premières lignes sont évaluées par un "0" - une variable / fonction non déclarée est égale à 0). Ce que je voudrais faire, c'est détecter la situation de logique circulaire et interdire à l'utilisateur de saisir une telle déclaration. Je veux le faire quelle que soit la profondeur de la logique circulaire, mais je ne sais pas comment faire.

En passant, les chaînes d'entrée sont converties en jetons via un simple scanner, puis en un arbre de syntaxe abstrait via un analyseur de descente récursif écrit à la main, puis l'AST est évalué. Le langage est C #, mais je ne cherche pas de solution de code - la logique seule suffira.

Remarque: il s’agit d’un projet personnel que j’utilise pour comprendre le fonctionnement des analyseurs syntaxiques et des compilateurs. Il n’est donc pas essentiel de la mission. Cependant, j’envisage de mettre à profit ce que je retiens de ce travail dans la vie réelle. . Toute aide que vous pourriez fournir serait grandement appréciée. =)

Modifier: Si vous êtes curieux, ce message sur mon blog décrit pourquoi j'essaie d'apprendre cela et ce que j'en retire.

Answer 1

J'ai eu un problème similaire à celui-ci dans le passé. Ma solution consistait à placer les noms de variables sur une pile à mesure que je revenais dans les expressions pour vérifier la syntaxe, puis à les extraire à la sortie d'un niveau de récursivité.

Avant de placer chaque nom de variable dans la pile, je vérifiais s'il était déjà présent. Si c'était le cas, il s'agissait d'une référence circulaire. J'ai même pu afficher les noms des variables dans la chaîne de référence circulaire (car elles figureraient dans la pile et pourraient être extraites en séquence jusqu'à ce que j'aie atteint le nom incriminé).

EDIT: Bien sûr, il s’agissait de formules simples ... Pour votre problème, un graphe cyclique d’assignations de variables serait la meilleure solution.

Answer 2

Une solution (probablement pas la meilleure) consiste à créer un graphique de dépendance.

Chaque fois qu'une fonction est ajoutée ou modifiée, le graphique de dépendance est vérifié pour les cycles.

Ceci peut être coupé court. Chaque fois qu'une fonction est ajoutée ou modifiée, marquez-la. Si l’évaluation appelle un appel à la fonction signalée, vous avez un cycle.

Exemple:

  

a = b

• marquer un
• eval b (non trouvé)
• unflag a

  

b = c

• drapeau b
• eval c (introuvable)
• unflag b

  

c = a

• drapeau c
• eval a
• eval b
• eval c (marqué) - > Cycle, abandonner le changement en c!
• unflag c

Answer 3

En réponse au commentaire de la réponse deux:

(Désolé, j'ai gâché ma création avec openid, je vais donc devoir relier les anciennes choses plus tard ...)

Si vous passez à " le drapeau " pour " pousser " et " unflag " pour "Pop", c'est à peu près la même chose :) Le seul avantage de l'utilisation de la pile est la facilité avec laquelle vous pouvez fournir des informations détaillées sur le cycle, quelle que soit la profondeur. (Utile pour les messages d'erreur :))

Andrew