09

De l’analyse Syntaxique a l’Arbre Binaire Abstrait

avr
No Comments |  Posted by Etienne SOBOLE |  Category:Divers Infos

Cela fait une bonne quinzaine de jours que je me bats avec Bison pour essayer de définir l’ensemble des règles qui permettent de parser un code PHP. Finalement ce n’est pas aussi simple de représenter l’ensemble d’un langage sous la forme d’un ensemble de règles syntaxique. Au départ on peut y aller à tâtons. Mais il y a un moment où il faut se poser pour conceptualiser tout ça.
On ne trouve pas (ou peu) sur Internet d’explications complètes permettant de parser un langage entièrement.

La structure de l’arbre syntaxique

Instruction de calcul

Voilà le cas le plus simple.
La représentation d’une instruction basique par un arbre syntaxique, est relativement simple.
Chaque nœud de l’arbre représente une opération entre 2 opérandes.
Les feuilles de l’arbre sont soit des valeurs numériques, soit des chaînes de caractères, soit des variables.

Exemple
	$y = $a * $x + $b;
Représentation de l’arbre

Le Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string sData;
	asaNode *arg_left;
	asaNode *arg_right;
	...
};

sData est de type string, car je conserve les chaînes de caractères que les feuilles de l’arbres soient des variables ou des valeurs immédiates.

Remarque : Une instruction évaluant une condition sera représenté par un arbre du même type. Une condition est une instruction de calcul qui retourne un booléen : 0 (faux) ou n’importe quel autre valeur (vrai).

Bloc d’instructions {…}

Avant de nous attaquer à des instructions complexes comme les structure conditionnelles et structure itératives (if, for, while, foreach…), intéressons nous déjà à le représentation en arbre d’un ensemble d’instructions encadré par des accolades.
Il doit être possible de représenter une suite d’instructions en utilisant la structure actuelle de la class asaNode, mais ce serait pénible et sans doute peu lisible.
Personnellement j’ai opté pour l’ajout du vecteur (tableau) d’arbre dans chaque nœud de l’arbre. Un premier nœud représente le container, toutes les entrées du vecteur sont alors les instructions contenues séquentiellement dans le bloc d’instruction.

Exemple
	{
		$e = 3;
		$c = 4;
		$x = $e + 1;
	}
Représentation de l’arbre

Le Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string *sData;
	std::vector<asaNode *> *vInstructions;
	asaNode *arg_left;
	asaNode *arg_right;
	...
};

Alors attention, j’ai turbiné un moment pour faire évoluer ma class asaNode.
ma variable sData est devenue un pointeur qu’il va falloir allouer.
mon vecteur vInstructions est lui aussi un pointeur plutôt qu’une instance de vecteur.
L’instanciation d’une chaîne et/ou d’un vecteur étant coûteux en terme de temps CPU, j’ai opté pour des pointeurs qui seront alloués uniquement en cas de besoin.

Evidemment ces considérations n’ont aucun sens à ce niveau du développement, mais il sera toujours moins galère d’implémenter la gestion des pointeurs dès à présent plutôt que de devoir un jour repasser sur tout le code pour convertir les instances en pointeurs.

Structures conditionnelles

Instruction if (…) … else …

Nous pouvons à présent monter d’un cran dans la complexité des arbres syntaxiques abstraits.
Essayons de voir comment convertir les instructions suivantes

if (condition) instruction
if (condition) instruction else instruction

L’implémentation du if que j’ai faite ne gère que les blocs d’instruction. Si l’instruction if est suivi d’une simple instruction isolée (et donc sans accolades) je la range dans un container afin de simplifier le traitement.
Le nœud n’est plus binaire puisque qu’il va avoir 3 fils.

  • Le fils pour évaluer la condition
  • Le fils contenant le container si la condition est vrai
  • Le fils contenant le container si la condition est fausse (dans le cas du else)
Exemple
	if ($z == 99)
		$p = 11;
	else
	{
		$v = 0;
		$c++;
	}
Représentation de l’arbre

Voici l’arbre pour la structure de contrôle if … else ….
Remarque : Je ne détaille plus de contenu des containers.

La Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string *sData;
	std::vector *vInstructions;
	asaNode *condition;
	union {
		asaNode *arg_left;
		asaNode *ctn_if;
	};
	union {
		asaNode *arg_right;
		asaNode *ctn_else;
	};
	...
}

J’ai d’abord ajouté un pointeur pour que les nœuds puissent disposer de 3 fils. Le nœud ajouté s’appelle condition. Je l’utiliserai que pour stocker l’arbre qui évalue la condition.
Puis j’ai créé des unions afin de mapper les pointeurs ctn_if et ctn_else sur arg_left et arg_right. Dit autrement, j’ai utilisé arg_left et arg_right pour pointer sur les containers des instructions à exécuter en fonction du résultat de l’évaluation de la condition.

Le choix d’utiliser des unions est discutable, j’en suis conscient. Bon. C’est comme ça ?
J’aurai pu faire pareil avec des #define ou encore dupliquer les variables, mais au final cela aurai donné des nœuds énormes en terme de taille mémoire.

Instruction switch (…) {case … : …}

La structure conditionnelle switch … case … est un peu plus complexe.
Elle va être représentée par un nœud de type container qui va accueillir lui-même autant de container qu’il y a de case (et default) dans le switch.
Sa représentation en arbre est finalement assez logique au vues des choix que j’ai fait précédemment.

Exemple
	switch($b)
	{
	case 4:
		$c = 9;
		break;
	case "text":
		$x = $z + 2;
		break;
	default:
		break;
	}
Représentation de l’arbre

La Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string *sData;
	std::vector *vInstructions;
	asaNode *condition;
	union {
		asaNode *arg_left;
		asaNode *ctn_if;
		asaNode *ctn_switch;
		asaNode *ctn_case;
	};
	union {
		asaNode *arg_right;
		asaNode *ctn_else;
	};
	...
}

A présent, c’est presque du classique.
J’ai juste ajouté dans la première union ctn_switch et ctn_case histoire d’y accéder avec des variables qui veulent dire quelque chose. Aucune autre modification n’est réalisée.

Structures itératives

Instruction while (…) …

La structure itérative while (…) … n’est pas la plus compliquée.
Son implémentation en arbre ressemble à celle de l’instruction if (…) ….

Exemple
while($b < $a)
{
	$a += 1;
	$b = 56 + $x;
}
Représentation de l’arbre

La Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string *sData;
	std::vector *vInstructions;
	asaNode *condition;
	union {
		asaNode *arg_left;
		asaNode *ctn_if;
		asaNode *ctn_switch;
		asaNode *ctn_case;
		asaNode *ctn_while;
	};
	union {
		asaNode *arg_right;
		asaNode *ctn_else;
	};
	...
}

J’ai juste ajouté dans la première union ctn_while.

Instruction do {…} while (…)
Exemple
do {
	$p = $x + 3;
} while($x != 16);
Représentation de l’arbre

La Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string *sData;
	std::vector *vInstructions;
	asaNode *condition;
	union {
		asaNode *arg_left;
		asaNode *ctn_if;
		asaNode *ctn_switch;
		asaNode *ctn_case;
		asaNode *ctn_while;
	};
	union {
		asaNode *arg_right;
		asaNode *ctn_else;
	};
	...
}
Instruction for(… ; … ; …) …

L’instruction for(… ; … ; …) … est la seule à nécessiter une condition et 3 containers.
Il s’agit également (pour autant que je sache) de la seule instruction qui accepte la virgule (,) en guise de séparateur d’instructions. Raison pour laquelle la première et la troisième partie de l’instruction sont eux aussi des containers.

Exemple
for($i = 0 ; $i < 10; $i++, $t=$i)
{
	$v = $v + $t + 1;
}
Représentation de l’arbre

La Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string *sData;
	std::vector *vInstructions;
	asaNode *condition;
	union {
		asaNode *arg_left;
		asaNode *ctn_if;
		asaNode *ctn_switch;
		asaNode *ctn_case;
		asaNode *ctn_while;
	};
	union {
		asaNode *arg_right;
		asaNode *ctn_else;
	};
	asaNode *ctn_for;
	...
}

Un pointeur ctn_for référençant un nouveau container à été ajouté à la structure asaNode.

Instruction foreach(…) …

La structure itérative foreach(…) … est particulière car elle porte sur des variables et non des containers. Afin d’économiser un nœud (est-ce bien utile ?!?) on utilisera la valeur du nœud pour y stocker la variable.

Exemple
foreach ($tArray AS $k => $v)
{
	$i = $j * $v + 1;
}
Représentation de l’arbre


On remarque que j’ai décidé de stocker dans le nœud parent la variable $tArray

La Class asaNode
class asaNode
{
public:
	int nodeType;
	std::string *sData;
	std::vector *vInstructions;
	asaNode *condition;
	union {
		asaNode *arg_left;
		asaNode *ctn_if;
		asaNode *ctn_switch;
		asaNode *ctn_case;
		asaNode *ctn_while;
	};
	union {
		asaNode *arg_right;
		asaNode *ctn_else;
	};
	asaNode *ctn_for;
	...
}

Conclusion

On a fait le tour (enfin je crois).
On a donc le structure “définitive” de notre arbre qui n’est plus si binaire que cela.

Si d’aventure, javais besoin de modifier la structure asaNode, je mettrai ce post à jour.

Répondre

Human control : 1 + 4 =