Base concepts

Formal language

Da un punto di vista algebrico, un linguaggio formale (vedi [SAKH2019b]) è una tupla di:

  • un insieme finito di simboli (alfabeto), su cui è costruito il linguaggio;
  • un insieme finito di regole di produzione, che specificano quali sequenze dei simboli predetti fanno parte del linguaggio (sintassi).

Più in generale (vedi [SLKU1995] pag.1) la definizione di un linguaggio richiede l’individuazione di tre componenti:

  • la sintassi, ovvero come combinare i simboli per creare frasi accettabili (nota: accettabili, non significative) per il linguaggio;
  • la semantica (vedi il capitolo relativo), che individua il significato associato alle frasi sintatticamente valide;
  • la pragmatica, ovvero gli aspetti del linguaggio che coinvolgono l’utente; ad esempio l’accettabilità di una frase in relazione alla sensibilità dell’utente (si pensi al turpiloquio o alla blasfemia).

La sintassi è il primo aspetto da definire: non è possibile fare analisi semantica (ovvero attribuire significati) alle frasi malformate. A questo scopo è necessario definire la grammatica del linguaggio.

Formal grammar

Una grammatica formale (vedi [SLKU1995] pag.2) è una quadrupla \(< \Sigma, N, P, S >\) composta da:

  • un insieme finito \(\Sigma\) di simboli terminali, che formano l'alfabeto del linguaggio, usato per comporre le frasi;
  • un insieme finito \(N\) di simboli non terminali, che formano le categorie sintattiche, ognuna delle quali rappresenta gruppi di componenti delle frasi;
  • un insieme finito \(P\) di regole, o produzioni, che descrivono le relazioni che i simboli terminali o non terminali devono avere tra loro per comporre frasi del linguaggio;
  • un simbolo di partenza \(S\) che specifica quale categoria viene definita, ad esempio un programma, o una frase.

Se l’alfabeto include i simboli terminali del linguaggio in osservazione, il suo vocabolario include tutti i simboli: terminali e non terminali.

Usualmente i simboli non terminali sono indicati nella forma “<nome della categoria>”.

Mentre le regole di produzione solitamente sono nella forma:

α ::= β

La precedente indica che l’espressione α può essere sostituita dall’espressione β.

Ad esempio una produzione potrebbe essere:

<dichiarazione> ::= var <lista di variabili> : <tipo>;

dove “var”, “:” e “;” sono simboli terminali del linguaggio. Il simbolo “::=” è parte del metalinguaggio [1] ed indica che la categoria (nota: è un non terminale) a sinistra può essere composta come indicato a destra.

In pratica la regola precedente recita: “una dichiarazione può essere formata dalla parola chiave var seguita da una lista di variabili, seguito dal simbolo : (due punti), seguito dalla indicazione del tipo”.

Questo modo di indicare le produzioni è detto forma di Backus-Naur, spesso abbreviato in BNF.

Questi concetti sono stati formalizzati originariamente da Noam Chomsky (vedi [CHOM1957]).

Lo stesso N. Chomsky ha classificato le grammatiche secondo alcune caratteristiche delle loro regole, definendo le seguenti classi ([SLKU1995] pag.3, 4):

  • type 0 o grammatiche senza restrizioni (unrestricted grammars);
  • type 1, grammatiche sensibili al contesto (context-sensitive grammars);
  • type 2, grammatiche libere dal contesto (context-free grammars);
  • type 3, grammatiche regolari (regular grammars).

Le grammatiche predette vanno dal tipo più generale (le type 0) a quello via via più specifico: le type 3 sono le più restrittive.

Unrestricted grammars

Sono le grammatiche di tipo più generale. L’unica imposizione è la presenza di almeno un elemento non terminale nel lato sinistro di una produzione α ::= β. Ad esempio:

a <qualcosa> b ::= b <qualcosaltro>

dove le lettere a e b sono terminali, mentre <qualcosa> e <qualcosaltro> sono non terminali.

Context-sensitive grammars

Se aggiungiamo la condizione che la parte destra della produzione contenga un numero di simboli uguale o superiore al numero di simboli nella parte sinistra, abbiamo una context-sensitive grammar. Ad esempio:

<qualcosa> b ::= b <qualcosa>

Si possono avere anche regole del tipo: \('\alpha <\negthickspace B \negthickspace > \gamma ::= \alpha \beta \gamma'\)

L’appellativo context-sensitive deriva dal fatto che la sostituzione di un simbolo non terminale tramite la regola di produzione, dipende dai simboli circostanti.

Context-free grammars

In questo caso le regole di produzione a sinistra possono avere un singolo non terminale, con la forma <A> :: = α, dove <A> e α sono non terminali, ma α contiene almeno un terminale.

Ad esempio, può essere:

<expr> ::= <expr> * <term>

dove il simbolo «*» è un terminale.

Queste grammatiche corrispondono alle grammatiche BNF.

Regular grammars

Queste sono le grammatiche più restrittive. Impongono di avere regole di produzione che a destra:

  • hanno un terminale,
  • oppure un terminale seguito da un non terminale.

cioè come segue:

  • <A> ::= a ;
  • oppure <A> ::= a <A>.

Semantics

Come accennato nei linguaggi formali, la semantica ([WIKI2019c]) consiste nell’assegnare un significato alle frasi sintatticamente valide.

Esistono fondamentalmente tre diversi approcci per effettuare questa operazione in modo formale:

L’approccio axiomatic semantics definisce il significato di una frase tramite affermazioni logiche (formali), ovvero predicati con variabili.

La denotational semantics assegna alla frase dei costrutti matematici (ad es. insiemistici) che ne esplicitano il significato. E' possibile osservare un esempio di applicazione di denotational semantics alla interpretazione delle espressioni regolari.

La operational semantics assegna alla frase delle regole di induzione dalle quali derivare il significato. Se nel fare questa operazione, si opera su ogni singolo costituente del discorso, allora si usa la structural operational semantics; invece se si astrae dai singoli costituenti, per arrivare direttamente al significato finale, si è applicata la natural semantics. Si può osservare un esempio d’uso di structural operational semantics nel capitolo relativo alla interpretazione del CCS tramite la SOS.

Deterministic finite automaton

Un automa a stati finiti deterministico, è una macchina a stati finiti che accetta una sequenza di simboli (comandi) e produce un calcolo univoco per ogni sequenza di input ammessa.

Formalmente (vedi [WIKI2019a]), è una quintupla \(M = (Q, \Sigma, \delta, q_0, F)\) dove:

  • \(Q\) è un insieme finito di stati;
  • \(\Sigma\) è un insieme finito di simboli di input, detto alfabeto;
  • \(\delta\) è una funzione di transizione definita come: \(\delta : Q \times \Sigma \rightarrow Q\);
  • \(q_0\) è lo stato di partenza, vale \(q_0 \in Q\);
  • \(F\) è un insieme di stati finali, vale \(F \subseteq Q\).

Data una stringa \(w = a_1 a_2 \cdots a_n\) sull’alfabeto \(\Sigma\), l’automa M accetta la sequenza w se esiste una sequenza di stati \(r_0, r_1, \cdots r_n\) tale che:

  1. \(r_0 = q_0\);
  2. \(r_{i+1} = \delta(r_i, a_{i+1}), \, per \, i = 0, 1, \cdots n -1\);
  3. \(r_n \in F\).

Nondeterministic finite automaton

Un automa a stati finiti non deterministico (vedi [WIKI2019b]), è una macchina a stati finiti analoga all’automa a stati finiti deterministico, con una differente tipo di funzione di transizione.

Abbiamo: \(M = (Q, \Sigma, \Delta, q_0, F)\) dove:

  • \(Q\) è un insieme finito di stati;
  • \(\Sigma\) è un insieme finito di simboli di input, detto alfabeto;
  • \(\Delta\) è una funzione di transizione definita come: \(\Delta : Q \times \Sigma \rightarrow P(Q)\) dove P(Q) è l’insieme delle parti di Q;
  • \(q_0\) è lo stato di partenza, vale \(q_0 \in Q\);
  • \(F\) è un insieme di stati finali, vale \(F \subseteq Q\).

Si nota che la funzione di transizione, qui ha come codominio P(Q), ovvero l’insieme delle parti di Q. Quindi la funzione di transizione in questo caso non determina univocamente un solo stato nel codominio Q, ma un gruppo di possibili stati: una parte di Q.

Equivalence classes

Dato un insieme A, e una relazione di equivalenza in esso; possiamo prendere un elemento a dell’insieme e considerare tutti gli altri elementi in esso presenti, per i quali vale la relazione di equivalenza predetta.

L’insieme formato da a e dai suoi equivalenti é la classe di equivalenza dell’elemento a di A, e si indica con \([a]\). Vale: \([a] = \{x | x \in A \wedge x \backsim a \}\)

Vedi [GASP1977] pag.12, oppure, informalmente, questo link.

RGDA arbiter

Un arbitro RGDA (Request Grant Done e Acknowledge, vedi [EDIS1998] e [SABL1994]) è un componente che controlla l’utilizzo di una risorsa condivisa permettendone l’accesso esclusivo a un singolo processo nell’ambito di un gruppo di processi contendenti.

[1]Per metalinguaggio intendo il linguaggio utilizzato per definire quello in osservazione.