Remerciez-le!

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

13/10/2015 1 Cours de théorie des langages Responsable du cours et des TDs : Mr

13/10/2015 1 Cours de théorie des langages Responsable du cours et des TDs : Mr. BESSAOUD Le 30/09/2015 1 Objectifs de la matière • La théorie des langages a pour objectif de décrire les langages formels. • L’objectif de cette matière est de maîtriser les types de langages existants ainsi que les automates qui permettent de les reconnaître. • Ce cours est une base pour le cours de compilation. 2 Un Langage • Qu'est-ce qu’un langage ? Tout système permettant de s’exprimer. Exemple : ▫Langage linguistique ▫Langage mathématique ▫Langage informatique • La théorie des langages étudie les aspects purement syntaxiques de tels langages, c'est-à-dire leurs structures internes formelles. • Syntaxe des langages : ▫Mots ▫Symboles 3 Un alphabet • Un ensemble de symboles fini permettant de construire les mots d’un langage. • Exemple : ▫{0,1} ▫{if, then, else, x, y, z} ▫{+, -, *, /, =, a, b} 4 Un mot • Un mot sur un alphabet est une séquence finie et ordonnée, éventuellement vide, de symboles de l’alphabet. • Exemple : ▫100111 est un mot de l’alphabet {0, 1} ▫a=b est un mot de l’alphabet {+, -, *, /, =, a, b} • Le mot vide est noté ε. 5 Propriétés • La longueur d’un mot m est noté m. • La concaténation : Soient deux mots u et v définis sur un alphabet A. La concaténation de u avec v, notée u.v ou simplement uv, est le mot formé en faisant suivre les symboles de u par les symboles de v. 6 13/10/2015 2 La puissance • On note A+ l’ensemble des mots de longueur supérieure ou égale à 1 que l’on peut construire à partir de l’alphabet A. • On note A∗l’ensemble des mots que l’on peut construire à partir de A, y compris le mot vide : A∗= {ε} ∪A+ • Etant donnée u et v deux mots, on note : ▫(uv)2 pour uvuv ▫u3v pour uuuv ▫(u3v)2 pour uuuvuuuv 7 Un langage • Un langage, défini sur un alphabet A, est un ensemble de mots définis sur A. Autrement dit, un langage est un sous-ensemble de A∗. • Description d’un langage : ▫Un langage fini peut être décrit par l’énumération des mots qui le composent. ▫Certains langages infinis peuvent être décrits par l’application d’opérations à des langages plus simples. ▫Certains langages infinis peuvent être décrits par un ensemble de règles appelé grammaire. ▫Enfin, certains langages infinis ne peuvent pas être décrits, ni par l’application d’opérations, ni par un ensemble de règles. On parle alors de langage indécidable. On peut noter que si un langage est indécidable, alors il n’existe pas d’algorithme permettant de déterminer si un mot donné appartient à ce langage. 8 Une grammaire • Un langage peut être décrit par un certain nombre de règles. Pour les langages naturels, le but étant de donner une description précise des règles permettant de construire les phrases correctes d’une langue. • Dans notre contexte, le but est de donner une description précise des règles permettant de construire tous les mots d’un langage. • Remarques : Une grammaire définit un seul langage. Par contre, un même langage peut être engendré par plusieurs grammaires différentes. 9 Une grammaire • Une grammaire est un quadruplet G = (T, N, S, R) tel que : ▫T est le vocabulaire terminal, c’est-à-dire l’alphabet sur lequel est défini le langage. ▫N est le vocabulaire non terminal, c’est-à-dire l’ensemble des symboles qui n’apparaissent pas dans les mots générés, mais qui sont utilisés au cours de la génération. Un symbole non terminal désigne une “catégorie syntaxique”. ▫S ∈N est le symbole de départ ou axiome. C’est à partir de ce symbole non terminal que l’on commencera la génération de mots au moyen des règles de la grammaire. ▫R est un ensemble de règles de production de la forme : u →v, avec u ∈(N ∪T)+ et v ∈(N ∪T)∗ 10 La règles de production • u →v, avec u ∈(N ∪T)+ et v ∈(N ∪T)∗ ⇒u ne peux pas être ε. • On dit que v dérive directement de u. • Lorsqu’on a u →u1→u2→u3…→u4→v : on dit que v dérive de u et on le note u→v • L(G)= {m∈T* / S →m} 11 * * Exemple de grammaire • Soit une grammaire G = (T, N, S, R) tel que : ▫T={0,1} ▫N={S} ▫R={S →0S/1S/ε} • Exemple de mots générés par cette grammaire : ▫ε : S→ε ▫0 : S→0S→0 ▫1 : S→1S→1 ▫00 : S→0S→00S→00 ▫01 : S→0S→01S→01 ▫11, 10, 000, 110, 101… • La grammaire génère les nombres binaires. • Le langage généré par cette grammaire est : (0*1*)* 12 13/10/2015 3 Types de grammaires • En introduisant des critères sur la forme des règles de grammaire, on obtient des classes de grammaires hiérarchisées, ordonnées par inclusion. La classification de CHOMSKY, distingue quatre classes de grammaires : ▫Type 3 : grammaires régulières génères des langages réguliers, ▫Type 2 : grammaires algébriques génères des langages algébriques, ▫Type 1 : grammaire contextuelles génères des langages contextuels, ▫Type 0 : grammaire sans restriction génères des langages décidables. 13 Types de grammaires • Il existe une relation d’inclusion entre ces 4 types de grammaires : type 3 ⊆type 2 ⊆ type 1 ⊆type 0. • Par contre, on entend par grammaire de type i le premier type satisfaisant la grammaire en commençant par le plus restrictif. • Une grammaire de type 1 sous entend implicitement qu’elle n’est pas de type 2 et donc pas de type 3. 14 Type 3 Type 2 Type 1 Type 0 Grammaires de type 3 • Il existe deux types de grammaires régulières : ▫Grammaires régulières à droite : Les règles de R sont de la forme S →aS’ ou S →a avec S, S’ ∈N et a ∈T ▫Grammaires régulières à gauche. Les règles de R sont de la forme S →S’a ou S →a avec S, S’ ∈N et a ∈T • La partie gauche de chaque règle est constitué d’un seul symbole non terminal, et la partie droite est constitué d’un symbole terminal et éventuellement d’un symbole non terminal. • Pour les grammaires régulières à droite, le symbole non terminal doit toujours se trouver à droite du symbole terminal tandis que pour les grammaires régulières à gauche, il doit se trouver à gauche. 15 Grammaires de type 2 • Les règles de R sont de la forme : S →m avec S ∈N et m ∈(N ∪T)* • La seule restriction concerne la partie gauche de la règle qui doit être constitué d’un seul symbole non terminal. 16 Grammaires de type 1 • Les règles de R sont de la forme : uSv →umv avec S ∈N, u, v∈(N∪T)* et m∈(N∪T)+ • Le symbole non terminal S est remplacé par m tout en gardant le préfixe u à gauche et le suffixe v à droite. 17 Grammaires de type 0 • Pas de restriction sur les règles 18 13/10/2015 4 Automates • Le mot 1101 appartient-il au langage (0*1*)*? • Un automate est une machine qui permet de lire un mot m et de dire formellement si m appartient à un langage donné. • Un automate est un reconnaisseur qui permet de reconnaitre tous les mots d’un langage. 19 Composition d’un automate • Il existe plusieurs types d’automates, cependant, ils ont tous une structure commune. • Un automate est composé de quatre parties : 1. une bande de lecture 2. une tête de lecture 3. une mémoire 4. une unité de contrôle 20 La bande de lecture • Une bande de lecture est composée d’une succession de cases. • C’est dans les cases de cette bande de lecture qu’est écrit le mot à reconnaître. • Chaque case pouvant contenir un seul symbole de l’alphabet d’entrée. 21 La tête de lecture • Une tête de lecture peut lire une case à un instant donné. • La case sur laquelle se trouve la tête de lecture à un moment donné s’appelle la case courante. • La tête peut être déplacée par l’automate pour se positionner sur la case immédiatement à gauche ou à droite de la case courante. 22 La mémoire • La mémoire n’est pas toujours présente dans un automate. • La mémoire possède un alphabet spécial. • La mémoire est caractérisée par des fonctions de recherche et de stockage. 23 L’unité de contrôle • L’unité de contrôle constitue le cœur d’un automate. • Elle peut être vue comme un programme qui dicte à l’automate son comportement. • Elle est définie par un ensemble fini d’états ainsi que par une fonction de transition qui décrit le passage d’un état à un autre en fonction du contenu de la case courante de la bande de lecture et du contenu de la mémoire. • L’unité de contrôle décide aussi de la direction dans laquelle déplacer la tête de lecture et choisit quels symboles stocker dans la mémoire. 24 13/10/2015 5 Définition formelle d’un automate • Un automate contient au minimum : ▫Un alphabet pour les mots en entrée noté uploads/s3/ cours-de-theorie-des-langages.pdf