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