[PDF] Théorie des Langages - Expressions régulières et Grammaires

View - Download Théorie des Langages - Expressions régulières et Grammaires

Previous PDF

Next PDF

LangagesGrammaires

Théorie des Langages

Expressions régulières et Grammaires

Claude Moulin

Université de Technologie de Compiègne

Printemps 2013

LangagesGrammaires

Sommaire

1Langages

2Grammaires

LangagesGrammaires

DéfinitionsSommaire

1Langages

Définitions

Expressions régulières

ER et langages

Exercices

2Grammaires

Introduction

Dérivation

Types de grammaires

Expressions régulières et grammaires

LangagesGrammaires

DéfinitionsAlphabet

Définition :

Un alphabet est un ensemble fini non vide de symboles appelés également lettres de l"alphabet.1-1=f0;1g2-2=fa;b;:::;zg

LangagesGrammaires

DéfinitionsChaîne

Définition :

Une chaîne est une suite finie de symboles choisis dans un alphabet.1

1=f0;1g01011, 111, 00, ...

2

2=fa;b;c;:::;zgabc, aa, xyzt, ...

: chaîne vide; chaîne ne contenant aucun symbole.

LangagesGrammaires

DéfinitionsFonction - Opération

La longueur d"une chaîne est le nombre de symboles la composant. jabcj=3; jj=0Concaténation u=x1x2:::xnetv=y1y2:::ymdeux chaînes6=définies sur le même alphabet, uv=x1x2:::xny1y2:::ymconcaténation deuet dev.

LangagesGrammaires

DéfinitionsConcaténation

Propriétés de la concaténation

associative :8u;8v;8w;(uv)w=u(vw)élément neutre :juvj=juj+jvjnon commutative. En général,uv6=vu.Préfixe - Suffixe

8u6=;8v6=;8w6=

Lorsquew=uv, u est un préfixe dewet v est un suffixe dew.

LangagesGrammaires

DéfinitionsLangage

Définition :

Un langage défini sur un alphabetest un ensemble de chaînes définies sur.

2est le langage composé de toutes les chaînes de

longueur 2 sur est le langage composé de toutes les chaînes constructibles sur l"alphabetPour tout langageLconstruit sur un alphabeton a : L

LangagesGrammaires

DéfinitionsOpérations

Réunion, Intersection de deux langages

SoientL1etL2deux langages définis sur un alphabet. L

1[L2etL1\L2sont aussi deux langages définis sur.Concaténation de deux langages

SoientL1etL2deux langages définis sur un alphabet. L

1L2=fuv=u2L1;v2L2gest le langage obtenu par

concaténation deL1et deL2.

LangagesGrammaires

DéfinitionsClôture de Kleene

SoitLun langage défini sur un alphabet.Clôture de Kleene La clôture de Kleene du langageL, notéeLest l"ensemble des chaînes qui peuvent être formées en prenant un nombre quelconque (éventuellement 0) de chaînes deLet en les concaténant.L 0=fgL 1=LL 2=LLL i=LL:::L, la concaténation deifoisLL =S i0Li

LangagesGrammaires

Expressions régulièresSommaire

1Langages

Définitions

Expressions régulières

ER et langages

Exercices

2Grammaires

Introduction

Dérivation

Types de grammaires

Expressions régulières et grammaires

LangagesGrammaires

Expressions régulièresOpérateurs

Les expressions régulières sont une façon déclarative de décrire la formation des chaînes d"un langage. On noteL(E)le langage engendré par une expression régulièreE.Opérateur * (fermeture)

0 * représente :f;0;00;000;:::g110*1 représente :f111;1101;11001;:::gOpérateurj(disjonction)0*j1* représente les chaînes formées par 0* et par 1*, 0, 00, 000, 1, 11, 111, ...

LangagesGrammaires

Expressions régulièresRègles

la chaîne vide,, et l"ensemble vide,;, sont des

expressions régulières.L() =fgetL(;) =;.8a2, la chaîne formée de l"unique symboleaest une

expression régulière.L(a) =fag.

LangagesGrammaires

Expressions régulièresConstruction

SiEetE0sont des expressions régulières alors :EE

0est une expression régulière, concaténation deEetE0.

Elle décritL(EE0) =L(E)L(E0)EjE0est une expression régulière. Elle décritL(EjE0) =L(E)[L(E0)(E)est une expression régulière, décrivant le même langage queE.

L((E)) =L(E).E

est une expression régulière.L(E) =L(E)

LangagesGrammaires

Expressions régulièresExemples

ab*; a*b (ab)* (a | b)* a*b(a*b)*

Questions

(a* | b*) = (a | b)*? (a | b)* b = (a | b)*? (a*b)* = (a | b)*b?

LangagesGrammaires

Expressions régulièresExemples

Opérateur unaire + : au moins une fois

E +=EEOpérateur unaire ? : 0 ou 1 fois

E? =EjClasses de caractères :

[abc] =ajbjc [az] =ajbjcj:::jz [ACaz] =AjBjCjajbjcj:::jz

LangagesGrammaires

Expressions régulièresPriorité des opérateurs + et * sont des opérateurs unaires et ont la plus forte prioritéLa concaténation est un opérateur binaire et a la seconde

prioritéjest un opérateur binaire et a la plus faible prioritéConcaténation etjsont associatives à gaucheExemple :

(a) | ((b)*(c)) = a | b*c

LangagesGrammaires

Expressions régulièresLois algébriques

EjE0=E0jEEj(E0jE00) = (EjE0)jE00; jE=Ej ;=EEjE=EE(E0E00) = (EE0)E00E=E=E;E=E;=;E(E0jE00) =EE0jEE00(EjE0)E00=EE00jE0E00

LangagesGrammaires

Expressions régulièresConséquences

(E)=E; =E +=EE=EEE +j=EE? =Ejp(qp)=(pq)p(pjq)=(p jq)(pq)=(pjq)=(p jq)

LangagesGrammaires

Expressions régulièresDéfinitions régulières

lettre![A-Za-z]chiffre![0-9]id!lettre ( lettrejchiffre )*chiffres!chiffre (chiffre)*fraction!. chiffresjexposant!E( +j-j) chiffresjnombre!chiffres fraction exposantid reconnaît : a, a0b, begin

nombre reconnaît : 0, 1.0, 2E4, 1.5E-8, 0.25E-0 nombre ne reconnaît pas : 0., .1, 1E2.0

LangagesGrammaires

ER et langagesSommaire

1Langages

Définitions

Expressions régulières

ER et langages

Exercices

2Grammaires

Introduction

Dérivation

Types de grammaires

Expressions régulières et grammaires

LangagesGrammaires

ER et langagesER et langages - 1

Dans les langages de programmation les expressions

régulières ont deux utilisations :Elles permettent de vérifier qu"une chaîne respecte une

forme donnée;Elles permettent de rechercher des chaînes d"un type particulier à l"intérieur d"un texte.

LangagesGrammaires

ER et langagesER et langages - 2

Les expressions régulières étendent les opérateurs de base avec :des classes de caractères; des définitions de groupes; des conditions de limites (mots, ligne, fichier); des facteurs de répétitions; des motifs prospectifs.

LangagesGrammaires

ER et langagesClasses de caractères - 1

[:::]Union des caractères entre les crochets ^:::]Complémentaire des symboles entre les crochets [xy]L"un des symboles entrexetynd[0-9]nD[ ^0-9]nw[a-zA-Z0-9]nW[ ^a-zA-Z0-9]ns ounp{Space}[\t\n\x0B\f\r]nS[^\t\n\x0B\f\r]Exemple :ndnDnw20-juin-20120-j

LangagesGrammaires

ER et langagesClasses de caractères - 2

np{Lower}Un caractère minuscule np{Upper}Un caractère majuscule np{ASCII}Un caractère dont le code ascii est compris entre 0 et 128 np{Alpha}Un caractère minuscule ou majuscule np{Alnum}np{Alpha}[ np{Digit}np{Punct}[! "#$%&"() *+,-./:;<=>?@[\]^_'{j}~]np{Print}np{Alnum}[ np{Punct}np{Blank}Caractères espace ou tabulation np{XDigit}Un chiffre hexadécimal[0-9a-fA-F].Un caractère quelconque jUnion des classes cl1 et cl2 [&&]Intersection des classes cl1 et cl2

LangagesGrammaires

ER et langagesGroupe - 1

Les parenthèses dans une expression régulière sont des méta symboles permettant de délimiter des groupes dans

une chaîne satisfaisant l"expression.Un groupe est une suite de caractères à l"intérieur d"une

chaîne satisfaisant l"expression.Chaque groupe possède un rang unique. Le rang d"un groupe dans une expression régulière est égal au nombre de parenthèses ouvrantes le précédant.

LangagesGrammaires

ER et langagesGroupe - 2

Un groupe peut-être non capturant. Il n"a pas de rang attribué.Le rang d"un groupe est égal au nombre de parenthèses ouvrantes le précédant - le nombre de groupes non capturant le précédant.Il est possible de faire référence à un groupe capturant précédent et de l"insérer dans le patron.(:::)Groupe capturant (? ::::)Groupe non capturant nnRéférence arrière au groupe capturant de rang n

LangagesGrammaires

ER et langagesConditions aux limites

^ounaDébut de chaîne $ounzFin de chaîne (?m)^Début de ligne ou de chaîne (?m)$Fin de ligne ou de chaîne nbDébut ou fin de mot nBAbsence de début ou de fin de mot nGFin du précédent groupe satisfaisant le gabarit

Exemple 1 :nw-(nd(nd))20-juin-2012n-20200

Exemple 2 :ndnb20-juin-201202

LangagesGrammaires

ER et langagesFacteurs de répétition

{n}Exactement n occurrences d"une classe de caractères +Au moins 1 occurrence d"une classe de caractères {n,}Au moins n occurrences d"une classe de caractères {n,p}De n à p occurrences d"une classe de caractères ?0 ou 1 occurrence *Un nombre quelconque de fois, éventuellement zéro

LangagesGrammaires

ER et langagesOpérateurs avides (gloutons)

Opérateur avide

Un opérateur est dit avide lorsque l"algorithme sous-jacent utilise le maximum de caractères pour satisfaire le facteur de répétition en tenant compte du contexte.*, +, {n,p} sont avides.

Patronndf2;6g3nd+Chaîne25331

ndf2;6g253

LangagesGrammaires

ER et langagesOpérateurs passifs

Opérateur passif

Un opérateur est dit passif lorsque l"algorithme sous-jacent utilise le minimum de caractères pour satisfaire le facteur de répétition en tenant compte du contexte.{n,p}?, *?, +? sont passifs.

Patronndf2;6g?3nd+Chaîne25331

ndf2;6g?25

LangagesGrammaires

ER et langagesOpérateurs possessifs

quotesdbs_dbs35.pdfusesText_40

[PDF] boucle if casio graph 35+

[PDF] mot 3 lettres y

[PDF] les français dans le monde de nouvelles mobilités stmg

[PDF] algorithme casio graph 35+ afficher

[PDF] xen scrabble

[PDF] les territoires ultramarins parmi lesquels les 5 drom

[PDF] algorithme tant que suite

[PDF] loi de stefan corps noir

[PDF] puissance rayonnée formule

[PDF] formule rayonnement thermique

[PDF] loi de planck démonstration

[PDF] emissivité corps noir

[PDF] rayonnement thermique cours

[PDF] rayonnement thermique définition

[PDF] finalité 1 bts am nathan