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é, il forme essentiellement la chaine 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. Par exemple une grammaire pourrait définir le non-terminal expr qui englobe toutes le expressions mathématique 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 --> \gamma
A : un non-terminal. \gamma : une composition de terminaux et non-terminaux.
Un non-terminal peut être dérivé par une des 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.
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érachie 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, 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.
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 -*> \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.
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.
Les automates finis
Un analyseur 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 Areconnaissables 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^nb^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.
TODO exemple prog
Les analyseurs syntaxiques
L'analyse syntaxique suit l'analyse lexical en se basant sur les unités lexicales définit par ce dernier. Ces unités lexicales sont nommées et utilisé en tant que terminaux par l'analyseur syntaxique.
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'a 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 forme 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^nb^n.
TODO image