Linguaggi Formali e Traduttori

• Teacher: Sproston Jeremy
• PDF Version
• Prova di laboratorio (progetto, interrogazione singola anche in caso di progetto di gruppo con gruppi da 3)

  • Sostenibile dopo aver superato Teoria 1/3 del voto

  • LFTCompiler

Testi

Compilatori

Principi tecniche e strumenti

Automi

Automi, Linguaggi e Calcolabilita’

Fasi Compilatore

• NB

  $$DFA=NFA=ϵ\text{-}NFA=RE$$
  • $$DFA\subset DPDA\subset CFG\text{ non ambigue}\subset CFG=PDA$$

Analisi Lessicale

sequenze di caratteri | token o lessemi

Si passa da

1. Programma come sequenza di caratteri
2. Programma come sequenza di token

Token

Costante numerica intera sequenza non vuota di cifre decimali, preceduta da + o - Costante numerica con virgola due sequenza (almeno 1 non vuota) di cifre decimali separate da . Identificatore sequenza on vuota di lettere numeri e _ e non inizia con un numero

Lexer

Analizzatore lessicale —-> Codice <—- La visione del programma passa da “carattere per carattere” a “token per token”

• spazi e commenti vengono scartati dal lexer
  • * *
  • //
    • finiscono con a capo o EOF
• Token
  • Identificatori
    • non comincia con un numero
    • non é composto solamente dal simbolo _
    • Ovvero corrisponde all’espressione regolare
      • ([a-zA-Z] | (()*[a-zA-Z0-9])) ([a-zA-Z0-9] | _)*

Analisi Sintattica

Vedi: Parser Top-Down e Codice Parser a Discesa Ricorsiva

• Prende input dall’analizzatore lessicale
• Crea un Albero Sintatico
  • che sará utilizzato poi dal Analizzatore Semantico
    • vedi Analisi Semantica
• In caso l’input non corrisponda ad un albero lessicale
  • deve restituire un errore
• Espressioni Booleane
  • RELOP $‘\in ‘$ $‘\{==,<>,<=,>=,<,>\}‘$
• Separatore
  • punto e virgola
    • non un terminatore di istruzione
• Produzioni
  • In caso di rami annullabili attenzione ai FOLLOW
• Sintassi scheme-like
  • espressioni aritmetiche
    • notazione prefissa
    • puó comprendere ID

    • operatori

      • - / : binarie
    • compaiono nelle espressioni booleane
      • impatto sull’insieme GUIDA
  • assegnamento
    • notazione prefissa
  • espressioni relazionali
    • notazione prefissa

Analisi Semantica

• Si occupa della valutazione delle espressioni

SDD

Syntax Directed Definition Definizioni dirette dalla sintassi strumento che permette la traduzione

• consistono in
  • grammatica libera
    • specifica la sintassi
      • gli operatori qui sono sintattici
  • attributi
    • risultati della traduzione
      • sono riferiti dall’analizzatore lessicale
    • (nome, valore)
    • rappresentano una qualunque informazione associata ad un nodo
  • regole semantiche
    • come calcolare gli attributi
    • specificano regole di calcolo e assegnamento tra attributi per ogni produzione
      • gli operatori qui sono semantici/matematici
    • sono valutate in ordine arbitrario
      • richiedono la costruzione di un albero sintattico annotato

Con cui si definisce un albero sintattico annotato

• i cui nodi possono essere annotati con 0 o piú attributi

1. Attributi

   • Sintetizzati Il suo valore dipende da quello di attributi dei figli ed eventualmente da altri attributi di se stesso
   • Ereditati Il suo valore dipende da quello dal padre e dai fratelli del nodo

2. Grafo delle dipendenze Alcuni attributi dipendono da altri, questo impone un’ordine tra questi

   • se il grado contiene dei cicli non é possibile trovare un’ordine di valutazione degli attributi

3. S-attribuite Contiene solo attributi sintetizzati

   • ogni S-attribuita é a sua volta L-attribuita

4. L-attribuite Per ogni produzione $‘A\to X_1{X}_2...X_n‘$ e ogni attributo ereditato $‘X_i.e‘$ la regola semantica che definisce il valore di $‘X_i.e‘$ dipende solo da

   • attributi ereditati da $‘A‘$
   • attributi sintetizzati ed ereditati dai simboli $‘X_1,X_2,...,X_{i-1}‘$ alla sinistra di $‘X‘$

SDT

Syntax-Directed Translation scheme Schema di traduzione, variante SDD che rende esplicito l’ordine di valutazione degli attributi

• grammatica in cui le produzioni sono arricchite da frammenti di codice
  • azioni semantiche
    • eseguite nel momento che i simboli alla loro sinistra sono stati riconosciuti
    • simili alle regole semantiche degli SDD
      • specificano il calcolo degli attributi ma anche codice arbitrario
      • l’ordine di esecuzione é esplicito a differenza delle regole semantiche
      • essendo eseguite da sinistra verso destra non richiedono la costruzione dell’albero sintattico annotato

1. da SDD L-attribute a SDT data $‘A\to X_1{X}_2...X_n‘$

   1. subito prima di $‘X_i‘$
      • azione semantica che calcola il valore degli attributi ereditati
        • che possono solo dipendere da attributi ereditati di $‘A‘$ e attributi dei nodi fratelli alla sua sinistra
   2. in fondo alla produzione a. azione semantica che calcola il valore degli attributi sintetizzati di $‘A‘$

Traduzione on the fly

Attributi sintetizzati principali

• il loro valore include sempre la concatenazione dei valori dello stesso attributo per tutte le variabili nel corpo di ogni produzione oltre che eventuali variabili ausiliarie
• la concatenzazione rispetta l’ordine delle variabili nel corpo delle produzioni Es, trasformazione da forma infissa a postfissa

$‘E\to E_1+T\{E.post=E_1.post||T.post||"..."\}‘$ Questo viene tradotto on the fly in { print(”…”) }

Automi

Esempio

automa: riconosce stringhe stati finiti: memoria finita input: stringa output: “si” se riconosciuta “no” altrimenti

L’automa ha visione locale e limitata , legge un simbolo alla volta

L’automa altera il suo stato in base al simbolo letto

Se alla fine della stringa l’automa si trova in uno stato finale la stringa é accettata, altrimenti rifiutata

Automi a stati finiti deterministici DFA

Deterministico: lo stato in cui si sposta é univocamente determinato dallo stato corrente e dal input

Quintupla composta da:

1. $‘Q‘$ - insieme finito di stati
2. $‘\Sigma ‘$ - alfabeto riconosciuto
3. $‘\delta ‘$ - funzione di transizione
4. $‘q_0‘$ - e’ lo stato iniziale
5. $‘F‘$ - insieme di stati finali

Funzione di transizione estesa

funzione definita su stringhe invece che singoli simboli definito per induzione

Linguaggio riconosciuto

Stringhe definite sull’alfabeto che per mezzo della F di transizione estesa portano ad uno stato finale dell’automa

Automi a stati finiti non deterministici NFA

Non deterministico: l’automa puo’ scegliere di spostarsi in 0 o piu’ stati possibili

• Il codominio della funzione di transizione e’ l’insieme delle parti degli stati $‘Q‘$

Quintupla composta da:

1. $‘Q‘$ - insieme finito di stati

2. $‘\Sigma ‘$ - alfabeto riconosciuto

3. $‘\delta ‘$ - funzione di transizione il cui codominio e’ un’insieme delle parti di Q

4. $‘q_0‘$ - e’ lo stato iniziale

5. $‘F‘$ - insieme di stati finali Insiemi singoletto indicano transizioni deterministiche (da funzione di transizione estesa) Automi che possono eseguire transizioni spontanee senza leggere alcun simbolo nella stringa da riconoscere

   • passa di stato anche senza consumare alcun simbolo

epsilon-chiusura

calcolare l’insieme di stati raggiungibili solo con transizioni-epsilon ECLOSE

• la chiusura e’ transitiva

• la chiusura di q include q ECLOSE(S) = Unione di ECLOSE(q_i) Gli NFA sono un caso particolare di epsilon-NFA in cui non ci sono transizioni epsilon

  • il potere riconoscitivo degli epsilon-NFA e’ almeno pari a quello dei DFA/NFA

1. Teorema Dato un eNFA E esiste un DFA D tale che L(D) = L(E)

Passaggio da DFA a NFA e viceversa

Da NFA a DFA sono possibili fino a $‘2^n‘$ stati

Da un DFA con piu’ stati finali e’ possibile ricavare un e-NFA equivalente con un unico stato finale

Espressioni regolari RE

Sono un approccio generativo alle classi di Linguaggi E’ sempre possibile creare un e-NFA a partire da una RE

Denotano un Linguaggio con $‘L(E)‘$ Definito per induzione

$‘L(0)=0‘$ $‘L(ϵ)=\{ϵ\}‘$ // la stringa vuota $‘L(a)=a‘$ $‘L(E+F)=L(E)\cup L(F)‘$ $‘L(EF)=L(E)L(F)‘$ $‘L(E\ast )=L(E{)}^{\ast }‘$ // chiusura di Kleene

precedenza

1. *
2. concatenazione
3. +

Proprietá

1. Unione
   • Commutativa
   • Associativa
   • Idempotenza
   • Identitá
2. Concatenazione
   • Associativa
   • Identitá
   • Assorbimento
   • distributivitá
3. Chiusura di Kleene
   • Idempotenza

Indistinguibilitá tra stati

Equivalenza (relazione riflessiva, simmetrica e transitiva) Due stati hanno lo stesso potere discriminante se presa una qualunque stringa del linguaggio si arriva ad uno stato finale in entrambi i casi o no in entrambi i casi, la indichiamo con ~

• Puó esserci una stringa che distingue i due stati
• Uno stato finale é distinto da altri stati non finali dalla stringa vuota

Minimizzazione di Automi

si raggiunge un automa minimo: $‘(Q/\widetilde{,}\Sigma ,\delta ,[q_0],F/\widetilde{)}‘$ in cui $‘\delta ([p],a)=[\delta (p,a)]‘$ Non esiste un automa corrispondente con meno stati dell’automa minimo

Equivalenza di Automi

Puó essere usato l’algoritmo riempi tabella per decidere se due automi sono equivalenti Si crea l’unione dei due DFA: $‘A=(Q_1\cup Q_2,\Sigma ,\delta ,q_1,F_1\cup F_2)‘$ $‘\delta (q,a)={\delta }_1\cup {\delta }_2‘$ Se $‘q_1‘$ e $‘q_2‘$ risultano indistinguibili in $‘A‘$ allora $‘A_1‘$ e $‘A_2‘$ sono equivalenti

Automi a Pila PDA

Approccio Riconoscitivo Utilizza operazioni push e pop su una pila di dimensione illimitata

• Simbolo sentinella $‘Z_0‘$ che indica la fine della stringa, é il simbolo della pila con cui quest’ultima viene inizializzata
• Ad ogni lettura di un simbolo l’automa fa push(x) o push(b) dipendentemente dal Linguaggio
• La $‘ϵ‘$ transizione finale puó eseguire solo se peek restituisce $‘Z_0‘$

$‘P=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)‘$

• $‘\Sigma ‘$ = alfabeto di input
• $‘\Gamma ‘$ = alfabeto della pila
• $‘\delta :Q\times (\Sigma \cup \{ϵ\})\times \Gamma \to p(Q\times {\Gamma }^{\ast })‘$ = funzione di transizione

Descrizioni istantanee

Fissato un automa a pila $‘P‘$ $‘D.I.=(q,w,\alpha )‘$

• stato in cui si trova l’automa
• ció che rimane da riconoscere nella stringa di input
• contenuto della pila dalla cima al fondo (sx a dx)

1. Mosse relazioni da $‘D.I.‘$ a $‘D.I.‘$ $‘I{⊢}_{P}J‘$ chiusura riflessiva e transitiva $‘I{⊢}_P^{\ast }J‘$

Linguaggio Accettato

Per stato finale: $‘L(P)=\{w\in {\Sigma }^{\ast }\mid (q_0,w,Z_0){⊢}_P^{\ast }(q,ϵ,\alpha ),q\in F\}‘$ Per pila vuota: $‘N(P)=\{w\in {\Sigma }^{\ast }\mid (q_0,w,Z_0){⊢}_P^{\ast }(q,ϵ,ϵ)\}‘$

• Per stato finale il contenuto della pila nella $‘D.I.‘$ finale é irrilevante
• Per pila vuoto lo stato nela $‘D.I.‘$ finale puó non essere finale

In ogni caso la stringa di input deve essere consumata completamente

Automi a Pila Deterministici

DPDA Strettamente meno espressivi dei PDA

• riconoscono comunque ogni Linguaggio Regolare
• riconoscono i linguaggi liberi non inerementemente ambigui

Dimostrabile:

1. Per ogni CFG $‘G‘$ esiste un PDA $‘P‘$ tale che $‘N(P)=L(G)‘$
2. Per ogni PDA $‘P‘$ esiste una CFG $‘G‘$ tale che $‘L(G)=N(P)‘$

I DPDA a paritá di stato simbolo letto e simbolo sulla pila possono fare al massimo una mossa.

• $‘\delta (q,a,X)\cup \delta (q,ϵ,X)‘$ deve contenere al massimo un elemento

Mentre il linguaggio $‘w{w}^R‘$ non é riconoscibile in quanto fa uso chiave del non determinismo mentre $‘wc{w}^R‘$ é riconoscibile grazie al simbolo sentinella $‘c‘$

• Dim - Ogni linguagio regolare é riconosciuto da un DPDA
  • $‘A=(Q,\Sigma ,{\delta }_A,q_0,F)‘$
  • $‘P=(Q,\Sigma ,\{Z_0\},{\delta }_P,q_0,Z_0,F)‘$ dove
  • $‘{\delta }_P(q,a,Z_0)=\{({\delta }_A(q,a,Z_0))\}‘$ per ogni $‘q\in Q,a\in \Sigma ‘$
  • $‘{\delta }_P(q,ϵ,Z_0)=\varnothing ‘$

Dimostrabile

1. Per ogni DPDA $‘P‘$ esiste una grammatica libera non ambigua $‘G‘$ tale che $‘L(G)=N(P)‘$
2. Il viceversa non vale

La famiglia dei linguaggi riconoscibili da DPDA é inclusa in - ma non concide con - quella dei linguaggi generabili da grammatiche libere non ambigue

Parser Top-Down

Vedi:Parser Top-Down

Grammatiche Libere

Teorema

Per ogni linguaggio regolare $‘L‘$ esiste una grammatica $‘G‘$ tale che $‘L(G)=L‘$

• dove $‘L(G)‘$ é il linguaggio generato da $‘G‘$

• le grammatiche possono generare tutti i linguaggi regolari
• possono anche generare linguaggi non regolari
  • stringhe palindrome
  • parentesi bilanciate

I linguaggi liberi includono propriamente i linguaggi regolari

LL(1)

Non LL(1)

Fattorizzazione

$‘A\to \alpha {\beta }_1|\alpha {\beta }_2‘$ quindi GUIDA$‘(A\to \alpha {\beta }_1)\cap ‘$ GUIDA$‘(A\to \alpha {\beta }_2)=/=\varnothing ‘$

Soluzione Fattorizzare il previsso comune in una variabile a parte $‘A^{\prime }‘$

Ricorsione immediata a sinistra

$‘A\to A\alpha |\beta ‘$

Soluzione Nuova variabile $‘A^{\prime }‘$ per spostare la ricorsione da sinistra a destra $‘A\to \beta A^{\prime }‘$ $‘A^{\prime }\to ϵ|\alpha A^{\prime }‘$

In generale l’eliminazione della ricorsione a sinistra non garantisce che la grammatica risultante sia LL(1)

Ricorsione indiretta a sinistra

$‘S\to Aa|b‘$ $‘A\to Ac|Sd|ϵ‘$

Soluzione

1. si impone un ordine arbitrario alle variabili
2. considerando ogni variabile nell’ordine imposto si elimina la ricorsione immediata per quella variabile e si riscrivono le occorrenze di quella variabile che compaiono nei corpi delle produzione delle variabili seguenti

Linguaggi

Linguaggio regolare

Esiste almeno un Automa A che lo riconosce

Linguaggi Regolari

def Un Linguaggio riconoscibile da un DFA

1. I linguaggi regolari sono chiusi rispetto all’operazione di unione ‘Collego’ i due automi deterministici attraverso uno stato q0 che con epsilon-transizioni passa da uno o dall’altro

2. I linguaggi regolari sono chiusi rispetto all’operazione di concatenazione ‘Collego’ lo stato finale (che non sara’ piu’ finale) del e-NFA corrispondente al primo automa con quello iniziale di quello e-NFA del successivo, con una epsilon-transizione

3. Chiusura dim p- $‘L\cup L^{{}^{\prime }}‘$

   • Dati $‘E_1‘$ e $‘E_2‘$
     • Si dimostra che $‘E_1+E{}_2‘$ genera $‘L{\text{cupL}}^{{}^{\prime }}‘$
     • Essendo quella ancora un’espressione regolare anche il linguaggio generato sará regolare
   • $‘L{L}^{{}^{\prime }}‘$
   • Simile all’unione
   • $‘notL‘$
   • $‘notL={\Sigma }^{\ast }-L‘$
   • si crea un automa $‘B=(Q,\Sigma ,\delta ,q_0,Q-F)‘$
     • abbiamo complementato l’insieme degli stati finali
   • i$‘L\cap L^{{}^{\prime }}‘$
   • Si utilizzano le leggi di De Morgan
     • ci si riconduce al caso dell’unione e della complementazione
   • O si construisce un automa $‘B‘$ che riconosce una simulazione dei due automi iniziali $‘A_1‘$ e $‘A_2‘$
   • $‘L-L^{{}^{\prime }}‘$
   • $‘L_1-L_2=L_1\cap not{L}_2‘$
   • $‘L^R‘$
     • L rovesciato
   • Si ricava un $‘E^R‘$ per induzione $‘{\varnothing }^R=\varnothing ‘$ $‘{ϵ}^R=ϵ‘$ $‘a^R=a‘$ $‘(E_1+E_2{)}^R={E_1}^R+{E_2}^R‘$ $‘(E_1{E}_2{)}^R={E_2}^R{E_1}^R‘$ $‘(E^{\ast }{)}^R=(E^R{)}^{\ast }‘$ Facile poi dimostrare che $‘L(E^R)=L(E{)}^R‘$ Tutti questi sono ancora regolari

Linguaggi non Regolari

Pumping Lemma

Per ogni linguaggio regolare $‘L‘$ esiste $‘n‘$ appartenente a $‘N‘$ tale che per ogni $‘w‘$ appartenente a $‘L‘$ con $‘|w|>=n‘$ esistono $‘x,y,z‘$ tc $‘w=xyz‘$ :

1. $‘y\ne ϵ‘$
2. $‘|xy|\le n‘$
3. $‘x{y}^{k}z‘$ appartiene $‘L‘$ per ogni $‘k\ge 0‘$ Abbiamo una stringa media $‘y‘$ non vuota che puó essere replicata un numero arbitrario di volte sempre ottenendo un Liguaggio Regolare.
   • Esempio
     • $‘L=\{a^k{b}^k\mid k>=0\}‘$ non é regolare

1. dim

   • $‘L‘$ regolare

   • $‘A=(Q,\Sigma ,\delta ,q_0,F)‘$ tc $‘L=L(A)‘$

   • $‘n=|Q|‘$

   • $‘|w|>=n‘$ tc $‘w=a_1{a}_2...a_m‘$ con $‘m>=n‘$

   • Dopo $‘m‘$ passaggi lo stato $‘q_m‘$ deve essere finale per definizione

   • Il numero di stati attraversati sará $‘m+1‘$

   • $‘m>=n‘$ implica $‘m+1>n‘$ quindi gli stati attraversati non possono essere tutti distinti

   • $‘q_i=q_j‘$ ( $‘i<j‘$ ) é il primo stato che si ripete nel cammino dell’automa Allora concludiamo identificando $‘x,y,z‘$

   • $‘x=a_1{a}_2...a_i‘$

   • $‘y=a_{i+1}{a}_{i+2}...a_j‘$

   • $‘z=a_{j+1}{a}_{j+2}...a_m‘$

   1. $‘y!=ϵ‘$ in quanto $‘i<j‘$
   2. $‘|xy|<=n‘$ in quanto $‘q_i=q_j‘$ é il primo stato che si ripete e sono al massimo $‘n+1‘$
   3. $‘x{y}^{k}z‘$ appartiene a $‘L‘$ per ogni $‘k>=0‘$

Linguaggi Liberi dal Contesto

Le grammatiche libere sono un approccio generativo alle stringhe $‘L=a^n{b}^n\mid n\in \mathbb{N}‘$ non e’ regolare:

• e’ il inguaggio delle parentesi bilanciate

$‘G=(V,T,P,S)‘$ e’ una grammatica libera

• $‘V‘$ variabili o simboli non terminali
• $‘T‘$ terminali
• $‘P‘$ produzioni $‘A\to \alpha ‘$
  • testa
  • corpo
    • La riscrittura della $‘A‘$ in $‘\alpha ‘$ (sequenza arbitraria di simboli terminali o non) é libera dal contesto
• $‘S‘$ simbolo iniziale

Derivazioni:

• derivazione in un solo passo
• derivazione in zero o piu’ passi

Il potere riconoscitivo delle grammatiche libere e’ almeno tanto quanto quello dei linguaggi regolari

Derivazioni canoniche

• leftmost
  • $‘{\Rightarrow }_{lm}‘$
• rightmost
  • $‘{\Rightarrow }_{rm}‘$ Se esistono due derivazioni canoniche distinte (entrambe lm o rm) per la stessa stringa allora $‘G‘$ e’ ambigua

Alberi Sintattici

Derivazioni differenti possono generare lo stesso programma

• anche imponendo regole all’ordine delle riscritture

Gli alberi sintattici (alternativa alle generazioni) astraggono dall’ordine delle riscritture e permettono di ragionare sulla struttura delle stringhe

• grammatiche ambigue
  • piú alberi con lo stesso prodotto
  • non é avere derivazioni distinte che mi porta ad alberi diversi e quindi ambiguitá

Data una grammatica $‘G=(V,T,P,S)‘$ gli alberi sintattici di $‘G‘$:

• ogni nodo etichettato con una var in $‘V‘$
• ogni foglia etichettata da $‘V‘$ o $‘T‘$ o $‘ϵ‘$
• $‘ϵ‘$ significa unico figlio del genitore
• se un nodo $‘A‘$ i suoi figli sono etichettati (sx a dx)
  • $‘X_1,X_2,...,X_n‘$
  • $‘A\to X_1,X_2,...,X_n‘$ e’ una produzione in $‘P‘$

Il prodotto é la stringa ottenuta concatenando(sx verso dx) le etichette di tutte le foglie

1. Teorema $‘A{\to }_G^{\ast }\alpha ‘$ se e solo se esiste un albero sintattico di $‘G‘$ con radice $‘A‘$ e prodotto $‘\alpha ‘$

2. Risoluzione delle ambiguitá (grammatiche in forma infissa)

   • Precedenza degli operatori

   • Associativitá degli operatori

     • per operatori associativi questo non é un problema
     • lo é per altri operatori Soluzione ad hoc Utilizziamo associativitá a sinistra, sbilanciamo le espressioni e le stratifichiamo

   • Espressione = somma di termini

   • Termine = prodotto di fattori

   • Fattore = costante o espressione tra parentesi Nuova grammatica: $‘(\{E,T,F\},\{0,1,...,9,+,\ast ,(,)\},P,E)‘$ Produzioni:

   • $‘E\to T\mid E+T‘$

   • $‘T\to F\mid T\times F‘$

   • $‘F\to 0\mid 1\mid ...\mid 9\mid (E)‘$

3. Linguaggi inerentemente ambigui

   $$L=\{a^n{b}^n{c}^m{d}^m\mid n\ge 1,m\ge 1\}\cup \{a^n{b}^m{c}^m{d}^n\mid n\ge 1,m\ge 1\}$$

   Qualunque Grammatica che genera $‘L‘$ ha sempre almeno due derivazioni canoniche distinte che generano una stringa della forma

   $$a^n{b}^n{c}^n{d}^n$$

Pumping Lemma

Chiusura

1. Unione & Concatenazione SI dati $‘L_1=L(G_1)‘$ e $‘L_2=L(G_2)‘$ dove $‘V_1\cap V_2=\varnothing ‘$ costruiamo la grammatica $‘(V_1\cup V_2,T_1\cup T_2,P_1\cup P_2\cup \{S\to S_1\mid S_2\},S)‘$ che genera $‘L_1\cup L_2‘$ e la grammatica $‘(V_1\cup V_2,T_1\cap T_2,P_1\cap P_2\cap \{S\to S_1{S}_2\},S)‘$ che genera $‘L_1{L}_2‘$

2. Intersezione NO tra 2 Linguaggi Liberi $‘L_1=\{a^n{b}^n{c}^m\mid \ge 0\}‘$ $‘L_1=\{a^m{b}^n{c}^n\mid \ge 0\}‘$ Sono liberi ma $‘L_1\cap L_2=\{a^n{b}^n{c}^n\mid n\ge 0\}‘$ Non é libero, dimostrabile con il pumping lemma SI tra linguaggio Libero e linguaggio Regolare NB: L’intersezione non é piú un linguaggio regolare es. $‘L=\{a^n{b}^n\mid n\ge 0\}‘$ e $‘R=L(a^{\ast }{b}^{\ast })‘$ $‘L\cap R=L‘$ il quale non é regolare

3. Complemento & Differenza NO Se fossero chiusi per complemento allora $‘L_1\cap L_2=\overline{\overline{L_1\cap L_2}}=\overline{\overline{L_1}\cup \overline{L_2}}‘$ Contrario a ció dimostrato Il complemento é esprimibile per differenze e quindi nemmeno la differenza é chiusa

4. Inversione SI $‘G^R=(V,T,P^{R}S)‘$ dove $‘P^R=\{A\to {\alpha }^R\mid A\to \alpha \in P\}‘$ Si dimostra che $‘L(G^R)=L(G{)}^R‘$

JVM

Vedi: IJVM, Bytecode Instruction Listing Progetto: Translator.java

• Interprete bytecode
• macchina virtuale basata su pila
• basso e alto livello (gestione della pila / oggetti)
• Garbage Collector

Pipeline del corso: .lft $‘\to ‘$ .j $‘\to ‘$ .class $‘\to ‘$ output

Pila

Composta da Frames

• uno per ogni metodo in esecuzione
  • NB I metodi non statici hanno come primo argomento il riferimento all’oggetto ricevente
• argomenti e variabili riferite con il loro indirizzo nella pila
• Instruction Set Gestione della Pila
  • istore
  • iload
  • swap Aritmetica
  • ineg
  • iadd
  • isub
  • imul Gestione Array
  • newarray
  • arraylength
  • iaload
  • iastore Controllo del Flusso
  • goto
  • if_icmpeq
  • if_icmpne
  • if_icmple
  • if_icmpge
  • if_icmplt
  • if_cmpgt
  • invokestatic
  • return
  • ireturn

Espressioni

Aritmetiche

Logiche

Implementazione di Valutazione Corto-Circuitata

Problemi

la compilazione di un metodo comporta il calcolo della dimensione del suo frame

• variabili locali
• pila degli operandi

inoltre deve assicurarsi che se il tipo di ritorno é diverso da void ci sia un valore restituito Questo senza eseguire il codice, utilizzando l’analisi statica del codice Nello sviluppo ci occupiamo di

• metodi statici
• con tipo di ritorno int o void

Verifica del Return

Analisi di ogni cammino per verificare che alla fine di ogni metodo ci sia una istruzione return

• l’analisi é statica in quanto non tiene conto dell’effettivo flusso di esecuzione del metodo
  • non garantisce che il return sia eseguito
    • in caso di ciclo infinito
    • in caso di eccezione

Vengono fatte delle approssimazioni:

• non sono valutate espressioni booleane anche se banali: il problema é indecidibile
• non viene controllato se il tipo di ritorno é giusto o meno
  • necessita un’altra analisi dei tipi

Questo é implementato con un attributo

• S.ret
  • true se l’espressione di S termina é perché esegue una return
  • in caso di liste di Comandi
    • l’attributo é determinato dall’OR tra i Comandi che compongono la lista:
      • questa informazione puó essere utile per individuare la presenza di codice morto
        • warning o errore

Allocazione delle variabili locali

Il piú piccolo numero di slot necessari all’interno di un frame per la memorizzazione di argomenti e variabili locali

• determinare il numero massimio di variabili che sono contemporaneamente attive
  • tener conto della localitá delle variabili

Questo é implementato con un attributo

• S.locals
  • max{ S1.locals, S2.locals }
    • nel caso di if else o liste di comandi

Calcolo dimensione massima della pila

Numero massimo di slot occupati sulla pila degli operandi durante l’esecuzione di un metodo

• tenendo conto del codice prodotto
  • approssimare per eccesso la dimensione massima della pila

Implementato con l’attributo stack per E, B, S

• E.stack
  • >= 1
• E_list.stack
  • >= 0

NB L’associativitá a sinistra mantiene la pila piccola perché le sottoespressioni vengono valutate man mano che si incontrano da sinistra verso destra