Tehnici+de+compilare+lab1 2

Tehnici de compilare Laborator 1-2

Automate finite Introducere Un compilator este un program care „traduce” un program scris într-un limbaj evoluat într-un limbaj „înŃeles” de calculator. Compilatorul are deci la intrare un program scris într-un limbaj de programare (C, Pascal, Basic, Java etc.) şi la ieşire generează codul obiect corespunzător. Pe parcursul acestei operaŃii de traducere, compilatorul semnalează eventualele erori lexicale, de sintaxă, etc. Compilarea unui program are loc în mai multe etape (analiza lexicală, analiza sintactică, analiza semantică şi generarea codului). Realizarea acestor etape se bazează pe noŃiuni elementare de limbaje formale (de exemplu: gramatici, expresii regulate, automate finite, gramatici independente de context) În continuare vom reaminti principalele noŃiuni legate de automate finite deterministe, nedeterministe cu λ-tranziŃii utile în faza de analiză lexicală.

Automat finit determinist (AFD) DefiniŃie: Un automat finit determinist este o structură M = ( Q, Σ, δ, q0, F ), unde Q – mulŃime finită de elemente numite stări Σ – alfabet finit de elemente numite simboluri de intrare δ : Q × Σ → Q – funcŃia de tranziŃie q0∈Q – starea iniŃială F⊆Q – mulŃimea stărilor finale FunŃia de tranziŃie poate fi extinsă în felul următor: δ’ : Q × Σ* → Q


                   

Reprezentarea unui AFD – exemplu: Un AFD poate fi reprezentat printr-un graf orientat în care nodurile reprezintă stări, iar arcele, etichetate cu simboluri de intrare, reprezintă tranziŃiile. 1

a start

b

q0

q1

b

q2

q0 q1 q2

Q

a

Σ

δ

a

b

a q0 q0 q2

b q1 q2 q2

FuncŃia de tranziŃie Diagrama de tranziŃie

Q = {q0, q1, q2, q3} Σ = {a, b} F = {q3} Limbajul generat de un AFD: T(M) = { w∈Σ* | δ(q0, w) ∈ F }. Un cuvânt w din Σ* este recunoscut/acceptat de automat, dacă există un drum în diagrama de tranziŃie de la starea iniŃială la o stare finală, astfel încât prin concatenarea simbolurilor cu care sunt etichetate arcele acelui drum se obŃine cuvântul w. În cazul exemplului de mai sus limbajul generat de automat este (a|b)*bb(a|b)*

Automat finit nedeterminist (AFN) DefiniŃie: Un automat finit nedeterminist este o structură M = (Q, Σ, δ, q0, F), unde Q, Σ, q0, F au aceeaşi semnificaŃie ca şi la AFD, iar δ, funcŃia de tranziŃie este definită în felul următor: δ : Q × Σ → P(Q), adică dintr-o stare pot exista mai multe tranziŃii cu acelaşi simbol de intrare (ceea ce la AFD nu era posibil). FunŃia de tranziŃie poate fi extinsă în felul următor: δ’ : Q × Σ* → P(Q) δ  

δ λ 



   !

         



Exemplu de AFN: a

a start

q0

b

Σ

δ b

q1

b

Diagrama de tranziŃie

Q

q2 b

q0 q1 q2

a {q0} {q2}

B {q0, q1} {q2} {q2}

FuncŃia de tranziŃie

2

Limbajul generat de un AFN: T(M) = { w∈Σ* | δ(q0, w) ∩ F ≠ ∅ }. În cazul exemplului de mai sus limbajul generat de automat este tot (a|b)*bb(a|b)*.

Automat finit nedeterminist cu λ-tranziŃii Un AFN cu λ-tranziŃii este un AFN în care există şi arce etichetate cu λ: M = (Q, Σ, δ, q0, F), unde Q, Σ, q0, F au aceeaşi semnificaŃie ca şi la AFD, iar δ, funcŃia de tranziŃie este definită: δ: Q × ( Σ ∪ {λ} ) → P(Q), o tranziŃie δ(q, λ) = p se numeşte λ-tranziŃie. Exemplu: λ

λ

a

q3

q2

start q0

λ λ

λ q6

q1 λ q4

b

q5

q11

a

q12 λ

λ λ

q7

b

q8

b

q9

λ

q10

λ

q15

λ q13

b

λ

q14

λ q16

λ

λ

Limbajul acceptat/recunoscut de automatul din exemplu este: (a|b)*bb(a|b)*. ObservaŃie: Există un algoritm care asociază fiecărei expresii regulate un automat finit nedeterminist cu λ- tranziŃii. FuncŃionarea unui AFN cu λ-tranziŃii Verificarea unui cuvânt w∈Σ* cu un AFN cu λ-tranziŃii M se face în modul următor, prin simularea funcŃionării sale deterministe: Algoritm: stari_curente = λ-închidere({q0}) stari_urmatoare = ∅ pentru i = 0,|w|-1 pentru fiecare q ∈ stari_curente daca δ(q,w(i)) ∉ stari_urmatoare atunci adauga δ(q,w(i)) la stari_urmatoare sfarsit daca sfarsit pentru stari_urmatoare = λ-închidere(stari_urmatoare) stari_curente = stari_urmatoare 3

stari_urmatoare = ∅ sfarsit pentru daca stari_curente ∩ F ≠ ∅ atunci scrie „cuvantul este acceptat“ altfel scrie „cuvantul nu este acceptat“ sfarsit daca Simularea funcŃionării deterministe al unui AFN – exemplu 0, 1

0, 1

start 0

q0

q3

0

q4

1

q1 1 0, 1

q2

Să presupunem că vrem să verificăm dacă cuvântul 010010 aparŃine este recunoscut sau nu de acest automat. Plecăm cu mulŃimea formată din starea iniŃială: " 

Din aceasta mulŃime construim mulŃimea stărilor în care se poate ajunge din această stare cu simbolul curent de pe banda de intrare (0), astfel obŃinem: "  # .

La următorul pas, construim mulŃimea stărilor în care se poate ajunge din stările din mulŃimea precedentă cu următorul simbol de pe bandă (1): "  $  Continuând în acest fel obŃinem: pentru 0 pentru 0 pentru 1 pentru 0

"  # 

"  #  % 

"  $  % 

"  #  % 

La sfârşit, dacă intersecŃia dintre F şi ultima mulŃime este nevidă atunci cuvântul este recunoscut, altfel nu este recunoscut. 4

În cazul nostru cuvântul este recunoscut deoarece intersecŃia este nevidă. ExplicaŃie: Algoritmul de simulare a funcŃionării unui AFN cu λ-tranziŃii este asemănător cu algoritmul de mai sus. DiferenŃa constă în faptul că se pleacă de la λ-închiderea mulŃimii formate din starea iniŃială. După care se construieste mulŃimea tuturor stărilor în care se poate ajunge cu simbolul curent de pe bandă. O altă diferenŃă este că în acest moment se construieşte λ-închiderea acestei mulŃimi şi se continuă algoritmul cu această mulŃime. La fiecare moment i determinăm mulŃimea tuturor stărilor în care se poate ajunge pornind de la starea iniŃială după ce au fost citite i simboluri de pe bandă. Acest lucru se realizează efectuând tranziŃii cu simbolul curent w(i) din mulŃimea stărilor (stari_curente), construită la pasul anterior, iar apoi efectuând λ-închiderea acestei mulŃimi. λ-închiderea unei mulŃimi de stări λ-închidere(T), unde T este o mulŃime de stări, reprezintă mulŃimea stărilor care pot fi atinse dintr-o stare s ∈ T printr-un drum de lungime λ. Pentru construcŃia λ-închiderii unei mulŃimi de stări T ale AFN-ului M se efectuează toate λ-tranziŃiile posibile. Vom utiliza o stivă S, în care păstrăm toate stările pentru care încă nu s-au testat λ-tranziŃiile. Algoritm: iniŃial S conŃine toate stările din T λ-închidere = T cât timp S ≠ ∅ execută q ⇐ S //extrage q din vârful stivei pentru fiecare p ∈ δ(q, λ) dacă p ∉ λ-închidere atunci adaugă p la λ-închidere p ⇒ S //pune p pe stivă sfârşit dacă sfârşit pentru sfârşit cât timp

Teme de laborator: 1. ConstruiŃi un AFN cu λ-tranziŃii. 2. SimulaŃi funcŃionarea deterministă a automatului de la punctul 1. 3. TransformaŃi acest AFN într-un AFD.

Temă pentru acasă: 1. DescrieŃi limbajul indicat de următoarele expresii regulate: a. 0(0|1)*1 5

b. (0|1)*(11|00)(0|1)* c. (0*11)* 2. ConstruiŃi câte un automat finit pentru fiecare dintre aceste limbaje. Bibliografie: Marinescu D, „Tehnici de compilare” Marinescu D, „Limbaje formale şi teoria automatelor”

6