1. Définitions
Un arbre syntaxique est un arbre :
- dont les nœuds sont étiquetés par des symboles : ces symboles sont les noms d'opérateurs de la syntaxe abstraite,
- dont les feuilles sont soit des opérateurs d'arité nulle, soit des terminaux instanciables.
Un opérateur est un modèle de définition de nœud : il est donné par :
- un nom : c'est le nom de l'opérateur ;
- une liste ordonnée de phyla : pour un arbre A dont la racine est étiquetée par un opérateur O, le i-ième fils de la racine de A est l'instance d'un opérateur qui doit appartenir au i-ème phylum de définition de l'opérateur O.
Un nœud de l'arbre syntaxique est alors une instance de l'opérateur qui étiquette ce nœud.
Un phylum est un sous-ensemble de l'ensemble des opérateurs définis. La notion permet d'imposer, sur un arbre donné et pour un fils donné de la racine, que ce fils soit une instance d'un opérateur appartenant à un sous-ensemble restreint de l'ensemble de tous les opérateurs définis.