Arbre syntaxique abstrait
Un article de Wikipédia, l'encyclopédie libre.
En informatique, un arbre syntaxique abstrait (abrégé en AST comme en anglais) est un arbre dirigé avec des labels dont les nœuds internes sont marqués par des opérateurs et dont les nœuds fils ( feuilles ou nœuds internes ) représentent les opérandes de ces opérateurs. Autrement dit, chaque feuille a un opérateur de valence nulle, des variables ou des constantes.
Un arbre syntaxique abstrait est utilisé par un analyseur syntaxique comme un intermédiaire entre un arbre d'analyse et une structure de données. On utilise celle-ci comme la représentation intermédiaire interne d'un programme informatique pendant qu'elle est optimisée et à partir de laquelle la génération de code est effectuée. La portée des structures possibles est décrite par la syntaxe abstraite.
Un AST diffère d'un arbre d'analyse par l'omission des nœuds et des branches qui n'affecte pas la sémantique d'un programme. Un exemple classique est l'omission des parenthèses de groupement, puisque dans un AST, le groupement des opérandes est explicite dans la structure de l'arbre.
La création d'un arbre syntaxique abstrait pour un langage décrit par sa grammaire est facile pour la plupart des langages. La plupart des règles de la grammaire créent un nouveau nœud dont les branches sont les symboles de la règle. Les règles qui ne contribuent pas à l'arbre sont les règles de groupement, qui passent simplement le nœud pour l'un de leurs symboles. Un analyseur syntaxique peut aussi créer un arbre complet, et faire une passe ultérieure pour supprimer les nœuds non utilisés par l'arbre syntaxique abstrait.
[modifier] Voir aussi
- Arbre de résolution sémantique (RST en anglais)
- Arbre d'interprétation syntaxique (IST en anglais)
- Arbre syntaxique de génération de code (sigle anglais : CST)
- Arbre sémantique (ASG)
- Table de symboles
[modifier] Références
Cet article est basé sur du matériel provenant d'une traduction de la Free On-line Dictionary of Computing et est utilisé avec permission selon la GFDL.
