Notes

Memoria virtuale Perché è utile la MV? I programmi non usano tutta la memoria, ma pensano di averla tutta disponibile dal suo punto di vista. L’idea principale è che molte zone di memoria sono inutili per lungo tempo, possono essere utilizzati per altro. caricamento codice dinamico Per esempio anche a caricare il codice di un compilatore è diviso in fasi, se andiamo a caricare tutto, stiamo utilizzando solo un pezzo piccolo, tanta inefficienza, se una pagina contiene una parte del compilatore potrei caricare in memoria solamente le parti eseguite sul momento, giusto per fare un esempio diciamo. Crescita dei segmenti stack, heap, ad esempio ci permette di far crescere come ci pare la stack, e anche caricare solamente le parti della stack che ci servono, e mantenere la memoria libera per altro. Gestione degli errori. che utilizzerà i dati solamente della parte di gestione di memoria attuale diciamo. Paginazione a richiesta Questo è un aspetto della cache delle pagine di cui abbiamo già parlato in Livello OS. ...

Tipologie di control plane La control plane è la parte al livello di rete che si occupa di riempire le tabelle di instradamento dei router. In questo caso si possono in generare dividere gli algoritmi in due grandi famiglie Centralizzati, anche chiamati algoritmi LS( Link state) perché devono conoscere in che modo sono collegati i router fra di loro. Solitamente le SDN ossia software defined networking di cui abbiamo parlato in Data Plane utilizzano questi metodi, c’è un server centralizzato (che per ragioni di tolleranza può anche essere distribuito, però diciamo che è esterno al router la decisione) Distribuiti in cui nessuno ha informazioni complete sulla rete, ma è possibile scambiarsi informazioni sui vicini e congiungere così al percorso più breve. Vengono in questa sede utilizzati algoritmi di distance vector. Possono anche essere statici, ma dato che la topologia della rete è spesso dinamica è difficile che vengano utilizzati. Sono molto più preferibili gli algoritmi dinamici che vanno ogni tot ad aggiornare le tabelle. ...

DPDA Definizione (2) La definizione di DPDA è molto simile a quella trattata in Linguaggi liberi e PDA, con solo costraints sulla deterministicità, che si traducono in due condizioni: Al massimo posso avere un risultato per ogni coppia di lettura e simbolo su stack Se ho una transizione senza leggere, posso avere solo quella Slide Linguaggio libero deterministico Un linguaggio è libero deterministico se esiste un PDA che lo riconosce per stato finale. ...

In questa parte del nostro percorso nei linguaggi di programmazione proviamo ad espandere NFA e DFA in modo che possano riconoscere linguaggi come $ww^r | w \in \{a, b\}^*$ , con r maggiore o uguale a zero (r per dire che è il contrario di w) (questo linguaggio per il pumping lemma). Grammatiche libere da contesto $$ G = \langle \mathcal{N}, S, \Sigma, \mathcal{R} \rangle $$ Dove $\mathcal{N}$ sono i non terminali, $S$ è il non terminale iniziale, $\Sigma$ sono l’alfabeto dei simboli finali e $\mathcal{R}$ le relazioni possibili. Spesso lo scriviamo solo tramite le relazioni, perché è la forma più compatta. I nodi di una derivazione da grammatica libera da contesto è chiamato costituente del linguaggio. Questo è più importante in linguistica. ...

LR(k) Grammatiche LR(k) Anche in questo caso proviamo a generalizzare il concetto dei pirmi k caratteri, in modo da generalizzare in qualche senso il concetto di LR(k), quindi andiamo a modificare la closure considerando ora first k Per ricordarti come si calcolava first k, andare a guardare Top-down Parser il problema che poi diventa pratico riguardo questo è l’impossibilità di gestire stringhe lunghezza k che sono una assurdità (esponenziale per la lunghezza) ...

Definizione ed esempi per macchine astratte Una macchina astratta è un qualunque insieme di algoritmi e strutture di dati che permettono di memorizzare ed eseguire il linguaggio $L$, quindi una macchina astratta esiste per esguire il proprio linguaggio (inteso come insieme finito di istruzioni primitive che riesce ad comprendere e eseguire). Si può proprio dire che esiste una simbiosi fra macchina e linguaggio. Si potrebbe dire che la macchina fisica è soltanto una implementazione FISICA di un linguaggio, ossia una macchina che capisce ed esegue quel linguaggio e che sia solamente un caso particolare della macchina astratta. ...

I Nomi e oggetti Oggetti denotati e identificatori I nomi sono sequenze di caratteri o numeri aka: token alfanumerico (anche IDENTIFICATORE (per token guardare Grammatiche Regolari) utilizzate principalmente come Astrazione sul controllo e sui dati (quindi sono cose molto più facili da ricordare rispetto il suo encoding binario o a indirizzi). Infatti utilizziamo i nomi per evitare di interessarci di informazioni come l’indirizzo di memoria del nostro dato o per creare una interfaccia con visibili solo nome della procedura e parametri. ...

Gestione del non determinismo Il modo più facile per gestire il non determinsmo è semplificare le grammatiche quindi andiamo a vedere metodi per fare ciò. Semplificazione grammatiche (5) Slide No produzioni del tipo $A \to \varepsilon$ per bottom up (altrimenti va all’infinito!) No produzioni unitarie, così evito cicli in cui da A derivo sé stesso. No simboli inutili No ricorsione sinistra (divergenza per top-down) Fattorizzazione della grammatica Eliminazione delel produzioni nulle Vogliamo creare un algoritmo utile ad eliminare le produzioni che non ci piacciono. ...

Top-down Algoritmo di parsing Slide Questo si potrebbe considerare come algoritmo classico di parsing con non determinismo. (vado avanti, ed esploro tutto, senza look ahead). Esempio di esecuzione Commenti efficienza di sopra È molto inefficiente, in particolare si potrebbe trovare una compessità esponenziale del tipo $O(b^{|w|})$, con b il massimo numero di produzioni. (la produzione maggiore la espando sempre!) Slide ...

Espressioni, Comandi, Ricorsione Espressioni Con espressione intendiamo una entità sintattica, che una volta valutata ritornerà un valore, oppure non termina, in questo caso si dice che la espressione è INDEFINITA. Questa è una definizione è leggermente ambigua dato che non abbiamo una definizione precisa di valutazoine, che è fortemente dipendente dalla macchina astratta in cui viene eseguito. Notazioni (sintassi possibili) (3) Notazione infissa Questa è la notazione classica matematica, per cose tipo $a -b$, in cui l’operando sta nel mezzo degli operatori. ...