Problème avec récursion écrire un petit analyseur en Haskell. Vérifiez les variables

Question

Je travaille toujours sur un petit analyseur pour une langue minuscule définie dans une tâche à l'école. L'analyseur syntaxique qui génère un AST (arbre de syntaxe abstraite) fonctionne. Ce que je veux est de vérifier les variables définies, elles doivent être limitées par l'expression let. D'abord la méthode qui est définie dans la tâche (suggestion, pas nécessaire):

checkVars :: Expr -> Char 

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
    deriving(Eq, Show) 

Une phrase valide serait "soit X 5 dans * (2, X)". X serait normalement un Var et 5 est normalement un int. Et la dernière peut être une partie du type dataExpr. Point principal: X est utilisé quelque part dans la dernière expression Le type de données pour let est:.

Let Expr Expr Expr

Lien vers les autres questions que j'ai posé des questions sur cette tâche ici juste FYI; Première question Deuxième

Comme vous le voyez le type de données aux checkVars est Expr, alors voici un exemple de ce que je nourrir à cette fonction:

parseProg "let X be 4 in let Y be *(2 , X) in let Z be +(Y , X) in
+(+(X , Y) , Z)"
Let (Var 'X') (Tall 4) (Let (Var 'Y') (Mult (Tall 2) (Var 'X')) (Let
(Var 'Z') (Sum (Var 'Y') (Var 'X')) (Sum (Sum (Var 'X') (Var 'Y')) (Var
'Z'))))
Just 24

Ceci est un exemple tout compris, la partie supérieure est la chaîne / programme en cours d'analyse. La deuxième partie, à partir de la ligne 3 (LET) est l'AST, l'entrée pour la fonction checkVars. Et la partie inférieure « Juste 24 » est l'évaluation. Ce que je serai de retour ici pour plus d'aide pour. Note: Le point est de cracher sur la première variable non trouvé comme une erreur, et « » si tout va bien. Il est évident que si vous voulez faire une autre façon que vous pouvez.

Answer 1

Voici quelque chose à penser:

Le premier champ de votre constructeur Let est un Expr. Mais peut-il tenir quoi que ce soit d'autre que Vars? Dans le cas contraire, vous devez en tenir compte en faisant ce type de champ, par exemple, String et adapter en conséquence l'analyseur. Cela rendra votre tâche beaucoup plus facile.

L'astuce standard pour évaluer une expression avec laissez-les liaisons (que vous faites) est d'écrire une fonction

type Env = [(String, Int)]
eval :: Expr -> Env -> Int

Notez l'argument supplémentaire pour l'environnement. L'environnement conserve la trace de ce que les variables sont liées à un moment donné à ce que les valeurs. Sa position dans le type signifie que vous obtenez de décider de sa valeur chaque fois que vous appelez eval sur les expressions de l'enfant. Ce point est crucial! Cela signifie également que vous pouvez avoir des variables déclarées localement. Liant une variable n'a pas d'effet sur son contexte, que sur les sous-expressions

Voici les cas particuliers:

• Dans un Var, vous voulez lookup le nom de la variable dans l'environnement et renvoie la valeur qui est liée à elle. (Utiliser la lookup norme de fonction de prélude.)
• Dans un Let, vous voulez ajouter un (varname, value) supplémentaire à l'avant de la liste de l'environnement avant de le transmettre à l'expression de l'enfant.

Je l'ai laissé quelques détails, mais cela devrait être suffisant pour vous aider à aller un long chemin. Si vous êtes coincé, poser une autre question. : -)

Oh, et je vois que vous voulez retourner une valeur Maybe pour indiquer l'échec. Je vous suggère d'essayer d'abord sans utiliser et error pour indiquer les variables non liées. Lorsque vous avez cette version de travail de eval, l'adapter pour retourner les valeurs de Maybe. La raison en est que le travail avec des valeurs Maybe fait l'évaluation un peu plus compliqué.

Answer 2

Je réellement essayer de evaluate l'AST. Commencez par le traitement (et supprimant ainsi) tous les Lets. Maintenant, essayez d'évaluer l'AST résultant. Si vous rencontrez un Var alors il y a une variable non liée.