Abstract syntax tree

Arbre syntaxique abstrait

Page d'aide sur l'homonymie Pour les articles homonymes, voir AST.

En informatique, un arbre syntaxique abstrait (abstact syntax tree ou AST en anglais) est un arbre 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 externes ) représentent les opérandes de ces opérateurs.
Autrement dit, chaque feuille a un opérateur de valence nulle (n'a pas d'opérande), 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.

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

Liens externes

  • PMD est un outil de contrôle de qualité de code Java, utilisant les arbres syntaxiques abstrait pour analyser le code source.

Références

Cet article est basé sur une traduction de la Free On-line Dictionary of Computing et est utilisé avec permission selon la GFDL.

Ce document provient de « Arbre syntaxique abstrait ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Abstract syntax tree de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Abstract syntax tree — In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the syntax of some source code (that has been written in a programming language). Each node of the tree denotes a construct occurring in the… …   Wikipedia

  • Abstract Syntax Tree — Der Begriff Abstrakter Syntaxbaum bzw. Abstract Syntax Tree bezeichnet eine logische Baumstruktur, welche die inhaltlichen Zusammenhänge eines Dokumentes im Sinne eines Syntaxbaumes wiedergibt. Nutzen Da komplexe Informationen meist durch eine… …   Deutsch Wikipedia

  • Abstract syntax — The abstract syntax of data is its structure described as a data type (possibly, but not necessarily, an abstract data type), independent of any particular representation or encoding. To be implemented either for computation or communications, a… …   Wikipedia

  • Higher-order abstract syntax — In computer science, higher order abstract syntax (abbreviated HOAS) is a technique for the representation of abstract syntax trees for languages with variable binders.Relation to first order abstract syntaxAn abstract syntax tree is abstract… …   Wikipedia

  • Abstract semantic graph — In computer science, an abstract semantic graph (ASG) is a data structure used in representing or deriving the semantics of an expression in a formal language (for example, a programming language).An abstract semantic graph is a higher level… …   Wikipedia

  • Syntax of programming languages — In computer science, the syntax of a programming language is the set of rules that a sequence of characters in a source code file must follow to be considered as a syntactically conforming program in that language.The rules specify how the… …   Wikipedia

  • Syntax — Syntactic redirects here. For another meaning of the adjective, see Syntaxis. For other uses, see Syntax (disambiguation). Linguistics …   Wikipedia

  • SYNTAX — In computer science, SYNTAX is a system used to generate lexical and syntactic analyzers (parsers) (both deterministic and non deterministic) for all kind of context free grammars (CFGs) as well as some classes of contextual grammars. It is… …   Wikipedia

  • Parse tree — For the trees used in computer science, see Abstract syntax tree. A concrete syntax tree or parse tree or parsing tree[1] is an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse… …   Wikipedia

  • Musical syntax — When analysing the regularities and structure of music as well as the processing of music in the brain, certain findings lead to the question, if music is based on a syntax which could be compared with linguistic syntax. To get closer to this… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”