Analyse syntaxique : l'AST

nœud de structure : astNode

struct astNode 
{
	/*One of the NODE_TYPE_xxx constant*/
	int type;
	/*Value information*/
	struct astNodeInfo *info;
	struct debugInfo *debug;
	struct astNode *parent;
	struct astNode *right;
	struct astNode *left;
};

Nous avons dans chaque nœud nos trois pointeurs classiques : le nœud "fils de gauche", le nœud "fils de droite", et le nœud parent.

Nous maintenons aussi deux pointeurs particuliers : info et debug car leurs informations ne concernent pas la manière dont notre arbre syntaxique est formé.

Par contre, nous maintenons au sein de la structure astNode le type de nœud dans une variable type. Cette variable nous informe de la signification de cette partie de code analysé par rapport à l'ensemble de la structure de notre arbre.
Nous utiliserons une des constantes dont le nom débute par NODE_TYPE_... que nous avons définie dans le fichier d'en-tête C.

Constantes NODE_TYPE_xxx

A titre d'exemple, voici quelques valeurs utilisées :

• NODE_TYPE_REXP : un nœud de type "expression droite".
• NODE_TYPE_DECL_FUNCTION : un nœud de type "déclaration de fonction".
• NODE_TYPE_FUNCTION_CALL : un nœud de type "appel de fonction".
• etc.

En pratique, comme nous avons un certain nombre de types de nœuds soumis aux mêmes règles imposées par la spécification du langage LSD⁰10, nous pouvons utiliser pour la variable type une même valeur pour ces différents éléments, et utiliser une variable subtype pour stocker le type exact.

« Etant donné que nous travaillons avec un arbre binaire (nous n'avons au maximum que deux enfants), comment pouvons-nous stocker plus de deux enfants pour un même nœud ? »

Ce n'est pas possible. Mais nous pouvons contourner le problème en créant un type NODE_TYPE_CONTAINER, qui ne possède pas de signification propre, et que nous n'utilisons que pour contourner cette limitation.
Nous pouvons décider de stocker dans le fils de gauche le premier enfant, puis placer dans le fils de droite un "container" qui possède comme fils de gauche le second enfant, puis un autre "container" à droite, et ainsi de suite.

Contents Haut

Information sur le contenu : astNodeInfo

struct astNodeInfo
{
	/*ID, Name of the item (variable, function, etc.)*/
	char *name;
	/*LSD10 Type of the item, one of the VAR_TYPE_xxx constants*/
	int type;
	/*
	Integer value for the integer vars
	O (false) or 1 (true) for the boolean vars
	*/
	int value;
};

Cette structure C contient les informations relatives à la partie de code analysée qui correspond à notre nœud de l'AST.

Nous avons un pointeur name vers le nom de l'élément analysé (une variable, une fonction, etc.).

Nous avons une variable value qui contient la valeur de l'élément analysé. Dans le cas d'un booléen, cette valeur est remplacée par son équivalant numérique⁴.

Nous avons une variable type pour le type de l'élément analysé. Nous parlons ici d'un des types de données définis dans le langage LSD⁰10, que nous utilisons sous la formes d'une des constantes suivantes :

• VAR_TYPE_VOID : type "vide" utilisé dans les déclarations de fonctions qui ne retournent pas de valeurs.
• VAR_TYPE_BOOLEAN : type booléen, qui peut prendre la valeur "true" ou "false"⁵.
• VAR_TYPE_INTEGER : type "numérique entier".
• VAR_TYPE_INTSTACK : type "tableau".

Nous pouvons parler de valeur syntaxique pour notre variable type, et de valeur sémantique pour notre variable value.

Contents Haut

Informations de traçabilité (debug) : debugInfo

struct debugInfo
{
	char* file;
	int line;
	int linePsn;
};

Cette structure C contient les informations relatives à la position de la partie de code analysée qui correspond à notre nœud de l'AST.

Nous avons les variables suivantes :

• un pointeur file vers le nom du fichier analysé.
• une variable line qui contient le numéro de ligne de la partie de code analysée.
• une variable linePsn qui contient la position dans la ligne (la colonne) de la partie de code analysée.

Au départ, ces données étaient seulement destinées à fournir l'information nécessaire pour la traçabilité du code lors de la gestion d'erreurs et de l'affichage de certains messages. Au cours du développement du compilateur LSD⁰10, j'ai utilisé ces informations à des fins de vérifications (par exemple les "forward declarations" interdites par le langage LSD010), donc le nom "debug" n'est plus approprié.

Nous pouvons constater que ces informations sont aussi présentes dans la structure YYLTYPE du fichier y.tab.h⁶, et moyennant certaines manipulations, YACC [“Yet Another Compiler Compiler”⁹] peut effectuer le travail à notre place.

Contents Haut