Compilatoare 1. Analiza sintactic predictiv 2. Analiza sintactic descendent cu reveniri 3. Analiza sintactic prin coborre recursiv 4. Maina abstract de analiz predictiv 5. Analiza sintactic LL(1) 6. Maina abstract de analiz LL(1) Analiza sintactic predictiv poate fi modelat prinintermediulunuiautomatfinitcustiv care lucreaz asupra unui ir de intrare. AF Si St isi ist LIFO Siiruldeintrare(conine atomiilexicaliobinuin urmaetapeideanaliz lexical) isi indice pentru Si St stiva (acces LIFO) ist vrful stivei Analiza sintactic predictiv pleac de la notiunea de derivare stnga: S => w1 => => wn, unde wi = xiAoI, wi+1 = xi|ioI, cu proprietatea A -> |i eP, iar xi e E* i oI e (VNE)*

Algoritmulanalizeisintacticepredictivepentruun limbaj definit printr-o gramatic generatoare este: 1.Analizasintacticpornetedelasimboluldestart S, care este introdus n stiv. 2.Sefaceexpandareavrfuluistivei,alegnd convenabil o regul de producie. 3. Dac n vrful stivei apare un terminal, acesta este comparat cu simbolul curent din irul de intrare. Dac celedousimbolurisuntegale,atuncivrfulstivei este scos i se avanseaz n irul de intrare. Altfel, se semnaleaz eroare. 4.Lasfrit,dacstivaestegoalis-aajunsla sfrituliruluideintrare,atunciacestaestecorect. Altfel nu este corect. Procedura de analiza este sf = false repeta daca (st(ist)eE)A(st(ist)=si(isi)) atunciist i | (E) Neterminale : VN = {E, T, F} Terminale : E = {+, *, (, ), i} Automatul de analiz sintactic predictiv: Q = {q} E = {+, *, (, ), i} I = {E, T, F, +, *, (, ), i} z0 = E q0 = q F = C f(q, a, a) = (q, ) , f(q, , A) = (q, o) , oricare A-> o e P AP = < {q}, {+, *, (, ), i}, {E, T, F, +, *, (, ), i} , f , q , E , C > f(q, a, a) = (q, ) f(q, , E) = {(q, E+T), (q, T)} f(q, , T) = {(q, T*F), (q, F)} f(q, , F) = {(q,i), q, (E)} Pentru analiza propozitiei i*i+i evolutia automatului este : (q, i*i+i , E) (q, i*i+i , E+T) (q, i , T) (q, i*i+i , T+T) (q, i , F) (q, i*i+i , T*F+T) (q, i , i) (q, i*i+i , F*F+T) (q, , ) (q, i*i+i , i*F+T) (q, *i+i , *F+T) (q, i+i , F+T) (q, i+i , i+T) (q, +i , +T) Pentruaputeautilizaanalizasintacticpredictiv, gramaticageneratoarealimbajuluiinttrebuies ndeplineasc condiiile: 1.Nusefoloseterecursivitatestnganregulilede producie:nuexistniciunneterminalAastfelnct A=+>A. ndeplinirea acestei condiii asigur faptul c stiva nu se va extinde la infinit, avnd n vedere c se folosete derivarea stnga pentru nlocuirea neterminalelor. 2.Pentruoriceneterminal,priledreptealeproduciilor salencepdiferit:NuexistdouproduciiA->iA->, cu diferit de . Aceastcondiieasiguridentificareauoarareguliide produciecaretrebuiefolositpentruaexpandaun neterminal din vrful stivei, pe baza simbolului curent din irul de intrare. Eliminarea recursivitii stnga: Dacexistregulideproduciecarefolosesc recursivitatea stnga, de exemplu: A->A, A-> AtunciintroducemunnouneterminalAi nlocuim regulile n cauz cu: A->A, A->A, A-> Ex: Dac nu este ndeplinit a doua condiie, i gramatica conine, de exemplu, regulile: A->, A-> AtunciintroducemunnouneterminalAi nlocuim regulile n cauz cu: A-> A, A->, A-> Ex: Exerciiu: Fie gramatica: Analizai sintactic propoziia: Analizasintacticprincoborrerecursiv constituieoimplementaredeterminista analizei sintactice predictive. AF Si St1 St2 isi ist2ist1 Siiruldeintrare (conineatomiilexicali obinuinurmaetapeide analiz lexical) isi indice pentru Si St1stiva(accesLIFO)cu frunzele arborelui sintactic ist1 vrful stivei St1 St2 stiva de retur Ist2 vrful stivei St2 Configuraia automatului finit este data de: (s, i, o, |), Unde: s - starea automatului finit, care poate fi: - q (stare normala), - b (stare de revenire), - e (stare de eroare), - t (stare de true) j - indicele sirurului de intrare j1 j2jn o-iruldinstivaSt2,formatdinsimboluridejarecunoscutenirulde intrare i din indicii regulilor de producie utilizate n derivri - irul din stiva St1, format din simboluri nc neexpandate (1) stare initiala(q, 1, , S) (2) expandarea(q,j,o,A|)(q,j,oA1,o1|),undeA1:A->o1 esteprima produciepentruneterminalulAdinvrfulstiveiSt1(Avafiexpandatconform primei alternative) (3) avans (q, j, o, a|) (q, j+1, oa, |), cand n varful stivei St1 se afl un terminal identic cu cel din poziia curent (j) a irului de intrare (4)necoincidenta(q,j,o,i|)(b,j,o,i|),candnvrfulstiveiSt1seaflun terminal care nu este identic cu cel din poziia curenta (j) a irului de intrare (5) revenire in starea de intrare (5.1) (b,j,oi,|)(b,j-1,o,i|),cndnvrfulstiveiSt2seaflun terminal; pasul 5.1 se repet atta timp ct se afl un terminal n vrful stivei St2 (5.2) (b, j, oAi, oi|) (q, j, oAi+1, oi+1|) , se sare la pasul 3 (5.3) (b, j, oAn, on|) (b, j, o, A|), se sare la pasul 5.1 (6) esec(b, j, o, S|) (e, j, o, S|) (7) succes(q, n+1, o, ) (t, n+1, o, ) Ex: Fie gramatica: (S1)S -> Ab (S2)S -> Ac (A1)A -> a (A2)A -> bAB (B1)B -> a Analizai propoziia w e E*: 1. w = bbaaab 2. w= bbaabab Starea initiala : (q, 1, , S) (2)(q, 1, S1, Ab) //expandare (2) (2)(q, 1, S1A1, ab) //st2(ist2)=si(isi) (4)(b,1,S1A1, ab) //necoincidenta (4) (5.2) (q, 1, S1A2, bABb) //back (5) (3)(q, 2, S1A2b, ABb) //avans (3) (2)(q, 2, S1A2bA1, aBb) //expandare A1 -> a (4)(b, 2, S1A2bA1, aBb)//necoincidenta(5.2) (q, 2, S1A2bA2, bABBb) //revenire (back) (3)(q, 3, S1A2bA2b, ABBb)//avans (2)(q, 3, S1A2bA2bA1, aBBb) //expandare (3)(q, 4, S1A2bA2bA1a, BBb) //avans (2)(q, 4, S1A2bA2bA1aB1, aBb) //expandare (3)(q, 5, S1A2bA2bA1aB1a, Bb) //avans (2)(q, 5, S1A2bA2bA1aB1aB1, ab) //expandare (3)(q, 6, S1A2bA2bA1aB1aB1a, b) //avans (3)(q, 7, S1A2bA2bA1aB1aB1ab, $) //avans (7)(q, 7, S1A2bA2bA1aB1aB1ab, A)//succes Pentruaputeautilizaanalizasintacticcu reveniri,gramaticageneratoarealimbajului inttrebuiesndeplineascnumaiprima condiiedintrecelecerutepentruanaliza sintactic predictiv. Este o implementare a analizei sintactice predictive. Fiecare neterminal devine un nume de funcie. Funciapentruunanumitneterminaleste responsabilsverificedacsepoategsila nceputuliruluideintrareoderivarecarepornete de la acest neterminal. Dacnuesteposibil,funciatrebuiessarpeste ceea ce a gsit i s semnaleze o eroare. Existofuncieprincipalcarelanseazfuncia pentru simbolul de start i verific dac intrarea este vid. Existofuncienextcarefaceunavanscuopoziie n irul de intrare. Exemplificmconstruciafunciilornecesare analizeisintacticeprincoborrerecursiv pentru gramatica: Exerciii: 1. Scriei funciile pentru neterminalele T i T pentru gramatica anterioar 2.Analizaipropoziia(id),reprezentnd strile stivei de apeluri. Pentruaputeautilizaanalizasintacticprin coborrerecursiv,gramaticageneratoarea limbajuluiinttrebuiesndeplineasc aceleai condiii ca i pentru analiza sintactic predictiv. Structura mainii de analiz predictiv MP Procesor SI ISI ISO SO ST VSIMP Procesorul este unitatea central virtual care interpreteaz programele i le execut. SIesteiruldeintrarecuindiceleISIcaremarcheazpoziia caracterului curent de analizat. SOesteiruldeieirecuindiceleISOcaremarcheazultimul caracter introdus sir. STeste o memorie de tip stiv, cuVS vrful stivei MPestememoriaprogram,accesibildoarlacitire,cuIMPindicele instruciunii curente. ProcesorulcitesteprogrameledinMPileexecutalafelcai procesoruloricruicalculatorreal.ElpoatecitiuncaracterdinSI, poate scrie un caracter n SO i poate scrie sau citi din varful stivei ST. MAP recunoate i execut patru instruciuni: 1.Instructiunea de test (V) 2.Instructiunea de apel cu revenire (A) 3. Instruciunea adevrat (T) 4. Instruciunea fals (F) 1.Instructiunea de test: V(a),E1,E2 Instruciunea de test face verificarea coincidenei dintre simbolul curent din SI i caracterul indicat ntre paranteze, adic a. In caz de identitate se scrie caracterul a nirul SO, se avanseaza n SI i se continu execuia cu instruciunea E1. n caz contrar se continu execuia cu instruciunea E2. DaccmpurileE1siE2 suntvide,execuiasecontinucuurmtoareainstruciunedin MP. E1 i E2 pot fi etichete ale unor instruciuni din MP, sau pot fi una dintre instruciunile T i F. 2.Instructiunea de apel cu revenire A(E),E1,E2 Permite executia secvenei de program de la eticheta E.nainte de execuia primei instruciuni de la eticheta E, se salveaz starea mainii de analiz, adic tripletul (ISI,ISO,IMP) n ST.Dacareturuldinsecvensefacecuinstruciuneaadevarat(T),sevaexecutan continuare instructiunea E1. Dacreturuldinsecvensefacecuinstruciuneafals(F),sevaexecutan continuare instruciunea E2. DaccmpurileE1siE2 suntvide,execuiasecontinucuurmtoareainstruciune din MP. E1iE2potfietichetealeunorinstruciunidinMP,saupotfiunadintre instruciunile T i F. Algoritmul MAP este urmatorul: ISI, ISO,ISt,IMP0 repeta daca MP(IMP)=A atunci *A altfel *V

Instruciunea V: k=1 daca MP(IMP+1)=SI(ISI) atunci ISIISI+1 SO(ISO)MP(IMP+1) ISOISO+1 K1IMP+2 altfel K1IMP+3 Continuare instruciunea V: repeta pana cand k=0 daca MP(K1)=blankatunci IMP=IMP+4 ; k=0 altfel daca MP(K1) =T atunci*T altfel daca MP(K1)=F atunci*F altfel IMP=MP(K1);k=0 Instruciunea A : ST(VS)=ISI,ISO,IMP VS=VS+3 IMPMP(IMP+1) Instruciunea F : daca VS=0 atunci *esec altfelIMP=ST(VS) ISO=ST(VS) ISI=ST(VS) K1=IMP+3

VS=VS-3 Instruciunea T : daca VS != 0 atunciIMP=ST(VS) VS=VS-3 SO(ISO)=MP(IMP+1) ISO=ISO+1 K1=IMP+2 altfel (daca VS=0) atunci daca SI(ISI-1) = atunci*succes altfel*eec Ex: Se consider gramatica: X Y Y Z+W Y Z*W Y Z Z -W Z W W a W (Y) Scriei programul de analiz pentru maina de analiz predictiv. Analizai propoziia: a+(-a) +*-a() XYYY YZ+W Z*W Z Z+W Z*W Z Z+W Z*W Z Z-WWW Wa(Y) 0X:A(Y) , , F 4 :V(),T, F 8Y:A(Z),, F 12 :V(+),Y1, 16 :V(-),Y1, T 20 Y1:A(W), T , F 24 Z:V(-), , 28 :A(W), T, F 32W:V(a) , T, 36 :V( ( ),, F 40 :A(Y) ,, F 44 :V( ) ), T , F SI ISI ISO IMP SO STa+(-a)$0 0 0 -a+(-a)$0 0 0 - (0,0,0)a+(-a)$0 0 8 - (0,0,0)(0,0,8)a+(-a)$0 0 24 - (0,0,0)(0,0,8)a+(-a)$0 0 28 - (0,0,0)(0,0,8)(0,0,28)a+(-a)$0 0 32 - (0,0,0)(0,0,8)(0,0,28)a+(-a)$1 2 28 aw (0,0,0)(0,0,8)a+(-a)$1 3 8 awz (0,0,0)a+(-a)$1 3 12 awz (0,0,0)SI ISI ISO IMP SO STa+(-a)$2 4 20 awz+ (0,0,0)a+(-a)$2 4 32 awz+ (0,0,0)(2,2,20)a+(-a)$2 4 36 awz+ (0,0,0)(2,2,20)a+(-a)$3 5 40 awz+( (0,0,0)(2,2,20)a+(-a)$3 5 8 awz+( (0,0,0)(2,2,20)(3,3,40)a+(-a)$3 5 24 awz+( (0,0,0)(2,2,20)(3,3,40)(3,3,8)a+(-a)$4 6 28 awz+(- (0,0,0)(2,2,20)(3,3,40)(3,3,8)a+(-a)$4 6 32 awz+(-(0,0,0)(2,2,20)(3,3,40)(3,3,8)(4,4,28)a+(-a)$5 8 28 awz+(-aw (0,0,0)(2,2,20)(3,3,40)(3,3,8)SI ISI ISO IMP SO STa+(-a)$5 9 8 awz+(-awz (0,0,0)(2,2,20)(3,3,40)a+(-a)$5 9 12 awz+(-awz (0,0,0)(2,2,20)(3,3,40)a+(-a)$5 9 16 awz+(-awz (0,0,0)(2,2,20)(3,3,40)a+(-a)$5 10 40 awz+(-awzy (0,0,0)(2,2,20)a+(-a)$6 11 20 awz+(-awzy) (0,0,0)a+(-a)$6 12 0 awz+(-awzy)w -a+(-a)$6 13 4 awz+(-awzy)wy - Analiza LL(k) este un tip de analiz sintactic descendent careanalizeazintrareadelastngaladreapta(Leftto right)iconstruieteoderivarestngapentruaceasta (Leftmost derivation). De aici denumirea de LL. AnalizasenumeteLL(k)deoarecencadrulacesteia deciziadeafolosioanumitproduciepentruaexpanda unneterminalseiadupinspectareanavansaunui numr de k simboluri (atomi lexicali) din irul de intrare. n consecin, analiza nu folosete reveniri (backtracking). DacpentruoanumitgramaticgeneratoareGsepoate definiunanalizatorLL(k),atuncigramaticasenumete gramaticLL(k).Limbajuldefinitprintr-oastfelde gramatic se numete limbaj LL(k). CelemairspnditesuntgramaticileLL(1):analizatorul trebuie s inspecteze doar urmtorul simbol (atom lexical) din irul de intrare pentru a putea lua deciziile de analiz. Fie gramatica: 1.1 S->aSAc 1.2 S-> 2.1 A->bA 2.1 A-> aabcc (q, 0, S) (q, 0, aSAc) (q, 1, SAc) (q, 1, aSAcAc) (q, 2, SAcAc) (q, 2, AcAc) (q, 2, bAcAc) (q, 3, AcAc) (q, 3, cAc) (q, 4, Ac) (q, 4, c) (q, 5, ) abC S1.1 sau 1.21.1 sau 1.21.1 sau 1.2 A2.1 sau 2.22.1 sau 2.22.1 sau 2.2 Pentru a putea defini un analizator LL(1) pentru o anumit gramaticgeneratoareG,aceastatrebuiesfieo gramatic LL(1). Condiiilenecesareisuficientepentrucaogramatic independent de context s fie o gramatic LL(1) sunt: AeVN , A o1| o2| o3| on 1. FIRST+ (oi) FIRST+ (oj) =C , i = j 2. FOLLOW+ (A) FIRST+ (oj) = C, i pentru care oi * i j FIRST+(oi )={ aeE | oi * a } Dacoi *,atuncitrebuiesinemcontdeceeace urmeaz dup A. FOLLOW+(A)={ a eE | S * xAY; aeFIRST+ (Y),x eE *} ncazulmetodeiLL1seanalizeaznavansunsingur atom lexical. n gramaticile LL1 nu este permis recursivitatea stnga. Demonstratie: Presupunem A o1| o2| o3| on . Presupunem existena recursivitii stnga. o1 * A| atunci A * o1* A| * o2 | FIRST+ (o1) _ FIRST+ (A) _FIRST+ (o2) =C Daca o2 = FIRST+ (|) c FIRST+ (o2 |) c FIRST+ (o1) FIRST+ (|) c FOLLOW(A) FIRST+ (o1) FOLLOW(A)=C Deci, dac gramatica folosete recursivitate stnga pentru definirea produciilor, ea nu ndeplinete condiiile necesare i suficiente pentru a fi o gramatic LL1 i deci nici nu poate fi construit pentru ea un analizator LL1. Fie gramatica: E E + T | T T T - F | F F a | (E) Gramaticafoloseterecursivitatestnga;caurmare,trebuieso modificm: 1. E TE16. T1 2. E1 +TE1 7. F (E) 3. E1 8. F a 4. T FT1 5. T1 -FT1 Calculm mulimile: D1 = FIRST+ (TE1) = FIRST+ (F) = { ( , a } D2 = FIRST+ (+TE1) = { +} D3 = FOLLOW+ (E1) = FOLLOW+ (E) = { ) } D4 = FIRST+ (FT1) = FIRST+ (F) = { ( , a } D5 = FIRST+ (*FT1) = { - } D6 = FOLLOW+ (T1) = FOLLOW+ (T) = FIRST+ (E1)FOLLOW+ (E) D6 = { + }{ ) }= { +, ) } D7 = FIRST+ ( (E) ) = { ( } D8 = FIRST+ ( a ) = { a } Verificm condiiile pentru ca gramatica s fie o gramatic LL1: D2D3 = C D5D6 = C D7D8 = C Rezult c gramatica este o gramatic LL1. PebazamulimilorFIRSTiFOLLOWcalculate,segenereaz tabela de analiz sintactic. Pe baza tabelei de analiz sintactic se poate implementa un analizor sintactic determinist cu structura: wx SI a Automat finit ISO SO VS ISI Pe baza mulimilor FIRST i FOLLOW calculate, segenereaztabeladeanalizsintactic astfel: Simbolul$reprezintterminatoruldeir pentru irul de intrare (SI). VN

E { $ } E { $ } P-popscoateunsimboldinstivi nainteaz n SI A - accept propoziia este corect E - error propoziia este incorect Rn-replacesenlocuieteVScu partea dreapt a produciei n, dup care se scrie n n SO Algoritmul de construcie al tabelei de analiz sintactic este: Pentru fiecare regul Rn: A-> Instruciune repetitiv (actualize linie neterminal A) PentrufiecareterminaldinFIRST+(),completeazcelula din tabel corepunztoare coloanei terminalului cu R n Dac=>*,atuncipentrufiecareterminaldin FOLLOW+(A),completeazceluladintabel corespunztoare coloanei terminalului respectiv cu R n Sfrit instruciune repetitiv Pentruexemplulanterior,tabeladeanaliz sintactic este (celulele goale reprezint E): a()+ - $ E11 E1323 T44 T16656 F87 aP (P )P +P - P $A Algoritm sf false repeta pana cand sf = true daca St(VS) eE i St(VS)=SI(ISI)atuncipop i ISI = ISI + 1 sau St(VS) eE i St(VS) =! SI(ISI)atunci error sau St(VS)=AeVNatunci replace n i SO(ISO) = n i ISO = ISO + 1 sau St(VS) = SI(ISI) = $ atunci accept sf truealtfelerror sf true Modelulmatematicalacestuitipdeanalizrmne automatul finit cu stiv, aa cum a fost definit pe slide-ul al9-lea,lacareseadaugunelementnplus,ianume irul de ieire. Funcia de tranziie: f(q, a, a) = {(q, )} pop f(q, $, $) = {(a, )} accept f(q, b, A) = {(q, o)}replace A bo conformtabelei de analiz sintactic f(q, i, x) = {(e, )}error Configuraia automatului la un moment dat este dat de: (S, x, , y) S = starea automatului x = irul de intrare rmas de analizat = stiva y = irul de iesire, format din indicii produciilor utilizate n derivri Stri posibile: (q, ax, a , y) (q, x, , y) pop (q, ax, A, y) (q, x, o, yi) replace i, conform tabelei de analiz (q, $, $, y) (a, , , y) accept (q, x, i, y) (e, , , y)error Ex:a -a + a (q,a-a+a$, E$, ) r (q,a-a+a$ ,TE1$ ,1) rr(q,a-a+a$, FT1E1$,14) r (q,a-a+a$,aT1E1$,148) pp(q,-a+a$,T1E1$,148) r (q,-a+a$ ,-FT1E1$,1485) pp(q,a+a$,FT1E1$,1485) r (q,a+a$,aT1E1$,14858)pp (q,+a$,aT1E1$,14858)r (q,+a$,E1$,148586) rr(q,+a$,+TE1$,1485862) p (q,a$,TE1$,1485862) rr(q,a$,FT1E1$,14858624) r (q,a$,aT1E1$,148586248) pp(q,$,T1E1$,148586248) r(q,$,E1$,1485862486) rr (q,$,$,14858624863) a (a,$,$,14858624863) -> if then () I1 I1-> else I1-> -> repeat until -> := -> E1 E1-> < E1-> i F1 F1-> () F1-> -> i L1 L1 -> , L1 -> FIRST+{ if } FIRST+{ else } FOLLOW+ { ) until $} FIRST+{ repeat } FIRST+{ i } FIRST+{ i } FIRST+{ < } FIRST+ { < F, deci fallow de F este Fallow de E1 { := <