1 COMPILATORI: Traducere bazată pe sintaxă de Jana Dvořáková

compilatoare

2 Ce este traducerea bazată pe sintaxă? Întregul compilator este controlat de procesul de analiză Traducere bazată pe sintaxă = legarea analizei cu următoarele faze de compilare analizând traducerea bazată pe sintaxă a fazei următoare Acțiunile sunt atribuite regulilor gramaticale Generarea codului Salvarea informațiilor într-un tabel de simboluri Generarea mesajelor de eroare Verificarea coerenței tipului .ad mai mult Notare 1 Definiție bazată pe sintaxă Notare abstractă 2 Schemă de traducere Similar definițiilor bazate pe sintaxă, dar mai multe detalii de implementare (ordinea acțiunilor)

3 Execuția acțiunilor 1 În timpul analizei O tranziție, utilizată în compilatoare Fără construirea explicită a arborelui de derivare Posibil pentru tipuri speciale de definiții controlate de sintaxă - De ex. Definițiile atributelor L includ practic toate definițiile bazate pe sintaxă care pot fi implementate fără construirea explicită a arborelui de derivare.

4 Definiție bazată pe sintaxă (SRD) Specificație abstractă a unei traduceri bazate pe sintaxă Este creată prin extinderea gramaticii CF a limbii de intrare cu 1 Atribute atribuite simbolurilor gramaticale Xx = atributul x al simbolului X plasează în memorie. 2 Reguli semantice atribuite regulilor gramaticale Bb: = f (C 1.c 1. C kc k) Folosit pentru a calcula atributele simbolului în cadrul unei reguli gramaticale Poate conține funcții cu efect secundar (de exemplu, valoarea de ieșire, modificarea valorii unei variabile globale) SRD fără funcții de efect secundar = gramatica atributului

5 Sus în arborele de derivare = înregistrare cu câmpuri atribut simbol atribut 1 atribut 2 Atribute Simbolul gramatical se află în primul câmp al înregistrării și este un steag în atribut Atributele sunt stocate în alte câmpuri Tipuri de atribute 1 Atribute sintetizate Valorile sunt calculat în funcție de valorile atributului copil utilizate 2 Atribute moștenite Valorile sunt calculate în funcție de valorile atributelor părinților și fraților Potrivit pentru exprimarea dependenței structurilor de contextul în care sunt situate Dacă Bb: = f (C 1 .c 1. C kc k) spunem că Bb este dependent de C 1.c 1. C kc k Arborele de derivare cu valori de atribut calculate se numește arborele de derivare adnotat. Terminalele au doar atribute sintetizate și nu. simbolul gramatical are numai atribute ereditare

6 Definiție bazată pe sintaxă Exemplul 1 - calculator Regula gramatică Regula semantică Funcția n n print (e.val) cu efect secundar EE 1 + T E.val: = E 1.val + T.val ET E.val: = T. val TT 1 F T.val: = T 1.val F.val TF T.val: = F.val F (E) F.val: = E.val F cifră F.val: = cifră. analizorul lexical trimis X.val este un atribut sintetizat pentru X cu valoare SRD întreagă numai cu atribute sintetizate se numește definiție a atributului S și poate fi întotdeauna evaluat pe arborele de derivare prin tranziție de jos în sus

7 Definiție bazată pe sintaxă Exemplul 2 - declarații Regula gramaticală D T L; T int T real LL 1, id L id Regula semantică L.in: = T. tip T. tip: = număr întreg T. tip: = real L 1.in: = L.în tip add (id. Intrare, L. în ) addtype (id.entry, L.in) L.in este un atribut moștenit T. type este un atribut sintetizat Nu poate fi evaluat pur și simplu ca definiții ale atributelor S

8 Afișează dependențe între atribute Grafic de dependență Grafic orientat D = (V, E) V - set de vârfuri, atribute ale simbolurilor gramaticale E - set de margini, Xx Yy E dacă Yy este dependent de Xx pentru fiecare vârf n din arborele de derivare la pentru fiecare atribut și simbol gramatic vn pentru a crea un vârf pentru a; pentru fiecare vârf din arborele de derivare la pentru fiecare regulă semantică b: = f (c 1. ck) asociată cu regula vn la pentru i: = 1 la k pentru a adăuga o margine zci la b Clasificare topologică D Aranjamentul vârfurilor m 1 .mk, astfel încât să rețină: Dacă există o margine mimj, atunci o am înainte de m j. Obținem o ordine validă de evaluare a atributelor (dacă D nu are un ciclu)

9 Metode de evaluare a atributelor 1 Metode de derivare a arborelui Arborele de derivare este construit în mod explicit, se găsește un grafic de dependență și se obține ordinea topologică a ordinii de evaluare a atributelor în timpul compilării 2 Metode de analiză a regulilor Ordinea de evaluare este determinată de analiza statică a regulilor semantice la compilator timp de construcție 3 Metode „neglijent” * Ordinea evaluării este determinată indiferent de regulile semantice. Dacă traducerea se efectuează în timpul analizei, ordinea este determinată de metoda de analiză la momentul construcției compilatorului.

10 Arborele sintactic Arborele de derivare simplificat Operatorii și cuvintele cheie sunt vârfuri interne Ramurile derivate de regulile lanțului sunt reduse Utilizate ca reprezentare temporară a unui program compilat sau a părților sale Traducerea bazată pe sintaxă se poate baza pe un arbore de derivare sau un arbore de sintaxă. la nodurile arborelui și este adnotat Avantajele arborelui de sintaxă Gramatica potrivită pentru analiză nu reprezintă întotdeauna structura ierarhică naturală a limbajului de programare de intrare Metoda de analiză restricționează ordinea de acces la nodurile arborelui de derivare și acest ordin nu este întotdeauna potrivit pentru traducere

11 Funcții pentru construcția vârfurilor: Arborele sintaxei pentru expresii 1 mknode (op, stânga, dreapta) 2 mkleaf (id, intrare) Returnează un pointer la un vârf construit de 3 mkleaf (num, val) Vertexurile pentru operatori sunt implementate ca înregistrări cu mai multe câmpuri operator pointer to operand 1 pointer to operand 2 Vertexuri pentru identificatori și constante numerice Operatorul este o etichetă de vârf La traducere, există și mai multe câmpuri în înregistrare pentru atributele id num 4 pointer la tabelul de simboluri

12 Arborele de sintaxă pentru expresii Definiție bazată pe sintaxă Regula gramaticală EE 1 + TEE 1 TETTT 1 FT (E) T id T num Reglă semantică E.nptr: = mknode (+, E 1.nptr, T.nptr) E.nptr: = mknode (, E 1.nptr, T.nptr) E.nptr: = T.nptr T.nptr: = mknode (, T 1.nptr, F.nptr) T.nptr: = E.nptr T.nptr: = mkleaf (id, id.entry) T.nptr: = mkleaf (num, num.val) X.nptr este un atribut sintetizat pentru X și conține un pointer către vârful corespunzător

13 Arborele sintactic vs. DAG Subexpresiile obișnuite sunt reprezentate de un singur subarborod La adăugarea unui vârf nou, se verifică dacă nu există un vârf identic Expresie: a + a (bc) + (bc) d * + * a * - d * da - bca - bcbc

14 Implementarea SRD pentru analiză Poate fi dificil să construim un compilator automat pentru orice SRD Avem clase mari pentru care este simplu 1 Definiții ale atributelor S Conțin doar atribute sintetizate 2 Definiții ale atributelor L Conțin atât atribute sintetizate, cât și moștenite Anumite constrângeri pentru calcul atribute moștenite Include toate SRD-urile care sunt implementate fără construcție explicită a arborelui de derivare Definiții ale atributelor S Definiții ale atributelor L Ambele clase pot fi implementate în analiza de sus în jos și de jos în sus

15 Definirea atributului S Implementare pentru analiza de jos în sus (1) Valorile atributelor sunt stocate în câmpuri speciale din stiva analizatorului și sunt asociate cu simboluri gramaticale (sau stări). Dacă simbolul nu are un atribut, valoarea este nedefinit Stiva cu spațiu pentru un atribut: stare ZYX val Zz Yy Xx sus Implementare - pereche de câmpuri 1. starea conține indicatori (indici) la tabelul de analiză LR (1) - Simbolul gramatical este în starea implicit, nu este necesar să ne amintim - Pentru simplitate afirmăm simbolul în loc de starea corespunzătoare 2. val conține valori ale atributelor - val [i] = valoarea atributului pentru simbolul din starea [i] Valorile atributelor sintetizate sunt întotdeauna calculate înainte de reducerea din atributele stocate în stivă (= atribute simbol în partea dreaptă a regulii)

16 Definiția atributului S Implementare pentru analiza de jos în sus (2) Exemplu: A XYZ, Aa = f (Xx, Yy, Zz) stare val stare val Z Zz top Y Yy X Xx calcul Aa reducere A -> XYZ A Aa top - Zz: = val [top] - Yy: = val [top 1] - Xx: = val [top 2] - top: = top 2 - val [top]: = Aa

17 Regula gramaticală Definiția atributului S Implementarea pentru analiza de jos în sus (3) fragment de cod LE n print (val [sus]) EE 1 + T val [ntop]: = val [sus 2] + val [sus] ETTT 1 F val [ntop]: = val [top 2] val [top] TFF (E) val [ntop]: = val [top 1] F cifre Fragmentele de cod sunt asociate cu reduceri ale parserului LR Le obținem din regulile semantice prin înlocuirea atribute cu poziții în câmpul val Executat chiar înainte de reducere Variabilele sus și ntop sus este vârful curent al stivei, ntop este noul vârf al stivei Procedura de reducere conform regulii A β, unde β = r 1 ntop este setat la vârf r Se efectuează fragmentul de cod, iar reducerea 3 este setată la ntop

18 Definiția atributului L O definiție bazată pe sintaxă este un atribut L dacă pentru orice regulă AX 1, X 2. X n susține că fiecare atribut moștenit al unui simbol din partea dreaptă a lui X j depinde doar de 1 atribute ale simbolurilor X 1, X 2. X j 1, care se află în regula din stânga lui X ja 2 atribute ereditare ale simbolului A. SRD, care nu este un atribut L Regulă gramaticală: A LM A QR Regulă semantică: Li: = l (ai) Mi: = m (ls) Ca: = f (Ms) Ri: = r (ai) Qi: = q (rs) Ca: = f (Qs) Notă: Fiecare definiție a atributului S este, de asemenea, o Atributul L nu se potrivește cu definiția

19 Definiția atributului L Evaluarea atributelor Atributele pot fi evaluate prin parcurgerea arborelui în profunzime (primul-primul ordin) procedura dfvisit (n: nod); începeți pentru fiecare dietă un m de vârf n zl ava la dreapta pentru a începe să evaluați atributele moștenite ale vârfului m; dfvisit (m) capăt; evaluați atributele sintetizate ale vârfului și capătului Mod natural de parcurgere a arborelui de derivare Implementarea definiției atributelor L în analiza 1 Analiza de sus în jos Toate SRD-urile bazate pe gramaticile LL (1) 2 Analiza de jos în sus Toate SRD-urile bazate pe gramaticile LL (1), mare parte SRD bazat pe gramaticile LR (1)

20 Scheme de traducere Un alt mod de a specifica traducerea bazată pe sintaxă Mai specifică decât SRD Precizează, de asemenea, ordinea în care sunt evaluate atributele Acțiunile semantice sunt închise în <> și inserate între simbolurile din dreapta ale regulilor Schema de traducere a regulilor care traduce adaos și scădere infix expresii la expresii echivalente ETR addfix TR 1 ε T num addop.lexeme poate fi + sau - Gramatică creată prin eliminarea recursiunii din stânga din celebra gramatică pentru expresii

21 Constrângeri pentru scheme de traducere Acțiunea nu trebuie să se refere la un atribut necalculat Scheme de traducere pentru definițiile atributelor S Soluție simplă - acțiunile sunt plasate la sfârșitul regulilor Scheme de traducere pentru definițiile atributelor L 1 Atributul moștenit al unui simbol din partea dreaptă a unei reguli trebuie calculată în acțiunea din stânga.el. 2 Acțiunea nu trebuie să se refere la atributul sintetizat al simbolului din dreapta. 3 Atributul nonterminal sintetizat din partea stângă a regulii poate fi calculat numai după ce au fost calculate toate atributele de care depinde. Acțiunea corespunzătoare pentru calculul său este situată de obicei la sfârșitul părții din dreapta a regulii. Exemplu schemă de traducere „proastă” S A 1 A 2 A

22 Definiția atributului L Implementarea în analiza predictivă Implementarea este posibilă numai pentru definițiile atributelor L (scheme de traducere *) bazate pe gramaticile LL (1), care, printre altele, nu pot conține recursivitate la stânga Există o metodă de eliminare directă a recursivității la stânga din schemele de traducere Extinderea algoritmului pentru eliminarea recursivității la stânga din gramatica CF Poate fi aplicată schemelor de traducere cu atribute sintetizate Dacă avem deja o schemă de traducere bazată pe gramatica LL (1), există un algoritm pentru construirea unei sintaxe predictive compilator

23 Eliminarea recursivității din stânga din traducere. schemă de traducere de intrare: A A 1 Y A X După eliminarea recursiunii din stânga din gramatica CF obținem o nouă gramatică: A X R R Y R ε După rescrierea acțiunilor semantice obținem translul rezultat. schema: A X R R Y R 1 R ε

25 Intrare de proiectare predictivă a compilatorului. Schemă de traducere bazată pe sintaxă bazată pe o gramatică adecvată analizei predictive. Ieșire. Cod pentru compilatorul bazat pe sintaxă predictivă. 1 Pentru fiecare nonterminal A, creați o funcție care are un parametru formal pentru fiecare atribut moștenit A și returnează valorile non-terminalelor sintetizate A. Funcția pentru A are o variabilă locală pentru fiecare atribut al fiecărui simbol care apare în regulă pentru A. 2 Codul pentru nonterminal A decide ce regulă să se aplice în conformitate cu simbolul curent de intrare. 3 Codul asociat fiecărei reguli efectuează următoarele acțiuni. (i) Pentru simbolul X cu atributul sintetizat x, stocați valoarea lui x în variabila declarată pentru X.x. Apelați apoi procedura de potrivire (x) și derulați la intrare. (ii) Pentru un non-terminal B, generați o atribuire de forma c: = B (b 1, b 2. bk), unde b 1, b 2. bk sunt variabile pentru atributele moștenite ale non-terminalului B, c este o variabilă pentru atributul net sintetizat. B și B este un apel funcțional pentru rețea. B. (iii) Pentru acțiune, copiați codul direct în parser, înlocuind fiecare referință de atribut cu o variabilă asociată.

26 Traducere bazată pe sintaxă în analiză Sumar 1 Implementarea definițiilor atributelor S Am avut un algoritm de analiză de jos în sus Pot fi implementate și în analiză de sus în jos - Eliminarea recursivității stânga din schema de traducere și construirea unui compilator predictiv 2 Implementare al definițiilor atributului L algoritmul de analiză de sus în jos Poate fi implementat și pentru analiza de jos în sus - Extensie de algoritm pentru procesarea definițiilor atributului S În ambele cazuri, setul de gramatică CF pe care se bazează SRP este limitat - De jos în sus compilatorul este mai puternic