Tematica cursului (partea I): Limbaje formale si

Curs 1

2020-21

Limbaje Formale, Automate s¸i Compilatoare - Curs 1

1 Prezentare curs

2 Limbaje formale

3 Mecanisme de generare a limbajelor: gramatici

4 Ierarhia lui Chomsky

5 Limbaje s¸i gramatici de tip 3 (regulate)

Limbaje Formale, Automate s¸i Compilatoare

Titulari curs:

O. Captarencu: [email protected]

http://profs.info.uaic.ro/˜otto/lfac.html A. Moruz:[email protected]

Sistem evaluare

7 seminarii, 6 laboratoare;

AS= activitatea la seminar (nota de la 0 la 10);

AL= activitatea la laborator (nota de la 0 la 10);

Test scris in sesiune format din 2 parti:

T1(nota de la 1 la 10) T2(nota de la 1 la 10)

Punctajul final se obt¸ine astfel:

P = 2.5 * AS + 2.5 * AL + 2.5 * T1 + 2.5 * T2

Condit¸ii miminale de promovare:AS≥5, AL≥5, T 1≥5, T 2≥5;

Sistem evaluare

AS= activitatea la seminar (max 10 puncte):

activitatea in timpul seminarului (rezolvare probleme): max 2 puncte (+ bounsuri)

test scris: max 8 puncte

AL= activitatea la laborator (nota proiect)

Tematica cursului (partea I): Limbaje formale si

automate

Tematica cursului (partea I): Limbaje formale si

automate

Tematica cursului (partea I):Limbaje formale si automate

Limbaje s¸i gramatici

Limbaje regulate; gramatici, automate , expresii regulate

Limbaje independente de context; gramatici, automate pushdown

Tematica cursului (partea II)

Limbaje de programare: proiectare s¸i implementare Analiza lexical ˘a

Analiza sintactic ˘a

Traducere ˆın cod intermediar

Bibliografie (select¸ii)

1 A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman: Compilers:

Principles, Techniques, and Tools. Boston: Addison-Wesley, 2007

2 Gh. Grigoras. Constructia compilatoarelor - Algoritmi fundamentali, Ed. Universitatii Al. I. ”Cuza Iasi”, ISBN 973-703-084-2, 274 pg., 2005

3 Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006).

Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley

4 J. Toader - Limbaje formale s¸i automate, Editura Matrix Rom, Bucuresti, 1999.

5 J. Toader, S. Andrei - Limbaje formale s¸i teoria automatelor. Teorie

Limbaje Formale, Automate s¸i Compilatoare - Curs 1

1 Prezentare curs

2 Limbaje formale

3 Mecanisme de generare a limbajelor: gramatici

4 Ierarhia lui Chomsky

Alfabet, cuv ˆant, multt¸ime de cuvinte

Alfabet: V o mult¸ime finit ˘a (elementele lui V = simboluri )

Alfabet, cuv ˆant, multt¸ime de cuvinte

Alfabet: V o mult¸ime finit ˘a (elementele lui V = simboluri ) Cuv ˆant: s¸ir finit de simboluri

cuv ˆantul nul este notat cuǫsauλ.

Alfabet, cuv ˆant, multt¸ime de cuvinte

Alfabet: V o mult¸ime finit ˘a (elementele lui V = simboluri ) Cuv ˆant: s¸ir finit de simboluri

cuv ˆantul nul este notat cuǫsauλ.

Lungimea unui cuv ˆant u: numarul simbolurilor sale. Notat¸ie: |u|.

|ǫ|=0

Alfabet, cuv ˆant, multt¸ime de cuvinte

Alfabet: V o mult¸ime finit ˘a (elementele lui V = simboluri ) Cuv ˆant: s¸ir finit de simboluri

cuv ˆantul nul este notat cuǫsauλ.

Lungimea unui cuv ˆant u: numarul simbolurilor sale. Notat¸ie: |u|.

|ǫ|=0

V^∗ - multimea tuturor cuvintelor peste alfabetul V, inclusivǫ.

{0,1}^∗ ={ǫ,0,1,00,01,10,11,000,001, . . .}

Alfabet, cuv ˆant, multt¸ime de cuvinte

Alfabet: V o mult¸ime finit ˘a (elementele lui V = simboluri ) Cuv ˆant: s¸ir finit de simboluri

cuv ˆantul nul este notat cuǫsauλ.

Lungimea unui cuv ˆant u: numarul simbolurilor sale. Notat¸ie: |u|.

|ǫ|=0

V^∗ - multimea tuturor cuvintelor peste alfabetul V, inclusivǫ.

{0,1}^∗ ={ǫ,0,1,00,01,10,11,000,001, . . .}

V⁺- multimea tuturor cuvintelor nenule peste alfabetul V {0,1}⁺={0,1,00,01,10,11,000,001, . . .}

Operat¸ii pe cuvinte

Concatenareaa doua cuvinte x, y: cuv ˆantul x ·y obt¸inut din simbolurile lui x, ˆın ordinea ˆın care apar, urmate de cele ale lui y de asemenea ˆın ordinea ˆın care apar:

x =0100, y=100, x·y =0100100 x =000, y=ǫ, x ·y =000

Operat¸ii pe cuvinte

Concatenareaa doua cuvinte x, y: cuv ˆantul x ·y obt¸inut din simbolurile lui x, ˆın ordinea ˆın care apar, urmate de cele ale lui y de asemenea ˆın ordinea ˆın care apar:

x =0100, y=100, x·y =0100100 x =000, y=ǫ, x ·y =000

Concatenarea este asociativ ˘a

Operat¸ii pe cuvinte

Concatenareaa doua cuvinte x, y: cuv ˆantul x ·y obt¸inut din simbolurile lui x, ˆın ordinea ˆın care apar, urmate de cele ale lui y de asemenea ˆın ordinea ˆın care apar:

x =0100, y=100, x·y =0100100 x =000, y=ǫ, x ·y =000

Concatenarea este asociativ ˘a

(V^∗,·)este monoid (ǫeste element neutru), se numes¸te monoidul liber generat de V .

Operat¸ii pe cuvinte

Concatenareaa doua cuvinte x, y: cuv ˆantul x ·y obt¸inut din simbolurile lui x, ˆın ordinea ˆın care apar, urmate de cele ale lui y de asemenea ˆın ordinea ˆın care apar:

x =0100, y=100, x·y =0100100 x =000, y=ǫ, x ·y =000

Concatenarea este asociativ ˘a

(V^∗,·)este monoid (ǫeste element neutru), se numes¸te monoidul liber generat de V .

Cuv ˆantul v este unprefixal cuv ˆantului u dac ˘a∃w ∈V^∗ :u=vw ; dac ˘a w ∈V⁺, atunci v este unprefix propriual lui u.

Operat¸ii pe cuvinte

Concatenareaa doua cuvinte x, y: cuv ˆantul x ·y obt¸inut din simbolurile lui x, ˆın ordinea ˆın care apar, urmate de cele ale lui y de asemenea ˆın ordinea ˆın care apar:

x =0100, y=100, x·y =0100100 x =000, y=ǫ, x ·y =000

Concatenarea este asociativ ˘a

(V^∗,·)este monoid (ǫeste element neutru), se numes¸te monoidul liber generat de V .

Cuv ˆantul v este unprefixal cuv ˆantului u dac ˘a∃w ∈V^∗ :u=vw ;

Fie V un alfabet. O submult¸ime L⊆V^∗ este unlimbaj(formal) peste alfabetul V (sau V-limbaj) dac ˘a L are o descriere

(matematic ˘a) finit ˘a.

O descriere poate fi:

Fie V un alfabet. O submult¸ime L⊆V^∗ este unlimbaj(formal) peste alfabetul V (sau V-limbaj) dac ˘a L are o descriere

(matematic ˘a) finit ˘a.

O descriere poate fi:

neformal ˘a (ˆın limbaj natural):

multimea cuvintelor peste alfabetul{0,1}care contin un numar par de 0.

L={x∈V⁺:|x|este par}.

{aⁿbⁿ|n∈N}.

{w∈ {0,1}^∗|w se termina in 00}.

Fie V un alfabet. O submult¸ime L⊆V^∗ este unlimbaj(formal) peste alfabetul V (sau V-limbaj) dac ˘a L are o descriere

(matematic ˘a) finit ˘a.

O descriere poate fi:

neformal ˘a (ˆın limbaj natural):

multimea cuvintelor peste alfabetul{0,1}care contin un numar par de 0.

L={x∈V⁺:|x|este par}.

{aⁿbⁿ|n∈N}.

{w∈ {0,1}^∗|w se termina in 00}.

formal ˘a (descriere matematic ˘a):

o descriere inductiv ˘a a cuvintelor

o descriere generativ ˘a a cuvintelor (gramatic ˘a generativ ˘a) o descriere a unei metode de recunoas¸tere a cuvintelor din limbaj

Operat¸ii cu limbaje

Operatiile cu multimi (reuniune, intersectie etc) Produs de limbaje: L₁·L₂={u·v|u∈L₁,v ∈L₂} Exemplu:

L1={aⁿ,n≥1}, L2={bⁿ,n≥1}

L1·L2={aⁿb^m,n≥1,m≥1}

Iterat¸ia (produsul Kleene): L^∗ =S

n≥0Lⁿ, unde:

L⁰={ǫ}

Lⁿ⁺¹=Lⁿ·L

Limbaje Formale, Automate s¸i Compilatoare - Curs 1

1 Prezentare curs

2 Limbaje formale

3 Mecanisme de generare a limbajelor: gramatici

4 Ierarhia lui Chomsky

5 Limbaje s¸i gramatici de tip 3 (regulate)

Gramatici

Definit¸ie 1

O gramatica este un sistem G= (N,T,S,P), unde:

N s¸i T sunt dou ˘a alfabete disjuncte:

N este multimea neterminalilor T este multimea terminalilor

S∈N este simbolul de start (neterminalul init¸ial)

P este o multime finita de reguli (product¸ii) de forma x →y , unde x,y ∈(N∪T)^∗ s¸i x cont¸ine cel put¸in un neterminal.

Derivare

Definit¸ie 2

Fie G= (N,T,S,P)o gramatica s¸i u,v ∈(N∪T)^∗.

Spunem c ˘av este derivat direct (ˆıntr-un pas) de la uprin aplicarea regulii x →y , s¸i not ˘am u⇒v , dac ˘a∃p,q ∈(N∪T)^∗ astfel ˆınc ˆat u =pxq s¸i v =pyq.

Derivare

Definit¸ie 2

Fie G= (N,T,S,P)o gramatica s¸i u,v ∈(N∪T)^∗.

Spunem c ˘av este derivat direct (ˆıntr-un pas) de la uprin aplicarea regulii x →y , s¸i not ˘am u⇒v , dac ˘a∃p,q ∈(N∪T)^∗ astfel ˆınc ˆat u =pxq s¸i v =pyq.

Daca u₁⇒u₂. . .⇒u_n,n>1, spunem ca u_neste derivat din u₁ˆın G s¸i notam u1⇒⁺un.

Derivare

Definit¸ie 2

Fie G= (N,T,S,P)o gramatica s¸i u,v ∈(N∪T)^∗.

Spunem c ˘av este derivat direct (ˆıntr-un pas) de la uprin aplicarea regulii x →y , s¸i not ˘am u⇒v , dac ˘a∃p,q ∈(N∪T)^∗ astfel ˆınc ˆat u =pxq s¸i v =pyq.

Daca u₁⇒u₂. . .⇒u_n,n>1, spunem ca u_neste derivat din u₁ˆın G s¸i notam u1⇒⁺un.

Scriem u⇒^∗v dac ˘a u⇒⁺ v sau u=v .

Limbaj generat

Definit¸ie 3

Limbajul generat de gramatica G este:

L(G) ={w ∈T^∗|S⇒⁺w}

Limbaj generat

Definit¸ie 3

Limbajul generat de gramatica G este:

L(G) ={w ∈T^∗|S⇒⁺w} Definit¸ie 4

Dou ˘a gramatici G₁s¸i G₂sunt echivalente dac ˘a L(G₁) =L(G₂).

Exemplu

G= (N,T,S,P), N={S,X,A}, T ={a,b}, P const ˘a din:

1 S→aXb

2 aX →aAb

3 Xb→bA

4 aA→aa

5 A→ǫ

L(G) ={ab,abb,aabb}

Gramatic ˘a echivalent ˘a cu un singur neterminal ?

Exemplu

L={aⁿbⁿ|n≥1}

Definit¸ia inductiv ˘a:

ab∈L

Daca X ∈L, atunci aXb∈L

Nici un alt cuv ˆant nu face parte din L

Exemplu

L={aⁿbⁿ|n≥1}

Definit¸ia inductiv ˘a:

ab∈L

Daca X ∈L, atunci aXb∈L

Nici un alt cuv ˆant nu face parte din L Definit¸ia generativ ˘a:

G= ({X},{a,b},X,P), unde P={X →aXb,X →ab}

Derivarea cuv ˆantului a³b³:

Exemplu

L={aⁿbⁿcⁿ|n≥1}

G= (N,T,S,P), N={S,X}, T ={a,b,c}, P const ˘a din:

1 S→abc

2 S→aSXc

3 cX →Xc

4 bX →bb

Derivarea cuv ˆantului a³b³c³:

S⇒⁽²⁾aSXc ⇒⁽²⁾aaSXcXc ⇒⁽¹⁾ aaabcX cXc⇒⁽³⁾ aaabX ccXc⇒⁽⁴⁾ aaabbccX c⇒⁽³⁾aaabbcX cc⇒⁽³⁾ aaabbX ccc ⇒⁽⁴⁾aaabbbccc=a³b³c³

Limbaje Formale, Automate s¸i Compilatoare - Curs 1

1 Prezentare curs

2 Limbaje formale

3 Mecanisme de generare a limbajelor: gramatici

4 Ierarhia lui Chomsky

Ierarhia lui Chomsky

1 Gramatici de tip 0 (generale) Nu exista restrictii asupra regulilor

Ierarhia lui Chomsky

1 Gramatici de tip 0 (generale) Nu exista restrictii asupra regulilor

2 Gramatici de tip 1 (dependente de context)

reguli de formapxq→pyq undex ∈N, y 6=ǫ, p,q∈(N∪T)^∗, S→ǫ, caz ˆın care S nu apare ˆın dreapta regulilor

Ierarhia lui Chomsky

1 Gramatici de tip 0 (generale) Nu exista restrictii asupra regulilor

2 Gramatici de tip 1 (dependente de context)

reguli de formapxq→pyq undex ∈N, y 6=ǫ, p,q∈(N∪T)^∗, S→ǫ, caz ˆın care S nu apare ˆın dreapta regulilor

3 Gramatici de tip 2 (independente de context) reguli de formaA→y undeA∈N s¸iy ∈(N∪T)^∗

Ierarhia lui Chomsky

1 Gramatici de tip 0 (generale) Nu exista restrictii asupra regulilor

2 Gramatici de tip 1 (dependente de context)

reguli de formapxq→pyq undex ∈N, y 6=ǫ, p,q∈(N∪T)^∗, S→ǫ, caz ˆın care S nu apare ˆın dreapta regulilor

3 Gramatici de tip 2 (independente de context) reguli de formaA→y undeA∈N s¸iy ∈(N∪T)^∗

Exemple

Tip 1: pxq →pyqundex ∈N, y 6=ǫ, p,q∈(N∪T)^∗,S→ǫ G= (N,T,S,P), N ={S,A,B}, T ={a,b,c}, P:

(1)S→aaAc (2)aAc→aAbBc (3)bB→bBc (4)Bc→Abc (5)A→a Gramatica tip 1

G= (N,T,S,P), N ={S,X}, T ={a,b,c}, P:

(1)S→abc (2)S→aSXc

(3)cX →Xc (nu este regul ˘a de tip 1!, gramatica va fi de tip 0)

Exemple

Tip 2: A→y undeA∈Ns¸iy ∈(N∪T)^∗

Tip3: A→usauA→uB undeA,B∈N s¸iu ∈T^∗. G:

(1)x →axb (2)x →ǫ

(Gramatic ˘a tip 2) G:

(1)x →ax (2)x →bx

Exemple

Fie

G= ({E},{a,+,−,(,)},E,{E →a,E →(E+E),E →(E−E)}) .

Ce tip are gramatica G ?

Construiti derivari din E pentru cuvintele(a+a)si((a+a)−a) Cuvantul(a+a−a)poate fi derivat din E?

Descrieti limbajul L(G)

FieG= ({A,B},{a,b},A,{A→aA,A→B,B→bB,B→ǫ}) Ce tip are gramatica G ?

Descrieti limbajul L(G)

Clasificarea limbajelor

Un limbaj L este de tipul j daca exista o gramatica G de tipul j astfel incat L(G) =L, unde j ∈ {0,1,2,3}.

Vom nota cuL_j clasa limbajelor de tipul j, unde j ∈ {0,1,2,3}.

Are loc: L3⊂ L2⊂ L1⊂ L0

Incluziunile sunt stricte:

orice limbaj de tip j+1 este si de tip j ∈ {0,1,2}

exista limbaje de tip j care nu sunt de tip j+1, j ∈ {0,1,2}

Propriet ˘at¸i

Fiecare din familiileLj cu 0≤j ≤3 contine toate limbajele finite Fiecare din familiileLj cu 0≤j ≤3 este inchisa la operatia de reuniune:

L₁,L₂∈ L_j =⇒L₁∪L₂∈ L_j,

∀j :0≤j≤3

Notat¸ii alternative pentru gramatici de tip 2: BNF

gramatici DTD

genereaz ˘a mult¸imea documentelor XML cu o anumit ˘a structur ˘a (limbaj independent de context)

gramatici DTD

Un ”cuv ˆant” din limbajul generat de gramtica DTD:

XML Schema

- rol similar gramaticilor DTD

Limbaje Formale, Automate s¸i Compilatoare - Curs 1

1 Prezentare curs

2 Limbaje formale

3 Mecanisme de generare a limbajelor: gramatici

4 Ierarhia lui Chomsky

Gramatici de tip 3

O gramatic ˘a G= (N,T,S,P)este de tip 3 dac ˘a regulile sale au forma: A→u sau A→uB unde A,B ∈N s¸i u∈T^∗.

Exemplu: G= ({D},{0,1, ...,9},D,P) Unde P este:

D→0D|1D|2D|. . .|9D D→0|1|. . .|9

Exemple

Fie gramatica G= ({A,B},{l,d},A,P)unde P este:

A→lB, B→lB|dB|ǫ(l = litera, d = cifra)

Exemple

Fie gramatica G= ({A,B},{l,d},A,P)unde P este:

A→lB, B→lB|dB|ǫ(l = litera, d = cifra) L(G): multimea identificatorilor

Fie gramatica G= ({A,B},{+,−,d},A,P)unde P este:

A→+dB| −dB|dB, B →dB|ǫ(d = cifra)

Exemple

Fie gramatica G= ({A,B},{l,d},A,P)unde P este:

A→lB, B→lB|dB|ǫ(l = litera, d = cifra) L(G): multimea identificatorilor

Fie gramatica G= ({A,B},{+,−,d},A,P)unde P este:

A→+dB| −dB|dB, B →dB|ǫ(d = cifra) L(G): multimea constantelor intregi

Forma normal ˘a

O gramatic ˘a de tip 3 este in form ˘a normal ˘a daca regulile sale sunt de forma A→a sau A→aB, unde a∈T , si, eventual S→ǫ( caz in care S nu apare in dreapta regulilor).

Pentru orice gramatica de tip 3 exista o gramatica echivalenta in forma normala.

Forma normal ˘a

Obtinerea gramaticii in forma normala echivalenta cu o gramatica de tip 3:

Se poate arata ca pot fi eliminate regulile de forma A→B (redenumiri) si cele de forma A→ǫ(reguli de stergere), cu exceptia, eventual a regulii S→ǫ.

Orice regula de formaA→a₁a₂. . .a_nse inlocuieste cu

A→a1B1,B1→a2B2, . . ., Bn−2→an−1Bn−1, Bn−1→an, n>1, B₁, . . . ,B_n−1fiind neterminali noi.

Orice regula de formaA→a₁a₂. . .a_nBse inlocuieste cuA→a₁B₁,