Langages algébriques

Les langages réguliers présentés dans le chapitre précédent sont très efficaces, mais en même temps présentent certaines limites. Ils peuvent être utilisés, par exemple, avec les mots-clés, le nom des identificateurs dans les langages de programmation, les nombres, etc.

Mais pour certaines applications plus intéressantes, telles que : l’analyse de syntaxes d’un langage de programmation, le langage de parenthèses, des palindromes, des expressions arithmétiques, l’analyse de structure de block ({…} en C, begin … end en PASCAL, …), les langages réguliers ne sauront pas les inclure, ni ses outils les manipuler ; c’est ici qu’il faut faire intervenir les langages algébriques.

Les langages algébriques (hors-contexte ; Context-Free, en anglais), deuxième du niveau dans la hiérarchie de Chomsky. Introduits initialement pour modéliser les langues naturelles, ils vont s’avérer être particulièrement intéressants et adaptés pour décrire la syntaxe des langages de programmation.

Il faut le signaler tout de suite, sans renverser l’ordre, les langages hors-contexte peuvent faire ce que font les langages réguliers, ce dernier est inclut au premier.

Autant qu’il en était du langage régulier, c’est grâce à ses outils (Expressions régulières, automates, etc.), qu’on arrive à démontrer que tel ou tel autre langage fait partie de la classe des langages réguliers ou carrément il en est un ; voici les outils des langages hors-contexte, lesquels servent aussi à prouver que tel langage est un langage hors-contexte, on :

  • Les automates à piles : l’équivalent de l’automate à état fini, sert à la reconnaissance du langage hors-contexte ;

  • La grammaire hors-contexte : l’équivalent de la grammaire régulière, et elle permet, en même que la génération, la description (comme les expressions régulières) du langage hors-contexte.

Dans ce chapitre, nous allons nous appesantir uniquement sur les automates à piles.

Figure 16 : Automate à Pile
                     Figure 16 : Automate à Pile

III.1 Automate à Pile

Un automate à pile (pushdown automaton) possède les différents éléments d’un reconnaisseur (bande de lecture, tête de lecture, unité de contrôle), sa particularité est son mode de stockage : une pile dans laquelle sont stockés des symboles d’un alphabet particulier appelé alphabet de pile. Comme l’automate sans pile, la tête de lecture ne peut se déplacer que d’une case à chaque mouvement, de gauche à droite.

Nota : Les automates à état fini, sans pile, peuvent en fait être aussi représentés comme un automate à pile, mais dont le pile n’est pas exploitée (pas d’empilement, ni de dépilement), mais pas l’inverse.

L’automate peut stocker et accéder à la pile mais comme son nom l’indique, uniquement au sommet. Ce type d’automate est capable, par exemple, de reconnaitre parce que la pile lui permettre de se souvenir de nombre du n caractère déjà lus.

Le mouvement d’un tel automate va être déterminé par 3 paramètres ; le symbole à la tête de lecture, l’état courant et le symbole en sommet de la pile. Par ailleurs, le mouvement d’un tel automate consistera en un déplacement de la tête d’une case à autres (sauf en cas d’ ) et le dépilement du caractère en sommet de pile et l’emplacement d’un caractère sur de la pile pour le cas particulier d’.

III.1.1 Définition

Formellement, on définit un automate à pile par un sextuple (Q, X, R, , ,, F) :

  • Q est un ensemble fini d’Etats ;

  • X est l’alphabet d’entrée (souvent noté) ;

  • R est l’alphabet de pile ;

  • est l’application de transition.: Q x (X) x {R) Q X R*

  • Q, est l’état initial

  • R, est le symbole de fond de pile

  • F C Q, est l’ensemble des états d’acceptation

Pour définir de façon précise un tel automate, il est pratique d’introduire la notion de configuration ; une configuration représente tous les aspects pertinents de la machine dans une situation donnée. On la définit comme un triplet :

(q, m,) Q x X* x R*, où :

  • q : est l’état courant de l’unité de contrôle ;

  • m : représente la partie du mot à reconnaitre non encore lue. Le symbole le plus à gauche de m est le caractère sous la tête de lecture ;

  •  : représente le contenu de la pile (si on la couche gauche). Le symbole le plus à gauche d’ est le symbole actuellement en sommet de la pile.

Une configuration, comme pour un automate sans la pile, permet de faire aussi des exécutions de mots, en vue de prouver qu’ils existent.

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s