Algorithmes d'analyse syntaxique

Un algorithme d'analyse syntaxique est un algorithme permettant de reconnaître l'existence d'un mot selon un langage, en cas général il est appliqué pour les langages informatiques et valide ou non un code source pour la syntaxe d'un langage informatique dans tous les compilateurs et interpréteurs. Mais la plupart des analyseurs syntaxiques ne se contentent pas de seulement valider l'entrée, ils extraient aussi la construction de cette entrée sous la forme d'un arbre abstrait de syntaxe détenant le sens de la chaîne d'entrée.

Les grammaires

Les symboles de grammaire

Toutes les grammaires sont composées de symboles regroupés sous deux catégories, les terminaux et le non-terminaux.

Les terminaux sont les symboles les plus petits ne pouvant être subdivisé, ils forment la chaîne d'entrée. Dans l'exemple d'une expression mathématique simple ces symboles sont tous les chiffres, tous les opérateurs et ponctuations.

Les non-terminaux sont des symboles pouvant être subdivisé, il servent à regrouper d'autre symboles. Il sont toujours associés à des productions décrivant les subdivisions possible. Par exemple une grammaire pourrait définir le non-terminal expr qui englobe toutes le expressions mathématique simple soit toutes les compositions valide de chiffres, opérateurs et ponctuations.

TODO exemple production 5 + 2 - 3

Les productions de grammaires

Les productions décrivent les subdivisions de non-terminaux, dans le cas d'une grammaire non-contextuelle toutes les productions sont de la forme :

$A\rightarrow \gamma$

$A$ : un non-terminal. $\gamma$ : une composition de terminaux et non-terminaux.

Un non-terminal peut être dérivé par une des ses productions associée, il est alors réécrit par la partie droite d'une production. Cette opération mène à une proto-phrase, cette proto-phrase est une phrase si elle est constituée seulement de terminaux. De même il est possible de réduire une proto-phrase en un non-terminal par une des productions ayant en partie droite la proto-phrase.

La hiérachie de Chomsky

La hiérachie de Chomsky définit quatre classes de grammaires, chacune pouvant décrire toutes les règles des grammaires de hiérarchie plus faible, les grammaires générales couvrent toutes les grammaires possibles.

Le niveau le plus faible est attribué aux grammaires régulières.

• Les grammaires régulières sont d'une forme linéaire gauche ou droite, chaque non-terminal peut être associé à une composition de terminaux et un non-terminal en préfixe ou suffixe seulement.
• Les grammaires algébrique (ou non-contextuelles) offrent une plus grande liberté en autorisant d'associer à un non-terminal n'importe quelle combinaison de terminaux et non-terminaux.
• Les grammaires contextuelles sont semblables aux grammaires algébrique mise à part l'ajout d'un contexte autour des productions en partie gauche et partie droite.
• Les grammaires régulières rendent possible l'association de n'importe quelle composition de non-terminaux et terminaux vers une autre composition.

Les grammaire non-contextuelles

Les grammaires non-contextuelles sont définits de la forme $G=(V,A,S,P)$.

• $V$ : l'ensemble des non-terminaux de la grammaires.
• $A$ : l'ensemble des terminaux.
• $S$ : le non-terminal axiome.
• $P$ : l'ensemble des productions associant un non-terminal à une composition de non-terminaux et terminaux : $N\rightarrow \alpha$.

Dans un contexte plus technique il suffit de préciser l'axiome et les productions car ces dernières listent tout les non-terminaux et terminaux existant. L'axiome joue un rôle important dans la validation d'un mot par une grammaire, si des dérivations successives partant de l'axiome mènent à une phrase correspondant au mot d'entrée alors l'entrée est validé. De même si la phrase correspondante au mot d'entrée et réduite jusqu'à obtenir l'axiome.

Plus formellement, soit $\omega$ le mot d'entrée : $S\xrightarrow {*} \omega$.

Les analyseurs lexicaux

L'analyse lexicale couvrent toutes les règles de la grammaire régulière, elle est utilisée pour faciliter le travail de l'analyseur syntaxique par la reconnaissance de certain groupe de lexème (les noms de variables, les nombres entiers, les nombres flottants) en unité lexicale. Ces unités lexicales seront utilisées comme terminaux par l'analyseur syntaxique et formeront donc la chaine d'entrée.

La plupart des règles d'une grammaire régulière sont décrites avec des expressions rationnelles se basant sur trois opération fondamentales : la concaténation, l'union et l'étoile de Kleene. Chacune de ces opération produit un ensemble de mot pouvant être reconnu par le motif.

• La concaténation permet de créer un singleton avec la concaténation de deux mots, autrement dit reconnaître que la concaténation de deux mots. $ab\rightarrow \{ab\}$
• L'union crée un ensemble constituée des deux mots, elle reconnaît l'un de deux mots seulement. $a|b\rightarrow \{a,b\}$
• L'étoile de Kleene permet de créer un ensemble contenant toutes les combinaisons d'un ensemble ainsi que le vide. $(a|b)^{*}\rightarrow \{\epsilon ,a,b,ab,ba,aab,...\}$

L'analyseur lexicale sépare en premier la chaine selon les blancs et d'autres séparateurs supplémentaires tels que les signes de ponctuations et les opérateurs, ensuite chaque portion de la chaine d'entrée est analysé selon un ensemble de règles rationnelles pour déterminer son unité lexicale.

Par exemple la chaine d'entrée "float i = 4.2 + 5;" sera découpée en {"float", "i", "=", "4.2", "+", "5", ";"}, ensuite selon les règles suivantes (utilisant le format de regex POSIX) :

• type $\rightarrow$ (int|float|bool)
• id $\rightarrow$ ([A-z]([A-z]|[0-9])*)[^(int|float|bool)]
• op_assign $\rightarrow$ =
• float $\rightarrow$ [0-9]*\.[0-9]*f?
• int $\rightarrow$ [0-9]*
• end $\rightarrow$ ;
• op $\rightarrow$ \+|\-|/|\*

On obtient donc un ensemble des unités lexicales reconnues : {type, id, op_assign, float, op, int, end}.

Les automates finis

Un analyseur lexicale peut être construit avec un automate finis car d'après le théorème de Kleene toutes les grammaires régulière sont reconnu par un automate finis.

Théorème de Kleene : l’ensemble des langages rationnels sur un alphabet A est exactement l’ensemble des langages sur A reconnaissables par automate fini.

L'automate suivant reconnaît le motif $a^{*}b^{*}$

Malheureusement la limite des analyseur lexicaux et très vite atteint notamment avec le motifs de la forme $a^{n}b^{n}$. Dans ce cas il faut trouver un moyen de compter le nombre de a consommé pour essayer de consommer le même nombre de b, or les automates finis ne dispose pas de mémoire supplémentaire où placer ce compteur. Ce type de motif est fortement utilisé dans les languages de programmations pour vérifier le bon nombre de parenthèses, accolades etc…

Les analyseurs syntaxiques

L'analyse syntaxique suit l'analyse lexical en se basant sur les unités lexicales définit par ce dernier nommé lexèmes. Ces unités lexicales sont utilisées en tant que terminaux par l'analyseur syntaxique dans une liste de lexèmes.

Les algorithmes d'analyseur syntaxiques se basent tous sur le même type d'automates : les automates finis à pile. Les deux majeurs techniques connus sont l'analyse descendante et l'analyse ascendante. La première consiste à dériver l'axiome de la grammaire jusqu'à obtenir le mot d'entrée, la seconde technique consiste à réduire le mot d'entrée jusqu'à obtenir l'axiome. Ces deux techniques sont considéré comme opposé par leur façon de traiter les proto-phrases, l'analyseur descendant va toujours dériver et l'analyseur ascendant toujours réduire. Malgré cette symétrie, ces deux types d'analyseur n'utilisent pas les mêmes ensembles de règles.

Les automates finis à pile

Les automates finis à pile forment une extension des automates finis par l'adjonction d'une mémoire organisé en pile.

Ils permettent de couvrir les limitations des analyseurs lexicaux en reconnaissant les motifs de la forme $a^{n}b^{n}$.

Ce type d'automate est utilisé pour les analyseurs syntaxique tant descendant que ascendant.

Les analyseurs descendants

Le principe de l'analyse descendante est assez simple à mettre en œuvre. L'analyseur initialise une proto-phrase contenant l'axiome de la grammaire, à chaque étape l'analyseur va lire le symbole à gauche de la proto-phrase. Si celui ci est un terminal alors on le compare avec le début de la chaîne d'entrée, si il correspond on consomme le début de la chaine d'entrée ainsi que le terminal au début de la proto-phrase, au contraire on signale une erreur. Si le début de la proto-phrase est un non-terminal alors on le remplace par la partie droite de l'une de ses productions.

Le pseudo code correspondant est le suivant :

initialiser une pile contenant S
Tant que la pile et la chaine d'entrée sont non-vide
  soit C le premier lexème de la chaine d'entrée
  soit T le sommet de la pile
  Si T est non-terminal
	choisir une production P de T
	dépiler le sommet de la pile
	empiler la partie droite de P
  Sinon si T équivaut C
	dépiler le sommet de la pile
	consommer le lexème C
  Sinon
	erreur

Si nous utilisons la grammaire contenant les deux productions $S\rightarrow aSb$ et $S\rightarrow \epsilon$ ($\epsilon$ pour ne rien consommer ou ajouter), $S$ est l'axiome de la grammaire implicitement. La trace de l'algorithme descendant du mot d'entrée "aabb" est alors :

Pile	Entrée	Opération
S	aabb
aSb	aabb	dériver par $S\rightarrow aSb$
Sb	abb	consommer a
aSbb	abb	dériver par $S\rightarrow aSb$
Sbb	bb	consommer a
bb	bb	dériver par $S\rightarrow \epsilon$
b	b	consommer b
		consommer b et valider le mot

Malgré la simplicité de cette technique posent deux problèmes majeurs sont présents et mènent tous deux à utiliser un ensemble restreint de règles de grammaire par rapport aux grammaires algébrique.

Le premier problème concerne la récursivité gauche. Si l'algorithme ne sait pas exactement comment choisir les productions à appliquer et que la grammaire possède des productions de la forme $N\rightarrow N\alpha$ ou autrement dit des productions associant le même non-terminal à gauche et à droite de la production, alors la dérivation du sommet d'une proto-phrase contenant $N$ mènera toujours à avoir le même non-terminal au sommet et l'algorithme ne pourra jamais arrêter de dériver.

• $N$
• $N\alpha$
• $N\alpha \alpha$
• $N\alpha \alpha \alpha$
• $N\alpha \alpha \alpha \alpha$
• …

Pour contrer ce problème il existe une méthode permettant de transformer la récursivité gauche en une récursivité droite d'un non-terminal secondaire :

Soit $N\rightarrow N\alpha$ $N\rightarrow \beta$

• $N\rightarrow \beta N'$
• $N'\rightarrow \alpha N'$
• $N'\rightarrow \epsilon$

En effet, les règles initiales mènent intuitivement aux motifs de la forme $\beta \alpha \alpha \alpha ...\alpha$. Remplacer la récursivité gauche consisterait en réécrire les règles donnant les mêmes motifs, soit $\beta$ en préfixe suivi d'une règle linéaire droite pour les $\alpha$.

Le second problème des analyseurs descendant et le determinisme lors du choix des productions à dériver. L'algorithme doit dériver un non-terminal selon la production qui à le plus de chance de réussir l'analyse. Dans l'exemple de la trace de l'analyse du mot "aabb", il fallait lors de la troisième dérivation dériver selon $S\rightarrow \epsilon$ seulement. Dans le cas contraire non-deterministe, l'algorithme pourrait autoriser de revenir en arrière dans l'analyse lors d'erreur et d'appliquer les productions restantes jusqu'à ne plus avoir de production et donc signaler une véritable erreur.

Les analyseurs à symbole de prévision

Un analyseur à symbole de prévision, nommé LL(k) ou k est le nombre de symboles, lors d'une dérivation va lire k symboles au début de la chaine d'entrée pour déterminer la production à dériver contenant ces k symboles en préfixe. La plupart des analyseurs se contentent de 1 symbole de prévision.

En amont de l'analyse un algortihme est utilisé pour générer une table de la forme $PRODUCTION(N,c)\rightarrow P$.

• $N$ : Le non-terminal courant (au sommet de la proto-phrase).
• $c$ : Le lexème courant (au sommet de la chaine d'entrée) utilisé comme préfixe.
• $P$ : la production ayant pour préfixe $c$

Dans le cas de productions sans $\epsilon$, l'algorithme va pour chaque non-terminal lire toutes les productions associées. Pour chacune des productions déterminer les préfixes possibles, en parfois dérivant jusqu'à obtenir un terminal à gauche, puis associer cette production avec ses préfixes dans la table.

Dans l'exemple d'une grammaire reconnaissant les déclarations de variables avec initialisation optionnelle par les règles suivantes :

• $decl\rightarrow type\,id\,decl'$
• $decl'\rightarrow =\,expr\,;$
• $decl'\rightarrow ;$

Cette grammaire reconnait les mots "int i = 0;" et "int i;" de la façon suivante :

• Dérivation de l'axiome : $type\,id\,decl'$
• Reconnaissance de $type$ et $id$ par respectivement "int" et "i"
• Dérivation de $decl'$ par l'une de ses productions
• Suite de l'analyse avec l'une des deux productions de $decl'$

Ici est mis en évidence le branchement lors de la dérivation de $decl'$, la table des productions par symbole de prévision est :

Non-terminal	Préfixe	Production
$decl$	$type$	$decl\rightarrow type\,id\,decl'$
$decl'$	=	$decl'\rightarrow =\,expr\,;$
$decl'$	;	$decl'\rightarrow ;$

Lors de la dérivation de $decl'$, l'analyseur va interroger la table de production pour le lexème en sommet d'entrée, dans le cas des deux mots "int i = 0;" et "int i;" ce symbole sera respectivement "=" ou ";". Ces deux symboles donnent dans la table deux productions valide pour continuer l'analyse.

Dans le cas où le préfixe n'est pas associer à une production, l'analyseur peut signaler une erreur car cela signifie que n'importe quelle dérivation mènera à une erreur lors de la reconnaissance du premier symbole terminal.

En ce qui concerne les grammaires possédant des productions en $\epsilon$, ces productions sont valide pour n'importe quelle préfixe mais sont soumise à une condition supplémentaire sur les symboles rencontré après l'usage des non-terminaux de ces productions.

Soit une production $N\rightarrow \epsilon$, nous regardons toutes les productions utilisant le non-terminal $N$ de la forme $L\rightarrow N\gamma$ et associant dans la table la production $N\rightarrow \epsilon$ avec tous les préfixes de $\gamma$.

Dans le même exemple de grammaire reconnaissant les déclarations de variables, les règles peuvent s'écrire :

• $decl\rightarrow type\,id\,decl'\,;$
• $decl'\rightarrow =\,expr$
• $decl'\rightarrow \epsilon$

Le non-terminal associé à la production $decl'\rightarrow \epsilon$ et utilisé seulement dans $decl\rightarrow type\,id\,decl'\,;$ et le symbole suivant $delc'$ est ";". $decl'\rightarrow \epsilon$ et donc associé à ";" dans la table comme pour la grammaire précédente sans productions utilisant $\epsilon$.

Non-terminal	Préfixe	Production
$decl$	$type$	$decl\rightarrow type\,id\,decl'\,;$
$decl'$	=	$decl'\rightarrow =\,expr$
$decl'$	;	$decl'\rightarrow \epsilon$

Les analyseurs ascendants

Le principe de l'analyse ascendante est de réduire successivement une phrase correspondant à la chaine d'entrée jusqu'à obtenir l'axiome de la grammaire. Ce type d'analyseur nécessite la création en amont d'une table d'analyse difficilement concevable manuellement.

Cette table d'analyse se base sur deux opérations, réduire et décaler. Décaler consiste à déplacer un terminal en sommet de la chaine d'entrée dans la pile d'analyse, réduire consiste à remplacer le sommet de la pile d'analyse correspondant à la partie droite d'une production par le non-terminal associé à cette production.

Pour la grammaire suivante et le mot d'entrée "aabb" :

• $S\rightarrow aSb$
• $S\rightarrow ab$

La trace de l'analyse ascendante est :

Pile	Entrée	Opération
	aabb
a	abb	décaler
aa	bb	décaler
aab	b	décaler
aS	b	réduire par $S\rightarrow ab$
aSb		décaler
S		réduire par $S\rightarrow aSb$ et valider

Malheureusement il ne suffit pas de reconnaître la partie droite d'une production sur le sommet de la pile pour réduire par celle ci. Le contre-exemple est le suivant : Soit une grammaire linéaire droite de la forme $A\rightarrow aA$, $A\rightarrow a$ et le mot "aa". En premier "a" est décalé, puis réduit par la production $A\rightarrow a$, puis le second "a" est décalé pour obtenir sur la pile d'analyse "Aa". Aucune production n'a le motif "Aa" en partie droite pourtant le mot "aa" est bien valide intuitivement. Pour réussir cette analyse il aurait fallu décaler les deux "a" pour obtenir "aa", réduire le dernier en "aA" selon $A\rightarrow a$ et enfin réduire en "A" selon $A\rightarrow aA$.

Les réductions valide sont nommées manche, ils dépendent de l'état de la pile.

Les tables d'analyse

La table d'analyse représente les différents états de l'automate à pile formant l'analyseur, ces états sont calculé en se basant sur la notion d'item de production.

Un item de production représente l'état actuel de validation d'une production, ou autrement dit, le nombre de symbole validé lors de l'analyse.

Pour une production de la forme $N\rightarrow \alpha \gamma \beta$ il existe 4 items, en cas générale il existe n + 1 items pour une production de n symboles en partie droite. Ces items sont notés :

• $N\rightarrow \bullet \alpha \gamma \beta$
• $N\rightarrow \alpha \bullet \gamma \beta$
• $N\rightarrow \alpha \gamma \bullet \beta$
• $N\rightarrow \alpha \gamma \beta \bullet$

Par exemple l'item $N\rightarrow \alpha \bullet \gamma \beta$ signifie que l'analyse à reconnu $\alpha$ et espère reconnaître $\gamma \beta$. Le dernier item $N\rightarrow \alpha \gamma \beta \bullet$ signifie que tous les symboles de la productions ont été reconnu et donc la production peut servir de réduction.

Tout d'abord pour pouvoir d'écrire des items de l'axiome de la grammaire, nous devons définir une grammaire augmenté similaire à la grammaire initiale mais avec l'adjonction d'un non-terminal $S'$ et de la production $S'\rightarrow S$. Ainsi l'état initiale de l'analyse est décrit par $S'\rightarrow \bullet S$, aucun symbole n'est reconnu.

Deux fonctions vont être utilisés sur ces items, en particulier sur des ensembles d'items. La fonction $Fermeture(X)$ et $Transition(X,c)$.

$Fermeture(X)$ prend en argument un ensemble d'item. Soit un item $N\rightarrow \gamma \bullet \alpha$ de $X$, si $\alpha$ est un terminal alors ajouter cet item dans le résultat, sinon si $\alpha$ est un non-terminal alors concaténer au résultat $Fermeture(Y)$ où $Y$ et l'ensemble de toutes les items des productions de $\alpha$ avec le point en première position : $\{\alpha \rightarrow \bullet \beta ,\alpha \rightarrow \bullet \delta ,...\}$

$Transition(X,c)$ prend en argument un ensemble d'item et un terminal, Soit $N\rightarrow \alpha \bullet c\beta$, concaténer au résultat $Fermeture(\{N\rightarrow \alpha c\bullet \beta \})$.

Ces deux fonctions vont permettre de déterminer les états de l'automates, chaque état et un ensemble d'items faisant partie de la collection canonique de l'analyseur. $Fermeture(S'\rightarrow \bullet S)$ est l'état initiale $I_{0}$ puis $Transition(X,c)$ détermine tous les états atteignables par un décalage de c, et enfin un état où aucune transition n'est possible mais contenant un item de la forme $N\rightarrow \gamma \bullet$ produira une réduction par $N$.

• $S\rightarrow aSb$
• $S\rightarrow ab$

La grammaire ci-dessus produits les états suivant :

• $Fermeture(\{S'\rightarrow \bullet S\})=\{S'\rightarrow \bullet S,S\rightarrow \bullet aSb,S\rightarrow \bullet ab\}=I_{0}$
• $Transition(I_{0},S)=\{S'\rightarrow S\bullet \}=I_{1}$
• $Transition(I_{0},a)=\{S\rightarrow a\bullet Sb,S\rightarrow a\bullet b,S\rightarrow \bullet aSb,S\rightarrow \bullet ab\}=I_{2}$
• $Transition(I_{2},S)=\{S\rightarrow aS\bullet b\}=I_{3}$
• $Transition(I_{2},a)=I_{2}$
• $Transition(I_{2},b)=\{S\rightarrow ab\bullet \}=I_{4}$
• $Transition(I_{3},b)=\{S\rightarrow aSb\bullet \}=I_{5}$

L'automate résultant est le suivant :

L'algorithme représentant un analyseur ascendant simple peut être de la manière suivante :

TODO latex dans pre

Les arbres abstraits de syntaxe

Les arbres abstraits de syntaxe contiennent le minimum de sens de la chaine d'entrée, soit dans la plupart des languages de programmation les opérateurs, les opérandes et les structures de donnée.

Dans l'exemple d'un bout de code HTML "<h1>Titre</h1>" nous voudrions obtenir un arbre nous indiquant seulement la présence de la balise "<h1>" contenant le mot "Titre" :

Pour obtenir cette arbre il faut transformer l'arbre de dérivation en sortie de l'analyseur syntaxique avec des attributs de productions.

Les arbres de dérivation

Les arbres de dérivation notent toutes les dérivation ou réduction de production au cours de l'analyse. Lors de la dérivation d'une production $N\rightarrow \alpha \beta$ nous produirons un sous arbre avec en racine le non-terminal $N$ et en nœuds enfants les symboles $\alpha$ et $\beta$ :

Malheureusement la majorité des grammaires utilisées par les analyseurs descendant produisent des arbres de dérivation éloigné des arbres abstraits de syntaxe, comme la grammaire suivante :

• $E\rightarrow id\ E'$
• $E'\rightarrow op\ id\ E'$
• $E'\rightarrow \epsilon$

Cette grammaire optimisée pour l'analyse descendante par la suppression de l'ambiguité et l'utilisation de préfixes unique, produit pour le mot d'entrée "5 + 2 - 3" l'arbre de dérivation :

Les grammaires attribuées

Les transformations entre arbre de dérivation et arbre abstrait de syntaxe sont décrites par des règles attribués à chacune des productions. Ses règles permettent de lire ou écrire des attributs de symbole. Pour éviter toute ambiguité entre les symboles dans les productions, les symboles de même nom sont renommés en $N_{i}$, $E'\rightarrow op\ id\ E'$ devient $E_{1}'\rightarrow op\ id\ E_{2}'$.

Les règles se regroupent en deux catégories, les règles synthétisées et les règles héritées.

Les règles synthétisées modifient le non-terminal à gauche d'une production en fonction des attributs des symboles à droite de la production. En gardant le même exemple de grammaire, la production $E'\rightarrow \epsilon$ doit produire un noeud vide, elle est associée à $E'.noeud=noeud()$. De même la production $E_{1}'\rightarrow op\ id\ E_{2}'$ définit le noeud $E_{1}'$ avec l'operateur : $E'_{1}.noeud=noeud(op.val)$.

Les règles héritées modifient des symboles à droite de la production en fonction des autres symboles à droite, les nœuds voisins, ou le non-terminal à gauche de la production. Ainsi la production $E_{1}'\rightarrow op\ id\ E_{2}'$ doit basculer la valeur $id$ dans le nœeud $E_{2}'$, elle est donc associée à la règle $E'_{2}.noeud.ajouter(noeud(id.val))$.

La totalité des règles est :

• $E\rightarrow id\ E'\Longrightarrow E.noeud=E'.noeud$
• $E'_{1}\rightarrow op\ id\ E'_{2}\Longrightarrow E'_{1}.noeud=noeud(op.val)E'_{1}.noeud.ajouter(E'_{2}.noeud)$
• $E'\rightarrow \epsilon \Longrightarrow E'.noeud=noeud()$
• $E\rightarrow id\ E'\Longrightarrow E'.noeud.ajouter(noeud(id.val))$
• $E'_{1}\rightarrow op\ id\ E'_{2}\Longrightarrow E'_{2}.noeud.ajouter(noeud(id.val))$

Dans notre cas les attributs $N.noeud$ contiennent les nœuds de l'arbre abstrait de syntaxe et donc $E.noeud$ est l'arbre abstrait de syntaxe entier. Un problème se pose toujours lors de l'ordre d'application des règles. En effet la règle $E\rightarrow id\ E'\Longrightarrow E'.noeud.ajouter(noeud(id.val))$ nécessite que $E'$ contienne déjà un attribut $noeud$ valide. Pour résoudre ce problème, il est possible de préfixer l'ordre d'exécution des règles manuellement lors de leur conception ou déterminer par une analyse l'ordre d'exécution par la construction d'un arbre de dépendance entre les règles. Dans ce cas, les règles n'ayant aucune dépendance sont exécuté puis les autres.

Le programme exemple

Pour mettre en application les algorithmes d'analyse syntaxique, un programme à été écrit avec le support de l'analyse descendante et ascendante simple. Ce programme est disponible dans le dépôt : https://github.com/panzergame/analyseur_cmi

Un fois compilé, l'exécutable build/analyzer prend quatre arguments :

• input_file : Fichier texte à analyser.
• bnf_file : Fichier de description des productions.
• regex_file : Fichier de description des règles lexicales et des séparateurs.
• method : La méthode d'analyse, naive pour LL récursif, stack pour LL avec pile et slr pour SLR.
• Résultat : un historique de l'analyse en console et un arbre de dérivation au format .dot : derivation_tree.dot.

Les fichiers de description de règles bnf_file et regex_file utilise le format Backus Naur Form, encadrant chaque non-terminal par "<>" et associant des producitons à des non-terminaux grâce à "::=", ainsi $N\rightarrow ab$ s'écrit :

N ::= a b

Pour analyser les expressions simple de la forme "a + b", il faut tout d'abord définir les règles de l'analyseur lexical ainsi que les séparateurs additionnels :

<separator> ::= +-/*

<integer> ::= [0-9]*
<float> ::= [0-9]*\.[0-9]*f?
<identifier> ::= [A-z]([A-z]|[0-9])*
<operator> ::= \+|\-|/|\*

Ici quatre unités lexicales sont définit pour reconnaitre les entiers (integer), les flottants (float), les noms (identifier) et les opérateurs (operator). De plus les opérateurs sont aussi utilisés pour séparer la chaîne d'entrée.

Ensuite pour un analyseur ascendant les règles seront au format BNF :

<value> ::= identifier | float | integer
<expr> ::= <value> operator <expr> | <value>
<root> ::= <expr>

Ici nous validons les mots composés de valeurs entremêler d'opérateurs, où les valeurs peuvent être des noms, entiers ou flottants. Le nom-terminal

<root>

et le nom prédéfinit pour l'axiome de la grammaire.

Pour le fichier input_file contenant "5 + 4.2 - 80", l'exécution de la commande avec le méthode slr produit en console un récapitulatif des règles présente puis un historique de l'analyse et un affichage de l'arbre de dérivation qui se retrouve aussi dans derivation_tree.dot :