Limbaje Formale si Translatoare

1. Introducere

Curs1 LFT

Limbajele de nivel nalt au o serie de avantaje n raport cu limbajele de asamblare. Pentru a putea ns folosi limbaje de nivel nalt, trebuie s existe posibilitatea de a converti programele scrise n aceste limbaje ntr-o form binar. Aceast necesitate a dus la dezvoltarea translatoarelor sau compilatoarelor programe care accept o reprezentare textual a unui algoritm exprimat printr-un program surs i care produc o reprezentare a aceluiai algoritm exprimat ntr-un alt limbaj, limbajul obiect sau un limbaj echivalent.

Translatorul este deci un program care traduce programele scrise de utilizator (ntr-un limbaj) n programe echivalente (ntr-un alt limbaj). Dac acestea din urm sunt programe n cod main sau un limbaj apropiat de limbajul calculatorului, translatorul se numete compilator.

Programul utilizatorului se numete program surs, iar programul n cod main obinut se numete program obiect. ntre cele dou programe trebuie s existe o relaie de echivalen n ceea ce privete efectul lor asupra calculatorului.

Execuia unui program n limbaj simbolic are loc n dou faze:

Faza 1. Compilarea: Program surs ( Compilator ( Program obiect

Faza 2. Execuia propriu-zis: Date iniiale ale programului ( Program obiect ( Rezultate

n faza de translatare, calculatorul execut programul compilator, iar n faza de execuie propriu-zis, calculatorul execut programul obiect, adic citirea datelor iniiale, prelucrarea lor i memorarea sau tiprirea rezultatelor.

Pentru scrierea unui compilator, trebuiesc foarte bine definite att limbajul surs, ct i limbajul int. Aceasta nseamn c ambele limbaje trebuie s fie formale.

Un limbaj are dou aspecte: sintax i semantic. Sintaxa stabilete care text este corect din punct de vedere gramatical, iar semantica stabilete modul n care se deriv semnificaia unui text corect din punct de vedere gramatical.

Exist numeroase formalisme i instrumente software pentru descrierea sintaxei unui limbaj formal. Pentru descrierea semanticii ns, formalismele i instrumentele existente nu sunt att de simple i uor de utilizat ca i specificaiile de sintax.

2. Clasificarea i structura translatoarelor

Un translator poate fi definit formal ca o funcie avnd domeniul de definiie limbajul surs i mulimea valorilor funciei limbajul obiect sau un limbaj echivalent (destinaie).

n dezvoltarea translatoarelor, sunt implicate cel puin trei limbaje: limbajul surs de translatat, limbajul obiect sau destinaie i limbajul gazd folosit la implementarea translatorului. Dac translatarea are loc n mai multe etape, pot exista i alte limbaje intermediare. Desigur, limbajul gazd i limbajul obiect nu sunt cunoscute de utilizatorul limbajului surs.

2.1. Diagrame T

Pentru descrierea programelor i n particular a compilatoarelor, exist o reprezentare schematic consacrat, numit diagram T, introdus de Bratman n 1961.

O diagram T pentru un program general este de forma:

O diagram T pentru un translator general este de forma:

2.2. Clasificarea translatoarelor.

Asamblorul. Termenul de asamblor este asociat cu translatoarele care transform instruciuni scrise n limbaj de nivel cobort n cod main, care poate fi executat direct. De obicei liniile individuale ale programului surs corespund cu o instruciune la nivel main. Rolul asamblorului este deci s converteasc reprezentrile simbolice ale instruciunilor n configuraii de bii, reprezentnd echivalentele n cod-main ale instruciunilor.

Macroasamblorul este un asamblor care permite utilizarea macrodefiniiilor. El utilizeaz o prim trecere i pentru colectarea macrodefiniiilor.

Rezultatul asamblrii este un text n form binar n care doar referinele externe sunt pstrate n form simbolic n tabele asociate seciunilor. Codul binar al seciunilor este nsoit de informaii ce indic locul referinelor relocabile pentru ca, n momentul ncrcrii, valorile acestora s se poat transforma n referine absolute.

Combinarea acestor seciuni ntr-un program executabil se face prin rezolvarea referinelor externe (nlocuirea numelor simbolice cu adrese de memorie) i adugarea eventual a rutinelor din bibliotecile standard, i ele pstrate sub form relocabil. Aceste operaii sunt deobicei fcute de un editor de legturi ( linkage editor). Programul furnizat de acesta este adus n memorie de ncrctor (loader).

Compilatorul este de obicei un translator care traduce instruciuni de nivel nalt n cod main, care poate fi executat direct. Liniile individuale din programul surs corespund de obicei cu mai multe instruciuni la nivel main.

Preprocesorul este un translator care traduce dintr-un superset al unui limbaj de nivel nalt n limbajul de nivel nalt original, sau care face simple substituiri de text nainea procesului de translatare propriu-zis. De exemplu, exist numeroase preprocesoare de FORTRAN structurat care traduc din versiuni structurate ale FORTRAN-ului n FORTRAN obinuit. Translatorul de nivel nalt este un translator care traduce un limbaj de nivel nalt ntr-un alt limbaj de nivel nalt, pentru care exist deja compilatoare sofisticate pentru un numr mare de maini. Interpretorul este un program care, primind un program surs, l prelucreaz n prealabil pentru a-l aduce ntr-o form mai simpl, dup care l execut simulnd execuia n limbaj surs. Forma intermediar executat de de interpretor este de fapt un alt limbaj mai simplu, mai apropiat de limbajele de asamblare. Principalul avantaj al folosirii unui interpretor este portabilitatea foarte simpl a unui limbaj, prin implementarea mainii virtuale pe un nou hardware. n plus, deoarece instruciunile sunt interpretate i executate n timpul rulrii, pot fi implementate limbaje foarte flexibile.

Compilatoarele incrementale mbin calitile compilatoarelor cu cele ale interpretoarelor. Programul surs este divizat de compilator n mici poriuni numite incremente. Acestea prezint o oarecare independen sintactic i semantic fa de restul programului. Incrementele sunt traduse de compilator. Execuia are loc interpretativ, permindu-se intervenia utilizatorului att n timpul compilrii ct i n timpul execuiei.

Decompilatorul sau dezasamblorul sunt tremeni care se refer la translatoare care au ca intrare un cod obiect i regenereaz codul surs ntr-un limbaj de nivel mai nalt. n timp ce acest lucru se poate realiza destul de bine pentru limbaje de asamblare, este mult mai dificil de implementat pentru limbaje de nivel nalt cum ar fi C, Pascal.

Cele mai multe compilatoare nu produc cod main cu adrese fixe, ci o form cunoscut sub numele de "semicompilat", "simbolic binar" sau form relocatabil. Rutinele astfel compilate sunt legate cu ajutorul unor programe numite editoare de legturi, linker, care pot fi privite ca ultima etap n procesul de translatare. Limbajele care permit compilarea separat a prilor unui program depind esenial de existena acestor editoare de legturi.

Diagramele T pot fi combinate pentru a arta interdependena translatoarelor, editoarelor de legturi etc.

Observaie. Un compilator nu necesit un limbaj int (de asamblare sau limbaj main) real. De exemplu, compilatoarele Java genereaz cod pentru o main virtual numit "Java Virtual Machine" (JVM). Interpretorul JVM interpreteaz apoi instruciunile JVM fr nici o translatare ulterioar.

2.3. Fazele translaiei.

Translatoarele sunt programe complexe, care necesit o abordare sistematic. Imaginea unui translator este cea a unui ir de transformri n cascad a programului surs n reprezentri din ce n ce mai apropiate de limbajul destinaie.

Procesul de translaie se divide ntr-o serie de faze. O faz( este o opera(ie unitar( de transformare a programului surs( dintr-o reprezentare n alta.

Cea mai simpl descriere mparte procesul de translatare ntr-o faz analitic urmat de o faz sintetic.

n faza analitic se analizeaz programul surs pentru a determina dac el corespunde cu restriciile sintactice i static semantice impuse de limbajul surs.

n faza sintetic se genereaz efectiv codul obiect n limbajul destinaie.

Componentele translatorului care ndeplinesc aceste faze majore se mai numesc "front end" i "back end". Prima este total independent de main, n timp ce a doua depinde puternic de maina destinaie.

n cadrul acestei structuri exist componente mai mici sau faze, aa cum se prezint n figura urmtoare:

Seciunea de gestionare caractere este cea care comunic cu lumea exterioar, prin sistemul de operare, pentru citirea caracterelor care formeaz textul surs. Cum setul de caractere i gestiunea fiierelor variaz de la sistem la sistem, aceast faz este de obicei dependent de main sau de sistem de operare.

Analizorul lexical (Scanner) preia textul surs( sub forma unei secven(e de caractere i le grupeaz n entit((i numite atomi (tokens). Acetia sunt simboluri ca identificatori, iruri, constante numerice, cuvinte cheie cum ar fi while i if, operatori ca type]);

switch(t->type)

{

case NAME:

printf(":%s\n",t ->info.name);

break;

case NUMBER:

printf(":%d\n",t ->info.value);

break;

default:

printf("\n");

break;

}

}

return 0;

}

Fluxul procedurii lex() se poate reprezenta prin diagramele de tranziii din figura urmtoare.

1. La preluarea unui nou atom (de exemplu la intrarea n lex() ) folosim starea special state 0 pentru a reprezenta faptul c nu am decis nc ce diagram s urmm. Alegerea e fcut pe baza urmtorului caracter de intrare Uneori, de exemplu pentru atomul LBRACE atomul e recunoscut imediat prin scanarea ultimului caracter din atom. Pentru ali atomi ns, de exemplu pentru NUMBER, cunoatem lungimea atomului numai dup citirea unui extracaracter care nu aparine numrului (stri notate cu *). n acest caz, caracterul n plus trebuie returnat la intrare.

2. Dac citim un caracter care nu corespunde cu o secven acceptat, se returneaz atomul special ERROR.

Diagramele de tranziie sunt grafuri orientate i etichetate n care nodurile simbolizeaz strile, iar arcele trecerea (tranziia) dintr-o stare n alta.

Generarea automat a analizorului lexical presupune conceperea unui program de traducere (un fel de compilator) care primete la intrare ntr-un limbaj de specificare, att structura atomilor lexicali, ct i eventualele aciuni semantice care trebuiesc realizate mpreun cu analiza lexical. Ieirea unui astfel de compilator va fi un program de analiz lexical. Un astfel de compilator poate fi aplicat unei clase mai largi de limbaje.

4. Noiuni generale de limbaje formale.

C3

Limbajele de programare sunt modelate matematic n cadrul limbajelor formale. Studiul modelrii limbajelor de programare are n vedere n primul rnd, structurile finite care permit dezvoltarea de limbaje cu un numr infinit de fraze.

Calea uzual de descriere formal a unui limbaj este de a folosi o gramatic pentru acel limbaj.

O gramatic G este definit de 4 componente:

O mulime finit T de simboluri care pot apare n frazele limbajului, numite simboluri terminale, sau primitivele limbajului.

O mulime infinit N de simboluri neterminale, sau categorii sintactice, care sunt utilizate pentru descrierea limbajului, dar nu apar n frazele acestuia. Deci, mulimile T i N sunt disjuncte.

O mulime P de reguli de generare sau producii care descriu aspectele constructive ale acestuia

Un simbol neterminal special S care apare doar ntr-o singur producie din mulimea P i care se numete simbol iniial, simbol de start sau axioma gramaticii. Produciile sau regulile de generare din P arat cum pot fi construite toate frazele limbajului pornind de la simbolul neterminal S.

Deci, cvadruplul:G={N, T, P, S}, unde N, T, P, S au semnificaiile menionate, constituie o gramatic.

Un alfabet A reprezint o mulime finit i nevid de simboluri. Un simbol din A este reprezentat printr-o liter, cifr sau semn, uneori printr-un ir finit de litere, cifre sau semne.

Se noteaz cu A* mulimea aranjamentelor cu repetiie ale simbolurilor din A, n care unele pot aprea de mai multe ori.

Exemplu: Pentru A1={(,)}, urmtoarele iruri sunt elemente din A1*:

( ,) ((((((())()etc.

n A* exist un ir care nu conine nici un simbol din A. Acest simbol, numit ir vid l notm cu (.

Un limbaj L peste alfabetul A este o submulime a lui A*. Orice ir din A* care aparine i lui L este un simbol sau cuvnt al limbajului L.

Evident, mulimea A* este infinit, deci i limbajul L poate reprezenta o mulime infinit. Acest lucru nltur orice abordare de tip enumerativ n definirea limbajului, fiind necesar o reprezentare finit a mulimii infinite.

Se disting dou categorii de astfel de reprezentri:

reprezentarea (finit) sintetic care genereaz toate cuvintele limbajului i corespunde noiunii de gramatic.

reprezentarea (finit) analitic care permite recunoaterea apartenenei sau nonapartenenei unei construcii la limbajul considerat, reprezentare care corespunde noiunii de automat sau analizor.

Cu notaile definite se construiesc mulimile: A = N ( T i A+ = A* - {(}.

Reuniunea A = N ( T reprezint alfabetul sau vocabularul gramaticii.

O producie p( P din gramatica G reprezint o transformare de forma:

(((

unde ( ( A+ i ( ( A* .

Fiind date ( i ( dou iruri oarecare din A* se poate defini relaia :

((( ( (((

care specific transformarea irului concaternat ((( n irul ((( pe baza regulii de generare ((( existent n mulimea P a produciilor.

Relaia notat cu "(" exprim doar o singur transformare de la un ir la altul n cadrul gramaticii G, dar ea poate fi extins pentru a exprima o ntreag succesiune de transformri, sub una din formele:

(1 (* k (ksau (1 (+k (k

Astfel se specific c irul (keste derivat (dedus) succesiv din irul (1 prin aplicarea unei serii de transformri, (derivare n k pai) prin utilizarea irului nul ( (relaia (* k) sau prin neutilizarea acestui ir (relaia (+ k).

Se poate defini un limbaj L generat de gramatica G ca fiind alctuit din acele simboluri terminale din G, numite propoziii, care deriv din simbolul iniial S:

L(G) = { s | s ( T* i S ( s}

O propoziie, notat mai sus cu s conine n exclusivitate simboluri terminale.Orice ir de simboluri terminale i neterminale derivat din axioma S este numit form propoziional.

-derivarea canonic stnga - este un ir de transformri n care neterminalul care se expandeaz este ntotdeauna cel mai din stnga neterminal al formei propoziionale

-derivarea canonic dreapta - este un ir de transformri n care neterminalul care se expandeaz este ntotdeauna cel mai din dreapta neterminal al formei propoziionale

Operaia invers derivrii se numete reducere.

Un limbaj se poate descrie prin mai multe gramatici diferite.

Dou gramatici se spune c sunt echivalente dac i numai dac limbajele generate de fiecare din acestea sunt identice.

O gramatic se numete recursiv dac permite derivri de forma:

u (+ ( u (, unde u (N iar (,( ( A*

O gramatic este:

recursiv la stnga dac: u (+ u w

recursiv la dreapta dac: u (+ w u

Exemplu:

Considerm o gramatic care descrie un set restrns de operaii algebrice

G = {N, T, P, S}

N = {S, , , }

T = {a, b, c, -, * }

P = {S (

( < term> | -

( | *

( a | b | c }

S ncercm s vedem dac expresia a-b*c aparine sau nu gramaticii.

S( ( - ( - ( a - ( a- *(( a - * ( a - b* ( a - b * c

Se observ c propoziia a - b * c s-a obinut n urma a 11 derivri, substituind la fiecare pas cte un simbol n forma propoziional curent.

4.1. Tipuri de gramatici i limbaje

Dup forma produciilor, N. Chomsky a mprit gramaticile n 4 mari clase:

gramatici de tip 0 - este forma cea mai general de gramatic, fra restricii, de tipul celei prezentate mai sus.

gramatici de tip 1 - sunt gramatici dependente de context (sensibile la context); ele au producii de forma ( u ( ( ( ( (, adic producia u ( ( se poate aplic doar dac u apare n contextul ( u (. Gramaticile dependente de context genereaz limbaje dependente de context.

gramatici de tipul 2 - sunt gramatici independente de context de forma u ((, adic derivarea are loc independent de contextul n care se afl u.

gramatici de tipul 3 - se numesc gramatici regulate, n care prile drepte ale produciilor ncep cu un terminal. Clasa mulimilor regulate peste alfabetul A reprezint clasa limbajelor regulate L3(A).

Notnd cu Gi clasa gramaticilor de tipul i, N. Chomsky a ademonstrat c exist urmtoarele relaii de incluziune ntre gramatici:

G0 (G1 (G2 ( G3

iar pentru limbaje incluziunile sunt stricte : L0 ( L1 ( L2 ( L3.

Dintre cele 4 tipuri de gramatici, doar gramaticile regulate i cele independente de context i-au gsit o aplicabilitate practic n construirea limbajelor de programare. Celelalte dou tipuri de gramatici prezint un interes pur teoretic.

Gramaticile regulate sunt un caz particular al gramaticilor independente de context. De aceea se spune c limbajele formale independente de context modeleaz limbaje de programare.

Un limbaj poate fi generat de o gramatic regulat dac el poate fi recunoscut de un automat finit. Dac n produciile gramaticii independente de context se folosete un singur tip de recursivitate la stnga sau la dreapta, ea devine o gramatic regulat.

Sintaxa unei propoziii ntr-un limbaj independent de context se poate reprezenta printr-o structur de arbore, numit arbore de derivare (sau deducie). Pentru recunoaterea unei propoziii dintr-un limbaj, este necesar ca arborele asociat s fie unic. n caz contrar, gramatica care genereaz limbajul se numete ambiguu.

Un limbaj este inerent ambiguu dac nu poate fi generat dect de o gramatic ambigu.

Exist posibilitatea ca prin modificarea setului de producii ale unei gramatici ambigue s se poat elimina ambiguitile existente, fr ca limbajul generat s sufere vreo modificare.

Producii vide

Partea dreapt a unei producii conine un ir de terminale sau neterminale. Uneori este util s se genereze un ir vid, adic un ir ce nu conine nici un simbol. Acest ir este notat cu e.

De exemplu, gramatica

(

( | ( ( 0 | 1 | |9

definete ca o secven de 0 sau mai multe cifre.

Producia ( e se numete producie vid.

n general, dac pentru un ir ( este valabil o derivare de forma ((*(, atunci ( se numete simbol anulabil. Un neterminal este anulabil dac exist o producie a crei definiie (parte dreapt) este anulabil.

4.2. Aspecte privind definirea limbajelor de programare

Pentru descrierea unui limbaj de programare este necesar adoptarea unui limbaj de descriere corespunztor, numit metalimbaj. Aceast idee aparine lui John Backus i notaia introdus de el este cunoscut sub numele de BNF (Backus Naur Form).

O producie definete o clas sintactic (simbol neterminal) sub forma general:

< nume clas sintactic> :: = definiie

Notaia :: = are semnificaia : "definit prin"

clasa sintactic, denumit i partea stng, corespunde unui simbol neterminal i este inclus ntre paranteze unghiulare.

partea de definiie este denumit i partea dreapt

Simbolurile terminale nu sunt incluse n perechea de paranteze unghiulare i ele apar n propoziiile limbajului.

BNF utilizeaz un set restrns de metasimboluri ( | < > :: =) i un set (specific limbajului) de simboluri terminale.

Formalismul BNF impune nite restricii asupra regulilor de generare:

fiecare clas sintactic (simbol neterminal) trebuie s apar n partea stng a unei singure producii;

simbolul de start nu trebuie s apar n partea stng a nici unei producii;

Ulterior s-au utilizat variante i completri la notaia BNF pentru a se descrie diferite limbaje de programare.

Pentru a crete lizibilitatea notaiilor, s-au adoptat prescurtri inspirate de metasimbolurile folosite pentru expresii regulate.

Aceste notaii extinse au denumirea de forma Backus Naur extins EBNF.

De exemplu pentru urmtoarea gramatic de descriere a ntregilor cu semn:

(

(

( + | - | (folosind EBNF se va rescrie:

( ()*

sau mai restrans:

( (+ | - | () ()*

Extensii introduse de Wirth

n definirea limabjelor Pascal i Modula-2, 1977, Wirth a introdus cteva extensii la forma original de notaie, obtinnd o form extins care a devenit larg utilizat:

neterminale - sunt scrise cu litere italice

instructiuneterminale - litere drepte i ntre apostrofuri begin

| () - au semnificaia din notaia original

[] - semnific aparitia opional a irului dintre paranteze

{} - denot repetiia de 0 sau mai multe ori a irului

. - marcheaz sfritul fiecrei producii

(* *) - simboluri pentru comentarii

( - se nlocuiete cu []

Exemplu: unsigned integer ::= digit {digit}

digit ::= 0 | 1 | 2 | | 9.

4.3. Automate de recunoatere. Diagrame de tranziie.

Pe baza gramaticii limbajului stabilit pentru atomi, analizorul lexical are sarcina s decid apartenena la limbaj a atomilor detectai n fiierul de intrare. Pentru gramatici regulate, problema apartenenei la limbaj este decidabil.

Problema deciziei trebuie completat cu sarcina codificrii atomilor lexicali, cu cea a semnalrii i tratrii erorilor.

Gramaticile de descriere a atomilor lexicali ofer analizorului lexical tiparele pentru identificarea atomilor. Pe baza acestor gramatici, implementarea procesului de recunoatere a atomilor se face folosind un model matematic, numit automat de recunoatere sau automat finit.

Modelul fizic al unui automat finit este o "main" cu operaii foarte simple care are un cap de citire, o unitate de comand i opional o memorie. Maina citete cte un caracter de pe banda de intrare i unitatea de comand decide n ce stare trece automatul pe baza caracterului citit. Automatul se poate afla ntr-un numr finit de stri.

n momentul n care automatul ncepe citirea unui caracter, acesta se afl n starea numit starea de start. Automatul are un numr de stri numite, stri finale. Un ir x este acceptat de automat dac pornind din starea de start, dup citirea tuturor caracterelor din irul de intrare, automatul ajunge ntr-o stare final. Cu alte cuvinte, irul aparine limbajului acceptat de automat.

Modelul matematic de reprezentare a automatului finit este acela al diagramelor de tranziii.

Simbolurile care eticheteaz arcele indic caracterul la citirea cruia automatul va trece din starea de la care pornete arcul n starea n care ajunge arcul respectiv.

Sgeata etichetat cu cuvntul "start" indic nodul de start al diagramei de tranziii, ori poate fi o sgeat de intrare neetichetat.

Pentru a indica orice alt caracter care poate urma la ieirea unei stri, n afara celor deja trecute pe arcele care ies din starea respectiv, se va utiliza o etichet special "altceva".

Diagramele de tranziii sunt deterministe, adic acelai simbol nu poate eticheta dou sau mai multe tranziii care ies din aceeai stare.

Unei tranziii, pe lng simbol i se pot asocia i anumite aciuni care se vor executa n momentul cnd fluxul de comand trece prin tranziia respectiv.

Exemplu:

n general analizorul lexical este format din mai multe astfel de diagrame de tranziii care pornesc din aceeai stare de start i recunosc grupe de atomi. Dac parcurgnd o anumit diagram se semnaleaz eec, se revine n starea de start i se trece la urmtoarea diagram. Revenirea n starea de start presupune i revenirea capului de citire n poziia anterioar ncercrii nereuite. Readucerea capului de citire se poate face memornd adresa locaiei cu citirea creia a nceput ultima recunoatere. Dac prin parcuregerea secvenial a tuturor diagramelor de tranziii. se va semnala eec la toate, nseamn c s-a gasit o eroare lexical i se va apela rutina de tratare a erorii.

Un alt aspect al analizei lexicale l constituie comunicarea datelor detectate de analizorul lexical analizorului sintactic, generearea erorilor lexicale i, dac este necesar, introducerea datelor n tabel. Pentru realizarea acestor sarcinci, diagramele de tranziii se completeaz cu proceduri semantice asociate cu tranziiile din diagram. Aceste proceduri semnatice fie genereaz ieiri ctre analizorul sintactic, realiznd i gestionarea tabelelor, fie trateaz erorile lexicale.

4.4. Exemplu de gramatic a atomilor lexicali i diagrame de tranziii

n cele ce urmeaz, dm notaia BNF a unei gramatici a atomilor lexicali, reprezentative pentru majoritatea limbajelor de programare. Notam G0 aceast gramatic.

1. < ir atomi>::= | < atom>

2. < atom>::= | | | |

3. ::= | |

4. ::= | |

5. ::= + | * | < | | >= | = |

6.::= ; |blanc

7. ::= (* < orice ir de caractere ce nu conine grupul '*)'> *)

8. ::= A | ... | Z

9. ::= 0 | ... | 9

Gramatica G0 nu este regulat dar poate fi transformat uor ntr-o gramatic regulat mrind numrul produciilor i al neterminalelor. Procednd astfel ns, gramatica se complic i procesul de proiectare al analizorului se poate lungi.

De exemplu, produciile 4 se pot scrie:

::= 0 | ... | 9| 0 | | 1| | 9

Se prefer o simplificare a gramaticii prin "stratificarea" gramaticii G0 ntr-o ierarhie de gramatici mai simple, care fiecare n parte este regulat, sau se transform n gramatic regulat. Pentru fiecare din aceste gramatici se va construi diagrama de tranziie, iar n final se asambleaz diagramele astfel nct limbajul n ansamblu rmne acelai.

Se partioneaz mulimea de neterminale i se stabilete o ierarhie ntre elementele partiiei. n exemplul dat, o asemenea partiionare este:

N1={, }

N2={, , , , }

N3={, }

Formm, n jurul celor trei mulimi, gramatici plecnd de la produciile lui G0.

Pentru fiecare gramatic vom considera ca terminale, pe lng terminalele lui G0 i neterminalele din grupul imediat inferior din ierarhie.

Noile gramatici sunt:

(G1) :< ir atomi>::= | < atom>

< atom>::= id | const | op | del | com

(G21) : ::=lit | lit | cif

(G22) :::= cif | | cif

(G23) :::= + | * | < | | >= | = |

(G24) :::= ; |blanc

(G25): ::= (* < orice ir de caractere ce nu conine grupul '*)'> *)

(G31) :::= A | ... | Z

(G32): ::= 0 | ... | 9

Gramaticile sunt regulate cu excepia lui G1 i G25.

Gramatica G1 se poate rescrie ntr-o form EBNF:

(G1) :< ir atomi>::=(id | const| op| del| com) | (id | const| op| del| com)* G25 s-ar putea i ea rescrie ntr-un mod asemntor, dar se prefer construirea automatului direct din aceast form intuitiv.

n figura urmtoare se prezint diagramele de tranziii ale automatelor finite echivalente cu gramaticile G1, G2i ( i = 1, , 5) G3j (j = 1,2):

Din analiza diagramelor, observm c efectul stratificrii const n existena unor tranziii condiionate de terminale care pe nivelul inferior reprezint diagrame de tranziii. Acest lucru nseamn c nu putem activa o asemenea tranziie pe nivelul superior dect dac diagrama de tranziie respectiv de pe nivelul inferior a fost parcurs din starea iniial ntr-o stare final.

Deci, un automat aflat pe un nivel inferior trebuie s transmit nivelului superior informaia de acceptare a irului inspectat.

Vom avea deci o asamblare a automatelor ca n figura urmtoare:

Cuplarea automatelor A1, A2, A3 se face n serie, ieirea unuia fiind intrarea celuilalt.

Pentru a putea descrie funcionarea automatului A0 printr-un limbaj de programare, trebuiesc ndeplinite dou condiii:

Automatele rezultate din diferite cuplri trebuie s fie deterministe

Orice simbol primit la intrarea unui automat i care nu activeaz nici o tranziie trebuie s duc la o situaie de neacceptare sau de eroare.

Observaie:

Exist situaii n care, pentru identificarea unui simbol, un automat consum un simbol care aparine atomului urmtor. Soluiile de implementare constau fie n revenirea n irul de intrare cu un simbol, fie n generalizarea avansului pentru toate strile finale.

Completarea diagramei de tranziii cu proceduri semantice.

n proiectarea analizorului lexical, automatul de recunoatere are un rol orientativ. El arat care sunt sarcinile analizorului n identificarea atomilor lexicali.

Pentru semnalarea erorilor i emiterea unor ieiri, se folosesc proceduri semantice asociate tranziiilor automatului de recunoatere.

Procedurile semantice lucreaz cu cu structuri de date pe care le utilizeaz n luarea deciziilor i pe care, eventual, le modific. Aceste structuri de date alctuiesc baza de date a analizorului lexical i controlul contextului activitii lui.

Controlul contextului are ca scop restabilirea la sfritul analizei unui atom lexical a unui context adecvat cutrii urmtorului atom, emiterea unei ieiri corecte care s reprezinte atomul analizat i semnalarea erorilor.

4.5. Probleme specifice implementarii unui analizor lexical4.5.1. Gestionarea tampoanelor de intrare

Textul surs parcurs i analizat de analizorul lexical este citit de pe suportul de intrare. Pentru efectuarea acestei operaii se recomand utilizarea a 2 zone tampon din urmtoarele motive:

Poate crete viteza prin umplerea unui tampon cnd analizorul lucreaza cu cellalt

Se poate trata simplu cazul n care un atom se continu dintr-un tampon n altul.

Soluiile concrete de gestiune ale tampoanelor depind de modul de implementare al analizorului:

1. Utilizarea unui generator de analizoare lexicale: rutinele pentru gestiune sunt incluse in generator, i nu se afl sub controlul programatorului.

2. Analizorul se scrie intr-un limbaj de nivel inalt. Posibilitile de gestionarea tampoanelor sunt cele specifice limbajului.

3. Analizorul se scrie n limbaj de asamblare. Tampoanele se pot gestiona n modul explicit la cel mai sczut nivel.

Eficiena i efectul cresc de la 1 la 3

Notm cu n dimensiunea tamponului; ea corespunde lungimii dimensiunii fizice (linie, articol) pe mediul de intrare. Fiecare tampon se umple printr-o singur comand de citire iar sfritul textului este marcat de EOF

Pentu localizarea atomului lexical (lexemei curente) n tampoane se utilizeaz pointeri numii pointeri de inceput pi i pointeri de anticipare pa.

La nceput, ambii pointeri indic primul caracter al lexemei curente, apoi pa avanseaza pn cnd analizorul gsete corespondena cu un tipar. irul de caractere dintre cei doi pointeri reprezint urmtorul atom lexical.

Dup detectarea unui atom lexical, pointerul de anticipare poate sa rmn ori pe ultimul caracter al lexemei curente ori pe primul caracter al lexemei urmtoare. Din motive de uniformitate se prefer a doua situaie.

Dup prelucrarea lexemei curente, pi este adus n aceeai poziie cu pointerul de anticipare, situaie n care se poate trece la analiza unui nou atom.

Trecerea pointerului pi din primul tampon n al doilea trebuie precedat de umplerea (citirea) celui de-al doilea tampon, operaie care se poate desfasura n paralel cu analiza propriu zis cnd sistemul de calcul i limbajul permite acest lucru. Analog, trecerea pointerului pa din al doilea tampon n primul n mod circular, trebuie precedat de umplerea (citirea) tamponului 1. Aceast tehnic poate fi aplicat atunci cnd lungimea maxim a unei lexeme nu poate depi 2n, ceea ce este o limitare rezonabil.

Algoritmul de avans al lui pa pentru situaia de mai sus este urmtorul:

if * pa este la sfirsitul tamponului 1 then

begin

* incarca tamponul 2;

pa:= pa +1;

end

else if * pa este la sfirsitul tamponului 2 then

begin

* incarca tamponul1;

pa:=1;

end

else pa:= pa +1

Principalul dezavantaj al acestui algoritm l reprezint faptul c pentru fiecare caracter (exceptnd sfritul tamponului 1, avansul pointerului de anticipare este precedat de 2 teste.

Cele dou teste se pot reduce la unul singur dac se marcheaz sfritul fiecrui tampon cu un caracter special numit santinel, care s fie acelai cu cel de sfrit EOF .

Algoritmul se modific astfel:

pa = pa +1;

if pa = EOF then

if* pa este la sfirsitul tamponului 1 then begin

*incarca tapon2

pa:= pa +1

end

else

if * pa este la sfirsitul tamponului 2 then begin

*incarca tampon 1

pa :=1

end

else *termin analiza lexical.

Se mai remarc i faptul c acelai unic test de sfrit de tanpon rezolv i testul de sfrit al textului surs necesar pentru ncheierea analizei lexicale.

4.5.2. Scrierea codului pentru diagramele de tranziii

Din punct de vedere al programrii, o secven de diagrame de tranziii poate fi implementat fie prin case fie prin succesiune de if. Pentru aceasta fiecrei stari i se asociaz o poriune de program distinct.

- Dac starea nu este final, adic exist arce care ies din acea stare, atunci poriunea de program se ncheie cu citirea unui caracter pe baza cruia se pot selecta tranziii spre stare urmtoare, dac exist arc de ieire etichetat cu acel caracter. Citirea unui caracter se poate face cu o procedur care gestioneaz tamponul de intrare, avanseaz pointerul de anticipare i returneaz urmtorul caracter.

Dac exist arc pornind din starea curent etichetat cu caracterul citit se va transfera controlul la secvena de program pentru noua stare.

Dac nu exist un astfel de arc i starea curent nu este final, se va apela o procedur eec care returneaz pointerul de nceput al atomului lexical i asigur saltul la urmtoarea diagram. n cazul cnd s-au epuizat toate posibilitile, se va apela procedura de eroare.

Dac limbajul nu are case, acesta poate fi simulat printr-un tablou (indexat prin codul caracterului de la intrare). Fiecare element al tabloului corespunde unei stri noi i reprezint un pointer spre o secven de cod ce trebuie executat atunci cnd caracterul curent corespunde indicelui. Poriunea de corespunztoare fiecrei stri se va ncheia fie cu luarea n considerare a strii urmtoare, fie cu salt la tabloul corespunztor urmtoarei diagrame.

5. Construirea automat a analizoarelor lexicale

C4

Un generator de analizoare lexicale pornete de la expresiile regulate care descriu toi atomii limbajului surs i obine diagrama de tranziie corespunztoare, sub forma unei tabele de analiz. Aceast tabel, mpreun cu procedura de analiz alctuiesc analizorul lexical.

5.1.Ob(inerea tabelei de analiz( pe baza expresiilor regulate

Exist dou( metode de transformare a expresiilor regulate n automate finite deterministe.

Metoda I Aceast( metod( presupune parcurgerea urmtoarelor etape:

a.Construirea unui automat finit nedeterminist (AFN) pornind de la expresiile regulate (ER).

b.Transformarea automatului nedeterminist (AFN) n automat finit determinist (AFD).

c.Minimizarea num(rului de st(ri ale automatului determinist.

Metoda IIAceast( metod( presupune parcurgerea urmtoarelor etape:

a.Construirea arborelui binar corespunz(tor ER.

b.Construirea AFD pe baza arborelui.

5.1.1. Construirea unui automat finit nedeterminist din expresii regulate

n diagramele de tranziii folosite pn acum, am implementat automate finite deterministe, (AFD)de genul celui din figura urmtoare:

Din fiecare stare iese o singur sgeat etichetat cu un simbol de intrare. Matricea de tranziii pentru acest automat este:

Dac renunm la unele restricii i permitem ca dintr-un nod s ias mai multe sgei etichetate cu acelai simbol de intrare, precum i sgei etichetate cu ( - care vor reprezenta tranziii independente de intrare obinem un automat finit nedeterminist. (AFN), prezentat n Figura 2.

Unei stri i unui simbol de intrare nu i mai corespunde o stare ci o mulime, eventual vid de stri.

Matricea de tranziii pentru acest automat este:

Evident, AFD este un caz particular al AFN.

Pornind de la expresii regulate, se pot construi automate finite nedeterministe.

Fie o expresie regulat 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 n componentele sale elementare (simboluri i operatori). Se vor construi automate elementare pentru fiecare simbol, dup care, folosind aceste automate, se vor construi automatele pentru expresiile compuse. Automatele pentru expresiile compuse se construiesc inductiv, pentru fiecare operaie : reuniune, concatenare, inchidere. Algoritmul de construcie introduce la fiecare pas cel mult 2 stri noi, prin urmare, automatul rezultat va avea cel mult de 2 ori attea stari cte simboluri si operaii are expresia regulat.

Algoritmul lui Thomson prezentat n continuare, nu este cel mai eficient (un algoritm mai performant ar genera un AFN cu mai puine stri pentru aceeai expresie regulat). Are ns avantajul simplitii, iar dup transformarea din automat nedeterminist n automat determinist, exist posibilitatea reducerii numrului de stri ale automatului finit determinist obinut.

Folosim urmtoarele notaii:

i - stare iniial

f - stare final

N(Ri) - automatul corespunztor expresiei regulate Ri.

- Pentru ( (simbolul vid notat i () se genereaz:

- Pentru a ( un simbol oarecare al alfabetului surs):

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 cte un AFN separat, cu stri notate distinct.

n continuare, se conecteaz ntre ele AFN elementare construite, corespunztor operatorilor aplicai asupra primitivelor din ER, compunndu-se astfel, din aproape n aproape (prin inducie) AFN final.

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

- Pentru R1|R2

Automatul corespunztor expresiei R1 | R2, este N(R1 |R2), obinut prin creerea a 2 stri noi: o stare iniial, diferit de strile iniiale ale automatelor N(R1) i N(R2) i o stare final diferit de strile finale din N(R1) i N(R2), care i pierd proprietatea de satre iniial i final.

Limbajul corespunztor expresiei regulate R1 |R2 este: L(R1) ( L(R2).

- Pentru R1R2

Automatul corespunztor expresiei R1R2 este N( R1R2) pentru care starea iniial este starea se start a automatului N(R1) iar starea final este cea a automatului N(R2). Starea final a automatului N(R1) se identific cu starea se start a automatului N(R2).

Un drum ntre i i f va traversa mai nti automatul N(R1), dup care va trece prin automatul N(R2). Prin urmare, irul de simboluri recunoscut va fi un ir din limbajul expresiei R1 urmat de un ir al limbajului expresiei R2. n consecin, limbajul modelat de automat este: L(R1)L(R2).

- Pentru R1*

Automatul are 2 stri noi i ne putem deplasa din starea iniial i n starea final f, fie direct prin tranziia (, fie prin automatul N(R1), de un numr oarecare de ori.

Un automat obinut pe baza algoritmului lui Thomson are urmtoarele proprieti:

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

- Fiecare stare a automatului are cel mult o tranziie etichetat cu un simbol din alfabet sau cel mult 2 tranziii etichetate cu (.

Aplicaie: Se consider expresia regulat R = (ab(a)*aa . Automatul construit pas cu pas, pornind de la aceast expresie este:

5.1.2. Transformarea AFN n AFD

Un AFN se poate transforma ntr-un automat finit determinist (AFD) care s( accepte acela(i limbaj ca (i AFN.

Notm cu s0 starea ini(ial( a AFN. O stare a AFD va fi compus( dintr-o mul(ime de st(ri {s1, s2,..., sn } ale AFN.

Noiunea de (-nchidere se definete pentru fiecare mulime de stri T ale unui automat: este mulimea strilor n care se poate trece din strile mulimii T pentru un simbol de intrare.

Exemplu: Pentru automatul din Figura 2, prin tranziii vide, (-nchidere(0) = {0,2}, (-nchidere(1) = {1}, (-nchidere(0, 3) = {0,2,3} etc.

Notm:

( alfabetul limbajului surs(

Dst(ri mul(imea st(rilor AFD

Dtranz mul(imea tranzi(iilor

Pentru implementarea algoritmului putem folosi ca structuri de date dou stive i un ir de cifre binare indexat de strile automatului. ntr-una din stive se ine evidena mulimii curente a strilor nedeterministe iar a doua stiv se utilizeaz pentru calculul mulimii de stri urmtoare. Vectorul de cifre binare nregistreaz dac o stare este prezent n stiv, pentru a se evita dublarea ei. Organizarea acestei structuri ca vector are avantajul timpului de cutare constant al unei stri. Dup ncheierea procesului de calcul a mulimii de stri urmtoare, rolul stivelor se inverseaz.

Se iniializeaz strile AFD cutat Dst(ri cu un singur element (o stare), i anume cu mulimea strilor n care se poate ajunge din starea s0 a AFN numai prin tranziii vide (de fapt (-nchidere({s0}), care va fi notat cu (-nchidere({s0}).

La nceput aceast stare e nemarcat. Totodat, mulimea tranziiilor este vid.

Pentru fiecare stare nemarcat din Dst(ri i pentru fiecare simbol din alfabet se caut strile n care se poate ajunge n AFN pentru simbolul respectiv. Adaug aceste stri la Dst(ri dac ele nu sunt deja incluse n aceast mulime, adaug tranziia la Ditranz i marcheaz starea testat din Dstri.

Algoritmul de ob(inere a AFD este:

procedura AFN2AFD este

*ini(ializeaz( Dst(ri cu (-nchidere({s0})

*la nceput st(rile din Dst(ri sunt nemarcate

Dtranz = (

ct timp mai exist( n Dst(ri o stare x = {s1, s2,. . ., sn } nemarcat( execut(

*marcheaz( x

pentru fiecare a ( ( execut(

*fie T = mul(imea st(rilor din AFN pentru care ( o tranzi(ie etichetat( cu a de la o

stare si ( x;

y = (-nchidere(T);

dac( y ( Dst(ri atunci

*adaug( y la Dst(ri, y - nemarcat(

*adaug( tranzi(ia x ( y la Dtranz, dac( nu exist( deja

(

(

(

sfr(it AFN2AFD

Algoritmul de calcul pentru func(ia (-nchidere este:

func(ia (-(nchidere( T ) este

*pune toate st(rile din T ntr-o stiv(

*ini(ializeaz( (-nchidere( T ) cu T

ct timp stiva nu e vid( execut(

*extrage starea s din vrful stivei

pentru fiecare stare t pentru care ( s ( t pentru simbolul ( execut(

dac( t ( (-(nchidere( T ) atunci

*adaug( t la (-nchidere( T )

*pune t n stiv(

(

(

(

sf(r(it (-(nchidere( T )

Exemplu: Fie AFN din figura 7. Limbajul acceptat este: {a, b, ab, abab, }.

Aplicm algoritmul AFN2AFD pe diagrama de tranziii.

Dstri = {(0,1,4)}

Dtranz = (Se marcheaz cu * starea (0,1, 4)

- Pentru simbolul a construim mulimea {2, 5} i calculm (-nchidere ({2, 5}) = {2, 5, 7}

Dstri = {(0,1,4)* , (2, 5, 7)} Dtranz = {(0,1,4)((2, 5, 7) cu simbolul a}

- Pentru simbolul b construim mulimea {6}i calculm (-nchidere ({6}) = {6, 7}

Dstri = {(0,1,4)* , (2, 5, 7), (6, 7)} Dtranz = {(0,1,4)((2, 5, 7) cu a; (0,1,4)((6,7) cu b }

Se marcheaz cu * starea (2, 5, 7)

- Pentru simbolul a nu avem tranziii

- Pentru simbolul b construim mulimea {3}i calculm (-nchidere ({3}) = {1, 3, 7}

Dstri = {(0,1,4)* , (2, 5, 7)*, (6, 7), (1, 3, 7)}

Dtranz = {(0,1,4)((2, 5, 7) cu a; (0,1,4)((6,7) cu b ; (2, 5, 7) ((1, 3, 7) cu b}

Se marcheaz cu * starea (6,7)

- Pentru simbolul a nu avem tranzitii

- Pentru simbolul b nu avem tranziii

Dstri = {(0,1,4)* , (2, 5, 7)*, (6, 7)*, (1, 3, 7)}

Dtranz = {(0,1,4)((2, 5, 7) cu a; (0,1,4)((6,7) cu b ; (2, 5, 7) ((1, 3, 7) cu b}

Se marcheaz cu * starea (1, 3, 7)

- Pentru simbolul a construim mulimea {2}i calculm (-nchidere ({2}) = {2}

Dstri = {(0,1,4)* , (2, 5, 7)*, (6, 7)*, (1, 3, 7)*, (2)}

Dtranz = {(0,1,4)((2, 5, 7) cu a; (0,1,4)((6,7) cu b ; (2, 5, 7) ((1, 3, 7) cu b; (1, 3, 7) ((2) cu a }

- Pentru simbolul b nu avem tranziii

Se marcheaz cu * starea (2)

- Pentru simbolul a nu avem tranziii

- Pentru simbolul b construim mulimea {3}i calculm (-nchidere ({3}) = {1, 3, 7}, dar ea exist.

Dstri = {(0,1,4)* , (2, 5, 7)*, (6, 7)*, (1, 3, 7)*, (2)*}

Strile pot fi redenumite, de exemplu:

(0,1,4) = A

(2, 5, 7)=B

(6, 7)=C

(1, 3, 7)=D

(2)=E

Matricea i diagrama de tranziii pentru AFD parial definit sunt cele din Figura 8.

Se observ c AFD obinut accept exact limbajul {a, b, ab, abab, } acceptat de AFN iniial.

St(rile acceptoare (finale) ale AFD ob(inut vor fi acele st(ri x care vor con(ine cel pu(in o stare acceptoare a AFN. Starea de start a AFD este cea format( din s0 mpreun( cu toate st(rile la care se poate ajunge din s0 doar prin simbolul (.

Algoritmul de mai sus este important pentru c d soluia pentru simularea unui AFN. Simularea direct este dificil, deoarece trebuie simulat calculul "n paralel" al diferitelor traiectorii ce pot fi urmate n AFN. Folosind algoritmul, se determin mai nti AFD echivalent i apoi se simuleaz AFD. Aceast simulare este echivalent cu construirea analizorului limbajului generat de gramatic.

5.1.3. Algoritm pentru simularea comportrii unui automat finit nedeterminist

Se consider un automat N construit dintr-o expresie regulat prin metoda Thomson. Se prezint algoritmul de simulare care va decide dac automatul N recunoate sau nu un ir de intrare x. Rspunsul automatului va fi da n cazul recunoaterii i nu altfel.

- Algoritmul citete intrarea simbol cu simbol (carurm)

- Calculeaz pentru fiecare mulime de stri T mulimea strilor n care se poate trece din strile din T numai prin tranziii vide. (( nchidere).

- Verific dac se poate ajunge ntr-o stare acceptoare.

S:= ( - nchidere(S0);

a:= carurm;

while a( eof do

begin

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

a := carurm;

end;

if S(F ( (( 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 strile automatului. ntr-una din stive se ine evidena mulimii strilor curente, iar a doua stiv se utilizeaz pentru calculul mulimii de stri urmtoare. Vectorul de cifre binare nregistreaz dac o stare este prezent n stiv, pentru a se evita dublarea ei. Organizarea acestei structuri ca vector are avantajul timpului de cutare constant al unei stri. Dup ncheierea procesului de calcul a mulimii de stri urmtoare, rolul stivelor se inverseaz.

5.1.4. Minimizarea numrului de stri ale unui AFD

Automatul finit determinist obinut din automatul finit nedeterminist nu este ntotdeauna cel mai simplu posibil pentru irul de intrare dat. Uneori este posibil reducerea numrului de stri ale AFD astfel obinut.

Se prezint un algoritm care, n caz c este posibil, reduce numrul de stri ale unui AFD.

O stare s a unui AFN este o stare important dac are cel puin o tranziie etichetat cu un simbol diferit de (. De exemplu, n algoritmul de conversie AFN-AFD, strile importante au fost cele care au determinat creerea unei noi stri n AFD.

Considernd mulimile de stri din AFN corespunztoare la 2 stri din AFD, 2 submulimi sunt identice dac:

1. ele au aceleai stri importante

2. ambele fie includ, fie exclud stri acceptoare

Algoritmul de minimizare :

Considerm c avem un AFD notat M, avnd mulimea strilor notat cu S, iar ( reprezint mulimea de simboluri de intrare. Presupunem c fiecare stare are o tranziie pentru fiecare simbol de intrare. Dac AFD nu ndeplinete aceast condiie, vom crea o stare fictiv, numit stare de blocaj, m din care vom trasa arce spre el nsui pentru fiecare simbol de intrare. Pentru toate strile care nu au tranziii pentru toate simbolurile, tranziiile lips se vor completa cu arce spre starea m.Iniial divizm mulimea strilor AFN n 2 submulimi, una coninnd strile care nu sunt finale, celalat coninnd mulimea strilor finale. Algoritmul va partiiona aceste mulimi astfel nct dou stri din aceeai mulime vor trece n aceeai mulime de stri pentru orice simbol de intrare.

Considerm P o partiie obinut la un moment dat n procesul de partiionare, S=(s1,s2,,sk( una din mulimile partiiei i un simbol de intrare a. Cutm pentru fiecare stare si starea n care trece pentru simbolul a. Dac strile urmtoare obinute aparin la mulimi diferite din P, mulimea S se va mpri n submulimi ale cror elemente duc n aceeai submulime din P. Procesul de divizare se repet pn cnd nu mai gsim grupuri ce trebuiesc divizate.

i) Se realizeaz o partiionare P a mul(imii Dst(ri n dou grupuri de stri: F=setul de stri acceptoare i Dst(ri - F = setul de stri non-acceptoare. Printr-o procedur, care se va da mai jos, se ncearc efectuarea unei noi partiionri, Pnou, prin descompunerea grupurilor lui P n subgrupuri. Dac Pnou ( P, se nlocuiete P cu Pnou i se repet procedura de descompunere. Dac Pnou( 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, pentru toate simbolurile a ( (, s (i t tranziteaz n stri aparinnd aceluiai subgrup

* subgrupurile obinute se pun n Pnou

sfr(it parti(ionare

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

iii) Toate tranziiile dintre strile automatului iniial se transform n tranziii ntre reprezentanii 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 plecnd din starea iniial. Tranziiile spre strile de blocaj dinspre alte stri devin nedefinite.

Exemplu: fie automatul din figura 9:

S=(A,B,C,D,E(Prima partiie: ( = (A,B,C,D( (E(Pentru a construi (nou, considerm mulimea (E(; aceast mulime nu se mai poate diviza, deci o includem in noua partiie.

Considerm acum (A,B,C,D(i cutm tranziiile pentru simbolul a: A -a-( B, B -a-( B, C -a-( B, D -a-( B, prin urmare simbolul a nu divizeaz mulimea.

Considerm acum b: A -b-( C, B -b-( D, C -b-( C, D -b-( E, aceste tranziii vor partiiona mulimea n (A, B, C( i n (D(.

(nou = ((A, B, C( (D( (E()

(A, B, C( -a-( (B, B, B((A, B, C( -b-( (C, D, C(Deoarece D este n alt partiie, obinem:

(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 strile (A, C( (B( (D( (E(. Din mulimea (A, C( alegem satrea A ca stare reprezentativ. Toate tranziiile spre C vor deveni tranziii spre A, iar celelalte tranziii le copiem din automatul iniial. Deci, n acest caz s-a reuit minimizarea numrului de stri cu o stare.

5.1.5. Construirea arborelui binar corespunztor ER

C5

a. Un arbore de derivare (parse tree) ntr-o gramatic G={N, T, P, S} este un arbore orientat, etichetat, cu urmtoarele proprieti:

rdcina arborelui este etichetat cu S;

nodurile interioare sunt etichetate cu neterminalele gramaticii, iar frunzele cu neterminale sau terminale;

pentru orice nod interior etichetat cu A avnd descendeni direci etichetai n ordine de la stnga la dreapta cu simbolurile din A: X1, X2, Xk (k ( 1) exist n P o producie: A ( X1 X2 Xk .

irul simbolurilor care eticheteaz frunzele arborelui scrise n ordine de la stnga la dreapta se numete frontiera arborelui.

Se poate arta c oricrei forme propoziionale ( din G i corespunde cel puin un arbore de derivare n G care are ca frontier pe (. El se numete arborele de derivare n G al lui (. .

Fie gramatica: G={{E}, {i, +, *}, P, E}

cu P = { E ( E + E

E ( E * E

E ( (E)

E ( i }.

Propoziia: i*(i+i) are urmtoarea derivare canonic stnga:

E ( E * E ( i * E ( i * (E) ( i * ( E + E) ( i * ( i + E ) ( i * ( i + i )

n figura urmtoare se prezint arborele de derivare al acestei propoziii. Construcia urmrete derivarea canonic stng: frontierele arborilor construii reproduc formele propoziionale din derivarea canonic stng.

b. Arborele corespunz(tor ER este un arbore binar care are cte un nod terminal pentru fiecare simbol ce apare n ER (i cte un nod interior pentru fiecare operator aplicat (concatenare, nchidere, sau). n prealabil ER va fi modificat(, n sensul c( la sfr(itul ei va fi concatenat un simbol special, notat cu #, care va servi drept marcator de sfr(it al ER. O asemenea ER modificat( se nume(te ER augmentat(.

n funcie de operatorul nmagazinat ntr-un nod, nodul se va numi nod-cat dac operatorul este concatenare, nod-sau dac operatorul este sau, nod-stea.

n automatul AFD corespunz(tor ER augmentate, orice stare de la care va exista o tranzi(ie etichetat( cu '#' va fi stare acceptoare.

Fiecare simbol din ER va fi numerotat, (n ordinea textual( a apari(iei sale (n ER. Dac( acela(i simbol apare de mai multe ori, fiecare apari(ie va avea un num(r distinct. Deci, unui simbol din alfabet i pot corespunde mai multe numere de poziie dac el este repetat n cadrul expresiei.

Numerele atribuite n acest mod se numesc pozi(ii..

Arborele se ob(ine aduc(nd ER la forma postfix .

Exemplu:

Fie ER : ( a | b )* a b b

ER augmentat este: ( a | b )* a b b #

ababb#

poz.123456

Fiecare nod al arborelui primete c(te un identificator unic, pentru a putea fi localizat. (n figura urmtoare, identificatorii nodurilor au fost nota(i cu Ni, i=1. .13. Arborele corespunz(tor va fi cel din figura urmtoare.

5.1.5. Ob(inerea AFD din arborele binar

Se folosete ER augmentat, se construiete arborele sintactic (ca n exemplul anterior) i se aplic o metod de analiz sintactic. Se poate demonstra c strile importante din AFN echivalent ER sunt echivalente cu poziia frunzelor din arborele sintactic corespunztor ER. De aceea, metoda obine direct un AFD, iar strile lui vor fi mulimi de poziii din arborele sintactic.

Prin traversri peste arborele construit, pentru fiecare nod n din arbore, se vor determina 4 funcii notate: Anulabil (n), Primapoz(n) , Ultimapoz(n), Pozurm(i), unde n este identificatorul nodului. AFD se va obine din funcia Pozurm(i), Primele 3 funcii sunt definite de nodurile arborelui sintactic i se folosesc n calculul lui Pozurm(i), care este definit numai de poziia din arbore.

Func(ia Pozurm(i) - unde i este o pozi(ie din arborele ER- reprezint( mul(imea pozi(iilor j care pot urma pozi(iei i n arbore.

Pentru expresia regulat din exemplul precedent, Pozurm(1) = {1, 2, 3}.

Poziia 1 corespunde primului a din ER. Dup acesta poate s urmeze:

un nou a din aceeai poziie datorit aplicrii operatorului *

un b din poziia 2 din acelai motiv, considernd i faptul c operatorul este sau un a de pe poziia 3 cu care ncepe irul final abb

Pentru a calcula Pozurm(i) trebuie s se cunoasc ce poziii pot fi puse n coresponden cu primul sau cu ultimul simbol al unui ir generat de o anumit subexpresie din ER.

Dac expresia este r* atunci fiecare poziie care poate fi prima n r poate urma dup fiecare poziie care poate fi ultima n r.

Dac expresia este rs atunci fiecare poziie care poate fi prima n s poate urma dup fiecare poziie care poate fi ultima n r.

Func(ia Primapoz(n) este mul(imea pozi(iilor corespunz(toare cu primul simbol al tuturor (irurilor generate de subexpresiile cu rdcina n n. Analog, Ultimapoz(n) este mul(imea pozi(iilor corespunz(toare cu ultimul simbol dintr-un astfel de ir.

Pentru expresia regulat din exemplul precedent, dac n este rdcina arborelui, Primapoz(n) = {1, 2, 3}, Ultimapoz(n) = {6}.

Pentru calculul acestor func(ii este necesar s( se determine acele noduri care sunt r(d(cini ale unor subarbori ce pot genera (irul vid. Asemenea noduri se numesc anulabile. Vom defini o func(ie Anulabil(n) care va returna valoarea logic( true dac( n este un nod anulabil, (i false n caz contrar.

Exist 2 reguli de baz i 3 reguli inductive pentru cei 3 operatori. Pe baza acestor reguli, parcurgnd arborele de la frunze spre rdcin, se pot determina valorile celor 3 funcii.

Regulile de calcul sunt urmtoarele:

Nr.

Nodul n

Anulabil (n)

Primapoz (n)

Ultimapoz (n)

1.

Frunz( cu

eticheta (true

(

(2. Frunz( eti-

chetat cu ifalse

{i}

{i}

3.

Anulabil(c1)

Primapoz(c1)

Ultimapoz(c1)

sau Anulabil(c2)

( Primapoz(c2)

( Ultimapoz(c2)

4.

Anulabil(c1)

dac( Anulabil(c1) dac( Anulabil(c2)

(i Anulabil(c2)

atunci Primapoz(c1) atunci Ultimapoz(c2)

( Primapoz(c2)

( Ultimapoz(c1)

altfel Primapoz(c1)altfel Ultimapoz(c2)

5.

true

Primapoz (c1)

Ultimapoz (c1)

Observaii:

Pentru Ultimapoz regulile sunt similare cu cele de la Primapoz, doar c( se nlocuie(te Primapoz cu Ultimapoz (i se interschimb( c1 cu c2 (unde este cazul).

Regula 5 pentru Anulabil (n) arat c dac nodul n este nchiderea expresiei prin * atunci Anulabil (n) este true, deoarece nchiderea expresiei prin * genereaz un limbaj care include cu certitudine pe (.

Regula 4 pentru Primapoz arat c dac n expresia rs, r genereaz pe ( (adic Anulabil(c1) = true) atunci Primapoz (s) "se vede" prin r i se include n Primapoz (n). n caz contrar, Primapoz (n) va conine Primapoz (r).

Funciile Primapoz (n) (i Ultimapoz(n), calculate pentru exemplul precedent sunt:

Regulile pentru calculul lui Pozurm(i) sunt:

i) Dac( n este un nod-concatenare (), cu fiul stng c1 (i cu fiul drept c2 (i i(Ultimapoz(c1), atunci se include Primapoz(c2) n Pozurm(i).

ii) Dac( n este un nod-nchidere (*) (i i(Ultimapoz(n), atunci se include Primapoz(n) n Pozurm(i).

n exemplul dat, avnd funciile Primapoz (n) (i Ultimapoz(n) calculate, se determin Pozurm(i).Nod Pozi(ieAnulabilPrimapozUltimapozPozurm

N132false{ 2 }{ 2 }{ 1,2,3 }

N121false{ 1 }{ 1 }{ 1,2,3 }

N11-false{ 1,2 }{1,2 }

N10*true{1,2 }{ 1,2 }-

N93false{ 3 }{ 3 }{ 4 }

N8true{ 1,2 }{ 1,2 }-

N74false{ 4 }{ 4 }{ 5 }

N6false{ 1,2,3 }{ 3 }-

N55false{ 5 }{ 5 }{ 6 }

N4false{ 1,2,3 }{ 4 }-

N36false{ 6 }{ 6 }(

N2false{ 1,2,3 }{ 5 }-

N1false{ 1,2,3 }{ 6 }-

Se parcurge arborele, lund n considerare numai nod-cat i nod-stea:

N2 este fiu stnga , N3 este dreapta, deci includem 6 n Pozurm pentru 5.

N4 este fiu stnga , N5 este dreapta, deci includem 5 n Pozurm pentru 4.

N6 este fiu stnga , N7 este dreapta, deci includem 4 n Pozurm pentru 3.

N8 este fiu stnga , N9 este dreapta, deci includem 3 n Pozurm pentru 1 i 2.

N10 este nod-stea, deci includem { 1,2 } n Pozurm pentru 1 i 2.

Deci:

Poz.Pozurm

1{1,2,3}

2{1,2,3}

3{4}

4{5}

5{6}

6-

Funcia Pozurm se poate reprezenta ca un graf orientat, avnd cte un nod pentru fiecare poziie i un arc orientat de la i la j, dac j este n Pozurm(i).

Acest graf este un AFN fr ( pentru ER dat, dac sunt ndeplinite condiiile:

Toate poziiile din Primapoz (rad) devin stri de start {1,2,3}

Fiecare arc orientat (i,j) este etichetat cu simbolul din poziia j

Starea asociat cu #este singura stare acceptoareNotnd cu rad nodul r(d(cin( al arborelui (i prelund nota(iile Dtranz (i Dst(ri de la cursul anterior, algoritmul de transformare a arborelui ER n AFD este:

procedura ER2AFD este

*ini(ializeaz( Dst(ri cu Primapoz (rad)

*la nceput st(rile din Dst(ri sunt nemarcate

ct timp exist( stare nemarcat( T n Dst(ri execut(

*marcheaz( T

pentru fiecare a ( ( execut(

*fie U=Pozurm (p), unde p ( T (i simbolul din pozi(ia p este a

dac( U (( (i U ( Dst(ri atunci

*adaug( U ca stare nemarcat( la Dst(ri

(

*adaug( tranzi(ia T U la Dtranz

(

(

sfr(it ER2AFDEtapele care se parcurg pentru ob(inerea AFD pe baza arborelui unei ER sunt:

I.Se determin( Primapoz (i Ultimapoz pentru fiecare nod al arborelui.

II.Se calculeaz( Pozurm pentru fiecare pozi(ie, parcurgnd arborele de sus n jos.

III.Se execut( procedura ER2AFD.

5.2. Implementarea generatorului automat de analizor lexical

Specificarea de intrare pentru un generator o reprezint expresiile regulate care descriu atomii lexicali, nsoite de specificaii semantice. Aciunile semantice sunt secvene de program care se execut atunci cnd n irul de intrare se identific o lexem corespunztoare tiparului cu care este asociat aciunea.

r1(aciune 1 (r2(aciune 2 (r3(aciune 3 (

rn(aciune n (Generatorul este un program care pe baza specificaiilor de intrare produce tabela de tranziii a automatului. Analizorul lexical va fi format dintr-un simulator pentru automat, mpreun cu tabela de tranziii generat.

Simulatorul citete tamponul de intrare i pe baza tabelei de tranziie identific lexemele.

Automatul generat la ieire poate fi nedeterminist sau determinist, n funcie de implementarea dorit.

n continuare vom analiza cteva probleme de proiectare specifice pentru cele 2 variante de automate.

a. Generator care implementeaz AFN

Considerm tiparele reprezentate prin ri, i=1,n pentru care se vor construi automatele nedeterministe N(ri). Automatele pariale obinute se combin ntr-un automat general, , numit AFN combinat astfel: se introduce o nou stare de start de la care pleac tranziii ( spre toate cele n automate.

Simularea automatului combinat se bazeaz pe o variant a algoritmului iniial, care recunoate cel mai lung cuvnt din intrare. Aceasta nseamn c de fiecare dat cnd automatul ajunge la o mulime de stri care conine o stare acceptoare, va reine poziia din intrare i tiparul ri asociat cu acea stare, dar simularea continu pn n momentul n care se ajunge n situaia de terminare, adic din mulimea de stri curent nu exist nici o tranziie pentru simbolul din intrare. La atingerea condiiei de terminare, pointerul de avans al intrrii se va retrage la poziia corespunztoare ultimei stri acceptoare marcate. Tiparul memorat pentru aceast poziie identific atomul gsit, iar lexema recunoscut se gsete ntre cei doi pointeri. Dac nu exist stare acceptoare, se poate genera un mesaj de eroare.

Exemplu:

Se consider urmtoarele tipare:

a ((

abb ((

a*b+ ((Automatele pariale corespunztoare celor 3 expresii sunt:

Combinarea automatelor pariale n automatul general este:

Se va analiza irul de intrare aaba

Mulimea strilor de start: 0,1,3,7

Mulimea de stri iniial este 0,1,3,7. La intrare avem simbolul a, deci se va trece n mulimea 2,4,7. ntruct starea 2 este stare final, se reine poziia 2 n irul de intrare i tiparul 1 asociat cu cuvntul 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 poziia 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 tranziii, n consecin, se revine la ultima coresponden recunoscnd lexema aab corespunztoare celui de-al treilea tipar.

Dac expresiile regulate ar avea asociate aciuni semantice, acestea s-ar executa n momentul recunoaterii unui tipar. Aceast operaie nu se va face n mod automat de fiecare dat cnd analizorul ajunge ntr-o stare acceptoare corespunztoare unui tipar, ci numai atunci cnd tiparul se dovedete a fi tiparul care realizeaz cea mai lung coresponden.

b. Generator care implementeaz AFD

Dac generatorul furnizeaz la ieire un AFD, programul de simulare este asemntor cu cel pentru AFN din capitolul anterior, adic se va cuta lexema de lungime maxim.

Problema care apare este c s-ar putea ca prin transformarea AFN-( AFD, mulimea de stri din AFN corespunztoare unei stri din AFD s conin mai multe stri acceptoare. Trebuie s decidem 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:Aplicm algoritmul de conversie automatului generalizat de mai sus:

stareabtiparul anunat

0,1,3,72,4,78nimic

2,4,775,8a

8-8a*b+

778nimic

5,8-6,8a*b+

6,8-8abb

n mulimea de stri (6,8( ambele stri 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 aceleai puncte de marcare ca i la simularea AFN.6. Analiza sintactic

C6

Este etapa din construcia compilatorului n care se recunosc construciile sintactice ale programului. Regulile care descriu structura sintactic a programelor corecte pentru un anumit limbaj de programare se exprim n mod uzual prin gramatici independente de context scrise de exemplu n notaia BNF. Utilizarea gramaticilor pentru descrierea limbajelor de programare are urmatoarele avantaje:

a. gramatica reprezint o notaie precis a unui limbaj, relativ uor de reinut;

b. s-au elaborat metode de construcie manual sau automat de analizoare sintactice eficiente pentru limbaje descrise prin gramatici; aceste metode permit i punerea n eviden a unor ambiguiti sintactice care ar trece neobservate n faza de definiie a limbajului sau la nceputul proiectrii compilatorului

c. descrierea limbajului printr-o gramatic corect favorizeaz procesul de detectare a erorilor i de traducere a programului surs n cod obiect

d. dac limbajul evolueaz n timp, i apar construcii de limbaj noi (completri la sintax) care trebuie s efectueze sarcini noi (completari la semantic), construciile noi se pot aduga mai uor limbajului iniial, iar modificrile implicate n compilator sunt mai simple

n cele ce urmeaz, se vor prezenta principalele metode de analiz sintactic utilizate n compilatoare. Se vor studia conceptele generale operaii cu gramatici, transformri aplicate gramaticilor-, tehnici de implementare manual a analizoarelor sintactice precum i tehnici de generare automat a analizoarelor sintactice. Metodele prezentate se vor completa cu tehnici specifice de revenire n caz de eroare.

6.1. Rolul analizei sintactice

Analizorul sintactic primete ca intrare de la analizorul lexical un ir de atomi lexicali i are sarcina de a verifica dac irul respectiv poate fi generat de gramatic. n caz de eroare va trebui s semnaleze ct mai clar att poziia ct i cauza erorii i s apeleze rutine de tratare i revenire din erori pentru a putea continua analiza.

atom

Program

arbore

codcod

surs

citire atom

Ieirea analizorului sintactic este o reprezentare a arborelui sintactic corespunztor irului de atomi furnizat de analizorul lexical. n diferite cazuri practice, arborele sintactic poate s nu fie construit efectiv ca o structur de date real, chiar dac el apare implicit n timpul analizei. n afara construirii arborelui sintactic, analiza sintactic are i alte sarcini: colectarea de informaii despre atomi i depunerea lor n tabela de simboluri, executarea verificrilor de tip, analiza de domeniu, alte verificri semantice mergnd pn la generare de cod intermediar.

Exist 3 tipuri de analizoare sintacice bazate pe gramatici:

-universale: pot analiza orice gramatic dar sunt practic ineficiente

-analizoare sintactice descendente (top-down parsing denumite i analizoare LL)

-analizoare sintactice ascendente (bottom-up parsing denumite i analizoare LR)

Cele mai eficiente analizoare sintactice ascendente respectiv descendente funcioneaz pentru subclase de gramatici, aceste subclase conin ns majoritatea construciilor de limbaj uzuale. Metodele bazate pe clasele de gramatici analizabile LL sunt utilizate n analizoare sintactice implementate manual, iar cele pentru gramatici LR sunt mai generale i utilizate n metodele de generare automat.

6.1.1. Tratarea erorilor sintactice

Un compilator trebuie s localizeze cu precizie o eroare, s identifice natura erorii i s asigure continuarea analizei. O prim dificultate provine din faptul c definiiile limbajelor de programare nu cuprind i tratarea erorilor, reacia fiind lsat n totalitate n sarcina proiectantului compilatorului.

Planificarea erorilor de la nceputul proiectrii compilatorului poate s simplifice structura acestuia i s mbuntaeasc reacia compilatorului la erori. Programele pot conine erori la diferite nivele: lexical, sintactic, semantic i logic. Cele mai multe erori detectabile n faza de compilare sunt erorile sintactice, iar metodele de analiz sintactic dispun de tehnici performante de detectare de erori care n anumite situatii garanteaz cu certitudine detecia tuturor erorilor. Pentru erorile semantice i logice nu exist metode de detecie att de precise.

La ntlnirea unei erori, analizorul sintactic trebuie s raporteze clar i precis eroarea i s aplice o metod de revenire din eroare. Toate aceste sarcini trebuie astfel implementate nct s nu reduc semnificativ viteza de prelucrare a programelor corecte. O tratare complet i detaliat a tuturor acestor probleme este dificil de realizat n practic. De obicei se prefer mecanisme mai simple de tratare a erorii care se bazeaz pe ideea c majoritatea erorilor de compilare care apar sunt simple i uor de detectat.

Metodele de analiz sintactica LL i LR au proprietatea de prefix viabil, adic sesizeaz apariia unei erori imediat ce apare la intrare un prefix care nu corespunde nici unui ir din limbaj, motiv pentru care sunt considerate metode rapide din punct de vedere al deteciei erorilor. La raportarea unei erori se indic de obicei locul n care s-a detectat eroarea, fr a exista certitudinea c acela este locul erorii. Exist totui probabilitatea ca eroarea s fie chiar n acel loc sau n imediata lui vecinatate, cel mult ctiva atomi mai n fa. Natura erorii se precizeaz prin mesaje de eroare, dac exist o probabilitate mare de estimare corect se genereaza un mesaj exact, de exemplu lipsete;, dac nu, este de preferat un mesaj mai vag: sintax error.

n ceea ce privete metodele de revenire din eroare, exist cteva metode generale. n principiu, compilarea nu poate fi abandonat dect la erori grave, iar analiza trebuie reluat dintr-un punct ct mai apropiat de locul erorii cu condiia ca prin revenire s nu se introduc erori noi.

6.1.2. Strategii de revenire din erori

Exist 3 strategii acceptate:

a. modul de panic este metoda cel mai frecvent folosit i cel mai uor de implementat. n momentul detectrii unei erori se elimin din intrare unul sau mai multe simboluri pn cnd se ajunge la un atom special de sincronizare, iar din acest punct al intrrii analiza se poate relua. Metoda are avantajul c se ajunge ntotdeauna la sfritul sirului de intrare i nu pot aprea cicluri infinite n analiz. Ca i atomi de sincronizare se aleg diferii delimitatori specifici limbajului.

b. revenirea la nivel de propoziie la detectarea unei erori, analizorul ncearc s fac corecii locale n irul de intrare, de genul: nlocuirea unui simbol cu altul, tergerea sau inserarea unui simbol. Prin aceste modificri urmrete s construiasc un prefix corect al intrrii n locul celui eronat. La aceast metod exist pericolul ciclului infinit (de exemplu la inserarea repetat a unuia i aceluiai simbol, fr a se putea continua analiza). Dezavantajul principal al metodei este c nu permite corecii adecvate n cazul n care eroarea este nainte de punctul de detecie.

c. utilizarea produciilor de eroare este o metoda care impune cunoaterea precis a tipurilor de eroare ce se pot ntlni i practic, numrul erorilor posibile nu este foarte mare. Pentru aceast metod se suplimenteaz gramatica limbajului cu producii care s genereze i construcii eronate, iar analizorul sintactic se construiete pe baza acestei gramatici extinse. Dac pe parcursul analizei se utilizeaz o producie de eroare, aciunile asociate cu acea producie nu vor conduce la traducere ci la un mesaj de eroare.

d. efectuarea de corecii globale este o metod teoretic care compar programul x cu un program y obinut printr-un numr minim de transformri, presupus a fi cel intenionat de programator.

6.2. Proiectarea unei gramaticiPentru a fi analizat sintactic, un limbaj va fi descris n continuare printr-o gramatic independent de context.

O gramatic independent de context nu poate descrie ns complet sintaxa unui limbaj de programare, deoarece exist i constructii dependente de context i acestea vor trebui tratate n fazele urmtoare de analiz (de exemplu cerina ca un identificator s fie declarat nainte de utilizare). O alt problem care se pune este faptul c fiecare metod de analiz poate trata numai gramatici de o anumit form i de aceea este uneori necesar ca gramatica iniial s fie transformat pentru a o face analizabil prin metoda aleas. n acest subcapitol se vor trata acele transformri care fac o gramatic potrivit pentru metode descendente de analiz: eliminarea ambiguitii din gramatic, eliminarea simbolurilor inutile, eliminarea recursivitii de stnga, factorizarea la stnga).

6.2.1. Comparaie: expresii regulate-gramatici independente de context

Pn acum, pentru descrierea atomilor lexicali, s-au folosit n principal expresiile regulate. Regulile lexicale sunt simple i descrierea lor nu necesit un formalism att de puternic ca i cel oferit de gramatici.

Expresiile regulate, fa de gramatici ofer urmtoarele avantaje:

a. pentru structuri simple de limbaj reprezint notaii mai precise i mai clare dect gramaticile

b. analizorul lexical realizat pe baza expresiilor regulate are structura mai simpl i poate fi mai uor generat automat.

Observaie: Fiecare construcie exprimabil printr-o expresie regulat se poate descrie i printr-o gramatic independent de context, respectiv orice automat finit nedeterminist se poate transforma ntr-o gramatic care generaz acelai limbaj.

Exemplu. Fie expresia regulat: (a|b)*abb. Ei i corespunde un AFN di figura urmtoare:

Pe baza acestui AFN se poate construi gramatica:

G: A0 ( aA0 | bA0 | aA1

A1 ( bA2

A2 ( bA3

A3 ( (

Metoda de transformare este:

Pentru fiecare stare i din automat se creaz un neterminal Ai

Pentru fiecare tranziie se creaz n gramatic o construcie de forma Ai ( aAj

Pentru fiecare tranziie se include n gramatic o construcie de forma Ai ( Aj

Pentru fiecare stare final i se include n gramatic cte o producie Ai ( (

Simbolul corespunztor strii de start devine simbol de start al gramaticii.

Nu exist reguli fixe de divizare a unui limbaj n parte lexical i nelexical. De obicei se descriu prin expresii regulate i se trateaz la expresii regulate construciile simple ale unui limbaj: identificatori, numere, iruri de caractere, iar n faza de analiz sintactic se trateaz construciile mai complexe care se exprim prin relaii recursive: instruciuni, declaraii, expresii etc.

6.2.3. Gramatici ambigue. Exemplu de transformare a unei gramatici ambigue ntr-o gramatic neambigu echivalent

Analizorul sintactic pentru un limbaj genereaz implicit sau explicit arborele sintactic pentru irul de intrare dat. Din aceast cauz este important ca arborele care se asociaz s fie unic. Considerm urmtoarea gramatic :

S ( AB|BC

A ( D

B ( E

C ( D

D ( a|b

E ( a|b

Dac irul din intrare este ab, atunci pentru aceast propoziie se pot forma doi arbori:

Definiie: O GIC se numeste ambigu dac n limbajul generat exist o propoziie care admite mai mult dect un arbore sintactic, obinut prin derivri dinstincte; n caz contrar gramatica este neambigu. Cu toate c gramaticile ambigue reprezint o descriere mai compact i mai clar a unui limbaj, ele sunt n general o piedic, un inconvenient n plus.

Pentru acelai limbaj, pot exista att gramatici ambigue ct i gramatici neambigue care s-l genereze.

Exemplu: G1: S ( i5 | SS

G2: S ( i5 | i5S

L(G1)=L(G2)={i5k | k>=1}

G1 este ambigu deoarece de exemplu pentru i15 avem dou derivri stnga:

S ( SS ( SSS ( i5SS ( i10S ( i15

S ( SS ( i5S ( i5SS ( i10S ( i15n timp ce G2 este neambigu.

Definiie: Un limbaj se numete inerent ambiguu dac orice gramatic care-l genereaz este ambigu.

Exemplu de transformare a unei gramatici ambigue ntr-o gramatic echivalent neambigu. Considerm urmtoarea gramatic a expresiilor matematice:

G1= < {E}, {+,*,(,),id}, P1, E >

P1: E ( E+E | E*E | (E) | id

Aplicnd produciile gramaticii, expresiei id+id*id i corespund urmtorii arbori sintactici:

Ambiguitatea se poate rezolva dac stabilim care dintre operatorii * i + este mai prioritar. Pentru primul arbore operatorul mai prioritar este * iar pentru al doilea este +. Modificnd gramatica astfel:

G2= < {E,T,F}, {+,*,(,),id}, P2, E >

P2: E ( E+T|T

T ( T*F | F

F ( (E) | idObinem pentru expresie un arbore unic:

Ambiguitatea s-a eliminat prin fixarea prioritii mai mari pentru operatorul de * fa de operatorul +. n general eliminarea ambiguitii implic mrirea numrului de neterminale.

n teoria limbajelor formale se demomstreaz urmatoarele teoreme:

1. Limbajele regulate din clasa L3 sunt neambigue.

2. O reuniune a unui numr finit de limbaje neambigue disjuncte 2 cte 2 reprezint de asemenea un limbaj neambiguu.

Teorema 2 permite ca studierea ambiguitii s se fac pentru pri ale limbajului, chiar pentru un set mic de producii.

S-a demonstrat faptul c nu exist un algoritm care acceptnd orice GIC s determine n timp finit dac aceasta este sau nu ambigu. Exist doar un set de condiii care dac sunt satisfacute de gramatic atunci este cert c gramatica nu este ambigu. Aceste condiii sunt suficiente dar nu i necesare, adic o gramatic poate fi neambigu i fr s respecte aceste condiii.

6.2.4. Eliminarea simbolurilor inutile dintr-o gramatic

Fie gramatica G = < N,T,P,S>, unde VG =N U T este vocabularul gramaticii. Un simbol ( ( VG este inutil dac nu exist nici o derivare de forma:

S =*> u ( v =*> u x v

unde u,x,v ( T*

Relaia de mai sus descrie dou tipuri de simboluri inutile:

a. simboluri inaccesibile : sunt acele simboluri care nu pot fi generate prin nici o derivare pornind de la simbolul de start nu apar n nici o propoziie generat de gramatic; ( este simbol inaccesibil

b. simboluri nefinalizate : sunt acele simboluri care nu se pot transforma ntr-un ir exclusiv de simboluri terminale, oricte derivri s-ar aplica

n timp ce simbolurile inaccesibile pot fi att terminale ct i neterminale, cele nefinalizate pot fi doar neterminalele gramaticii.

Se poate demonstra c pentru orice GIC cu limbajul generat L(G) ( ( exist o gramatic echivalent cu ea (deci genereaz acelai limbaj) care nu are simboluri inutile.

Eliminarea simbolurilor inutile din gramatic se poate face n doi pai:

1. se caut i se elimin toate simbolurile nefinalizate precum i relaiile care le conin

2. se determin i se elimin toate simbolurile inaccesibile i relaiile corespunztoare lor

Gramaticile care descriu limbajele de programare sunt obligatoriu fr simboluri inutile.

6.2.5. Eliminarea recursivitii de stnga dintr-o gramatic

O gramatic este recursiv la stnga dac are cel puin un neterminal A pentru care exist o derivare de forma: A =+> A ( unde ( este un ir oarecare. n mod similar se definete recursivitatea la dreapta a unei gramatici .

Metodele de analiz sintactic descendent nu pot trata gramaticile recursive la stnga (analizorul intr n ciclu infinit) rezultnd deci c pentru a face o gramatic analizabil prin aceast metod este necesar s se elimine acest tip de recursivitate. Cazul cel mai simplu l constituie acela n care gramatica are producii de forma:

A(A(, ceea ce nseamn recursivitate de stnga imediat. Acest tip de recursivitate se rezolv simplu n felul urmtor:

Avnd produciile A ( A ( | ( unde ( nu ncepe cu neterminalul A, se introduce un nou neterminal A iar produciile se modific n felul urmtor:

A ( (A

A ( ( A | (Se poate arta uor c limbajul generat de noua gramatic nu s-a schimbat.

Exemplu:

E ( E + T | T

T ( T * F | F

F ( (E) | idProduciile recursive sunt cele pentru E i T.

=> E ( T EE ( + T E | ( T ( F TT ( * F T | (

F ( (E) | idAlgoritm de eliminare a recursivitii stnga imediate

La modul general, recursivitatea stnga imediat pentru un simbol A se poate elimina prin urmtoarea metod:

- se grupeaz produciile pentru A

A ( A (1 | A (2 | | A (m | (1 | | (nastfel nct nici un (i nu ncepe cu A

-se nlocuiesc produciile pentru A prin urmtoarele producii echivalente:

A ( (1 A | (2 A || (n A

A ( (1 A| (2 A| | (m A | (Metoda elimin orice caz de recursivitate imediat cu condiia ca nici un (i s nu fie (. Eliminarea recursivitatii de stnga s-a obinut prin transformarea ei n recursivitate de dreapta care ns nu deranjeaz n procesul de analiz descendent.

Recursivitatea de stnga poate s nu fie imediat. De exemplu pentru gramatica:

S( A a | b

A ( A c | S d | (Att pentru S ct i pentru A exist producii recursive, pentru S recursivitatea nefiind imediat.

Se prezint un algoritm care elimin complet recursivitatea stnga cu condiia ca gramatica s nu aib cicluri ( A=+> A) i s nu aib producii vide (A((). Problema ciclului i a produciilor vide poate fi rezolvat anterior aplicrii algoritmului de mai jos, prin transformri specifice.

Algoritm de eliminare a recursivitii stnga

1. se aranjeaz neterminalele gramaticii ntr-o anumit ordine i se numeroteaz A1, A2, An2. for i:=1 to n do begin

for j:=1 to i-1 do begin

* inlocuiete fiecare producie de forma Ai ( Aj ( prin producia

Ai ( (1 ( | | (k ( unde Aj ( (1 | | (k reprezint toate produciile corespunztoare lui Aj* elimin recursivitatea stnga imediat pentru Ai, dac este cazul

end;

end;

Algoritmul funcioneaz corect deoarece nainte de iteraia i oarecare orice producie de forma Ak( Al ( cu k< i are n mod obligatoriu l >k. Ca rezultat, la urmtoarea iteraie (i), ciclul interior (cu j) va ridica progresiv limita inferioar m n orice producie Ai ( Am ( pn cnd m ( i. Eliminnd acum recursivitatea imediat pentru Ai, rmne m > i, adic poate ncepe urmtoarea iteraie.

Trasarea algoritmului pentru gramatica anterioar: (chiar dac exist producie vid pentru A, pentru gramatica dat nu deranjeaz)

1. ordonm produciile pentru S i A

2. pentru i=1 bucla pentru j nu are efect (neterminalul S)

pentru i=2 adic neterminalul A

A ( Ac | Aad | bd | (Introducem un neterminal nou A i obinem

A ( bdA | A

A ( cA | adA | (( s-a obinut gramatica

S ( Aa | b

A ( bdA | A

A ( cA | adA | (6.2.6. Factorizarea la stnga

Dac pentru un neterminal A exist mai multe alternative care ncep cu acelai simbol sau acelai grup de simboluri, n procesul de analiz top-down nu se poate decide care alternativ s fie aleas. Factorizarea ntrzie luarea deciziei pn n momentul n care parcurgnd suficiente simboluri din intrare exist suficient informaie pentru a lua o decizie de expandare corect. Din acest motiv este necesar introducerea unei etape intermediare de factorizare a produciilor de acest gen.

( if then else

if then | altceva

( b

Dac n intrare apare if, nu se poate ti care din variante s se utilizeze pentru expandarea neterminalului . n general se poate nota A( ( (1 | ( (2 cu ( ( (. Factorizarea const n introducerea unui neterminal A i transformarea gramaticilor astfel: A( A, A ( (1 | (2.

Algoritmul de transformare:

* pentru fiecare neterminal A se caut cel mai lung prefix ( comun la dou sau mai multe alternative ale lui A. Dac ( ( ( atunci toate produciile de forma

A ( ( (1 | ( (2 | | ( (k | (, unde ( reprezint produciile care nu au pe ( ca prefix) se vor nlocui cu A ( ( A | (, A ( (1 | (2 | | (k

* se repet acest procedeu pn nu mai exist neterminale cu alternative avnd prefix comun

( ( if then | altceva

( else | (

( b

Exemplu de eliminarea recursivitii stnga dintr-o gramatic

Fie gramatica:

S ( CB | a; B ( Sa | b; C ( Bb | Cba

Algoritmul se bazeaz pe ordonarea neterminalelor urmat de prelucrarea produciilor astfel nct s nu apar producii de forma Ai ( Aj ( cu j ( i.

Ordonm neterminalele:

A1 = S, A2 = B, A3 = C

Gramatica cu producii numerotate devine:

1. A1 ( A3 A2

2. A1 ( a

3. A2 ( A1 a

4. A2 ( b5. A3 ( A2 b

6. A1 ( A3 ba

Producia 3 este nlocuit cu:

3', 3" A2 ( A3A2 a| aa

Producia 5 este nlocuit cu:

5', 5", 5"' A3 ( A3A2 ab| aab | bb

Produciile 5', 5", 5"' i 6 se nlocuiesc datorit recursivitii stngi imediate a lui A3 cu:

A3 ( aab A' | bb A'i A' ( A2 ab A'| ba A' | (Renumerotnd produciile, gramatica devine:

0. A' ( A2 ab A'

1. A' ( ba A'

2. A' ( (3. A1 ( A3 A2

4. A1 ( a

5. A2 ( A3A2 a

6. A2 ( aa

7. A2 ( b

8. A3 ( aab A'

9. A3 ( bb A'

C7

Exemplu de eliminarea recursivitii stnga dintr-o gramatic

Fie gramatica:

S ( CB | a; B ( Sa | b; C ( Bb | Cba

Algoritmul se bazeaz pe ordonarea neterminalelor urmat de prelucrarea produciilor astfel nct s nu apar producii de forma Ai ( Aj ( cu j ( i.

Ordonm neterminalele:

A1 = S, A2 = B, A3 = C

Gramatica cu producii numerotate devine:

1. A1 ( A3 A2

2. A1 ( a

3. A2 ( A1 a

4. A2 ( b5. A3 ( A2 b

6. A1 ( A3 ba

Producia 3 este nlocuit cu:

3', 3" A2 ( A3A2 a| aa

Producia 5 este nlocuit cu:

5', 5", 5"' A3 ( A3A2 ab| aab | bb

Produciile 5', 5", 5"' i 6 se nlocuiesc datorit recursivitii stngi imediate a lui A3 cu:

A3 ( aab A' | bb A'i A' ( A2 ab A'| ba A' | (Renumerotnd produciile, gramatica devine:

0. A' ( A2 ab A'

1. A' ( ba A'

2. A' ( (3. A1 ( A3 A2

4. A1 ( a

5. A2 ( A3A2 a

6. A2 ( aa

7. A2 ( b

8. A3 ( aab A'

9. A3 ( bb A'

Tipuri de analizoare sintactice

Rolul analizei sintactice este transformarea irului de atomi lexicali ntr-o descriere structural a irului n cazul n care acesta e corect, sau ntr-un mesaj de eroare, n cazul n care irul nu e corect. Descrierea structural este de obicei un echivalent al arborelui de derivare.

a. n principiu, exist dou strategii de construire a arborelui de derivare: strategia descendent, n care arborele este construit de la rdcin spre frunze i strategia ascendent, n care arborele este construit de la frunze spre rdcin.

n ambele cazuri, construcia e ghidat de irul de la intrare.

Corespunztor acestor strategii, exist analizoare sintactice descendente i, respectiv, analizoare sintactice ascendente. Metodele de analiz sintactic descendent sunt simple comparativ cu cele ascendente i permit construirea manual uoar de analizoare sintactice destul de eficiente. Analizoarele sintactice ascendente sunt mai generale, adic permit tratarea unor clase mai largi de limbaje.

b. O alt clasificare a analizoarelor sintactice este dat de existena revenirilor.

Un analizor sintactic cu reveniri permite prin program posibilitatea ncercrii tuturor alternativelor de continuare a analizei, n situaia n care unui neterminal i corespund mai multe alternative dintre care nu se poate alege n mod univoc una exact la un moment dat al analizei. Abandonarea unei alternative necesit revenirea la situaia anterioar ncercrii ei.

Dac se asigur n orice moment o singur posibilitate de continuare a analizei sintactice se pot realiza analizoare sintactice fr reveniri, care sunt mai eficiente.

7. Analiza sintactic descendent

Analiza sintactic descendent const n ncercarea de a gsi o succesiune de derivri stnga, pornind de la simbolul de start, pn se obtine irul dat la intrare. Ea este echivalent cu ncercarea de a construi arborele sintactic pentru irul respectiv, pornind de la rdcin spre frunze, construind nodurile n preordine.

7.1. Analiza sintactic descendent cu reveniri

Construcia arborelui sintactic ncepe de la rdcin, principalele operaii ale analizorului sintactic fiind:

nlocuirea unui neterminal A din vrful stivei cu un ir ce reprezint o parte dreapt a produciilor gramaticii pentru simbolul neterminal respectiv, operaie ce se numete expandare. La nodul curent et