Table des symboles

La table des symboles contient les différents symboles (qui sont, rappelons-le, des chaînes de caractères alphanumériques) rencontrés au cours de l'analyse syntaxique. Pour la mettre en uvre, le sujet suggérait un tableau unidimensionnel où les différentes occurrences de chaînes se suivaient. Cette structure ne nous paraissait pas satisfaisante pour plusieurs raisons. D'abord, elle est statique et il est donc nécessaire de faire des tests de débordement. Ensuite, les symboles sont dupliqués et il est donc coûteux de comparer deux chaînes pour savoir si elles représentent le même symbole.
Nous avons donc opté pour un arbre binaire de recherche dans lequel les chaînes sont triées dans l'ordre alphabétique (dans l'ordre ASCII plus précisément) et ne sont pas dupliquées. Ainsi, on économise de la mémoire et il n'y a plus de limite, si ce n'est celle de la quantité totale de mémoire disponible pour l'application. De plus, l'insertion d'un nouveau symbole est rapide puisqu'elle est en $O(\log_2 n)$ où $n$ est le nombre de symboles dans l'arbre. Encore plus intéressant, puisqu'il est facile d'éviter la duplication des chaînes, il suffit pour en comparer deux de ne regarder que leurs pointeurs.