Hiérarchie de Chomsky
| Image manquante EbaucheCrochets.png | Cet article est une ébauche concernant la linguistique, vous pouvez partager vos connaissances en le modifiant. |
La hiérarchie de Chomsky est une classification des langages décrits par les grammaires formelles, proposée en 1956 par le linguiste Noam Chomsky. Elle est aujourd'hui largement utilisée en informatique, en particulier pour la conception d'interpréteurs ou de compilateurs, ou encore pour l'analyse des langages naturels.
Voir l'article Grammaire formelle pour une brève présentation de la hiérarchie de Chomsky.
| Sommaire |
Définition
La grammaire d'un langage est définie grâce à quatre éléments :
- T (ensembles de mots) : terminaux
- N : non-terminaux
- R : règles
- S (S ∈ N) : symbole de départ
Les règles définissent les lois de construction du langage, sa grammaire. En français par exemple, la structure : sujet + verbe + compléments est un élément de grammaire. Il est bien entendu que les langages de notre planète ont des grammaires bien plus complexes que celle des langages de programmation.
4 catégories
Selon son auteur, il y a 4 familles de grammaires dont tous les langages font partie.
régulière ∈ hors contexte ∈ contextuelle ∈ générale
générale
aucune règle
Cette catégorie est impossible à traiter, la grammaire étant trop faible le temps pour savoir si une phrase appartient ou non à celle-ci n'est pas forcément fini.
contextuelle
(N ∪ T)* ↦ (N ∪ T)*
Où la seconde partie est plus petite que la première (ce qui permet lors de la recherche de ne pas poursuivre trop longtemps de mauvaises voies).
Contextuelle car le remplacement d'un élément non-terminal par un élément terminal peut dépendre des éléments autour de lui, de son contexte.
hors contexte
N ↦ (N ∪ T)*
Ici plus de context, ce qui signifie que les éléments non-terminaux sont traités individuellement.
régulière
N ↦ T N ↦ NT
La plus restrictive des 4.
exemple
une chaîne commence par un a et se termine par un z, elle peut contenir 0 à n = séparé par 1 à n - entre elles.
Mots (valides) :
- az
- a=z
- a=-=z
- a-=-=-z
- a-----z
Réponse :
T = {a,z,=,-}
N = {S,A,B}
S = {S}
R = {
S ↦ Az,
A ↦ A-,
A ↦ B=,
B ↦ A-,
A ↦ a,
B ↦ a
}