J'apprends seul à écrire un interprète pour un langage de programmation et j'ai lu sur les arbres de syntaxe abstraites. J'ai une idée de ce qu'ils sont, mais je ne vois pas leur utilisation.
Pourquoi les asts sont-ils utiles?
5 Réponses :
Ils représentent la logique / la syntaxe du code, qui est naturellement un arbre plutôt que une liste de lignes, sans se boucher dans des problèmes de syntaxe concrets tels que l'endroit où vous Placez votre astérisque .
La logique peut ensuite être manipulée d'une manière plus cohérente et plus pratique du POV du backend, qui peut être (et est, pour tout, mais que Lisps;) très différente de la manière dont nous écrivions la syntaxe concrète.
Alors, pourquoi voudriez-je utiliser une AST au lieu de simplement faire un flux de choses comme «Identifiant Blah Asterisk Numberisk Number 4» et avoir une FSM ou quelque chose descendre et manger un jeton à la fois?
@RAC: Ce que vous décrivez, c'est une étape entre le fichier brut et générer une AST. C'est: RAW -> Jetons -> Ast. Binaysop (multiplier, identifiant ("bla"), entier (4)) est plus pratique pour le backend.
@Racecar Votre FSM pour analyse mangerait le flux pour produire une AST; Les routines de votre génération de code et de vos routines utiliseraient l'AST
Y a-t-il un nom spécifique pour cela? Aussi, je peux penser à quelque chose où l'interprète va et voit une déclaration de si et le bytecode ou tout ce que vous avez dit que si quelque chose est vrai, l'interprète devrait aller vers l'avant 8 jetons, sinon, aller de l'avant 0 jetons (ou quelque chose) . Comment un Ast fonctionnerait-il pour quelque chose comme ça? Peut-être donner le prochain chemin (nœud suivant) que l'interprète devrait descendre?
Analyse lexicale . L'Ast aurait un nœud pour la maladie qui a deux sous-notes: vrai et faux. Un AST est très différent du bytecode / ASM (ils sont la même chose, ciblant simplement différentes machines) où vous avez "sauter en avant x instructions" (pas de jetons).
C'est la différence entre les machines virtuelles et ... tout ce que cela serait appelé?
Les machines virtuelles sont implémentées "au-dessus de" une autre machine. Cependant, même x86 est un machine virtuelle , mais, généralement , "VM" est utilisé pour décrire quelque chose implémenté purement dans des logiciels.
Ah, je vois. Mais, un langage de programmation normal génère une AST et l'exécute, mais une langue basée sur la machine virtuelle a byTecode et des trucs qu'il gémit avec une FSM ou quelque chose de vrai? Désolé, je ne peux pas comprendre cela mais je veux m'assurer que je reçois toutes les informations que je peux.
Comment l'AST est utilisé dépend de votre objectif. CPPHON (la principale implémentation de Python), par exemple, génère des bytecodes à partir d'une AST que son interprète peut utiliser. Cependant, il est possible de "exécuter" directement d'une AST aussi, et de nombreux interprètes "plus petits" font cela (/ bin / sh me vient à l'esprit, mais il y en a de nombreuses implémentations).
OK, donc bytecode est pour VMS. Merci beaucoup Roger, cela m'a beaucoup aidé.
En général, vous allez analyser votre code dans une forme d'AST, cela peut être plus ou moins un modèle formel. Donc, je pense que ce que Kirk Woll en passait par son commentaire ci-dessus est que lorsque vous analysez la langue, vous utilisez très souvent l'analyseur pour créer une sorte de modèle de données de la teneur brude de ce que vous lisez, généralement organisé de manière générale d'une arborescence. . Donc, par cette définition, une AST est difficile à éviter à moins que vous fassiez un traducteur très simple.
J'utilise souvent d'Antlr pour analyser les langues complexes et dans ce contexte, il existe une signification légèrement plus spécifique d'une AST. AntLR a une manière pratique de générer une AST dans la grammaire d'analyseur à l'aide d'actions assez simples. Vous écrivez ensuite un analyseur généralement plus simple pour cet AST que vous pouvez utiliser comme une version beaucoup plus simple, la langue que vous traitez. Si le travail supplémentaire de construction de deux analyses est un gain net est fonction de la complexité linguistique et de ce que vous planifiez de faire avec elle une fois que vous l'avez analysée.
Un bon livre sur le sujet que vous voudrez peut-être jeter un coup d'œil à «Schémas de mise en œuvre de la langue» par Terrence Parr l'auteur d'AntLR. Il aborde ce sujet assez soigneusement. Cela dit, je n'ai pas vraiment eu des asts avant d'avoir commencé à les utiliser, de sorte que (comme d'habitude) est le meilleur moyen de les comprendre.
Le système d'exploitation principale à l'aide d'une AST est que vous séparez la logique d'analyse et de validation de la pièce de mise en œuvre. Les interprètes mis en œuvre comme des asts sont vraiment plus faciles à comprendre et à entretenir. Si vous avez un problème d'analyse de la syntaxe étrange, vous regardez l'analyseur AST, si un code de code ne produit pas les résultats escomptés que vous ne regardez le code qui interprète l'AST.
L'autre excellent avantage est que la syntaxe nécessite "lookahead" par exemple. Si votre syntaxe permet à un sous-programme d'être utilisé avant qu'il ne soit défini, il est trivial pour valider l'existence d'un sous-programme lorsque vous utilisez un AST - c'est beaucoup plus difficile avec un analyseur "à la volée".
Merci. Je viens de travailler à travers des analyseurs de bâtiments avec Java, qui prétend que la construction d'une AST est un problème supplémentaire qu'à des langues simples. Le vôtre est le seul commentaire sur cette page qui reconnaît même qu'il est possible de faire quelque chose d'utile sans construire une AST.
Vous avez besoin de "syntaxes arbres" pour représenter la structure de la plupart des langueurs de programmation, afin de mener une analyse ou une transformation sur des documents contenant du texte de la programmation. (Vous pouvez voir des exemples de fantaisie de cela via ma bio).
si cet arbre est abstrait (AST) ou concret (CST) est une question de goût, de commodité et de sueur de l'ingénierie. Le terme CST est spécialement utilisé pour décrire l'arbre de dérivation d'analyse lorsqu'une grammaire est utilisée pour déconstruire le code source; Il contient généralement des éléments d'arbres pour beaucoup de syntaxes concrètes telles que des points-virgules de terminaison de déclaration. AST est utilisé pour signifier "quelque chose de plus simple que le CST", par exemple, laissant des nœuds d'arbre de semi-fluide car ils n'affectent pas beaucoup l'analyse du programme, et donc des analyseurs qui traitent que les asts sont moins conceptuels et en ingénierie que d'écrire le même analyseur sur un CST. Un meilleur moyen de comprendre que cela consiste à comprendre que l'AST est généralement aussi isomorphe équivalent du CST, c'est-à-dire que vous devriez pouvoir régénérer le CST. Si vous voulez transformer le texte source et le régénérer, le CST est souvent un meilleur choix car il perd moins d'informations à partir du programme d'origine (et mon exemple de fantaisie utilise cette approche).
Je pense que vous trouverez la discussion sur Abstract contre la syntaxe concrète des arbres assez utiles.
C'est la meilleure réponse de ce fil. Cela nécessite plus de upvotes.
en retard à la question mais je pensais ajouter quelque chose. Vous n'avez réellement pas à construire une AST. Il est possible d'émettre des instructions directement lorsque vous analysez le code source. Dans ce cas, l'AST est implicite dans la grammaire analysée. Pour des langues simples, surtout des langues dactylographiques dynamiquement, c'est une stratégie parfaitement correcte. Pour plus de langages complexes ou où vous devez analyser davantage le code source, une AST peut être très utile. Par exemple, si votre langue est statiquement dactylographiée, c'est-à-dire que vos variables sont déclarées avec des types fixes, l'AST peut être utilisé pour vérifier que vous n'abandonnez pas le type de type à une variable. Par exemple, attribuer une chaîne à une variable déclarée pour tenir un entier serait fausse et cela peut être pris de manière plus pratique avec l'AST.
En outre, comme d'autres personnes ont mentionné, l'AST offre une séparation propre entre l'analyse de la syntaxe et la génération de code et rend le code beaucoup plus modulaire.
Sans AST, comment envisagez-vous de modéliser la syntaxe de la langue? c'est-à-dire quand écrire un analyseur / compilateur / interprète / etc.