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. ...
Ripasso Prox: 10 Ripasso: May 29, 2023 Ultima modifica: May 19, 2023 10:33 AM Primo Abbozzo: May 8, 2023 9:20 AM Stato: 🌕🌕🌕🌕🌑 Studi Personali: No Elementi di ripasso Object orientation il tipo di dato astratto Introduzione Per questi tipi di dato non ci interessa di sapere cosa ci sia sotto (storato come bit? storato come sabbia boh), ci interessa solamente che abbia quei metodi, che possiamo in un certo senso identificare come la sua capsula, opaca in questo caso. ...
Introduzione Monoforfo Quando non posso utilizzare un tipo come parametro. Ossia non possiamo definire una funzione generica. Slide monomorfismo Polimorfismo Polimorfismo, come dice il nome, significa avere tante forme, in questo caso tanti tipi. Ma avere tanti tipi non è una cosa ambigua? Questa cosa si risolve solitamente a compile time (facendo checks di sottotipo, oppure dispatch della funzione corretta). Tipologie di Polimorfismo (3) Slide tipologie di monomorfismo ad-hoc polymorphism questo è anche chiamato overloading in cui vado a definire un nuova funzione (con lo stesso nome) che accetti il nuovo tipo di dato. ...
Vincoli sintattici contestuali Intro: dipendenze da contesto I vincoli sintattici non sono esprimibili tramite BNF perché dipendono dal contesto, mentre le grammatiche libere sono per definizione libere da contesto, vogliamo quindi trovare una soluzione a questo problema. Vengono usati metodi Ad-Hoc nella fase di analisi semantica del programma. Grammatiche dipendenti dal contesto Queste grammatiche sono molto più complicate (e lente) rispetto a quelle libere da contesto, quindi è poco pratico e non utilizzabile (tempo esponenziale, quindi non finisce mai). ...
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. ...
Ripasso Prox: 30 Ripasso: June 6, 2023 Ultima modifica: May 14, 2023 6:13 PM Primo Abbozzo: March 13, 2023 9:20 AM Studi Personali: No Elementi di ripasso Teoria dei Tipi Introduzione Definizione Un metodo sintattico praticabile per dimostrare l’assenza di determinati comportamenti del programma, fatto classificando le unità sintattiche in base ai tipi di valore che assumono Vogliamo che fosse praticabile nel senso che effettivamente lo possiamo implementare, cioè ci permettono di avere certe tipologie di garanzia. ma ancora è una definizione molto ampia. E di solito si può fare una analisi statica del comportamento del programma. ...