Descrizione linguaggio

Introduzione

Per questa parte c’è un sacco di roba in comune con [Tecniche di definizione di semantica (4)

Trattiamo alcune caratteristiche che descrivono ad alto livello un linguaggio di programmazione. È da notare che questa parte della spiegazione del linguaggio non è limitante al solo linguaggio di programmazione, è utile per analizzare tutti i linguaggi (tranne la parte di implementazione)

Sintassi

Relazione fra segni. si occupa di decidere quando una frase è corretta.

Aspetto lessicale

Il lessico per una sintassi descrive le parole legali, In un linguaggio naturale il lessico è descritto solamente da dizionari. Se un vocabolo non esiste nel lessico di interesse, allora è erroneo, poi andremo a descrivere questo aspetto in modo formale

Vedere Scanner in appunti dopo

Aspetto grammaticale

Descrive la descrizione di frasi corrette a partire dal lessico, può essere utile in questo passo ricordarsi delle BNF [Sintassi e RI strutturali-

trattiamo-alcune-caratteristiche-che-descrivono-ad-alto-livello-un-linguaggio-di-programmazione.-è-da-notare-che-questa-parte-della-spiegazione-del-linguaggio-non-è-limitante-al-solo-linguaggio-di-programmazione,-è-utile-per-analizzare-tutti-i-linguaggi-(tranne-la-parte-di-implementazione)

###-sintassi-

relazione-fra-segni.-si-occupa-di-decidere-quando-una-frase-è-corretta.

aspetto-lessicale

il-lessico-per-una-sintassi-descrive-le-parole-legali,-in-un-linguaggio-naturale-il-lessico-è-descritto-solamente-da-dizionari.-se-un-vocabolo-non-esiste-nel-lessico-di-interesse,-allora-è-erroneo,-poi-andremo-a-descrivere-questo-aspetto-in-modo-formale

vedere-scanner-in-appunti-dopo

aspetto-grammaticale

descrive-la-descrizione-di-frasi-corrette-a-partire-dal-lessico,-può-essere-utile-in-questo-passo-ricordarsi-delle-bnf-[[sintassi-e-ri-strutturali) del corso di logica

Principalmente sono delle regole per costruire delle frasi che hanno un senso

Semantica

Ossia riguardo il significato di una frase sintatticamente corretta→ relazione fra segni e significato.

Linguaggio di appartenenza

Una stessa parola, a seconda della lingua di interpretazione, può avere significati diversi → FAME (fama, oppure fame?)

Voglio utilizzare questo linguaggio per calcolare la semantica di questo linguaggio basandomi su qualcosa che già esiste. (alla fine, per l’architettura esistente attuale, saranno sempre 0 e 1 di bits).

Pragmatica

Si occupa di studiare in quale modo le frase corrette sono utilizzate. Quindi va a rispondere a domande come “A cosa serve un costrutto?”, “Come si utilizza il comando”

Insieme di regole per dare un indirizzo di uso

Esempio: stile: non usare goto, scopo: questo comando fa quello e questo quindi usalo per….

Dato che principalmente la pragmatica non è presente al momento della creazione del linguaggio ma si evolve con l’uso di esso, non è molto interessante da questo punto di vista (+ sull’ingegneria del software).

Un altro esempio è tipo utilizzare lei, invece del tu in contesti formali

Esiste anche una pragmatica per la semantica Pragmatica

Il linguaggio eseguibile

Un linguaggio formale deve soddisfare alcune regole in più rispetto al linguaggio naturale, in particolare → l’implementazione.

Eseguire una frase sintatticamente corretta in modo semanticamente corretto.

Quindi si occupa dell’implementazione vera e propria del compilatore o dell’interprete del linguaggio. (In questo corso si faranno solo cenni, dato che non si implementerà tale linguaggio).

Lessico e frasi di un linguaggio

Alfabeto lessico e frasi

Definiamo ora alcune parole fondamentali per poter parlare di linguaggi in modo formale:

Alfabeto: a non-empty set of symbols/glyphs, typically thought of as representing letters, characters, or digits. (tipicamente finito, ma può essere anche infinito)

Lessico: un insieme di parole finite formate da lettere dell’alfabeto che consideriamo validi

Frasi: seguenze finite (o countably infinite, non vale per il lessico CREDO) di parole del lessico

Il linguaggio formale

Sia $A$ il nostro alfabeto, e $A^0 = \{ \varepsilon \}$, e $A^{n + 1} = A \cdot A^n$ con dot un operazione di concatenazione, allora L è un sottoinsieme solitamente finito di tutte le parole su $A$, ossia

$L \subseteq A^*$, $A^* = \bigcup_{n \geq 0}A^n$. Questo insieme si può creare con un insieme di regole, ma anche come elenco è corretto.

• Esempi di linguaggi

  

Numerabilità per alfabeti

Si può dimostrare che $A^*$ formato da alfabeti infiniti è ancora un infinito numerabile, si utilizza un argomento simile a Cantor spiegato in R e Intervalli e in Relazioni fra insiemi.

• Dimostrazione numerabilità di A-star

Questo dimostra che ogni unione di insiemi numerabili è numerabile. C’è una altra dimostrazione molto più semplice rispetto a questa costruzione di funzioni.

Praticamente numeriamo l’alfabeto finito che abbiamo, in ordine $\sigma_{1} \sigma_{2}, \dots, \sigma_{n}$ Allora questi hanno valore $1, \dots, n$, poi per le stringhe nella forma $\sigma_{1}\sigma_{2}, \sigma_{1}\sigma_{3}, \dots \sigma_{n}\sigma_{n}$ li metto anche ora in ordine di indice e inizio a contare da $n + 1$ e così via. Così so che ogni singola stringa del linguaggio ha un intero associato e posso dire che $A^{*}$ è numerabile.

Definizioni operazioni di base (6)

Lunghezza

Viene definita in modo ricorsiva in questo modo:

• Slide

  

Concatenazione

• Slide

  

Deve soddisfare principalmente 3 proprietà

1. La lunghezza della stringa risultante è uguale alla somma della lunghezza delle singole stringhe
2. prima parte della stringa risultato è uguale alla prima stringa
3. seconda parte della stringa risultato è uguale alla seconda stringa

Sottostringa, suffisso e prefisso

• Slide

  

È abbastanza banale dai, credo (in pratica posso prendere v in mezzo alla stringa di partenza mettendoci qualcosa prima e dopo

Potenza n-esima

• Slide

  

Ossia provo a concatenera sé stesso più volte

Operazioni di base su linguaggi (6)

Complemento

Unione

Intersezione

Concatenazione

Questo è la concatenazione a livello linguaggio, mentre prima era la concatenazione a livello stringa

Potenza

Chiusura / stella di Kleene / Ripetizione

Rappresentazione del linguaggio (2)

Generativo - sintetico

Non posso rappresentare un alfabeto infinito di caratteri! Ma posso memorizzare le regole che la generano. Per esempio posso memorizzare i numeri naturali con solamente gli assiomi di peano (in particolare mi bastano 2 delle 5 regole di peano

Riconoscimento - analitico

Sono le stringhe che vengono riconosciute da un automa che vedremo in seguito.

Ma non tutti i linguaggi sono riconoscibili da AUTOMI, resta il finito contabile come limite massimo, il motivo per cui è questo è perché le grammatiche sono equipotenti a $\N$, mentre tutti i linguaggi sono sottoinsieme di $\R$ e quindi non riesco a detectarlo.

• Slide grandezza di grammatiche ed alfabeti

  

Grammatiche e BNF

Def grammatica libera (4)

È una quadrupla di

1. Non terminali (insieme finito, indicato di lettere maiuscole)
2. Terminali (insieme finito, indicato da lettere minuscole)
3. Simbolo iniziale (simbolo speciale non terminale)
4. Produzioni (ricorda qui che la grammatica libera si può rappresentare con questa) Questa viene descritta in mood più formale in Linguaggi liberi e PDA.

Backus Naur-Form

In questa sezione cerchiamo di definire in modo più dettagliato le BNF introdotte nella lezione di logica di Sintassi e RI strutturali trattati in logica.

• Slide esempio di una BNF per palindromi

  

• Stesso precedente, ma scritto tramite la sintassi delle grammatiche

  

• Definizione tramite assiomi

  

• Definizione in via ricorsiva

  

Indichiamo con $L(P)$ il linguaggio generabile a partire da un P, con le regole di inferenza di sopra

L’unica differenza con le grammatiche libere è la sintassi differente per la descrizione di essa (utilizzo delle <>), ma storicamente credo che si siano evolute in modo distinto, e poi si sono accorti che erano la stessa cosa

Derivazioni (leftmost e rightmost)

Definizione di derivazione immediata

Sia $G = (NT, T, R, S)$ una grammatica libera da contesto, si dice che $v$ deriva immediatamente da $w$, indicato con $w \implies v$, quando $\exists (A \to z) \in R$, con $R$ le produzioni e $A \to z$ una produzione, e $w = xAy$, e $v = xzy$

In altre parole posso dire che una stringa è derivata in modo immediato da una altra stringa quando posso ricavarla con una singola operazione di una funzione presente in produzione.

• Slide definizione derivazione immediata

  

Definizione derivazione “generale”

Posso affermare che da $v$ si deriva $w$ quando esiste una sequenza finita (anche vuota) di derivazioni immediate tali che

$$ v \implies w_0 \implies ... \implies w $$

Tale cosa è riscritta come $v \Rightarrow^* w$

• Slide Definizione di Derivazione generale (!!!)

  

Derivazione left e rightmost

• Concetto di derivazione left e right most

  

Il concetto più generale è che nel processo di derivazione di una stringa in un linguaggio viene sempre espanso il non terminale più a sinistra.

Check appartenenza

Si può verificare che una stringa appartiene a un certo linguaggio descritto in modo formale come sopra se si può creare un albero di derivazione

• Esempio di derivazione

  

Linguaggio generato da grammatica

Data una grammatica $G = (NT, T, R, S)$ a contesto libero definiamo il linguaggio libero $L(G)$ generato dalla grammatica come

$$ L(G) = \{ w \in T^* : S \Rightarrow ^* w\} $$

Ossia in parole umane, tutte le stringhe terminali generabili da quella grammatica.

• Slide definizione

  

Alberi di derivazione

Un albero di derivazione è una rappresentazione molto utile per un compilatore per comprendere la struttura interna intermedia. fornisce informazioni semantiche!

[ \varepsilon \ A \to \varepsilon $$

Questo linguaggio genera solamente dei vuoti, ma lo può fare in modi diversi eg:

$S \to \varepsilon$, o $S \to A \to \varepsilon$

Una altra grammatica che descrive il linguaggi equivalente non è però ambiguo

$S \to \varepsilon$

Ambiguità nel linguaggio

Si può dire che un linguaggio è ambiguo se ogni sua grammatica è ambigua.

• Esempio di linguaggio ambiguo

  

Risoluzione delle ambiguità

In modo simile a quanto trattato in [Sintassi e RI strutturali-+-1-

una-altra-osservazione-importante-è-che-possiamo-associare-un-albero-di-derivazione-a-ogni-derivazione.

###-definizione-albero-di-derivazione-(5)-+-1-

vogliamo-descrivere-la-struttura-di-un-albero-di-derivazione-generale

1.-la-radice-è-il-non-terminale-iniziale-ossia-$s$ 2.-tutti-i-nodi-hanno-simboli-in-$nt-\cup-t-\cup-\{\varepsilon-\}$ 3.-i-nodi-interni-hanno-solo-simboli-$nt$ 4.-esiste-una-relazione-diretta-fra-padre-e-figli-definiti-da-una-produzione,-più-in-generale-se-$a\in-nt$-e–$x_1,...,-x_n$-sono-nodi-figli,-esiste-una-produzione-$a-\to-x_1,-...,-x_n$ 5.-se-$\varepsilon$-è-su-un-nodo,-allora-quella-è-una-foglia-ed-esiste-la-produzione-$a-\to-\varepsilon$,-con-a-l’etichetta-per-il-parent

inoltre-andiamo-a-chiamare-albero-di-derivazione-completo-se-ogni-foglia-è-un-terminale.

–slide

—-<img-src="/images/notes/image/universita/ex-notion/descrizione-linguaggio/untitled-26.png"-style=“width:-100%"-class=“center”-alt=“image/universita/ex-notion/descrizione-linguaggio/untitled-26”>

###-relazione-con-derivazione-

si-può-dimostrare-che-una-stringa-appartiene-a-un-linguaggio,-solo-se-esiste-un-albero-di-derivazione-per-essa-in-quel-linguaggio,-quindi-è-un-buon-metodo-per-descrivere-la-derivabilità-in-modo-non-ambiguo.

–idee-per-la-bigezione

—-chiaramente-se-vado-derivazione-→-albero-è-una-cosa-abbastanza-ovvia-perché-è-il-modo-con-cui-si-crea-l’albero

—-se-vado-nella-direzione-albero-→-derivazione-(dx,-sx)-sto-facendo-in-pratica-una-dfs-che-espande-sempre-il-primo-a-sinistra-o-primo-a-destra-di-non-terminali,-e-ho-anche-bisogno-di-una-funzione-che-sia-in-grado-di-restituirmi-una-stringa-data-dalle-foglie,-fatto-ciò-dovrebbe-essere-easy.

###-alberi-sintattici-

quando-abbiamo-un-albero-di-derivazione-completo,-possiamo-estrarre-l’albero-formato-dalle-foglie,-come-in-figura,-per-avere-un-albero-che-abbia-qualche-informazione-riguardo-la-semantica-di-quanto-descritto.

–esempio-estrazione-albero-sintattico

—-<img-src="/images/notes/image/universita/ex-notion/descrizione-linguaggio/untitled-27.png”-style=“width:-100%"-class=“center”-alt=“image/universita/ex-notion/descrizione-linguaggio/untitled-27”>

###-albero-di-sintassi-concreta-o-astratta

c’è-una-leggera-differenza-fra-sintassi-astratta-e-concreta.

di-sotto,-durante-la-risoluzione-delle-ambiguità-facciamo-uso-delle-parentesi-per-disambiguare,-questo-utilizzo-delle-parentesi-è-presente-nell’albero-di-sintassi-concreta,-anche-chiamato-parse-tree.

invece-l’albero-di-sintassi-astratta-può-essere-ambigua,-rappresenta-una-astrazione-sulla-sintassi-concreta-del-linguaggio-e-spesso-è-ambigua.

–email-mandata,-in-todo

—-albero-di-derivazione

—-è-l-albero-che-soddisfa-le-6-proprietà-presentate-(radice-è-il-non-terminale-iniziale,-i-nodi

—-interni-sono-etichettati-come-non-terminali,-etc..).

—-albero-di-sintassi-concreta

—-è-l-albero-che-rappresenta-tutta-la-sintassi-del-programma-(con-anche-zucchero-sintattico)

—-questo-albero-inoltre è-un-albero-di-derivazione perché-soddisfa-tutte-le-proprietà.

—-albero-di-sintassi-astrattaè-formato-solamente-dalle-foglie-dell-albero-di-sintassi-concreta,-senza-le-foglie-dovute-allozucchero-sintattico,-quindi-non-è-un-albero-di-derivazione-perché-non-soddisfa-le-proprietàdi-essa-(e.g.-nodi-interni-non-terminali)-e-contiene-informazioni-semantiche-riguardo-al-programma.

##-ambiguità

###-tipologie-di-ambiguità-(con-esempi-2)-

ambiguità-nella-grammatica

si-può-dire-che-una-grammatica-è-ambigua-se-esistono-due-alberi-di-derivazione-differenti-per-una-stessa-stringa.

–esempio-di-ambiguità-per-alberi-di-derivazione

—-<img-src="/images/notes/image/universita/ex-notion/descrizione-linguaggio/untitled-28.png”-style=“width:-100%"-class=“center”-alt=“image/universita/ex-notion/descrizione-linguaggio/untitled-28”>

–esempio-di-grammatica-ambigua

—-$$ —-s-\to-a-) bisogna stabilire:

1. Ordine di precedenza degli operatori

   • Esempio di problema di precedenza

     

2. Associatività sinistra o destra

   • Esempio di necessità di associatività dx e sx

     

3. Parentesi

   1. Questo è un zucchero sintattico che non ha nessun valore semantico che aiuta a disambiguare la precedenza. (L’albero semantico non serve avere le informazioni sulle parentesi)
   2. Questo è necessario per essere equivalente semanticamente ossia possono generare ora gli stessi alberi semantici

   • Aggiunta parentesi

     

Grammatica ambigua:

$$ S = a|b...|S + S|S\times S $$

Soluzione ambiguità

$$ E = E + T | T \\ T = A \times T | A \\ A = a|b ...| (E) $$