Introduction

Dans ce billet, nous allons expliciter les notions relatives à l’analyse syntaxique des langues et les grammaires formelles.

Au commencement était la grammaire…

Ce terme de “grammaire” doit vous être familier mais de quoi s’agit il exactement? Un truc casse pieds que l’on apprend à l’école primaire? Eh bien pas seulement. A l’école primaire, on nous apprend que la grammaire, c’est l’ensemble des règles qu’il faut appliquer pour écrire un français correct. Cette définition ne se rapporte en fait qu’à la grammaire de la langue française. Nous allons donc voir ici une généralisation de ce concept que l’on appelle la théorie des grammaires formelles.

Définition formelle

Une grammaire dans un sens formel se compose de quatre éléments :

• un ensemble de symboles dits “terminaux“
• un ensemble de symboles dits “non terminaux“
• un symbole appartenant à l’ensemble des symboles “non terminaux” qui se veut être la racine de notre grammaire, appelé l’axiome, noté conventionnellement S
• un ensemble de règles dites de production définissant les conventions de notre grammaire

Vous êtes perdus? Pas de panique, Nous allons voir ce que cela donne avec la grammaire française.

Exemple avec la grammaire française

• Les symboles terminaux : j’en écris depuis tout à l’heure. Ce sont les mots qui constituent notre langue.
• Les symboles non terminaux : ce sont ce que l’on pourrait appeler les concepts de la grammaire. Les concepts de Nom (chat, souris, lion, …), de Verbe (manger, sortir, …), de Sujet (le chat, le lion, la souris, …) ou encore de Déterminant (le, la, les, …) sont des exemples de non terminaux de la grammaire française
• L’axiome : disons que c’est le concept “imaginaire”, racine de la grammaire. Toute phrase écrite dans un français correct fait partie de ce concept et inversement, les autres n’en font pas partie. On verra par la suite un exemple qui explicitera mieux cela.
• Les règles : ce sont les fameuses règles à appliquer pour écrire correctement le français. Elles permettent de définir concrètement les moyens d’obtenir des non terminaux (concepts de la grammaire) à partir d’autres non terminaux et de terminaux (les mots).

Prenons un exemple avec une pseudo grammaire française :

S -> VN
VN -> SU V
SU -> D N
D -> le | un
N -> chat | lion
V -> mange | sort

Dans cette exemple minimaliste, les non terminaux sont constitués par les concepts de verbe (V), nom (N), déterminant (D), sujet (SU), noyau verbal (VN) ainsi que par l’axiome S de notre grammaire. Les terminaux sont quant à eux, les mots le, un, chat, lion, mange et sort. Chaque ligne représente une règle de production différente où le non terminal de la partie gauche peut être obtenu en combinant les terminaux / non terminaux de la partie droite.

Ainsi, un nom peut être obtenu par le terminal “chat” ou bien par le terminal “lion” (5ème règle). De même, un noyau verbal peut être obtenu en combinant successivement un sujet et un verbe (2ème règle). Enfin, l’axiome de la grammaire peut être obtenu en réalisant un noyau verbal (1ère règle). Il faut comprendre par là que toute phrase correcte pour cette pseudo grammaire est constituée d’un noyau verbal.

Exemple avec une grammaire formelle et notion de dérivation

Voici un autre exemple de grammaire, non rattaché à la langue cette fois :

S -> Ab
A -> AA|B
B -> a|b

Où S est le non terminal jouant le rôle d’axiome, A et B des non terminaux et a et b les terminaux.

De manière générale, une grammaire permet de générer un langage (le langage français dans le cadre de la grammaire française). On dit alors que le langage est accepté, reconnu par la grammaire. Un langage se caractérise par l’ensemble des dérivations de la grammaire l’ayant engendré. Les dérivations sont des séquences de symboles terminaux de la grammaire de telle manière que l’application successive des règles de la grammaire depuis l’axiome permette d’aboutir à cette séquence de terminaux. Une dérivation est parfois aussi appelée un mot du langage (mais ne correspond pas avec la notion de mots dans la langue française).

Pour notre grammaire d’exemple, le mot (dans le sens des grammaires formelles) bbab est une dérivation de la grammaire car une application successive des règles de notre grammaire permet d’obtenir cette séquence de terminaux à partir de l’axiome.

Par contre, le mot aba n’est pas une dérivation de cette grammaire et n’appartient donc pas au langage généré par cette dernière car le dernier symbole terminal de la séquence ‘a‘ ne peut être obtenu en appliquant les règles successives.

De manière formelle, l’ensemble des mots dérivés de cette grammaire peut être représenté par l’expression régulière “[ab]+b“. Cela en fait une grammaire de type régulière comme nous l’explicitons par la suite.

Pour notre pseudo grammaire française, le mot “le chat sort” est une dérivation tandis que le mot “le chat dort” n’en est pas une.

5 types de grammaires : la hiérarchie de Chomsky

Dans ses travaux, Chomsky distingue 5 types de grammaires (dont 4 sont en fait couramment utilisés dans l’état de l’art) dans ce qu’il appelle la hiérarchie de Chomsky :

• Les grammaires récursivement énumérables ou de type 0 dans la hiérarchie
• Les grammaires contextuelles ou de type 1 dans la hiérarchie
• Les grammaires non contextuelles ou de type 2 dans la hiérarchie
• Les grammaires régulières ou de type 3 dans la hiérarchie

On parle de hiérarchie car tous les langages / grammaires d’un niveau x dans la hiérarchie sont également inclus dans les niveaux y de la hiérarchie où y<x (forme de pyramide comme l’illustre le schéma ci dessus). Ainsi, les grammaires non contextuelles sont aussi contextuelles (avec un contexte nul) et récursivement énumérables (si un mot appartient à un langage généré par une grammaire, on peut le déterminer en un temps fini) mais pas nécessairement régulières (dont les dérivations sont descriptibles par une expression régulière).
De manière simpliste, les langages naturels peuvent être traités en tant que non contextuels (type 2) même si cela n’est pas toujours vérifié.

A chaque type de grammaire / langage correspond des méthodes d'analyses particulières (valables donc aussi pour les niveaux plus élevés de la hiérarchie)

… puis vint l’analyse syntaxique

L’analyse syntaxique est le procédé visant à établir un arbre de dérivation entre une grammaire et une séquence de terminaux donnée (une dérivation si l’analyse est un succès). En d’autre terme, il s’agit de déterminer si la séquence est un dérivation de la grammaire.

L’arbre généré nous indique les différentes étapes de dérivation à appliquer à partir de l’axiome pour aboutir à la dérivation. Les schémas d’arbre réalisés dans le premier paragraphe sont des exemples d’arbres de dérivation.

On distingue deux types d’analyse : les premières sont du type analyse descendante ou top-down et visent à parvenir à la séquence de terminaux visée depuis l’axiome. Les secondes sont du type analyse montante ou bottom-up et visent à parvenir à l’axiome en partant de la séquence de terminaux visée.

Les analyses bottom-up sont intéressantes dans le sens où elles permettent plus facilement des analyses partielles que les top-down. C’est pourquoi dans des contextes peu rigoureux au niveau syntaxique, elles sont souvent préférées car elles renvoient toujours au moins un résultat partiel contrairement aux top-down qui ne peuvent qu’échouer dans la plupart des cas.

Deux méthodes d’analyse servent de références dans le domaine des grammaires non contextuelles (type 2 et 3 de la hiérarchie) :

• l’analyse CYK pour les analyse bottom-up
• l’analyse Earley pour les analyses top-down

D’autres méthodes d’analyses existent également pour chacun des types de grammaire de la hiérarchie de Chomsky. Quelques exemples sont disponibles sur la page wikipédia consacrée à l’analyse syntaxique.

Perspectives

Je réalise en ce moment une étude sur les parseurs syntaxiques existants en licence open source ayant atteint un niveau “état de l’art”. Je pense donc réaliser un billet ultérieurement sur ces parseurs et leurs performances.

Mots clefs : analyse syntaxique, grammaire formelle, hiérarchie de Chomsky, TAL

Cette entrée a été publiée le Mercredi 27 octobre 2010 à 13 h 50 min, et rangée dans TAL. Vous pouvez suivre les réponses à cette entrée via son flux RSS 2.0. Vous pouvez laisser un commentaire, ou faire un rétrolien depuis votre site.