Autre méthode d'analyse syntaxique

En plus de la technique de descente récursive, il existe d’autres méthodes pour analyser la syntaxe d’un langage. Parmi ces méthodes, on peut citer l’analyse syntaxique descendante pilotée par les tableaux et …

Analyse syntaxique descendante pilotée par tables (Table-driven Top-down Parsing)

L’idée derrière cette technique est de construire un algorithme générique pour l’analyse syntaxique descendante. Cet algorithme reçoit la grammaire du langage en entrée et utilise un tableau (ou un graphe) pour stocker les règles de production de la grammaire. L’algorithme utilise ensuite le tableau pour déterminer la règle de production à appliquer à chaque étape de l’analyse.

Si la structure est représentée par un graphe, nous pouvons alors considérer son interprétation comme une traversée du graphe, guidée par le texte source en cours d’analyse.

Analyse syntaxique ascendante (Bottom-up Parsing)

Les analyses syntaxiques descendantes récursives et pilotées par table présentées ici sont toutes deux des techniques basées sur le principe d’analyse descendante (top-down). Avec ces techniques, on part du symbole de départ et on essaie de dériver le texte à analyser. Tous les symboles non terminaux rencontrés sont remplacés par des suites de symboles jusqu’à ce que le texte soit complètement analysé.

Il est également possible de procéder en partant des éléments du texte à analyser et en essayant de les regrouper en symboles non terminaux. Cette technique est appelée analyse syntaxique ascendante (bottom-up).

• La méthode ascendante est appelée analyse LR (Left-to-right, Leftmost derivation). Le premier L exprime le fait que le texte est lu de gauche à droite. Le R indique que la dérivation est effectuée en réduisant la partie la plus à droite de règle.
• la méthode descendante est appelée analyse LL. Le premier L exprime toujours le fait que le texte est lu de gauche à droite. Le L indique que la dérivation est effectuée en développant le symbole non-terminal le plus à gauche.

Cette notation est généralement suivie d’un paramètre k (LL(k), LR(k)) indiquant le nombre de symboles qui doivent être lus pour déterminer la prochaine étape. Si le nombre est omis, nous supposerons implicitement que k = 1.

Les analyseurs ascendants utilisent toujours des tables, c’est-à-dire des structures de données analogues à celles de l’analyseur descendant piloté par table présenté ci-dessus. En plus de la représentation de la syntaxe sous forme de structure de données, d’autres tables sont nécessaires pour permettre de déterminer la prochaine étape de manière efficace. L’analyse ascendante est donc généralement plus complexe et plus complexe que l’analyse descendante.

Pour la suite de ce cours, nous nous concentrons sur l’analyse syntaxique descendante récursive, car elle est plus simple et plus intuitive et plus facile à mettre en œuvre.