Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Hiérarchie de Chomsky

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.

Langages

Un langage est un ensemble de mots, qui sont simplement des séquences de symboles choisi dans un ensemble fini appelé alphabet. Les langages de la hiérarchie de Chomsky sont formés de mots qui respectent une grammaire formelle particulière. Ce qui les distingue dans le cadre de la classification est la nature de la grammaire.

(Le plus souvent, les « symboles » que l'on considère sont formés de plusieurs caractères, de sorte qu'ils correspondent plutôt à ce que l'on appelle des mots dans la langue courante. Lorsqu'il y a ambiguïté, par exemple en analyse lexicale et syntaxique, on parle de caractères pour les symboles de l'alphabet utilisé pour coder les informations, et de lexèmes pour les symboles de l'alphabet abstrait, qui sont les unités de base du langage. De même, les « mots » du langage correspondent plutôt à des phrases ou à des textes.)

Grammaires formelles

Une grammaire formelle, ou simplement grammaire, est formée d'un ensemble fini de symboles terminaux (qui sont les lettres ou les mots du langage), d'un ensemble fini de non-terminaux, d'un ensemble de productions dont les membres gauche et droits sont des mots formés de terminaux et de non-terminaux, et d'un axiome. Appliquer une production consiste à remplacer son membre de gauche par son membre de droite ; l'application successive d'un certain nombre de productions s'appelle une dérivation. Le langages défini par une grammaire est l'ensemble des mots formés uniquement de symboles terminaux qui peuvent être atteints par dérivation à partir de l'axiome.

On note habituellement les terminaux par des lettres minuscules, les non-terminaux par des majuscules, et l'axiome par la lettre S. Ainsi, la grammaire de terminaux {a, b}, de non-terminaux {S, A, B}, et de productions

S → ABS

S → ε (où ε désigne le mot vide)

BA → AB

BS → b

Bb → bb

Ab → ab

Aa → aa

et d'axiome S définit le langage des mots de la forme (un certain nombre de 'a', suivi du même nombre de 'b').

La hiérarchie de Chomsky

La hiérarchie de Chomsky est formée des quatre niveaux suivants, du plus restrictif au plus large.

• Les langages de type 3, ou langages réguliers : ce sont les langages définis par une grammaire régulière ou une expression régulière, ou bien encore les langages reconnus par un automate fini.

• Les langages de type 2, ou langages algébriques : ce sont les langages définis par une grammaire formelle hors-contexte, ou bien encore les langages reconnaissables par un automate à pile non déterministe. Dans cette catégorie se trouvent les langages de programmation informatique.

• Les langages de type 1, ou langages contextuels : ce sont les langages définis par une grammaire contextuelle, ou encore les langages reconnaissables par une machine de Turing non-déterministe à ruban de longueur bornée par un multiple fixé de la longueur du mot d'entrée.

• Les langages de type 0, ou langages récursivement énumérables. Cet ensemble inclut tous les langages définis par une grammaire formelle. C'est aussi l'ensemble des langages acceptables par une machine de Turing (que l'on autorise à boucler sur un mot qui n'est pas du langage).

Outre les 4 types de la hiérarchie de Chomsky, il existe des classes intermédiaires remarquables :

• entre 3 et 2 : les langages non-contextuels déterministes, reconnaissables par automate à pile déterministe ;
• entre 1 et 0 : les langages récursifs, c'est-à-dire reconnaissables par une machine de Turing (celle-ci doit refuser les mots qui ne sont pas du langage).

Les six types ci-dessus sont strictement inclus les uns dans les autres. Notons que si dans le type 1, on transforme « non déterministe » en « déterministe », on obtient un type plus petit, mais on ne sait pas montrer s'il est strictement inclus dans le type 1 ou s'il est égal à celui-ci.

Analyse

Un analyseur pour un langage formel est un programme informatique qui décide si un mot donné en entrée appartient ou non au langage, et éventuellement en construit une dérivation.

On dispose de méthodes systématiques pour écrire des programmes d'analyse des langages de type 2 ou 3. Les interpréteurs ou compilateurs comprennent presque toujours une phase d'analyse lexicale, qui consiste à reconnaître des langages de type 3, suivie d'une phase d'analyse syntaxique qui est une analyse de langage de type 2. Des outils comme lex et yacc facilitent l'écriture, respectivement, d'analyseurs lexicaux et d'analyseurs syntaxiques, en produisant automatiquement des portions de programmes à partir d'une spécification de la grammaire à reconnaître vérifiant certaines contraintes.