Linguaggi Formali e Compilazione: Frontend

LFC

Il front-end di uncompilatoreArchitettura del front-end

Symbol table

Traduzione guidata dallasintassi

Generazione delthree-address codeLinguaggi formali e compilazione

Corso di Laurea in Informatica

A.A. 2008/2009

LFC


Symbol table


Generazione delthree-address code

Linguaggi formali e compilazione

Il front-end di un compilatoreArchitettura del front-endSymbol tableTraduzione guidata dalla sintassiGenerazione del three-address code

LFC


Symbol table



Componenti del front-end

◮ Il front-end di un compilatore (cioè la parte chetermina con la creazione di una rappresentazioneintermedia del programma) è costituita dai seguentimoduli:

◮ analizzatore lessicale;◮ parser;◮ symbol table;◮ generatore di codice intermedio.

◮ Per ragioni di tempo non ci potremo occupare, inquesto corso, della gestione degli errori.

LFC


Symbol table



Il modello di front-end

◮ La seguente figura illustra un tipico schema diorganizzazione del front-end di un compilatore (trattoda Aho, Lam, Sethi, Ullman (2007)).

Analizzatorelessicale

Parser

Gestore dellasymbol table

Generatore dicodice intermedio

Token

Programmasorgente

Alberosintatt ico

three-addreesscode

Richiestatoken

LFC


Symbol table



Analizzatore lessicale

◮ L’analizzatore lessicale ha il fondamentale ruolo dileggere la sequenza di caratteri che forma l’input filee inviare al parser una sequenza di token, oggettiastratti che coincidono essenzialmente con i simboliterminali del linguaggio (ma vedremo subito dopouna definizione precisa).

◮ Ci sono però altri compiti che deve svolgerel’analizzatore lessicale:

◮ riconoscere e “filtrare” commenti, spazi e altricaratteri di separazione;

◮ associare gli eventuali errori trovati da altri moduli delcompilatore (in particolare dal parser) alle posizioni(righe di codice) dove tali errori si sono verificati alloscopo di emettere appropriati messaggi diagnostici;

◮ procedere all’eventuale espansione delle macro (se ilcompilatore le prevede).

LFC


Symbol table



Interazione parser-lexical analyzer

◮ L’analizzatore lessicale è normalmente programmatocome “routine” del parser.

◮ Quando il parser deve leggere il prossimo simbolo diinput (si ricordino gli esempi di parser, top down obottom up indifferentemente, visti nel gruppo di lucidirelativi al parsing di linguaggi liberi) esegue in realtàuna chiamata all’analizzatore lessicale;

◮ quest’ultimo si attiva leggendo la “prossima”porzione di input fino a quando non riconosce unsimbolo terminale della grammatica, che vienerestituito al parser;

◮ ciò che viene propriamente restituito è un tokenname, una delle due componenti che costituiscono iltoken vero e proprio.

LFC


Symbol table



Token

◮ Un token è un oggetto astratto caratterizzato da dueattributi, un token name (obbligatorio) e un valoreopzionale.

◮ Ecco alcuni esempi di sequenze di caratteririconosciuti come token da un compilatore C++:

◮ “0.314E+1 ”, cui corrisponde la coppia (token) in cuiil nome è number e il valore è il numero razionale3.14, opportunamente rappresentato;

◮ “x1 ”, cui corrisponde un token in cui il nome è id e ilcui valore è, a sua volta, un insieme di informazionielementari (la stringa di caratteri che formal’identificatore, il suo tipo, il punto del programmadove è stato definito);

◮ “else”, cui corrisponde il solo token name else.

LFC


Symbol table



Token name

◮ Il nome del token serve principalmente al parser, inquanto sono propriamente i token name checoincidono con i simboli terminali della grammatica.

◮ Il valore dei token è invece (in prima istanza) nonrilevante dal punto di vista della correttezza sintatticadel programma.

◮ Ad esempio, le frasi “x<10 ” e “pippo!=35 ” sono deltutto equivalenti e riconducibili alla frase generica incui il valore di un identificatore è confrontato con unnumero.

◮ Una tale frase può quindi essere astrattamentedescritta come “id comparison number”, doveabbiamo utilizzato il nome comparison per il tokenche descrive gli operatori relazionali.

LFC


Symbol table



Token value

◮ Il valore di un token gioca il ruolo principale nellatraduzione del codice.

◮ Con riferimento agli esempi del lucido precedente:◮ di un identificatore è importante sapere (tra gli altri) il

tipo, perché da questo dipende (in particolare) laquantità di memoria allocare;

◮ di un operatore di confronto è necessario sapereesattamente di quale confronto si tratta, per poterpredisporre il test e l’eventuale istruzione di saltoopportuna;

◮ di una costante numerica è necessario sapere ilvalore per effettuare l’inizializzazione corretta.

LFC


Symbol table



Token (continua)

◮ Il progettista del linguaggio stabilisce quali debbanoessere considerati i simboli terminali del linguaggi, equindi i token.

◮ Naturalmente, a tali simboli potranno corrispondere(in generale) molte stringhe alfanumeriche nel codicesorgente (si pensi ai token che descrivono numeri oidentificatori).

◮ Il progettista deve quindi stabilire esattamente anchela mappatura fra stringhe e token name/terminali dellinguaggio.

◮ Tale mappatura viene tipicamente descritta, comegià sappiamo, mediante espressioni regolari.

LFC


Symbol table



Pattern, lessemi e terminali

◮ Una descrizione ben formalizzata di quanto appenaricordato può essere fatta utilizzando i concetti dilessema e pattern.

◮ Un pattern è una descrizione (formale o informale,ma tipicamente esprimibile mediante espressioniregolari) delle stringhe che devono esserericonosciute (dall’analizzatore lessicale) comeistanze di un determinato simbolo terminale.

◮ Le stringhe stesse sono dette lessemi.

LFC


Symbol table



Pattern, lessemi e terminali (continua)

◮ La seguente tabella illustra, mediante alcuni esempi,i concetti che stiamo analizzando.

Token name Pattern Esempio di lessemaid letter(letter | digit)∗ pippo1number [+ | -]nzd digit∗[.]digit∗ -3.14comparison <, >, <=, >=, =, != <literal “[:alpha:]” “Pi greco ”if if ifwhile while while

Si noti che, per ragioni di spazio, il pattern che descrive iltoken number non prevede la notazione scientifica.

LFC


Symbol table





LFC


Symbol table



Symbol table◮ Come evidenziato dalla struttura del front-end,

l’analizzatore lessicale presenta al parser unafunzione, get-next-token() , che il parser invocaquando deve leggere il prossimo simbolo terminaledella grammatica.

◮ Il risultato esplicito della get-next-token() è ilnome del prossimo token.

◮ Nei casi in cui è significativo anche il valore (fannoeccezione le keyword, simboli di separazione come ilpunto e virgola e gli operatori), l’analizzatorelessicale restituisce anche (tipicamente) unpuntatore alla symbol table dove è statomemorizzato il valore stesso.

◮ In pratica, la funzione get-next-token() puòrestituire una coppia 〈nome, valore〉, oppure (comenel caso di Lex/Yacc) il valore viene restituitoattraverso una variabile globale.

LFC


Symbol table



Esempio

◮ Nel caso del seguente frammento di programma C++

while (i<10) {i=i+1;

}

l’analizzatore lessicale restituisce al parser laseguente sequenza di token:

〈while〉〈id, pointer〉〈leftpar〉〈assign_op〉〈id, pointer〉〈id, pointer〉〈comparison, pointer〉〈plus_op〉〈number, pointer〉〈number, pointer〉〈rightpar〉〈semicolon〉〈leftbrace〉〈rightbrace〉

LFC


Symbol table



Symbol table (continua)

◮ Come già detto, le informazioni raccolte nella symboltable, relative ai token ai quali è associato un valore,sono fondamentali nella generazione del codice, manon solo.

◮ Mediante tali informazioni il front-end può anchecompletare l’analisi sintattica del programma e,dicendo questo, intendiamo procedere a chiarire unaspetto che potrebbe essere rimasto oscuro,

◮ In precedenza abbiamo affermato che, dal punto divista sintattico, frasi come i < 10 o j < 10 sono deltutto equivalenti,

◮ Questo non è del tutto vero e non solo perché esse(in termini di codice generato) significano cosediverse.

LFC


Symbol table



Symbol table (continua)◮ Infatti, in molti linguaggio di programmazione

moderni, una variabile deve essere dichiarata primadi poter essere utilizzata.

◮ Se, con riferimento all’esempio appena fatto,l’identificatore i fosse stato dichiarato mentre j no,allora la presenza della seconda frase genererebbeun errore.

◮ Usare una variabile non definita è un erroresintattico? Si e no.

◮ Teoricamente sarebbe possibile inserire nellagrammatica il vincolo che ogni variabile deve esseredichiarata prima dell’uso.

◮ Questo però richiederebbe l’uso di produzioni (equindi di grammatiche) non context-free, per le qualinon è neppure garantita l’esistenza di algoritmi diparsing.

LFC


Symbol table



Symbol table (continua)◮ La soluzione adottata è quindi di non inserire tali

regole nella grammatica ma di controllare ilsoddisfacimento dei vincoli in altro modo, cioèproprio mediante l’uso della symbol-table.

◮ Più precisamente, quando il parser incontra unidentificatore nel contesto, poniamo, diun’espressione, va a verificare nella symbol table setale identificatore è già presente (ed eventualmentecon quale tipo è stato dichiarato).

◮ Se non è presente (ovvero se il tipo non è quello“giusto”) segnala una condizione di errore, checonsidereremo di natura semantica.

◮ Un altro esempio di vincolo non facilmentedescrivibile con produzioni libere è quello dellaconcordanza fra numero di parametri formali di unaprocedura e argomenti ad essa passati nelle variechiamate.

LFC


Symbol table




◮ Precisiamo bene come tali controlli vengono svoltidal front-end usando la symbol table, che può esserestrutturata in modo tale da soddisfare la più ampiaesigenza rappresentata dalla implementazione delleregole di ambiente o di visibilità dei simboli (ininglese scoping rule).

◮ Ricordiamo che lo scope di una variabile (e delladichiarazione che tale variabile introduce) è laporzione di programma in cui tale variabile è visibile(e dunque utilizzabile).

◮ Lo stesso identificare (un caso comune è i ) puòessere definito più volte in un programma, ma adesso saranno associati ambienti diversi.

LFC


Symbol table




◮ Nei moderni linguaggi di programmazione l’ambientedi una variabile è “quasi sempre” determinabile inmodo statico, cioè guardando il testo del programma(se escludiamo alcuni casi ricercati).

◮ In particolare, le regole di visibilità degli identificatoririflettono la struttura di annidamento dei blocchi diprogramma (incluse le procedure e le classi, sepreviste).

◮ Come detto, in quaesto caso si parla di static (olexical) scoping.

◮ Dal punto di vista del compilatore, la nozione diambiente può essere realizzata definendo una nuovasymbol table all’ingresso di ogni blocco diprogramma e “concatenando” le simbol table in unalista, in cui la testa è sempre l’ultima symbol tabledefinita.

LFC


Symbol table



Esempio

◮ Si consideri, come esempio, il seguente sempliceframmento di programma C++:

1. { int i,j;2. cin » i » j;3. { int i; float x;4. i=1;5. x=2.0 * j;6. cout « i « “: ” « x;7. }8. cout « i « “: ” « j;9. }

LFC


Symbol table



Esempio (continua)◮ Chiameremo ambiente la lista di symbol table.◮ All’ingresso del blocco più esterno viene creata una

symbol table S1 (essenzialmente un dizionario) chediviene la testa di ambiente.

◮ Ogni volta che viene incontrata una definizione,l’identificatore viene inserito nella symbol table allatesta di ambiente.

◮ Ne consegue che gli identificatori i e j di riga 1vengono inseriti in S1.

◮ All’ingresso del blocco interno (riga 3) viene creata(e inserita in testa ad ambiente) una seconda symboltable, S2, nella quale vengono poi inseriti gliidentificatori i e x di riga 3 (col loro tipo).

◮ All’uscita di ogni blocco, il puntatore alla testa diambiente viene fatto avanzare, con l’effetto direndere inaccessibile la symbol table di testa.

LFC


Symbol table



Esempio (continua)

◮ Quando nel programma si incontra un riferimento aduna variabile, l’identificatore relativo viene cercatonella lista ambiente, seguendo il naturale ordine.

◮ Ad esempio, il riferimento alla variabile i di riga 4viene risolto con un lookup alla symbol table di testa(S2), che contiene un’entry con chiave i .

◮ Si noti quindi che, nel blocco interno, la variabile idefinita alla riga 1 diviene inaccessibile.

◮ Il riferimento alla variabile j di riga 5 richiede inveceil lookup di due symbol table, nell’ordine in cui sonopresenti nella lista ambiente: S2 (search miss) ed S1

(search hit).

LFC


Symbol table




◮ Come già sottolineato, oltre alla implementazionedello scope (e alla verifica del soddisfacimento divincoli non facilmente esprimibili a livellogrammaticale), le symbol table mantengonoinformazioni fondamentali per la generazione delcodice

◮ Ad esempio, la entry per un identificatore contiene:◮ la sequenza di caratteri che ne costituisce il lessema

(che può essere usata come chiave per l’accessoalla tabella);

◮ il tipo della variabile;◮ l’indirizzo di memoria della variabile.

LFC


Symbol table





LFC


Symbol table



Le due parti del compilatore

◮ Il passaggio dal codice sorgente ad un codicemacchina efficiente viene tipicamente spezzato indue parti.

◮ La prima parte, gestita dal front-end del compilatore,termina con la generazione di un opportuno codiceintermedio ed è chiaramente dominata dallecaratteristiche del linguaggio sorgente.

◮ La seconda parte, gestita dal back-end, è invecespecializzata ad ottenere un codice macchinaefficiente in funzione della particolare architettura.

◮ La suddivisione netta del progetto di un compilatorein front-end e back-end (la prima indipendentedall’architettura e la seconda indipendente dallinguaggio) ha, fra le altre proprietà, un notevoleimpatto in termini di economicità di progetto.

LFC


Symbol table



Rappresentazioni intermedie

◮ Le rappresentazioni intermedie più importanti sono isyntax tree e il cosiddetto three-address code.

◮ Per ora ci concentriamo sui syntax tree, posponendoalla sezione sulla generazione del codice intermediola definizione di three-address code.

◮ Un abstract syntax tree per un linguaggio L è unalbero in cui:

◮ i nodi interni rappresentano costrutti di L;◮ i figli di un nodo che rappresenta un costrutto C

rappresentano a loro volta le componenti significativedi C;

◮ le foglie sono “costrutti elementari” (nonulteriormente decomponibili) caratterizzati da unvalore lessicale (tipicamente un numero o unpuntatore alla symbol table).

LFC


Symbol table



Esempio

◮ Un abstract syntax tree per la frase id + id× id è+

×

〈id, ptr〉〈id, ptr〉

〈id, ptr〉

◮ Abstract syntax tree e parse tree sono oggetti diversi.E

T

F

id

×T

F

id

+E

T

F

id

LFC


Symbol table



Rappresentazioni intermedie

◮ Per alcuni semplici linguaggi interpretati, unarappresentazione finale basata su una struttura adalbero (da dare poi in input all’interprete) può esseresufficiente.

◮ Questo è il caso, ad esempio, della realizzazione diun semplice “desk calculator” (interattivo) cheaccetta in input formule che seguono la sintassiclassica (con operatori infissi).

◮ In questo caso, infatti, è semplice scrivere uninterprete per la formula rappresentata comeabstract syntax tree.

◮ In generale, tuttavia, i syntax tree costituiscono soloun passaggio intermedio verso al generazione dicodice intermedio (tipicamente il three-addresscode).

LFC


Symbol table



I vari passaggi in dettaglio

◮ Per chiarezza didattica, possiamo “in prima battuta”immaginare che tutte le strutture intermedie cheportano alla generazione del three-address codevengano effettivamente costruite.

◮ A partire dalla sequenza di token restituitadall’analizzatore sintattico, possiamo quindiimmaginare (per il momento) che il parser costruiscaesplicitamente tanto il parse tree quanto l’abstractsyntax tree delle stringhe “corrette”.

◮ In un compilatore reale, tuttavia, il parser emette ilthree-address code senza costruire “esplicitamente”il syntax tree ne’ il parse tree.

◮ In realtà, anche nell’ambito della nostra trattazionesemplificata vedremo come almeno la generazionedel parse tree sia (quasi sempre) evitabile.

LFC


Symbol table



Traduzione guidata dalla sintassi◮ La generazione dell’abstract syntax tree, il nostro

obiettivo attuale, può essere eseguita mediantel’applicazione di una tecnica nota come Traduzioneguidata dalla sintassi (in inglese Syntax-DirectedTranslation).

◮ In altre parole, l’output desiderato (un abstract syntaxtree) viene generato mediante un processo che èguidato dalla stessa grammatica e, in particolare,dalle sue produzioni.

◮ Tipicamente, quando viene applicata una produzione(nel parsing top-down) oppure viene effettuata unariduzione (nel parsing bottom-up) viene ancheeffettuata una qualche azione di costruzionedell’abstract syntax tree.

◮ La modalità specifica che vedremo per larealizzazione del processo di traduzione è quelladegli schemi di traduzione (syntax-directedtranslation scheme).

LFC


Symbol table



Syntax-directed translation scheme◮ Uno schema di traduzione prevede l’inserimento di

frammenti di codice nel corpo (parte destra) delleproduzioni.

◮ Per ogni produzione, il codice viene eseguito dalparser in un preciso momento che può essere prima,durante o dopo l’applicazione della produzionestessa.

◮ Negli esempi di costruzione del syntax tree chesvilupperemo le azioni saranno essenzialmenteoperazioni di costruzione di nodi e manipolazione dipuntatori.

◮ L’aspetto importante che dovremo chiarire è relativoal preciso ordine di esecuzione dei vari frammenti dicodice.

◮ Dobbiamo però preliminarmente descrivere quali dativengono manipolati dagli schemi di traduzione.

LFC


Symbol table



Attributi

◮ Un qualunque processo di calcolo richiede lamanipolazione di informazione, che deve esserememorizzata “da qalche parte”.

◮ Nel caso degli schemi di traduzione, l’informazionemanipolata è costituita da attributi associati ai simbolidella grammatica.

◮ Naturalmente abbiamo bisogno di una notazione perpoter fare riferimento a tale informazione.

◮ Se X è un simbolo della grammatica e a è il nome diun suo attributo, useremo dunque la scrittura X .a perindicare il valore dell’attributo a di X .

◮ Il valore di un attributo può essere di qualunquenatura: stringa, numero, albero, tabella, tipo di dato,ecc.

LFC


Symbol table



Attributi (continua)

◮ Si noti tuttavia che nel processo di derivazione di unastringa, (e quindi nel corrispondente parse tree) unsimbolo X della grammatica può apparire più volte.

◮ Dobbiamo quindi precisare che la scrittura X .a siapplica non tanto al “generico” simbolo X bensì aduna sua occorrenza nel parse tree.

◮ In altri termini, se la scrittura X .a nel frammento dicodice associato (poniamo) alla produzioneA→ XYZ si dovrà intendere come riferita ad ognispecifica applicazione della regola (che introduce ilsimbolo X ), bisognerà comunque tenere conto delfatto che, in applicazioni diverse della regola, il valoredi X .a potrà essere (e in generale sarà) diverso.

LFC


Symbol table



Attributi (continua)

◮ Nel nostro caso, i valori degli attributi sarannopuntatori al “costruendo” syntax tree.

◮ Per questa ragione, associato ad ogni non terminaledella grammatica si troverà sempre un attributo dinome node.

◮ In alcuni casi ci potranno essere anche ulterioriattributi

◮ Siamo ora in grado di presentare il nostro primoesempio di schema di traduzione, relativo alla “solita”grammatica delle espressioni aritmetiche.

LFC


Symbol table



Esempio

E → E1 + T {E .node← new node (′+′, E1.node,T .node)}

E → T {E .node← T .node}T → T1 × F {T .node← new node (′×′, T1.node,

F .node)}T → F {T .node← F .node}F → (E) {F .node← E .node}F → id {F .node← new leaf (id, id.lexval)}

◮ Si noti che:◮ ai non terminali è associato il solo attributo node;◮ ai terminali è associato l’attributo lexval (tipicamente,

un puntatore alla entry della symbol table).◮ l’aggiunta dell’indice ai non terminali E e T , nella

parte destra delle produzioni E → E + T eT → T × F , serve unicamente a disambiguare iriferimenti nelle corrispondenti azioni.

LFC


Symbol table



Calcolabilità degli schemi

◮ Come si passa dalla descrizione “statica” delle azioniassociate alle singole produzioni ad un processo dicalcolo precisamente definito?

◮ Se immaginiamo (come più volte affermato) che ilparser costruisca effettivamente il parse tree,possiamo pensare che le azioni descritte dalloschema vengano eseguite nell’ambito di un“opportuno” attraversamento del parse tree stesso.

◮ In questo modo, specificando il tipo diattraversamento, otteniamo la descrizione cercata.

◮ Infatti, una volta stabilito l’attraversamento (adesempio, in ordine posticipato) rimane univocamentedeterminato l’ordine di visita ai nodi del parse treecon conseguente esecuzione delle azioni specificatedallo schema.

LFC


Symbol table



Calcolabilità degli schemi (continua)

◮ Si noti che, in generale, il valore di un attributopresente in un nodo del parse tree dipende dalvalore degli attributi presenti in altri nodi.

◮ L’ordine di attraversamento dell’albero deve quindigarantire il soddisfacimento della fondamentaleproprietà che il valore di ogni attributo presente nelloschema sia calcolato prima di essere utilizzato.

◮ Ad esempio, con riferimento allo schema introdotto, ivalori degli attributi T1.node e F .node dovrannoessere disponibili nel momento in cui viene eseguitol’assegnamentoT .node← new node (‘×′, T1.node, F .node).

◮ Si tratta di un punto molto delicato, al qualedobbiamo dedicare attenzione specifica utilizzandoanche la terminologia appropriata.

LFC


Symbol table



Il ruolo del parse tree

◮ Prima di procedere, vogliamo però soffemarci sulruolo del parse tree nei processi di calcolo dei qualistiamo discutendo.

◮ Tale ruolo è essenzialmente di “raccordo”, in quantoil processo di parsing consente di generare in modonaturale prorpio il parse tree e non (direttamente) ilsyntax tree.

◮ Il parse tree offre, da un lato, un “posto” permemorizzare gli attributi (cioè l’informazionemanipolata dagli schemi), dall’altro (come abbiamoappena visto) un modo per descrivere l’ordine diesecuzione delle azioni dello schema.

◮ Va comunque da se che, qualora si trovino modi piùefficienti per risolvere questi due problemi, lacostruzione esplicita del parse tree diviene superflua.

LFC


Symbol table



Tipi di attributi

◮ Tornando al nostro problema (garantire cioè che ilcalcolo del valore di un attributo venga eseguito soloquando tutti gli attributi ai quali esso fa riferimentosiano stati a loro volta calcolati), definiamo le duediverse tipologie di attributi utilizzate nelleapplicazioni reali: gli attributi sintetizzati e gli attributiereditati.

◮ Con riferimento ad una generica produzione

A→ X1 . . . Xi−1Xi . . . Xk

un attributo per A si dice sintetizzato se il suo valoredipende solo dal valore degli attributi dei simboli Xi

nella parte destra della produzione.

LFC


Symbol table



Tipi di attributi (continua)

◮ Più precisamente, un attributo che etichetta un nododel parse tree è sintetizzato se il suo valore dipendesolo dal valore degli attributi nei nodi figli.

◮ Ci si può facilmente rendere conto che questacondizione vale per tutti gli attributi dell’unico schemadi traduzione finora visto come esempio.

◮ Uno schema in cui tutti gli attributi sono sintetizzati èdetto S-attributed.

◮ Se associamo ad uno schema S-attributed un ordinedi attraversamento posticipato del parse tree, laproprietà fondamentale viene automaticamentesoddisfatta.

LFC


Symbol table



Esempio

◮ Attraversando in ordine anticipato il parse treerelativo alla stringa di input id + id× id si ottiene unprocesso che costruisce correttamente il syntax tree.

◮ Il risultato completo del processo (incluso il valoreassociato a tutti gli attributi utilizzati nello schema)può essere descritto mediante il cosiddettoannotated parse tree, che mostriamo di seguito.

E

T

F

id

+

E

T

FT

F id

id

E.node

E.node

T.node

T.node

F.node

T.node

F.node

F.node

<id,id.lexval> <id,id.lexval>

<id,id.lexval>

< , >

< , >

LFC


Symbol table



Esempio (continua)

◮ Nell’annotated parse tree sono evidenziati gli attributipresenti ai vari nodi nodi e il loro valore, che (inquesto caso) è un puntatore ai nodi dell’abstractsyntax tree.

◮ Per semplificare l’interpretazione della figura,abbiamo usato frecce diverse per rappresentarederivazioni (e dunque puntatori ai nodi del parsetree) e valori degli attributi (puntatori ai nodidell’abstract syntax tree).

◮ Comprendere il modo in cui si arriva alla situazioneillustrata eseguendo le azioni è, in questo caso,molto semplice.

LFC


Symbol table



Esempio (continua)

◮ Seguendo l’ordine di attraversamento posticipato adogni nodo A si esegue l’azione prevista dallo schemain corrispondenza della produzione A→ XYZ , doveX , Y e Z sono i figli del nodo A.

◮ Si noti che, in realtà, non è necessario neppureseguire strettamente l’ordine di attraversamentoposticipato; è infatti sufficiente procedere in modobottom up, dalle foglie verso la radice, con notevoligradi di libertà sull’ordine preciso di esecuzione delleazioni descritte dallo schema.

◮ Si noti infine che il syntax tree completo è accessibileattraverso l’attributo E .node nella radice parse tree.

LFC


Symbol table



Tipi di attributi (riprende)◮ Ancora con riferimento alla generica produzione

A→ X1 . . . Xi−1Xi . . . Xk

un attributo per Xi si dice ereditato se il suo valoredipende (eventualmente) dal valore di attributiereditati di A e di attributi (ereditati o sintetizzati) diX1, . . . , Xi−1.

◮ Con riferimento al parse tree, un attributo a un nodoè ereditato se il suo valore dipende dal valore diattributi ereditati al nodi genitore o attributi (diqualunque tipo) ai nodi che sono “fratelli maggiori”.

◮ Questa definizione non è la più generale ma, di fatto,è quella operativa.

◮ In particolare, schemi di traduzione in cui vi sia (oltread eventuali attributi sintetizzati) almeno un attributoereditato secondo questa definizione vengono dettiL-attributed.

LFC


Symbol table



Esempio

◮ Il seguente schema di traduzione, relativo allagrammatica per le espressioni modificata (perrenderla adatta al parsing a discesa ricorsiva), èL-attributed.

◮ Si noti che alcuni nodi hanno due attributi,sintetizzato (node) ed ereditato (inh).

E → TE ′ {E ′.inh← T .node; E .node← E ′.node}E ′ → +TE ′

1 {E ′

1.inh ← new node (′+′, E ′.inh, T .node);E ′.node← E ′

1.node}E ′ → ǫ {E ′.node← E ′.inh}T → FT ′ {T ′.inh← F .node; T .node← T ′.node}T ′ → ×FT ′

1 {T ′

1.inh← new node (′×′, T ′.inh, F .node);T ′.node← T ′

1.node}T ′ → ǫ {T ′.node← T ′.inh}F → (E) {F .node← E .node}F → id {F .node← new leaf (id, id.lexval)}

LFC


Symbol table



Calcolabilità degli schemi (riprende)

◮ Vedremo un poco più avanti la logica che sta dietrolo schema L-attributed dell’esempio appena visto.

◮ Qui vogliamo riconsiderare per un istante il problemagenerale della calcolabilità degli schemi.

◮ Esiste infatti un rischio insito nella definizione diattributi con dipendenze “arbitrarie”, e cioè che nonesista nessun ordine di esecuzione delle azioni ingrado si soddisfare la proprietà fondamentale.

◮ Comunque, sempre nel caso generale, ladeterminazione dell’esistenza di un tale ordine diesecuzione costituisce problema algoritmico moltodifficile.

LFC


Symbol table



Calcolabilità degli schemi (continua)

◮ È alla luce di ciò che dobbiamo “apprezzare” la bontàdegli schemi S-attributed e L-attributed.

◮ Infatti, l’esistenza (e la immediata determinazione) diun ordine di esecuzione delle azioni previste daglischemi è garantita proprio nei seguenti due casi:

◮ la grammatica ammette parsing di tipo LR e loschema è S-attributed, oppure

◮ la grammatica ammette parsing di tipo LL e loschema è L-attributed.

LFC


Symbol table



Parsing LR

◮ La prima combinazione, di grammatica analizzabilecon parser LR unitamente a schema S-attributed, èpiù semplice da comprendere e, di fatto, l’abbiamogià vista.

◮ Infatti, in un parser LR, il parse tree viene costruito(anche solo implicitamente) dal basso verso l’alto.

◮ Questo implica che, nel momento in cui vieneeseguita una riduzione A→ α, è possibile calcolare ilvalore degli attributi (sintetizzati) definiti nel nodocorrispondente ad A.

◮ Tali valori dipendono infatti solo dal valore di attributidefiniti ai nodi corrispondenti ai simboli di α, chesono stati a loro volta già calcolati.

◮ In altri termini, la situazione che abbiamo vistonell’esempio è del tutto generale per grammaticheLR e schemi S-attributed.

LFC


Symbol table



Esempio

◮ Riconsideriamo in dettaglio l’esempio relativo alparsing della stringa id + id× id, secondo lo schema(S-attributed) introdotto.

◮ Usando il parser SLR(1) che abbiamo discusso asuo tempo, l’albero di parsing viene costruito dalbasso verso l’alto.

◮ Se le azioni indicate dallo schema vengono eseguitenel momento in cui si eseguono le corrispondentiriduzioni, i valori degli attributi sono tutti calcolabili(cioè le dipendenze sono tutte soddisfatte) comeillustrato nelle due seguenti trasparenze (nelle quali,per semplicità, non sono state disegnate foglieisolate).

LFC


Symbol table



Esempio (continua)

F

id

E.node

F.node

T.node

F.node


E

T

F

id

Dopo F−>id

F.node

<id,id.lexval>

F

id

F.node

T.node

<id,id.lexval>

T

F

id

E.node

F.node

T.node

<id,id.lexval>

E

T

F

idDopo la riduzione F−>id Dopo T−>F Dopo E−>T

T

F

id

E.node

T.node

F.node

T.node

F.node


E

T

F

id

Dopo T−>F

LFC


Symbol table



Esempio (continua)

FT

F id

id

E.node

T.node

F.node

T.node

F.node

F.node


<id,id.lexval>

E

T

F

id

Dopo F−>id

< , >T

FT

F id

id

E.node T.node

T.node

F.node

T.node

F.node

F.node


<id,id.lexval>

E

T

F

idDopo T−>T*F

< , >

< , >

+

E

T

FT

F id

id

E.node

E.node

T.node

T.node

F.node

T.node

F.node

F.node


<id,id.lexval>

E

T

F

idDopo E−>E+T

LFC


Symbol table



Aspetti implementativi◮ Nel caso di parsing LR e schema S-attributed è

relativamente semplice mostrare come lacostruzione esplicita del parse tree non sia richiesta.

◮ Se infatti è vero che gli attributi sono logicamentedefiniti ai nodi del parse tree, è però immediatoconvincersi del fatto che, non appena un nodo N èstato collegato al padre P (a seguito di unariduzione), gli attributi definiti in N non servono più.

◮ Nella pratica è sufficiente una modifica allo stackutilizzato dal parser LR, in modo che esso nonmemorizzi soltanto stati ma anche gli attributiassociati al simbolo che corrisponde a quello stato.

◮ A quest’ultimo riguardo, possiamo notare come ognistato s dell’automa possa essere associato ad unsimbolo della grammatica (si riconsideri, ad esempio,l’automa LR(0) relativo alla nostra grammatica per leespressioni, che riportiamo per comodità nellasuccessiva trasparenza).

LFC


Symbol table



Aspetti implementativi (continua)

I0

I1

I3

I2

I6

I4

I5 I8

I7

I11

I9

I10

accept

$

EF

F

(

+

F

(T

T(

id

id

(

id

+

)

×

×

F

T

id

F

LFC


Symbol table



Schema di traduzione modificato

◮ Presentiamo di seguito lo schema di traduzione perla grammatica delle espressioni, modificato in mododa utilizzare lo stack per memorizzare gli attributi.

◮ Più precisamente, lo stack memorizza ora coppie〈s, p〉, dove s è uno stato (un numero compreso fra 0e 11), mentre p è il valore della proprietà node (inpratica, un puntatore ad un nodo dell’abstract syntaxtree in costruzione) del simbolo associato ad s.

◮ Si noti che non è più necessario distinguere differentioccorrenze dello stesso simbolo (in quanto nonvengono più indicati esplicitamente gli attributi nelleazioni dello schema).

LFC


Symbol table



Schema di traduzione modificato

E → E + T {p2 ← pop().p; pop (); p1 ← pop ().p;s ← GOTO(top ().s, E);push (〈s, new node (′+′, p1, p2)〉)}

E → T {p ← pop ().p; s ← GOTO(top ().s, E);push (〈s, p〉)}

T → T × F {p2 ← pop().p; pop (); p1 ← pop ().p;s ← GOTO(top ().s, T );push (〈s, new node (′×′, p1, p2)〉)}

T → F {p ← pop ().p; s ← GOTO(top ().s, T );push (〈s, p〉)}

F → (E) {pop (); p ← pop ().p; pop ();s ← GOTO(top ().s, F ); push (〈s, p〉)}

F → id {p ← pop ().p; s ← GOTO(top ().s, F );push (〈s, new leaf (id, id.lexval)〉}

LFC


Symbol table



Parsing LL

◮ Passiamo ora ad unalizzare il secondo caso dicalcolabiltà efficiente degli schemi di traduzione, eprecisamente quello relativo a schemi L-attributed inunione con grammatiche di tipo LL.

◮ Anche in questo caso, l’esempio che ci guiderà saràquello relativo alla grammatica per le espressionimodificata con l’eliminazione della ricorsione asinistra.

◮ Abbiamo già visto come lo schema sia L-attributed.◮ Ciò che ci resta da stabilire è dunque come debbano

essere sequenzializzati i frammenti di codiceassociati alle varie produzioni in modo da ottenereun processo di calcolo che produca effettivamente(ed efficientemente) l’output desiderato (l’abstractsyntax tree).

LFC


Symbol table



Un semplice esempio

◮ Per capire il processo generale ci aiutiamo con ilsemplice esempio di parsing della frase id1 + id2:

E

E ′

E’

ǫ

T

T ′

ǫ

F

id2

+

T

T ′

ǫ

F

id1

◮ Come già per gli schemi S-attributed, le dipendenzefunzionali fra gli attributi (e dunque il flusso di datinecessario affinché il calcolo proceda in modocorretto) possono essere evidenziati utilizzando unannotated parse tree.

LFC


Symbol table



Esempio (continua)◮ In questo caso, nel disegno dell’annotated parse tree

abbiamo utilizzato una notazione semplificativa.◮ Ciò è dovuto al fatto che la maggior parte dei nodi ha

due attributi i quali, se scritti esplicitamente,avrebbero reso la figura difficile da “leggere”.

◮ Abbiamo quindi usato la seguente convenzione:◮ una freccia indica un arco del parse tree

(queste frecce sono sempre orientate verso il basso);◮ una freccia (orientata verso l’alto) indica che

l’attributo sintetizzato al nodo di partenza è usato percalcolare l’attributo sintetizzato al nodo di arrivo;

◮ una freccia (orientata verso il basso) indicache l’attributo ereditato al nodo di partenza è usatoper calcolare l’attributo ereditato al nodo di arrivo;

◮ infine, una freccia (orientata verso destra)indica che l’attributo sintetizzato al nodo di partenzaè usato per calcolare l’attributo ereditato al nodo diarrivo.

LFC


Symbol table



Esempio (continua)

◮ L’annotated parse tree:

E

T E’

F T’ +

F T’

E’

id1

id2 ε

εε

T

LFC


Symbol table



Organizzazione concreta del calcolo

◮ Nel caso di implementazione del parser LL medianteprocedure ricorsive, un’implementazione delloschema di traduzione che rispetti le dipendenzefunzionali è alquanto semplice.

◮ Consideriamo infatti l’utilizzo di una genericaproduzione A→ X1 . . . Xi−1Xi . . . Xk .

◮ Nel momento in cui la procedura per Xi vienechiamata (dalla procedura per A), le procedure perX1, . . . , Xi−1 sono già state chiamate e dunqueeventuali valori da esse produtti possono esserepassati in input a Xi .

◮ Questo consente proprio di implementare il flussodati richiesto dalla definizione di attributo ereditato,nel senso che, qualora Xi abbia attributi ereditati,questi dipendono da valori associati a (e producibilidalle procedure per) A e/o X1, . . . , Xi−1.

LFC


Symbol table



Organizzazione concreta del calcolo(continua)

◮ In realtà, è proprio la struttura delle procedurericorsive di un parser LL ad aver suggerito la nostradefinizione di attributo ereditato.

◮ Tornando alla nostra grammatica per le espressioni,consideriamo, ad esempio, la procedura per E e lecorrispondenti azioni dello schema:

E ′.inh← T .node e E .node← E ′.node.

◮ La procedura invocherà quindi dapprima la routine T(che non necessita di “informazione ereditata”).

◮ Il valore restituito da quest’ultima (T .node) saràpassato in input a E ′ come valore ereditato.

◮ Il valore restituito dalla chiamata ad E ′ sarà poianche il valore restituito da E .

LFC


Symbol table




◮ Si noti quindi che le procedure corrispondenti ai nonterminali sono più utilmente realizzate mediantefunzioni.

◮ La funzione per E può quindi essere sinteticamenteespressa nel modo seguente:

1: Tnode ← T ()2: return E ′(Tnode)

LFC


Symbol table




◮ Consideriamo, come altro esempio, la routine per E ′.◮ Abbiamo appena visto che essa riceve in input un

argomento (attributo ereditato) che supporremovenga assegnato al parametro formale inh.

◮ Il corpo della funzione può essere espresso nelmodo seguente (si ricordi la tabella di parsing per laproduzione E ′ → +TE ′):

1: if t ← get _next _token () =′ +′ then2: Tnode ← T ()3: inh1 ← new node (′+′, inh, Tnode)4: return E ′(inh1)5: else if t =′ )′ or t =′ $′ then6: return inh7: else8: error ()

LFC


Symbol table




◮ Nel caso di implementazione ricorsiva del parser,non è dunque necessario che vengapreliminarmente costruito il parse tree.

◮ Nel caso il parse tree sia disponibile non ècomunque difficile rendersi conto di come ledipendenze funzionali presenti negli schemi sianosoddisfattibili mediante un attraversamento in ordineanticipato (preordine) del parse tree medesimo.

◮ Infatti, l’attaversamento in ordine anticipato consente(sempre con riferimento alla generica produzioneA→ X1 . . . Xi−1Xi . . . Xk ) di “raccogliere”l’informazione (attributi) relativa ad A e X1, . . . , Xi−1

prima di usarla (come informazione ereditata) nelcalcolo degli attributi per Xi

◮ Si veda al riguardo l’annotated parse tree relativoalla frase id1 + id2.

LFC


Symbol table





LFC


Symbol table



Il completamenento del front-end◮ Obiettivo di quest’ultima parte del corso è la

presentazione di alcuni semplici esempi digenerazione di codice intermedio.

◮ Non intendiamo presentare una descrizionecompleta, sia per ragioni di tempo sia perché (anostro avviso) questa attività è molto menointeressante dal punto di vista delle idee sottostanti.

◮ Gli esempi hanno dunque il solo scopo di illustrarel’approccio base per la generazione di codiceintermedio, ignorando quegli aspetti cherichiederebbero un ragionamento più approfondito.

◮ Faremo inoltre tre ipotesi molto forti, e precisamente:(1) di disporre dell’abstract syntax tree delle stringheda tradurre; (2) che il risultato debba esserepresentato sotto forma di file alfanumerico, (3) cheesista un unico tipo di dato nei programmi sorgenti(ad esempio, numeri interi).

LFC


Symbol table



Il modello di computer intermedio◮ Il codice intermedio nel quale dovrà essere tradotto il

programma sorgente sarà il cosiddetto three-addresscode.

◮ Naturalmente, prima di descrivere gli esempi ditraduzione, dobbiamo precisare che cosa si intendacon codice a tre indirizzi, cioè a quale modelloastratto di calcolatore tale codice faccia riferimento.

◮ Ipotizziamo dunque che la macchina astratta sia ingrado di eseguire semplici istruzioni caratterizzate daun codice operativo e da al più tre indirizzi per glioperandi.

◮ Fra le istruzioni disponibili troviamo le operazionilogico/aritmetiche binarie e unarie, le istruzioni disalto (condizionato o incondizionato), il sempliceassegnamento, la chiamata di procedura e lagestione di array lineari.

◮ Ogni istruzione può essere preceduta da una o piùetichette (stringhe letterali)

LFC


Symbol table



Istruzioni del three-address code

◮ Più precisamente, allo scopo di presentare gliesempi, noi considereremo solo le seguentiistruzioni, il cui significato dovrebbe risultare chiaro:

◮ A← B op C, dove op ∈ {+,−,×, /} e A, B e C sonoidentificatori definiti dall’utente nel programmasorgente oppure temporanee generate dal parser;

◮ A← B, dove A e B sono definiti come al puntoprecedente;

◮ goto L, dove L è un’etichetta generata dal parser;◮ if A goto L, dove A è un identificatore definito

dall’utente oppure una temporanea generata dalparser ed L è un’etichetta generata dal parser;

◮ ifFalse A goto L, dove A ed L sono definiti comeal punto precedente.

LFC


Symbol table



Ulteriori assunzioni◮ Ipotizzeremo che il parser possa invocare una

funzione per generare identificatori univoci, comepure una funzione per generare etichette univoche.

◮ Assumeremo inoltre la disponibilità di una funzione,che chiameremo emit(), che stampa la stringapassata come parametro (che rappresenta unaporzione del programma in three-address code) suun opportuno supporto di output.

◮ Assumeremo infine che il generico nodo dell’abstractsyntax tree abbia la seguente struttura:

◮ un campo label che caratterizza il tipo di nodo(assegnamento, operatore, comando if, ...);

◮ se significativo (ad esempio nel caso di identificatoreo operatore), un puntatore alla symbol table per ilcorrispondente valore lessicale, accessibie mediantela funzione lexval;

◮ uno o più puntatori ai nodi che rappresentano icomponenti del costrutto, accessibili mediante icampi c1 , c2 , ...

LFC


Symbol table



La struttura generale del traduttore

◮ Con le ipotesi fatte, il traduttore (da syntax tree athree-address code) può essere organizzato comeprocedura ricorsiva il cui corpo è costituitoessenzialmente da una “grossa” istruzione case (o,se si preferisce, switch ), che analizza il nodo ppassato come parametro e, a seconda del tipo,esegue operazioni diverse.

◮ Data la struttura del parse tree, la generazione delcodice per un dato nodo implicherà poi una o piùchiamate ricorsive per la generazione del codiceassociato ai nodi figli.

◮ La procedura, che chiameremo gencode, riceve unulteriore parametro (RES) che è una stringa(eventualmente vuota) alla quale (vista come nomedi variabile) deve essere assegnato il risultatocalcolato dal codice generato per il nodo p.

LFC


Symbol table



Procedure 1 gencode(string RES, AST ∗ p)

tag ← (p → label )case tag of

id : . . .assignment : . . .comparison : . . .binaryop : . . .seq : . . .if : . . .ifElse : . . .while : . . .

. . .default : error()

end

LFC


Symbol table



Il caso degli identificatori

◮ Si tratta del caso più semplice da trattare.◮ Infatti, se un nodo è etichettato come identificatore,

tutto ciò che bisogna fare è semplicemente emettereuna stringa che ne rappresenta il valore lessicale.

◮ Al riguardo, utilizziamo una funzione toString (esisteanche in Java), che, nel caso il valore lessicaledell’identificatore sia già internamente rappresentatocome stringa, equivale ad un no-op.

◮ Per altri tipi di nodo, toString svolge effettivamenteuna funzione: ad esempio, se il nodo è un operatorebinario, la chiamata toString(lexval(p)) ne fornisce laconsueta rappresentazione matematica (+,-, ecc).

LFC


Symbol table



Il caso degli identificatori (continua)

◮ Il codice relativo a questo caso è dunque:

id : string name ← toString(lexval(p))if not empty(RES) then

emit(RES+“←”+name)else

emit(name)

dove l’operatore + applicato a stringhe denotaconcatenazione.

◮ Si noti anche il controllo (che sarà ricorrente anchenei seguenti esempi) sulla stringa RES.

◮ Se RESnon è la stringa vuota, il codice da generaredeve infatti prevedere un assegnamento al nome daessa rappresentato.

LFC


Symbol table



Assegnamento

◮ Un nodo etichettato come assignment ha due figli, ilprimo dei quali deve necessariamente essere un id .

◮ Il codice da generare prevede la chiamata ricorsivaal secondo figlio, in modo che lasci il valore nellavariabile il cui nome è il valore lessicale del primofiglio.

◮ In altre parole:assignment : string name ← lexval(p → c1 )if not empty(RES) then

emit(RES+“←”+gencode(name, p → c2 )else

gencode(name, p → c2 )

LFC


Symbol table



Gli operatori (aritmetici) binari

◮ Se l’etichetta del nodo è un operatore binariobisogna:

◮ generare ricorsivamente il codice per il figlio disinistra, in modo che lasci il risultato in una variabileil cui nome univoco è generato dal parser stesso(supporremo che tali nomi abbiano la forma TEMPn,con n progressivo);

◮ generare (analogamente) il codice per figlio di destra,in modo che lasci il risultato in una seconda variabile;

◮ generare la stringa per un’istruzione a tre o dueindirizzi (a seconda del valore del parametro RES)che esegue l’operazione indicata dal particolareoperatore binario sui dati memorizzati nelletemporanee.

LFC


Symbol table



Gli operatori (aritmetici) binari (continua)

◮ Il codice corrispondente è:

binaryop :string t1 ← new temporary()string t2 ← new temporary()gencode(t1 , p → c1 )gencode(t2 , p → c2 )string op ← toString(lexval(p))if not empty(RES) then

emit(RES+“←”+t1 + op + t2 )else

emit(t1 + op + t2 )

LFC


Symbol table



Esempio

◮ Per l’abstract syntax tree del comando C/C++x = a × b + c (rappresentato in modo da evidenziaredirettamente il valore lessicale degli operatori e degliidentificatori)

=

+

×

cb

a

x

viene generato il seguente codice a tre indirizzitemp1 ← atemp3 ← btemp4 ← ctemp2 ← temp3 × temp4x ← temp1 + temp2

LFC


Symbol table



Sequenza◮ Una sequenza di comandi, definita dalle produzioni

L → L; S | S,

produce alberi sintattici con la struttura indicata diseguito (in cui ogni singolo statement può, a suavolta, essere un syntax tree)

seq

statementseq

statementseq

statementstatements

◮ Il codice corrispondente consiste semplicemente didue chiamate ricorsive:

seq :gencode(“”, p → c1 )gencode(“”, p → c2 )

LFC


Symbol table



Comando “If then”

◮ È rappresentato da alberi sintattici del tipoif

statementexpression

◮ I passi per effettuare la traduzione sono i seguenti:◮ si genera ricorsivamente il codice per calcolare

l’espressione, lasciando il risultato in unatemporanea;

◮ si genera un’etichetta e si emette un’istruzione disalto a tale etichetta, condizionato al valore falsodella temporanea;

◮ si genera quindi ricorsivamente il codice per ilcomando (che verrà dunque eseguito se il valoredella temporanea è vero);

◮ infine si emette l’etichetta generata (che andrà adetichettare la prossima istruzione a tre indirizzi, nonemessa dal trattamento del condizionale).

LFC


Symbol table



Comando “If then” (continua)

◮ Il codice corrispondente è:

if :string t ← new temporary()gencode(t , p → c1 )string l ← new label()emit(“ifFalse ”+t +“ goto ”+l )gencode(“”, p → c2 )emit(l +“: ”)

LFC


Symbol table



Comando “If then else”

◮ È solo leggermente più complicato del casoprecedente, per cui presentiamo direttamente ilcodice

ifElse :string t ← new temporary()gencode(t , p → c1 )string l1 ← new label()emit(“ifFalse ”+t +“ goto ”+l1 )gencode(“”, p → c2 )string l2 ← new label()emit(l1 +“: goto +“ ”+l2 )gencode(“”, p → c3 )emit(l2 +“: ”)

LFC


Symbol table



Esempio

◮ Alla frase C/C++

if a >= 0 then x = a else x = −a

corrisponde il seguente abstract syntax treeifElse

=

-

a

x

=

ax

≥

0a

(si ricordi che abbiamo scelto di evidenziaredirettamente il valore lessicale degli operatori e degliidentificatori anziché inserire simboli astratti eriferimenti alla symbol table).

LFC


Symbol table



Esempio (continua)

◮ Il codice a tre indirizzi corrispondente è:

temp2 ← atemp3 ← 0temp1 ← 2 ≥ temp3ifFalse temp1 goto label1temp4 ← ax ← temp4goto label2label1 : temp5 ← ax ← −temp5label2 :

LFC


Symbol table



Comando “while”

◮ Come ultimo caso, consideriamo la traduzione diabstract syntax tree corrispondenti al costrutto while.

◮ Il costrutto ha due componenti, la condizione e lostatement da ripetere finché la condizione è vera.

◮ La strategia di traduzione consiste quindi nelgenerare il codice per la condizione, emettereun’istruzione di salto condizionato (ifFalse ),generare il codice per il comando ed emettereun’istruzione di salto incondizionato al codicegenerato per la condizione.

◮ Lo pseudocodice dettagliato è riportato nellasuccessiva trasparenza.

LFC


Symbol table



Comando “while” (continua)

while :string t ← new temporary()string l1 ← new label()emit(l1 +“: ”)gencode(t , p → c1 )string l2 ← new label()emit(“ifFalse ”+t +“ goto ”+l2 )gencode(“”, p → c2 )emit(“goto ”+l1 )emit(l2 +“: ”)

Linguaggi Formali e Compilazione: Frontend

Technology

Transcript of Linguaggi Formali e Compilazione: Frontend