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. 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, par exemple pour des expressions mathématiques composé d'opérateurs et d'opérandes.

Les grammaires

Les symboles de grammaire

Toutes les grammaires sont composées de symboles regroupé 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, 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. Ces grammaires 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.

TODO image

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$

Grâce aux productions il est possible de subdiviser un non-terminal en d'autres éléments égaux ou plus petits, cette opération est appelé dérivation est mène à produire une proto-phrase (la partie droite des productions), si une proto-phrase est constituée essentiellement de terminaux alors elle est nommé phrase.

Les analyseurs lexicaux

L'analyse lexicale couvrent toutes les règles de la grammaire régulière, elle est utilisé 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é 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.

L'union crée un ensemble constituée des deux mots, elle reconnaît l'un de deux mots seulement.

L'étoile de Kleene permet de créer un ensemble contenant toutes les combinaisons d'un ensemble ainsi que le vide.

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 operateurs, ensuite chaque portion de la chaine d'entrée est analysé selon un ensemble de règles rationnelles pour déterminer son unité lexicale.

Pour 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^{*}$

TODO image

Malheuresement 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 et 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é, la seconde technique consiste à réduire le mot d'entré jusqu'à obtenir l'axiome. Ces deux techniques sont considéré comme opposé par leur façon de traiter les proto-phrase, l'analyseur descendant va toujours dériver et l'analyseur ascendant toujours réduire. Malgré cette symétrie, ces deux type d'analyseur n'utilise 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}$.

TODO image

Les analyseurs descendants

Le principe de l'analyse descendante est assez simple à mettre en oeuvre. L'analyseur initialise une proto-phrase contenant l'axiome de la grammaire, à chaque étapes 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

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 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 choisir les productions à appliquer et que la grammaire possèdent 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.

Analyseur à symbole de prédiction

Un analyseur à symbole de prédiction, 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édiction.

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	Prefix	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$.