Remerciez-le!

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

Introduction et Généralités Description de la grammaire du langage source Lit

Introduction et Généralités Description de la grammaire du langage source Littéraire Un programme est une suite de définitions de fonction Une définition de fonction est composée du nom de la fonction suivie de ses arguments suivie de la déclaration de ses variables internes suivie d’un bloc d’instructions Une instruction est est une opération de base du processeur ou d'un langage de programmation, une opération que le programmeur demande à la machine d'exécuter. Introduction et Généralités Notion de langage But de la théorie des langages Le français est un langage, Java également. Le but de la théorie des langages est de donner un modèle de ce qu'est un langage Introduction et Généralités Notion de langage Un modèle d'aide • pour pouvoir décrire un langage ; • pour pouvoir décrire un langage ; • pour fabriquer une machine capable de reconnaître les textes qui appartiennent à un langage donné. Introduction et Généralités Notion de langage Problématique il faut donner une description finie d'un objet en général infini : il y a en effet une infinité de textes français, une infinité de programmes Java Introduction et Généralités Alphabets, Mots, et Langages Introduction et Généralités Alphabets, Mots, et Langages Introduction et Généralités Quelques opérations sur les mots Étant donné deux mots m1 et m2, la concaténation de m1 et de m2, notée m1.m2, ou notée m1m2, est le mot obtenu en mettant m2 à la fin de m1. Exemple: aba.ba est le mot ababa sur = {a, b}. Exemple: aba.ba est le mot ababa sur = {a, b}. La concaténation est une opération associative, avec un élément neutre, le mot vide . si m = m1m2, m1 est appelé un préfixe de m et m2 une suffixe de m. La longueur d’un mot m est le nombre de symboles qui le composent. Elle est notée par |m|. Exemples: |ababb|=5 , | ε|=0 Introduction et Généralités Quelques opérations sur les langages Soient L et L’ deux langages définis sur un alphabet Ω. - L L’ (ou L+L’ ou L | L’) est un langage sur un Ω obtenu par la réunion de L et L’, tel que: L L’= {m / m L ou m L’}. - L∩L’ est un langage sur un Ω obtenu par l’intersection de L et L’, tel que L∩L’= {m / m L et m L’}. - Le complément du langage L , noté par ,est obtenu par: = {m / m L} L L  - Le complément du langage L , noté par ,est obtenu par: = {m / m L} - LL’ est un langage sur un Ω obtenu par la concaténation de L et L’, tel que: L.L’ = {m / u L, v L’ : m = uv}. - Le langage exposant (itération) d’un langage L, noté Ln, est obtenu par: Ln=L.L...L= {m / u1, u2, ...un L : m = u1u2 ...un }. n L L  Introduction et Généralités Opérations sur les langages (Tableau récapitulatif) Notation Définition Nom L1  L2 = {p p  L1 ou p  L2} union L1 . L2 = {x . y x  L1 et y  L2} concaténation C(L) = {x x est une phrase sur  et x  L} complément C(L) = {x x est une phrase sur  et x  L} complément Ln = L . L . L . … . L exponentielle L0 = {} ou puissance L* = n  0 Ln étoile de Kleene a = {"a"} singleton  = { } (  !) langage vide  = {} mot vide Introduction et Généralités Grammaires formelles Les contraintes syntaxiques sont représentées sous la forme de règles de réécriture. La règle A BC , nous dit que le symbole A peut se réécrire comme la suite des deux symboles B et C. comme la suite des deux symboles B et C. L’ensemble des règles de réécriture constitue la grammaire du langage. La grammaire d’un langage L permet de générer tous les programmes corrects écrits en L et seulement ceux-ci. Introduction et Généralités Notations et Terminologie Dans la règle A a A est appelé partie gauche de la règle. a est appelé partie droite de la règle. Lorsque plusieurs règles partagent la même partie gauche : Lorsque plusieurs règles partagent la même partie gauche : A a1 , A a2 , . . . , A an On les note : o A a1 | a2 |. . . | an Introduction et Généralités Avantages des grammaires formelles Une grammaire formelle : Pousse le concepteur d’un langage à en décrire la syntaxe de manière exhaustive (précise et détaillée). Permet de répondre automatiquement à la question mon programme est-il correct? à l’aide d’un analyseur syntaxique. Fournit, à l’issue de l’analyse, une représentation explicite de l’organisation du programme en constructions (structure syntaxique du programme). Cette représentation est utile pour la suite du processus de compilation. Expression régulière et automates finis Expression régulière Définition Soit Ω un alphabet quelconque ne contenant pas les symboles { ,+,|,.,(,)}. Une expression régulière (ou rationnelles) est un mot défini sur l’alphabet Ω { ,+, |, ., (, )} permettant de représenter un langage régulier de la façon suivante : – L’expression régulière ε dénote le langage vide (L = {ε}) ; ∗ – L’expression régulière ε dénote le langage vide (L = {ε}) ; – L’expression régulière a (a Ω) dénote le langage L = {a} ; – Si r est une expression régulière qui dénote L alors (r)∗(resp. (r)+) est l’expression régulière qui dénote L∗(resp. L+) ; – Si r est une expression régulière dénotant L et s une expression régulière dénotant L′ alors (r)|(s) est une expression régulière dénotant L L′. L’expression régulière (r).(s) (ou simplement (r)(s)) dénote le langage L.L′. Alors on peut dire qu’une expression régulière est une notation qui permet de décrire un ensemble (une classe) de chaînes de caractères. Expression régulière et automates finis Expression régulière Exemples considérons l’alphabet Ω={0,1} 1- L’expression 0* décrit tous les mots composés uniquement du symbole 0 ainsi que le mot vide ε. (0000, 000,…..). 2- L’expression 110*1 décrit tous les mots contenant deux fois le symbole 1 suivis d’un nombre quelconque de symboles 0 ou vide et du symbole 1. (1100001, 110000001,……). 3- L’expression 0*110*1 est la concaténation des deux expressions 1 et 2. (00001100001, 00011001,……). 4- L’expression 0*|110*1 décrit l’expression des mots générées soit par l’expressions 1 ou par 2 (00000, 1100001, ……). Expression régulière et automates finis Expression régulière Exemples Un nombre entier non signé est une chaîne constituée d'une suite de chiffres, au moins un. L'expression régulière associée est: (chiffre)+ + est un opérateur unaire post-fixe qui veut dire un ou plusieurs fois Expression régulière et automates finis Propriétés algébriques sur les expressions régulières: Soit r,s et t des expressions régulières. r|s = s|r : l'opérateur| (ou) est commutatif. r|(s|t) = (r|s)|t : l'opérateur | est associatif. (rs)t = r(st) : la concaténation est associative. r(s|t)=rs|rt :la concaténation est distributive par rapport au | ε r = r ε = r : ε est l'élément neutre de la concaténation. r* =(r| ε)* : ε est inclus dans une fermeture. Remarque: la chaîne vide ε = s° Expression régulière et automates finis Notations: * est un opérateur unaire poste-fixe qui veut dire zéro, un ou plusieurs fois. + est un opérateur unaire poste-fixe qui veut dire un ou plusieurs fois. r+ = r r* = r*r r+ = r r* = r*r r* = r+| ε ? est un opérateur unaire poste-fixe qui veut dire zéro ou une fois. r? = r| ε [a-z] désigne un élément (une lettre) de cette classe. [a-z] = a|b|c...|z Expression régulière et automates finis Priorité 1- L' opérateur unaire poste-fixe * a la plus haute priorité et est associatif à gauche. 2- Les opérateurs + et ? ont la même priorité et la même associativité que *. associativité que *. 3- La concaténation a la deuxième priorité et est associative à gauche. 4- Le | a la plus faible priorité et est associatif à gauche. Selon ces conventions, (a)|((b)*(c)) est équivalente à a|b*c Expression régulière et automates finis Langages réguliers Définition Les langages réguliers (ou rationnels) sont les langages générés par des grammaires de type 3 (ou encore grammaires régulières) selon la hiérarchie de Chomsky. Ils sont reconnus grâce aux automates à états finis (Voir la partie suivante). Exemples: a∗: dénote le langage régulier an (n ≥ 0) ; (a|b)∗: dénote les mots dans lesquels le symbole a ou b se répètent un nombre quelconque de fois. Elle dénote donc le langage de tous les mots sur {a, b} ; (a|b)∗ab(a|b)∗: dénote tous les mots sur {a, b} contenant le facteur ab. Expression régulière et automates finis Langages réguliers Propriétés Soient L et L’ deux langages réguliers désignés respectivement par les expressions régulières r et s, nous avons : 1- L+L’ , L∩L’, , LR, L.L’, L∗(resp. L+) sont des langages réguliers. ∗ 2- L’union finie de langages réguliers représente un langage régulier. Ainsi, on uploads/Philosophie/ diapo2-compilation.pdf