Generarea automata a analizoarelor lexicale

Generarea automata a analizoarelor lexicale

Principiul generarii automate a analizoarelor lexicale

Un generator de analizoare lexicale porneste de la setul de expresii regulate care descriu toti atomii limbajului sursa si, pe baza unor algoritmi ce vor fi prezentati mai jos, obtine diagrama de tranzitie corespunzatoare, sub forma unei tabele de analiza, avand structura similara celei indicate in Lucrarea "Proiectarea analizoarelor lexicale" (paragraful Algoritmul de analiza lexicala automata, varianta prin structuri de date). Aceasta tabela, impreuna cu procedura de analiza (prezentata in acelasi paragraf), alcatuiesc analizorul lexical.

Obtinerea tabelei de analiza pe baza expresiilor regulate

In literatura de specialitate se prezinta doua modalitati de transformare a expresiilor regulate in automate finite deterministe.

1.Metoda Thompson
Aceasta metoda presupune parcurgerea a trei etape:

Construirea unui automat finit nedeterminist (AFN) pornind de la expresiile regulate (ER).
Transformarea automatului nedeterminist in automat finit determinist (AFD).
Minimizarea numarului de stari ale automatului determinist.
1.1.Obtinerea AFN pe baza ER (algoritmul lui Thompson)

Dandu-se o expresie regulata ER, se doreste obtinerea automatului finit nedeterminist (AFN) care sa accepte limbajul descris de ER.
Pentru aceasta, se descompune ER in componentele sale primitive. Pentru fiecare componenta se construieste cate un AFN conform urmatoarelor reguli:

a) pentru lambda (simbolul vid):

b) pentru a (simbol oarecare al alfabetului sursa):

Obs: pentru fiecare AFN elementar construit, starile vor fi notate cu nume (numere) distincte; daca un acelasi simbol al alfabetului apare de mai multe ori in ER, se va construi pentru fiecare aparitie a sa cate un AFN separat, cu stari notate distinct. In schemele de mai sus, cu i si f s-au notat starea de start, respectiv starea finala a AFN.
In continuare, AFN elementare se vor conecta intre ele, corespunzator operatorilor aplicati asupra primitivelor ER, compunandu-se astfel, din aproape in aproape (prin inductie) AFN final.
Descompunerea ER in componente elementare, respectiv compunerea acestora se face aducand ER la forma postfix, tinand cont ca operatorii se evalueaza in ordinea urmatoare: parantezele, inchiderea ( * ), concatenarea si selectia ( | ).

In cele ce urmeaza vom nota cu N_i AFN corespunzator ER R_i. Regulile de compunere sunt:

c) pentru R₁|R₂

d) pentru R₁R₂

e) pentru R₁*

AFN final va avea o singura stare de start si o singura stare finala.

1.2.Transformarea AFN in AFD

Pe baza AFN obtinut aplicand regulile de mai sus, se va construi un automat finit determinist (AFD) care sa accepte acelasi limbaj ca si AFN.
Vom nota cu:

Sigma - alfabetul limbajului sursa,
D_stari - multimea starilor AFD,
D_tranz - multimea tranzitiilor si
s₀ - starea initiala a AFN.

O stare a AFD va fi de fapt compusa dintr-o multime de stari {s₁, s₂, . . . ,s_n } ale AFN.
Algoritmul de obtinere a AFD este:

procedure AFN2AFD is
    *initializeaza D_stari cu lambda-inchidere({s₀})
    *la inceput starile din D_stari sunt nemarcate
    D_tranz= multimea vida
    while mai exista in D_stari o stare x = {s₁, s₂, . . . ,s_n} nemarcata do
        *marcheaza x
        for fiecare a din Sigma do
           *fie T = multimea starilor din AFN pentru care exista o tranzitie etichetata cu a de la o
              stare s_idin x;
         y = lambda-inchidere(T);
         ify nu se afla in D_starithen
                *adauga y ca stare nemarcata la D_stari
                *adauga tranzitia xy la D_tranz, daca nu exista deja
         endif
        endfor
    endwhile
end AFN2AFD

Functia lambda-inchidere este definita pe o multime T de stari ale AFN si reprezinta multimea starilor in care se poate ajunge pornind de la starile din T, pentru simbolul lambda.
Algoritmul de calcul pentru aceasta functie este:

function lambda-inchidere( T ) is
    *pune toate starile din T intr-o stiva
    *initializeaza lambda-inchidere( T ) cu T
    while stiva nu e vida do
        *extrage starea s din varful stivei
        for fiecare stare t pentru care exista s t do
           if t nu se afla in lambda-inchidere( T ) then
                *adauga t la lambda-inchidere( T )
                *pune t in stiva
           endif
        endfor
    endwhile
end lambda-inchidere

Starile acceptoare ale AFD obtinut vor fi acele stari x care vor contine cel putin o stare acceptoare a AFN. Starea de start a AFD este cea formata din s₀ impreuna cu toate starile la care se poate ajunge din s₀ doar prin simbolul lambda.

1.3.Minimizarea AFD

De cele mai multe ori AFD obtinut cu algoritmul de mai sus nu este cel mai mic posibil (cu numar minim de stari). Reducerea numarului de stari ale AFD implica urmatorii pasi:

Se realizeaza o partitionare P a multimii D_stari care, initial, consta din doua grupuri de stari:

F = setul de stari acceptoare si

D_stari - F = setul de stari non-acceptoare.

Printr-o procedura, care se va da mai jos, se incearca efectuarea unei noi partitionari, P_nou, prin descompunerea grupurilor lui P in subgrupuri. Daca P_nou este diferit de P, se inlocuieste P cu P_nou si se repeta procedura de descompunere. DacaP_nou este identic cu P, inseamna ca partitionarea nu se mai poate face.

procedure partitionare is

for

fiecare grup G din P do

* descompune G in subgrupuri astfel incat. 2 stari s si t din G sa se afle in acelasi subgrup daca

si numai daca, pt. toate simbolurile adinSigma, s si t tranziteaza in stari apartinand aceluiasi

subgrup

* subgrupurile obtinute se pun in P_nou

_endfor

end partitionare

Din fiecare grup al partitiei obtinute in pasul anterior, se alege cate o stare oarecare (stare reprezentanta). Acestea vor fi starile AFD minimizat. Starea initiala va fi starea reprezentanta a grupului ce contine starea initiala s₀, iar starile finale vor fi reprezentantele subgrupurilor provenite din F.
Daca AFD minimizat contine o stare de blocaj d, adica o stare care nu este finala si care tranziteaza in ea insasi pentru toate simbolurile a din Sigma, aceasta stare se elimina. Se vor elimina, de asemenea, starile care nu pot fi atinse plecand din starea initiala. Tranzitiile spre starile de blocaj dinspre alte stari devin nedefinite.

2.Metoda arborelui binar

Aceasta metoda presupune:

Construirea arborelui binar corespunzator ER.
Construirea AFD pe baza arborelui.

2.2.Construirea arborelui binar

Arborele corespunzator ER va avea cate un nod terminal pentru fiecare simbol ce apare in ER si cate un nod interior pentru fiecare operator aplicat (concatenare, inchidere,selectie). In prealabil ER va fi modificata, in sensul ca la sfarsitul ei va fi concatenat un simbol special, notat cu #, care va servi drept marcator de sfarsit al ER. O asemenea ER modificata se numeste ER augmentata.

In AFD corespunzator ER augmentate, orice stare de la care va exista o tranzitie etichetata cu '#' va fi stare acceptoare.

Luand ca exemplu ER augmentata : a ( b | c )^*d b #

arborele corespunzator va fi cel din figura de mai jos.

Fiecare simbol din ER va fi numerotat, in ordinea textuala a aparitiei sale in ER. Daca acelasi simbol apare de mai multe ori, fiecare aparitie va avea un numar distinct. Numerele atribuite in acest mod se numesc pozitii. Pe de alta parte, fiecare nod al arborelui va primi cate un identificator unic, pentru a putea fi localizat. In cazul arborelui din figura de mai sus identificatorii nodurilor au fost notati cu N_i, i = 1. .12.
Obs: daca ER pentru care se construieste arborele este de forma a | b, atunci forma augmentata va fi (a |b) #, deoarece operatorul de concatenare are precedenta mai mare fata de operatorul selectie.

Ca si in cazul algoritmului lui Thompson, arborele se obtine aducand ER la forma postfix.

2.2.Obtinerea AFD din arborele binar

Notand cu rad nodul radacina al arborelui si preluand notatiile D_tranz si D_stari de la paragraful anterior, algoritmul de transformare a arborelui ER in AFD este:

procedure ER2AFD is
    *initializeaza D_stari cu Primapoz(rad)
    *la inceput starile din D_stari sunt nemarcate
    while exista stare nemarcata T in D_stari do
        *marcheaza T
        for fiecare a din Sigma do
            U = multimea vida
            for fiecare p din T do
                if a este simbolul din pozitia p then
                   U = U + Pozurm(p)    // '+' inseamna reuniune
                endif
            endfor
            if (U nu este multimea vida) and ( U nu se afla in D_stari ) then
                *adauga U ca stare nemarcata la D_stari
_endif
           *adauga tranzitia T U la D_tranz (**)
_endfor
_endwhile
end ER2AFD

O stare a AFD din D_stari va fi o multime formata din numere de pozitii din arbore. Fiecare asemenea multime va primi cate un identificator de stare distinct. De obicei identificatorii de stari sunt numere intregi.

Se observa ca operatia din linia notata cu (**) se executa chiar daca U este multimea vida. Acest lucru se intampla cand simbolul a de pe pozitia p este chiar terminatorul '#'. Semnificatia unei asemenea tranzitii este aceea ca starea reprezentata de T este stare acceptoare.

Functia Pozurm(i), unde i este o pozitie din arborele ER, returneaza multimea pozitiilor j care pot urma pozitiei i in arbore. Calculul acestei multimi presupune ca, in prealabil, pentru fiecare nod n din arbore, sa se determine doua multimi: Primapoz(n) si Ultimapoz(n). Se face observatia ca n este identificatorul nodului, NU pozitia.

Functia Primapoz(n) defineste multimea pozitiilor corespunzatoare cu primul simbol al unui sir generat de subarborele cu radacina in n.

Analog, Ultimapoz(n) defineste multimea pozitiilor corespunzatoare cu ultimul simbol dintr-un sir generat de subarborele cu radacina in n.

Pentru calculul acestor functii este necesar sa se determine acele noduri care sunt radacini ale unor subarbori ce pot genera sirul vid. Asemenea noduri se numesc anulabile. Vom defini, in consecinta, o functie Anulabil(n) care va returna valoarea logica true daca n este un nod anulabil, si false in caz contrar.

Regulile de calcul pentru functiile Anulabil si Primapoz sunt date in tabelul de mai jos.

Nod n	*Anulabil (n)*	*Primapoz (n)*
Frunza cu eticheta *lambda*	true	multimea vida
Frunza avand pozitia i	false	{ i }
	Anulabil(c₁) or Anulabil(c₂)	Primapoz(c₁) + Primapoz(c₂)
	Anulabil(c₁) and* Anulabil(c₂)*	if Anulabil(c₁) then Primapoz(c₁) + Primapoz(c₂) else Primapoz(c₁) endif
	true	Primapoz (c₁)

Obs: operatorul '+' semnifica reuniune de multimi.

Pentru Ultimapoz regulile sunt similare cu cele de la Primapoz, doar ca se inlocuieste Primapoz cu Ultimapoz si se interschimba c₁ cu c₂ .

Acum, regulile pentru calculul lui Pozurm(i) sunt:

Daca n este un nod-concatenare (.), cu fiul stang c₁ si cu fiul drept c₂ si i se afla in Ultimapoz(c₁), atunci se include Primapoz(c₂) in Pozurm(i).
Daca n este un nod-inchidere (*) si i se afla in Ultimapoz(n), atunci se include Primapoz(n) in Pozurm(i).

Spre deosebire de Primapoz si Ultimapoz, care se determina "punctual" (adica pentru fiecare nod in parte), pentru calculul lui Pozurm se va folosi o procedura care va construi din aproape in aproape toate multimile Pozurm, printr-o singura baleiere a arborelui. Procedura este data mai jos:

procedure Calc_Pozurm is
    for fiecare pozitie p din arbore do
        *initializeaza Pozurm(p) cu multimea vida
    _endfor
    for fiecare nod n din arbore do
        ifn este un nod concatenare then
            *fie c₁ si c₂ fiii stang, respectiv drept ai lui n
           for fiecare pozitie i din Ultimapoz(c₁) do
                *adauga Primapoz(c₂) la Pozurm(i).
           endfor
        endif
        ifn este un nod inchidere then
           for fiecare pozitie i din Ultimapoz(n) do
                *adauga Primapoz(n) la Pozurm(i).
           endfor
        endif
_endfor
end Calc_Pozurn

Pentru exemplificare, in tabelul de mai jos se dau valorile calculate ale functiilor Anulabil, Primapoz, Ultimapoz si Pozurm corespunzatoare arborelui dat la inceputul paragrafului.

Nod	Pozitie	Anulabil	Primapoz	Ultimapoz	Pozurm
N₁₂	3	false	{ 3 }	{ 3 }	{ 2,3,4 }
N₁₁	2	false	{ 2 }	{ 2 }	{ 2,3,4 }
N₁₀	-	false	{ 2,3 }	{ 2,3 }	-
N₉	*	true	{ 2,3 }	{ 2,3 }	-
N₈	1	false	{ 1 }	{ 1 }	{ 2,3,4 }
N₇	4	false	{ 4 }	{ 4 }	{ 5 }
N₆	.	false	{ 1 }	{ 1,2,3 }	-
N₅	5	false	{ 5 }	{ 5 }	{ 6 }
N₄	.	false	{ 1 }	{ 4 }	-
N₃	6	false	{ 6 }	{ 6 }	multimea vida
N₂	.	false	{ 1 }	{ 5 }	-
N₁	.	false	{ 1 }	{ 6 }	-

In concluzie, etapele care se parcurg pentru obtinerea AFD pe baza arborelui unei ER sunt:

Se determina Primapoz si Ultimapoz pentru fiecare nod al arborelui.
Se calculeaza Pozurm pentru fiecare pozitie, parcurgand arborele de sus in jos.
Se executa procedura ER2AFD.

Atasarea actiunilor semantice

Pentru simplificare, algoritmul de analiza va fi proiectat astfel incat, in timpul delimitarii unui atom sa se memoreze caracterele componente ale atomului intr-un buffer separat (de exemplu CarAtom folosit in lucrarea "Proiectarea analizoarelor lexicale"). In momentul cand se ajunge in starea acceptoare corespunzatoare atomului respectiv, se vor efectua operatiile dorite, utilizandu-se bufferul. Cu alte cuvinte, vom avea rutine semantice atasate doar cu starile acceptoare.

Desfasurarea lucrarii

Se va proiecta cate un generator de tabele de analiza lexicala, utilizand metodele descrise in lucrare. Generatoarele vor primi la intrare lista expresiilor regulate pe baza carora vor construi AFN, respectiv arborele ER, apoi vor intocmi tabelele de analiza. Prelucrarea expresiilor regulate de la intrare se va face utilizand gramatica propusa in Anexa E.
La generatoarele obtinute se va atasa procedura de analiza lexicala automata, varianta prin structuri de date descrisa in lucrarea "Proiectarea analizoarelor lexicale", si se va analiza un text de intrare continand atomi formati dupa ER avute in vedere.
ER se vor lua fie din Anexa A, fie vor fi propuse de conducatorul lucrarii.