Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 161 2.3

Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 161 2.3 : Théorie des langages Plan du chapitre: 1. Notations et définitions générales 2. Grammaire formelle ou algébrique 2.1 Monoïde 2.2 Grammaire formelle 2.3 Opérations sur les mots 2.4 Langage engendré par une grammaire 2.5 Grammaire d’états finis 2.6 Arbre de dérivation d’un mot 2.7 Diagrammes syntaxiques 3. Classification de Chomsky des grammaires 3.1 Les grammaires syntaxiques 3.2 Les grammaires sensibles au contexte 3.3 Les grammaires indépendantes du contexte 3.4 Les grammaires d’états finis ou de Kleene 4. Applications et exemples 4.1 Expressions arithmétiques : une grammaire ambiguë 4.2 Expressions arithmétiques : une grammaire non ambiguë Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 162 1. Notations et définitions générales Un langage est fait pour communiquer. Les humains doivent communiquer avec les ordinateurs : ils ont donc élaboré les bases d’une théorie des langages. Dans ce chapitre nous donnons les fondements formalisés d’une telle théorie autour de la notion de grammaire formelle. Remarque et convention :  Certains éléments d’un langage s’appellent les symboles.  Soit S un ensemble de symboles (S ). Ce sont les éléments indécomposables dans ce langage (c’est-à-dire non exprimables en autres symboles du langage). Définition expression sur S On appelle expression sur S, toute suite finie de symboles de S. e : [ 1, n ] S , e est une expression sur S, n est un entier naturel, n  1. ( e est alors un métasymbole décrivant l’expression S ). Notation: On désigne e par : e = s1s2s3...sn , n  1 où : k, 1  k n , sk S et par définition e (k) = sk ( k [1, n] ). On note S+ = { e / e, e expression sur S } S+ est l'ensemble de toutes les expressions formées sur S. Définissons deux opérations sur S+ : L'égalité d’expressions Soient e1 et e2 deux expressions sur S, on définit leur égalité ainsi : e1 = e2 ssi k , k 1 e1 : [1, k]S e2 : [1, k]S i, 1 i k e1(i) = e2(i) Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 163 la concaténation d’expressions soient eS+ et f  S+, on construit le "produit" des deux expressions e.f : e : [1, n]  S f : [1, p] S e.f: [1, n+p] S avec : e.f(i) = e(i) ssi i [1, n] e.f(i) = f(i) ssi i [n+1, n+p] Notation : (la concaténation de 2 expressions sur S ) Soient e et f deux expressions : e = s1s2s3...sn f = t1t2t3...tp e.f est notée : s1s2s3...sn t1t2t3...tp 2. Grammaire formelle ou algébrique Comme dans les langages naturels, les informaticiens ont, grâce aux travaux de N.Chomsky, formalisé la notion de grammaire d’un langage informatique. 2.1 Monoïde A) Soit A un ensemble fini appelé alphabet ainsi défini : A = { a1 ,..., an } ( A ) Notations : A1 = A A2 = { x1x2 / (x1A) et (x2A) } A3 = { x1x2x3 / (x1A) et (x2A) et (x3 A) } .......... An = { x1x2....xn /  i, 1 i  n , (xi A) } convention A0 = { } (appelé séquence vide) Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 164 B) On note A*et A+ les ensembles suivants : A+ = A* - { } = A* - A0 On définit sur A* une loi de composition interne appelée concaténation, notée : ( x, y ) x y = xy (noms des symboles accolés) La concaténation possède les propriétés suivantes :  La loi est associative : (x y) z = x (y z)  l’élément est un élément neutre pour la loi  :  x  A* , x  =  x = x Définition : ( A*, ) est un monoïde libre 2.2 Grammaire formelle Notations : Un alphabet est aussi appelé vocabulaire ; une chaîne ou un mot est un élément d’un monoïde ; la longueur d’un mot x (ou chaîne) est le nombre d’éléments du vocabulaire qui le compose et elle est notée habituellement |x|. Exemple : Vocabulaire V = { a , b } x = aaabbaab , x V* et |x| = 8 Remarque : On note |x|a le nombre de symboles " a " du vocabulaire V composant le mot x. x = aaabbaab |x|a = 5 et |x|b = 3 Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 165 Définition : C-Grammaire On appelle C-Grammaire (ou, grammaire algébrique de type 2) tout quadruplet : G = ( VN, VT, S, R ) où : VN est un vocabulaire non terminal ou auxiliaire ( VN  ) VT est un vocabulaire terminal ( VT  ) S VN , un élément particulier appelé axiome de G VN VT =  R  ( VN  VT )* x ( VN  VT )* , R est un sous-ensemble fini Notations :  R est appelé l’ensemble des règles de la grammaire G ;  Une règle riR est de la forme ( A ,  ) / [ A VN et  ( VN  VT )* ] , Elle est notée : ri : A    Lorsque  VT * , la règle ri : A  , est dite règle terminale. Nous ne considérerons par la suite que les grammaires dites de type 2 encore appelées grammaires indépendante du contexte (Context Free), dans lesquelles les règles ont la forme suivante : R  VN x ( VN VT )* 2.3 Opérations sur les mots Soit G une C-Grammaire, G = (VN,VT, S, R). On définit sur ( VN VT )* une relation binaire appelée " dérivation directe " notée définie comme suit : Définition : dérivation directe Soient a  ( VN  VT )*et b  ( VN  VT )* On note a b et l’on dit que b dérive directement de a, ou que a se dérive directement en b, si et seulement si 1°)    ( VN  VT )* 2°)    ( VN  VT )* 3°)  ri R, telle que : ri : Ai  4°) a et b s'écrivent : a =  Ai  b =    Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 166 Notation : On emploie aussi les termes de " règle de réécriture " ou de " règle de dérivation ". Nous obtenons un processus de construction des mots de la grammaire G par application de la dérivation directe. Si l’on réitère plusieurs fois ce processus de dérivation directe, on obtient à partir d’un mot, une suite de mots de G. En fait il s’agit de construire la fermeture transitive de la relation binaire . Cette nouvelle relation est appelée la dérivation dans G (la dérivation directe en devenant un cas particulier) Définition : dérivation On dit que x se dérive en y, s’il existe une suite finie de dérivations directes permettant de passer de x à y : (x, x0, x1,...,xn et y) étant des mots de ( VN  VT )*on a le chemin suivant : x x0 x1 .... xn  y on écrit : x * y , que l'on lit : x se dérive en y. * est la fermeture transitive de la relation binaire  2.4 Langage engendré par une grammaire Nous nous intéressons maintenant à toutes les dérivations possibles construites dans G, par application des règles de G, en privilégiant un point de départ unique pour chacune des dérivations. Nous avons vu que chaque règle de G commençait en partie gauche par un élément de VN. Nous construisons alors toutes les productions ayant comme point de départ S l’axiome de G. L’ensemble L de tous les mots construits s’appelle le " langage engendré par la grammaire G " : L  VT *. Définition : langage engendré Soit la C-grammaire G, G = ( VN , VT , S , R ) L’ensemble L(G) = { u  VT * / S * u } s'appelle le langage engendré par G. Les bases de l’informatique - programmation - ( rév. 04.01.2005 ) page 167 Exemple grammaire G0 : G0 : VN = { S } ,VT = {a,b} Axiome : S Règles 1 : S aSb 2 : S ab Le langage engendré par G0 est : L(G0) = { anbn / n  1 } 2.5 Grammaire d’états finis Ce sont des C-Grammaires dans lesquelles les parties droites de règles ont une forme particulièrement simple (on classifie d’ailleurs les grammaires algébriques en général en 4 types en fonction de la forme de leurs règles. Les C-grammaires sont dites de type-2 et les K-grammaires ou grammaires de Kleene sont dites de type-3). Pour une grammaire de type-3 ou K-grammaire les règles sont uploads/s3/ theorie-des-languages-pdf.pdf