Est-il difficile d'écrire un langage interprété en supposant que vous ayez un AST ?

Question

J'ai déjà un analyseur pour un langage sur lequel je travaille.Est-ce difficile de le faire interpréter ?Je pensais que c'était simple.L'analyse et la vérification de la syntaxe sont terminées.J'ai juste un arbre d'objets.Chaque fois qu'un objet est créé, je crée une branche et stocke son type (string, int, float, class/obj).Ensuite, chaque fois qu'un nouveau membre est ajouté à l'objet, je crée une branche et je répète.

J'essaie de faire en sorte que cela paraisse simple.J'ai encore besoin de vérifier que l'objet A peut être ajouté à l'objet B et autres.

Est-ce en fait assez simple une fois l'AST et la vérification de la syntaxe effectués ou y a-t-il encore beaucoup de travail à faire ?

Answer 1

En règle générale, vous devez créer des tables de symboles et effectuer une vérification de type.Pour certaines langues, vous pouvez le faire à la volée ;pour d'autres, je pense qu'il faut d'abord résoudre le nom et vérifier le type, sinon vous ne pourrez pas bien l'interpréter (le C++ me vient à l'esprit).

Une fois que vous avez construit des tables de symboles, vous pouvez pratiquement écrire un interpréteur en parcourant l'arbre dans l'ordre d'exécution et en faisant ce que disent les opérateurs.L'arithmétique de base est assez simple.La gestion des chaînes et du stockage dynamique est plus difficile ;vous devez comprendre comment vous allez gérer l'allocation et la désallocation du stockage, et pour les langages qui gèrent le stockage, vous devrez implémenter une sorte de garbage collector.La vie se complique vite à ce stade.

Vous découvrirez probablement des fonctionnalités linguistiques que vous n'aviez pas prises en compte.Gestion des exceptions?Plusieurs missions ?Des portées locales ?Des Lambda ?Des fermetures ?Vous découvrirez assez rapidement tout ce qui rend les langues modernes utiles.

Lorsque vous commencerez à écrire des programmes plus compliqués, vous aurez besoin d'un débogueur.Des points d'arrêt ?Une seule étape ?Contrôle variable ?Mise à jour?Commencer à des endroits arbitraires ?Boucle lecture-évaluation-impression ?

Vous devez toujours lier votre langue à des bibliothèques externes ;la plupart des gens veulent parler à des consoles et à des fichiers ;voulez-vous des fichiers mis en mémoire tampon ou êtes-vous d'accord avec 1 caractère à la fois et les performances correspondantes ?Vous aurez l'occasion d'argumenter avec les représentations de caractères (ASCII 7 bits ?8 bits?UTF8 avec des caractères non étendus à l'unité ?Unicode complet ?) et les bibliothèques de support standard (concatentation de chaînes, recherche, conversions de nombres [y compris les conversions précises en virgule flottante dans les deux sens], arithmétique des grands nombres, pièges à virgule flottante, ....La liste des problèmes est assez longue si vous voulez un langage de programmation utile.

Le noyau d’interprètes sera probablement assez restreint.Vous constaterez que les autres éléments nécessitent probablement un ou deux ordres de grandeur supplémentaires.Quelque part ici, si vous voulez que quelqu'un utiliser la langue, vous devez documenter tous les choix que vous avez faits.Et le ciel t'aide si tu changement l'interprète un peu après que quelqu'un ait lancé une grosse application.

Ensuite, quelqu’un se plaindra des performances.Vous pouvez maintenant ajuster votre implémentation et commencer à regretter le fait que vous ayez écrit un interpréteur au lieu d'un compilateur.

Apprécier.Si vous avez un AST, vous avez à peine effleuré la surface.Si vous acceptez cela, vous apprendrez à vraiment apprécier ce que les langues modernes offrent dès le départ et les efforts qu'il a fallu pour le fournir.

Answer 2

Cela dépend de la complexité d'une langue que vous souhaitez écrire un interprète et votre choix d'outils. Les interprètes simples sont simples.

Considérez ce qui suit comme définition sur une AST dans HASKELLL pour une langue prenant en charge des fonctions et des chiffres d'ordre supérieur:

data Exp = Lam String Exp 
         | App Exp Exp 
         | Var String 
         | Num Int

Vous pouvez maintenant écrire un interprète pour cela comme la simple fonction "eval":

eval (App e1 e2) env = (unF (eval e1 env)) (eval e2 env)
eval (Lam x e) env   = F (\v -> (eval e ((x,v):env)))
eval (Num n) env     = N n
eval (Var x) env     = case (lookup x env) of 
                         Just v -> v
                         Nothing -> error ("Unbound variable " ++ x)

Et c'est tout. Les quelques définitions de soutien ennuyeuses sont les suivantes.

data Val = F (Val -> Val)  | N Int
unF (F x) = x
instance Show Val where 
    show (F _) = "<procedure>"
    show (N n) = show n

En d'autres termes, si vous copiez collez les trois blocs de code ci-dessus dans un fichier source Haskell, vous aurez un interprète de travail que vous pouvez tester à l'aide de GHCI comme suit:

*Main> eval (App (Lam "x" (Var "x")) (Num 1)) []
1
*Main> eval (Var "x") []
*** Exception: Unbound variable x

Vous pouvez lire sur la création de langues dans le classique SICP ou EOPL ou le petit livre . Si vous souhaitez créer une langue dactylographiée, vous devrez peut-être en lire d'autres.

Cela dit, si vous allez construire des langues, pourrais-je recommander fortement beaucoup de lecture en premier. Pour un, c'est très enrichissant. Et deuxièmement, trop de langues hideuses ont été infligées au monde par des personnes qui ne savent pas créer de langues (dont beaucoup sont devenues très populaires pour diverses raisons historiques) et nous sommes bloqués avec eux.

Answer 3

Je dirais que la partie difficile (et la partie la plus drôle en fait) commence après que vous ayez fait l'Ast.

regarder LLVM , il contient des liaisons pour beaucoup de langues (je n'ai utilisé que c ++ et haskell, jeJe ne peux pas dire pour d'autres langues), et cela devrait vous aider à écrire un compilateur juste dans le temps pour votre langue.En fait, LLVM facilite la rédaction d'un compilateur qu'un interprète!