Construirea unui automat finit nedeterminist din expresii regulate

2.6. Construirea automata a analizoarelor lexicale

2.6.1. Construirea unui automat finit nedeterminist din expresii regulate
Se considera o expresie regulata R peste un alfabet . Algoritmul de mai jos va genera un automat finit nedeterminist N, care va accepta limbajul definit de R.

Se descompune expresia R in componentele sale elementare(simboluri si operatori). Se vor construi automate elementare pentru fiecare simbol, dupa care, folosind aceste automate, se vor construi automatele pentru expresiile compuse. Automatele pentru expresiile compuse se construiesc inductiv, pentru fiecare operatie : reuniune, concatenare, inchidere. Algoritmul de constructie introduce la fiecare pas cel mult 2 stari noi, prin urmare, automatul rezultat va avea cel mult de 2 ori atatea stari cate simboluri si operatii are expresia regulata.

Algoritmul lui Thomson prezentat mai jos nu este cel mai eficient, un algoritm mai performant ar genera un AFN cu mai puţine stări pentru aceeaşi expresie regulată, are avantajul însă de a fi simplu de implementat iar după ce se face transformarea din automat nedeterminist în automat determinist, avem posibilitatea de a reduce numărul stărilor automatului finit determinist, algoritm ce se va prezenta în cap. 2.5.5.

Considerăm urmatoarele notatii: i - stare iniţială, f - stare finală, N(R) - automatul corespunzător expresiei regulate R.

i) pentru (simbolul vid):
f

i

ii) pentru a (simbol oarecare al alfabetului surs):

a

f

i

Pentru fiecare AFN elementar construit, strile vor fi notate cu nume (numere) distincte; dac un acelai simbol al alfabetului apare de mai multe ori în ER, se va construi pentru fiecare apariie a sa câte un AFN separat, cu stri notate distinct.

În continuare, AFN elementare se vor conecta între ele, corespunztor operatorilor aplicai asupra primitivelor ER, compunându-se astfel, din aproape în aproape (prin inducie) AFN final.

Descompunerea ER n componente elementare, respectiv compunerea acestora se face aducnd ER la forma postfix, innd cont c operatorii se evalueaz n ordinea urmtoare: parantezele, nchiderea ( * ), concatenarea i selecia (|).

În cele ce urmeaz vom nota cu N(R_i) AFN corespunztor ER R_i. Regulile de compunere sunt:

iii) pentru R₁|R₂

N(R₁)
i
f


N(R₂)

Automatul corepsunzător expresiei R₁ |R², este N(R₁ |R₂), obţinut prin creerea a 2 stări noi: o stare iniţială, diferită de stările iniţiale ale automatelor N(R1) şi N(R2) şi o stare finală diferită de stările finale din N(R1) şi N(R2), care îşi pierd proprietatea de satre finală.

Limbajul corespunzător expresiei regulate R₁ |R₂ este L(R₁) L(R₂).

iv) pentru R₁R₂

Pentru expresia R₁R₂ vom construi un AFN pentru care starea iniţială este starea se start a automatului N(R₁) iar starea finală este cea a automatului N(R₂). Starea finală a automatului N(R₁) se va identifica cu starea se start a automatului N(R₂).

f

N(R₂)

i

N(R₁)

Un drum între i şi f va traversa mai întâi automatul N(R₁), după care va trece prin automatul N(R₂), prin urmare, şirul de simboluri recunoscut va fi un şir din limbajul expresiei R₁ urmat de un şir al limbajului R₂. În consecinţă, limbajul modelat de automat este L(R₁)L(R₂).

v) pentru R₁*

f
i

N(R₁)

Automatul are 2 stări noi şi ne putem deplasa din starea iniţială i în starea finală f, fie direct, prin tranziţia , fie prin automatul N(R), de un număr oarecare de ori.

Un automat obţinut pe baza algoritmului lui Thomson are următoarele proprietăţi:

* AFN final va avea o singur stare de start i o singur stare final.

* fiecare stare a automatului are cel mult o tranziţie etichetată cu un simbol din alfabet sau cel mult 2 tranziţii etichetate cu .

Aplicaţie: Se consideră expresia regulată R = (ab)^*abb şi construim AFN pentru această expresie.

Descompunem expresia regulată în componentele sale elemementare şi construim arborele sintactic al expresiei:

R₉

R₁₁

N₁₀

b

R₇

b

R₈

R₅

R₆

a

R₄

*

)

R₃

(

|

R₂

R₁

b
c

În continuare se construiesc automatele finite nedeterministe pentru expresiile R1, R2, … R11.

2

3

a

start

N(R₁)

4

5

b

start

N(R₂)

În construirea AFN s-ar putea face unele simplificări, de exemplu la pasul 3, am putea unifica stările de start ale automatelor fără a introduce o nouă stare de start, respectiv stare finală. Această îmbunătaţire ar genera însă mai mult de 2 ieşiri pentru o stare, ceea ce ar putea complica implementarea.

2.6.2. Algoritm pentru simularea comportării unui automat finit nedeterminist
Se consideră automatul N construit din expresia regulată prin metoda Thomson. Se prezintă algoritmul de simulare care va decide dacă automatul N recunoaşte sau nu un şir de intrare x. Răspunsul automatului va fi “da” în cazul recunoaşterii şi “nu” altfel. Algoritmul citeşte intrarea simbol cu simbol şi pentru fiecare prefix al intrării se calculează mulţimea de stări în care ajunge automatul (- închidere). Pentru a mări eficienţa acestui calcul se pot utiliza proprietăţile suplimentare ale unui AFN rezultat prin construcţia Thomson.
S:= - închidere(s₀);

a:= carurm;

while a eof do

begin

S:= - închidere(f_t(S,a));

a := carurm;

end;

if SF then generează(“da”)

else generează(“nu”);
Pentru implementarea algoritmului putem folosi ca structuri de date două stive şi un şir de cifre binare indexat de stările automatului. Într-una din stive se ţine evidenţa mulţimii curente a stărilor nedeterministe iar a doua stivă se utilizează pentru calculul mulţimii de stări următoare. Vectorul de cifre binare înregistrează dacăp o stare este prezentă în stivă, pentru a se evita dublarea ei. Organizarea acestei structuri ca vector are avantajul timpului de căutare constant al unei stări. După încheierea procesului de calcul a mulţimii de stări următoare, rolul stivelor se inversează.

Exemplu:

Pentru automatul finit nedeterminist din subcap. anterior, N(R₁₁) şi avem la intrare şirul a eof.

S := - închidere(0) = 0,1,2,4,7

a := a ;

S := - închidere (3,8) = 1,2,3,4,6,7,8

a := eof ;

F= 10;

S F = deci răspunsul va fi “nu”.

2.6.3. Minimizarea numărului de stări ale unui AFD
Automatul finit determinist obţinut din automatul finit nedeterminist nu este cel mai mic posibil pentru şirul de intrare dat. Se prezintă un algoritm care, în caz că este posibil, reduce numărul de stări ale unui AFD.

O stare s a unui AFN este o stare importantă dacă are cel puţin o tranziţie etichetată cu un simbol diferit de . De ex. în algoritmul de conversie AFN-AFD, stările importante au fost cele care au determinat creerea unei noi stări în AFD, prin calculul mulţimii - închidere(f_t(S,a)).

Considerând mulţimile de stări din AFN corespunzătoare la 2 stări din AFD, 2 submulţimi sunt identice dacă:

1. ele au aceleaşi stări importante

2. ambele fie includ, fie exclud stări acceptoare
Exemplu: AFN al expresiei (ab) ^* abb are ca stări importante 2,4,7,8,9. Starea A = 0,1,2,4,7a AFD construit şi starea C = 1,2,4,5,6,7 au aceleaşi stări importante şi nu conţin stări acceptoare, deci ele sunt identice. Starea E = 1,2,4,5,6,7,10, deşi are aceleaşi stări importante cu A şi ce, conţine starea finală 10, ceea ce nu îl face identificabil cu A.

Algoritmul de minimizare :

Considerăm că avem un AFD notat M, având mulţimea stărilor notată cu S, iar reprezintă mulţimea de simboluri de intrare. Presupunem că fiecare stare are o tranziţie pentru fiecare simbol de intrare. Dacă AFD nu îndeplineşte această condiţie, vom crea o stare fictivă, numită “stare de blocaj”, m din care vom trasa arce spre el însuşi pentru fiecare simbol de intrare. Pentru toate celelalte stări care nu au tranziţii pentru toate simbolurile, tranziţiile lipsă se vor completa cu arce spre starea m.

Iniţial divizăm mulţimea stărilor AFN în 2 submulţimi, una conţinând stările care nu sunt finale, celalată conţinând mulţimea stărilor finale. Algoritmul va partiţiona mulţimile de start astfel încât două stări din aceeaşi mulţime vor trece în aceeaşi mulţime de stări pentru orice simbol de intrare.

Considerăm P o partiţie obţinută la un moment dat în procesul de partiţionare, S=s1,s2,…,sk una din mulţimile partiţiei şi un simbol de intrare a. Căutăm pentru fiecare stare s_i starea în care trece pentru simbolul a. Dacă stările următoare obţinute aparţin la mulţimi diferite din P, mulţimea S se va împărţi în submulţimi ale căror elemente duc în aceeaşi submulţime din P. Procesul de divizare se repetă până când nu mai găsim grupuri ce trebuie divizate.

i) Se realizeaz o partiionare P a mulimii D_stri care, iniial const din dou grupuri de stri: F=setul de stri acceptoare i D_stri - F = setul de stri non-acceptoare. Printr-o procedur, care se va da mai jos, se încearc efectuarea unei noi partiionri, P_nou, prin descompunerea grupurilor lui P în subgrupuri. Dac P_nou P, se înlocuiete P cu P_nou i se repet procedura de descompunere. Dac P_nou P, înseamn c partiionarea nu se mai poate face.

procedura partiionare este

pentru fiecare grup G P execut

* descompune G în subgrupuri a.î. 2 stri s i t din G s se afle în acelai subgrup dac i numai dac, pt. toate simbolurile a , s i t tranziteaz în stri aparinând aceluiai subgrup

* subgrupurile obinute se pun în P_nou

sfârit partiionare

ii) Din fiecare grup al partiiei obinute în pasul anterior, se alege câte o stare oarecare (stare reprezentant). Acestea vor fi strile AFD minimizat. Starea iniial va fi starea reprezentant a grupului ce conine starea iniial s₀, iar strile finale vor fi reprezentantele subgrupurilor provenite din F.

iii) Toate tranziţiile dintre stările automatului iniţial se transformă în tranziţii între reprezentanţii grupelor respective. Dac AFD minimizat conine o stare de blocaj m, adic o stare care nu este final i care tranziteaz în ea însi pentru toate simbolurile a , aceast stare se elimin. Se vor elimina, de asemenea, strile care nu pot fi atinse plecând din starea iniial. Tranziiile spre strile de blocaj dinspre alte stri devin nedefinite.
a

Exemplu: fie automatul

a

b

b

C

D

B

A

b

a

E

b

a

b

S=A,B,C,D,E

Prima partiţie: = A,B,C,D E

Pentru a construi _nou, considerăm mulţimea E; această mulţime nu se mai poate diviza, deci o includem in noua partiţie. Considerăm acum A,B,C,Dşi căutăm tranziţiile pentru simbolul a: A -^a- B, B -^a- B, C -^a- B, D -^a- B, prin urmare simbolul a nu divizează mulţimea. Considerăm acum b: A -^b- C, B -^b- D, C -^b- C, D -^b- E, aceste tranziţii vor partiţiona mulţimea în A, B, C şi in D.

_nou = (A, B, C D E)
A, B, C -^a- B, B, C

A, B, C -^b- C, C

_nou = (A, C B D E)
A, C -^a- B, B

A, C -^b- C, C

_nou = (A, C B D E)
În acest moment _nou = deci automatul minimizat va avea stările A, C B D E. Din mulţimea A, C alegem satrea A stare reprezentativă. Toate tranziţiile spre C vor deveni tranzitii spre A, iar celelalte tranziţii le copiem din automatul iniţial.
2.6.4. Implementarea generatorului automat de analizor lexical

Specificarea de intrare pentru un generator o reprezintă expresiile regulate care descriu atomii lexicali, însoţite de specificaţii semantice. Acţiunile semantice sunt secvenţe de program care se execută atunci când în şirul de intrare se identifică o lexemă corespunzătoare tiparului cu care este asociată acţiunea.

r1 acţiune 1

r2 acţiune 2

r3 acţiune 3

…

rn acţiune n

Generatorul este un program care pe baza specificaţiilor de intrare generează tabela de tranziţii a automatului. Analizorul lexical va fi format dintr-un simulator pentru automat, împreună cu tabela de tranziţii generată.
generator

specificare de intrare

tabela de tranziþii

Funcţionare analizor lexical:

lexemã

simulatorul automatului

finit
ieºire
tabela de tranziþii
Simulatorul citeşte tamponul de intrare şi pe baza tabelei de tranziţie identifică lexemele. Automatul generat la ieşire poate fi nedeterminist sau determinist, în funcşie de implementarea dorită.

În continuare vom analiza câteva probleme de proiectare specifice pentru cele 2 variante de automate.

a. Generator care implementează AFN
Considerăm tiparele reprezentate prin r_i, i=1,n pentru care se vor construi automatele nedeterministe N(r_i). Automatele parţiale obţinute se combină într-un automat general, , numit AFN combinat astfel: se introduce o nouă stare de start de la care pleacă tranziţii spre toate cele n automate.

N(R_i)

N(R_i)

.

.

.

.
start

s₀

Simularea automatului combinat se bazează pe o variantă a algoritmului iniţial, care recunoaşte cel mai lung cuvânt din intrare. Asta însemnă că de fiecare dată când automatul ajunge la o mulţime de stări care conţine o stare acceptoare, va reţine poziţia din intrare şi tiparul r_i asociat cu acea stare, dar simularea continuă până în momentul în acre se ajunge în situaşia de terminare, adică din mulţimea de stări curentă nu există tranziţie pentru simbolul din intrare. La atingerea condiţiei de terminare, pointerul de avans al intrării se va retrage la poziţia corespunzătoare ultimei stări acceptoare marcate. Tiparul memorat pentru această poziţie identifică atomul găsit, iar lexema recunoscută se găseşte între cei doi pointeri. Dacă nu există stare acceptoare, se poate genera un mesaj de eroare.

Exemplu:

Se consideră următoarele tipare:

a

abb

a^*b⁺

Automatele parţiale corespunzătoare celor 3 expresii sunt:

1

2

start

3

6

start

4

5

a

a

b

b

7

8

start

a

a

b

Combinarea automatelor parţiale în automatul general este:
1

2

3

6

start

4

5

a

a

b

b

7

8

b

a

b
0

Se va analiza şirul de intrare aaba
Mulţimea stărilor de start: 0,1,3,7
a

terminare

b

8

7

a

2

4

7

a

0

1

3

7

tipar 3

tipar 1

Mulţimea de stări iniţială este 0,1,3,7. La intrare avem simbolul a, deci se va trece în mulţimea 2,4,7. Întrucât starea 2 este stare finală, se reţine poziţia 2 în şirul de intrare şi tiparul 1 asociat ci cuvântul recunsocut. Se continuă simularea şi pe baza celui de-al doilea a din intrare se trece în starea 7, apoi în starea 8 care este stare finală. Pointerul este acum pe simbolul b din intrare deci se va memora poziţia lui b şi tiparul 3 asociat cu şirul aab. Se continuă simularea pentru ultimul a la care s-a ajuns şi din acest punct nu mai avem tranziţii, În consecinţă, se revine la ultima corespondenţă recunoscând lexema aab corespunzătoare celui de-al treilea tipar.

Dacă expresiile regulate ar avea asociate acţiuni semantice, acestea s-ar executa în momentul recunoaşterii unui tipar. Această operaşie nu se va face în mod automat de fiecare dată când analizorul ajunge într-o stare acceptoare corespunzătoare unui tipar, ci numai atunci când tiparul se dovedeşte a fi tiparul care realizează cea mai lungă corespondenţă.

a. Generator care implementează AFD
Dacă generatorul furnizează la ieşire un AFD, programul de simulare este asemănător cu cel pentru AFN din capitolul anterior, adică se va căuta lexema de lungime maximă.

Problema care apare este că s-ar putea ca prin transformarea AFN- AFD, mulţimea de stări din AFN corespunzătoare unei stări din AFD să conţină mai multe stări acceptoare. Care stare din cele acceptoare se va alege pentru a determina tiparul asociat? Regula este că se va alege acea stare care corespunde expresiei regulate aflate mai în faţă, în ordinea introducerii expresiilor.

Exemplu:

Aplicăm algoritmul de conversie automatului generalizat de mai sus:

stare	a	b	tiparul anunţat
0,1,3,7	2,4,7	8	nimic
6,8	-	8	abb

În mulţimea de stări 6,8 ambele stări sunt finale. Deoarece starea 6 este stare terminală pentru o expresie regulată care apare înaintea expresiei regulate pentru starea finală 8 (ordinea de introducere a fost a, abb, a*b+), se va alege starea 6 ca stare acceptoare.

Pentru şirul de intrare aaba, algoritmul de simulare va genera aceleaşi puncte de marcare ca şi la simularea AFN.