Giter Club home page Giter Club logo

appunti-lfc's Introduction

Appunti di Linguaggi Formali e Compilatori

logo

Indice

Il progetto

Questo testo è una dispensa di appunti scritta da studenti; lo scopo è quello di raccogliere i contenuti del corso di Linugaggi Formali e Compilatori e organizzarli secondo un'esposizione quanto più completa, efficace ed intuitiva possibile, tanto per lo studente desideroso di ottenere un'ottima padronanza degli argomenti, quanto anche per lo studente pigro in cerca di risorse per "portare a casa" l'esame.

Gli appunti sono stati presi durante il corso di Linguaggi Formali e Compilatori tenuto dalla professoressa Paola Quaglia per il Corso di Laurea in Informatica, DISI, Università degli studi di Trento, anno accademico 2020-2021. I contenuti provengono quindi primariamente dalle lezioni della professoressa, mentre invece ordine ed esposizione sono in gran parte originali. Allo stesso modo, la maggior parte degli assets (figure, grafi, tabelle, pseudocodici) sono contenutisticamente tratti dal materiale della professoressa, ma ricreati e molto spesso manipolati dagli autori; inoltre, per ottenere il risultato appena citato, è stato molto spesso necessario abbandonare quasi del tutto l'esposizione della professoressa e usarla, appunto, come canovaccio per svilupparne una originale.

Maggiori informazioni sul progetto e e sugli autori possono essere trovate nella prefazione dell'elaborato.

Segnalazione errori

Se durante la lettura doveste incorrere in errori di qualsiasi tipo, tra gli altri errori di battitura, errori concettuali o di impaginazione, vi chiediamo di fare una segnalazione; ve ne saremo riconoscenti e provvederemo a correggere quanto prima. Se siete arrivati a questo punto assumiamo una buona familiarità con Github, per cui come canali per segnalare errori:

  • aprire una Github issue, se possibile referenziando all'interno del corpo anche la porzione di codice in cui è presente l'errore
  • se volete direttamente proporre un vostro fix, potete clonare la repo (istruzioni per la build qui) e aprire una pull request con i commit che risolvono l'errore, vi daremo un riscontro quanto prima

Se preferite non segnalare l'errore tramite Github potete comunque contattarci personalmente tramite gli indirizzi email che trovate sui nostri profili Github, oppure con la mail istituzionale [email protected], o naturalmente con mezzi più informali.

How to build

Standard build chain

Prerequisiti:

  • una distribuzione TeX, ad esempio MiKTeX o TeXLive
  • pip, per cui assicuratevi di aver installato Python
  • se volete compilare utilizzando il tool Arara, allora dovrete avere una JVM installata

A questo punto:

  1. clonate la repository con git clone https://github.com/filippodaniotti/Appunti-LFC
  2. installate il pacchetto Pygments con pip install Pygments
  3. compilate, ad esempio:
    • lanciando tre volte pdflatex -shell-escape main.tex
    • lanciando latexmk -pdf -shell-escape main.tex
    • per una compilazione rapida, potete utilizzare Arara con arara main.tex (dovete necessariamente trovarvi nella directory ~/src/), sarà equivalente a lanciare una sola passata di pdflatex

È possibile compilare singolarmente ogni capitolo e ogni asset, è sufficiente lanciare la compilazione sul singolo .tex desiderato.

Se lavorate con degli IDE o con degli editor in coppia con dei tool per la scrittura LaTeX (e.g. VS Code + LaTeX Workshop o Atom + latex), assicuratevi di attivare il flag -shell-escape dalle impostazioni di compilazione del vostro tool.

How to build with Docker

Se non disponete dei prerequisiti per la build indicati sopra (o non volete installarli system-wide), potete buildare con docker.
Se poi avete sia VS Code che Docker, potete riferirvi a questo gist per una configurazione già pronta.

Prerequisiti:

  • Docker
  • almeno 5/6 GB liberi su disco

Procedimento:

  1. clonate la repository con git clone https://github.com/filippodaniotti/Appunti-LFC
  2. se non siete su linux, buildate l'immagine docker contenuta nel Dockerfile con docker build -t dispensa_lfc .
    Nel caso siate su linux, usate questo comando per buildare docker build -t dispensa_lfc --build-arg UID=$(id -u) --build-arg GID=$(id -g) . (si assicura che il vostro userId e groupId corrispondano a quelli che il container userà)
  3. avviate un container, ricordandovi di montare la cartella della dispensa/ Esempio: docker run -ti --rm -v $(pwd):/dispensa --name dispensa_lfc dispensa_lfc
  4. ora avete accesso ad un ambiente con tutte le dipendenze installate e potete buildare usando i comandi della sezione how to build (ad eccezione di Arara, perché il container non ha una JVM installata)

Principali pacchetti impiegati

  • standalone per gestire la compilazione autonoma di capitoli e assets
  • tabularx per la gestione delle tabelle
  • forest per la generazione degli alberi
  • tikz con librerie automata per la generazione dei grafi
  • algorithm2e per la scrittura degli pseudocodici
  • minted per la scrittura di codice

La squadra

appunti-lfc's People

Contributors

bigemperor26 avatar civts avatar euberdeveloper avatar fedeizzo avatar filippodaniotti avatar francescobozzo avatar samaretas avatar simone-alghisi avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

appunti-lfc's Issues

Automa production wrong

Figure 8.5 (Figura 8.5: Automa Caratteristico per la Bottom-Up Parsing Table) on page 158 has b transiction from state 3 to state 7. This is wrong. In the original automa the transition is trought d.

Labels refactoring

L'idea è di utilizzare convenzioni molto forti sulla definizione e uso delle labels.

In particolare, vorrei che le labels fossero assegnate a:

  • ogni asset importato nel documento;
  • tutte le equazioni non anonime;
  • tutti quei marker di sezione che lo dovessero richiedere.

Ogni label dovrà avere il seguente formato \label{type:file-name}, dove:

  • type (tutto in minuscolo) indica il "tipo" dell'elemento cui la label è assegnata, quali ad esempio: fig, alg, tab, eq, subsec, etc;
  • file-name è il nome dell'asset, se l'elemento è un asset;
  • il formato per gli elementi che non sono asset verrà specificato a breve.

Nel testo si dovranno usare le labels nel seguente formato Type.\ref{label}, con il tipo di elemento capitalized.

Fix Fig 1.5

Nel test si dice che la Fig. 1.5 contiene il parse tree sulla destra mentre il codice intermedio sulla sinistra, tuttavia viene visualizzato solo il parse tree. Ho dato un occhiata al sorgente e sembra ok (?)
Schermata 2020-10-30 alle 16 18 42

Revisionare lec-05

È la sezione sugli esercizi di applicazione del pumping lemma for free languages e attualmente è un po' un blocco di testo monolitico, e manca in generale di un po' di dettaglio.

\subsection{Applicazioni}
Qui passiamo alle applicazioni del \emph{Pumping Lemma}. In particolare può essere utilizzato per provare che un linguaggio \(\mathcal{L}\) non è libero.
In generale, da un'implicazione logica del tipo \(A \implies B\), è possibile ottenere la negazione \(\neg A \implies \neg B\). Nel nostro caso, da \(\mathcal{L}\) libero \(\implies\) Tesi del \emph{Pumping Lemma}, abbiamo \(Not\) tesi del \emph{Pumping Lemma} \(\implies\) \(\mathcal{L}\) \(Not\) libero.
La negazione della tesi del \emph{Pumping Lemma} è la seguente:
\begin{itemize}
\item \(\forall p \in \mathbb{N}^+\) tale che
\item \(\exists z \in \mathcal{L} : |z| > p\), allora
\item \(\forall u, v, w, x, y\) tale che:
\begin{itemize}
\item \(z = uvwxy \textrm{ } \land\)
\item \(|vwx| \leq p \textrm{ } \land\)
\item \(|vx| > 0 \textrm{ }\land\)
\item \(\exists i \in \mathbb{N}.uv^iwx^iy \not\in \mathcal{L}\)
\end{itemize}
\end{itemize}
Lasciamo al lettore immaginare gli altri modi in cui è possibile riscrivere la negazione della tesi del \emph{Pumping Lemma} applicando le basi di algebra booleana.
Passiamo dunque ad esempi pratici.
ES 1
Sia \(\mathcal{G}\) così definito
\(S \rightarrow aSb \ abc\)
\(cB \rightarrow Bc\)
\(bB \rightarrow bb\)
ci chiediamo dunque se \(\mathcal{G}\) è \emph{context dependent} o \emph{free}. Ovviamente è \emph{context dependent}.
Ci chiediamo quale sia il linguaggio generato da \(\mathcal{G}\), \(\mathcal{L(G)}\) ed è \({a^n b^n b^n | n>0}\)
Ci chiediamo infine se il linguaggio \(\mathcal{L(G)}\) sia o meno un linguaggio libero. Per farlo possiamo semplicemente utilizzare la negazione del \emph{Pumping Lemma} per dimostrare che \(\mathcal{L(G)}\) non è libero.
Sia \( p \in N^+\) un numero intero arbitrario
Possiamo prendere un numero \(z=a^pb^pc^p \in \mathcal{L}\) che soddisfa la condizione \(|z|\leq p\)
Quindi possiamo prendere qualsiasi decomposizione di \(z = uvwxy, |vwx|\leq p |vx|>0\).
Sappiamo che la parola \(z\) è composta in questo modo. \(\underbrace{aa...a}_\text{\emph{p}}\underbrace{bb...b}_\text{\emph{p}}\underbrace{cc...c}_\text{\emph{p}}\).
La sottostringa \(vwx\) deve essere sicuramente in una di queste possibili posizioni
\(a\underbrace{a...a}_\text{\emph{vwx}}
a\underbrace{a...abb...b}_\text{\emph{vwx}}
b\underbrace{b...b}_\text{\emph{vwx}}
b\underbrace{b...bc...c}_\text{\emph{vwx}}
c\underbrace{c...c}_\text{\emph{vwx}}c\)
da cui abbiamo che qualsiasi sia la posizione di \(vwx\) all'interno della parola \(z\) è possibile costruire una parola con un numero non bilanciato di \(a,b,c\) semplicemente ponendo \(v^i,x^i,i=0\)
Dunque troviamo una parola che non appartiene al linguaggio. Se il linguaggio fosse libero, tutte le parole costruite in questa maniera dovrebbero appartenere al linguaggio. Dunque il linguaggio non è
\emph{free}
Passiamo dunque ad un altro esempio riprendendo l'esercizio lasciato per casa a suo tempo
ES 2
\(S \rightarrow CD \)
\(C \rightarrow aCA | bCB \)
\(AD \rightarrow aD \)
\(BD \rightarrow bD \)
\(Aa \rightarrow aA \)
\(Ab \rightarrow bA \)
\(Ba \rightarrow aB \)
\(Bb \rightarrow bB \)
\(C \rightarrow \epsilon \)
\(D \rightarrow \epsilon \)
Si verifica facilmente che il linguaggio generato da tale grammatica è \(\mathcal{L(G)} =\{ww | w\in\{a,b\}^*\}\)
Ci chiediamo allore se tale linguaggio sia libero o meno
Un lettore naive potrebbe essere portato ad applicare la proprietà di chiusura dei linguaggi liberi rispetto alla operazione di concatenazione per dimostrare che suddetto linguaggio sia libero, in quanto sappiamo che \(\mathcal{L'(G)} =\{w | w\in\{a,b\}^*\}\) è un linguaggio libero. Tuttavia l'operazione di concatenazione non rispetta la proprietà di palindromia di \(\mathcal{L}\).
È infatti semplice provare che \(\mathcal{L}\) non è libero
DIM
Sia \(\mathcal{L}\) libero
sia \(z=a^pb^pa^pb^p, z\in \mathcal{L}, z=uvwxy, |vwx|\leq p \)
Per esempio supponiamo sia \(|vwx|=b^p\), allora ic è facile prendere \(uv^0wx^0y\) e verificare che questo non può avere la forma \(a^pb^pa^pb^p\)
Dunque abbiamo trovato un elemento che contraddice il \emph{Pumping Lemma} e dunque l'ipotesi iniziale non è valida, ovvero \(\mathcal{L}\) non è \emph{free}

Error in example

image

In questo caso, se io avessi "abababab", alla fine otterrei una pila vuota, quindi il procedimento "passerebbe", anche se la parola non appartiene al linguaggio (a^n)(b^n). Può essere che mi sbagli, ma il procedimento dia sempre dei negativi giusti, ma che abbia dei falsi positivi.

Appendice A: Foglio di esercizi 1

La professoressa ha rilasciato un foglio di esercizi simili a quelli che potremmo trovare nella prima parte dell'esame; sarebbe interessante svolgerli per bene, descriverne dettagliatamente il procedimento e presentarlo in un'appendice a fine testo.

  • Risoluzione degli esercizi su supporti meno raffinati di LaTeX
  • Impaginazione LaTeX

Labels refactoring

Servirebbe fare un bel refactoring delle labels, stabilendo delle convenzioni moderatamente forti sia su:

  • formato: come devo chiamare la label che si riferisce al terzo esercizio sull'applicazione della subset construction? sc-es-3? sc_ex_3?
  • utilizzo: quali sono le situazioni in cui è opportuno usare references alle labels? Potremmo ad esempio pensare di utilizzarle sempre per riferirci alle immagini, data l'imprevedibilità del comportamento di LaTeX con il loro posizionamento nel testo.

Refactoring stile tabelle

Alcune tabelle sarebbero molto più chiare se aggiungessimo delle vertical rules, come ad esempio le seguenti, riguardanti gli esercizi sulla subset construction.
novrule
vruled

Capitolo 8 pagina 170

Nell'ultimo passaggio dell'algoritmo shift reduce manca la S nel symSt dopo aver effettuato la riduzione S -> aABe
Schermata 2021-01-02 alle 14 48 08

Errore formattazione esercizio 3.4

Nell'esercizio 4 alla fine del terzo capitolo c'e' un errore nella consegna:
scrot-2020-12-18_15:33:14
L'ultima k di entrambi i linguaggi dovrebbe stare all'esponente di c assieme al 2

Typo capitolo 8

Lista dei typo trovati durante la lettura del capitolo 8 (post-refactoring):

  1. riga 10 pagina 142 "la andremo ..."
  2. penultima riga pagina 144 "per fare in questo"
  3. ultima riga prima dello pseudocodice pagina 146 "due volte di fila due punti"
  4. punto 1 pagina 147 "calcoliamo il la chiusura"
  5. riga 5 pagina 149 "gli stessi item; in questo casp"
  6. riga 4 sezione 8.4 pagina 159 "l'algoritmo di s/r viene uisto"
  7. nota 5 pagina 163 interrotta sul piu' bello per poi tornare nella pagina dopo
  8. nota 6 pagina 169 "meglio tenere la conscienza"
  9. nota 7 pagina 170 "QUesta frase"

Revisione capitoli 1 e 2

La formattazione attuale fa schifo, c'è l'identazione di paragrafo senza separazione del testo praticamente ogni due righe.

  • Capitolo 1
  • Capitolo 2

Utilizzo di \emph{}

Dobbiamo decidere una prassi comune per l'utilizzo del comande \emph{} e in base a tale decisione ristrutturare l'intera dispensa.
Al momento l'utilizzo di tale comando è abbastanza randomico.

Errore Tabella 10.1

Nella tabella mancano le seguenti entry:

  • Tab[7,digit]=s6
  • Tab[7,F]=4
    Che corrispondono agli archi colorati in rosso in figura
    immagine

Risoluzione labels per gli pseudocodici

Gli pseudocodici non hanno alcuna label assegnata e, di conseguenza, non è possibile referenziarli attraverso il consueto comando \ref{<label>}.
Inoltre, il pacchetto algorithm2e prevede la possibilità di fare riferimenti alle righe stesse, per cui si potrebbe considerare di implementare anche questa funzionalità.

Bisogna spiegarlo

Bisogna spiegarlo
image

\begin{figure}[H]
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_a.tex}
\subcaption{step by step by mike by bisognaspiegarlo}
\label{pl-es4-sbs_1}
\end{minipage}
\hfill
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_b.tex}
\subcaption{step by step by mike by bisognaspiegarlo 2}
\label{pl-es4-sbs_2}
\end{minipage}
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_c.tex}
\subcaption{step by step by mike by bisognaspiegarlo 3}
\label{pl-es4-sbs_3}
\end{minipage}
\hfill
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_d.tex}
\subcaption{step by step by mike by bisognaspiegarlo 4}
\label{pl-es4-sbs_4}
\end{minipage}
\caption{}
\end{figure}

Assets names refactoring

Vorrei stabilire delle convevnzioni abbastanza forti sui nomi dei file degli assets.

Al momento non ho ancora idee precise, se non che vorrei utilizzare solamente lettere minuscole, dashes e underscores.

Ricreare gli alberi di if-else in LaTeX

Queste due figure dovrebbero essere ricreate in LaTeX con dei pacchetti appositi (forse forest può essere il pacchetto giusto, ma non ci metterei la mano sul fuoco)
dangling_else_1
dangling_else_2

\begin{figure}
\centering
\includegraphics[width=.7\textwidth,keepaspectratio]{dangling_else_1.jpg}
\caption{Primo albero di derivazione per Eq. \ref{dangling_else}}
\label{dangling_else_1}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=.7\textwidth,keepaspectratio]{dangling_else_2.jpg}
\caption{Secondo albero di derivazione per Eq. \ref{dangling_else}}
\label{dangling_else_2}
\end{figure}

[Enhancement] Includere PDF nella repo

Per quanto il source sia importante e fondamentale non mi è chiara la scelta di non includere direttamente un pdf compilato all'interno della stessa repo.

Consiglio di settare una action in modo che il pdf sia automaticamente ricompilato ad ogni cambiamento

Edit, ho notato solo ora che la action è già settata ma non vi è alcun pdf in /src :(

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.