Grammatiche formali, 20/10/22

Table of contents

1 Introduzione e definizioni

Il ruolo centrale del front-end di un compilatore è probabilmente quello del parser, il cui compito è di verificare la correttezza delle sequenze di token inviategli dal lexer, trattato come una sub-routine. Per fare ciò, il parser si basa su una serie di regole grammaticali.

\(\blacktriangleright\) Una grammatica, quindi, è un'insieme di formalismi o regole atte a descrivere un linguaggio.

In particolare, il linguaggio descritto da una grammatica è composto da tutte le stringhe ottenibili attraverso le regole della grammatica stessa.

Una grammatica è solitamente descritta da una quadrupla di elementi:
\(G=(N,T,P,S)\), dove:

  • \(N\) è l'insieme dei simboli non terminali;
  • \(T\) è l'insieme dei simboli terminali, ossia degli elementi "non scomponibili" elementari;
  • \(S\) è detto assioma, o simbolo iniziale, appartenente all'insieme \(N\);
  • \(P\) è l'insieme delle produzioni, ossia le "funzioni" che descrivono le varie trasformazioni possibili. Sono il "cuore" della grammatica.

Un'importante categoria di grammatiche è quella delle grammatiche libere. Esse sono "indipendenti dal contesto": ciò significa che le trasformazioni dei simboli non terminali non dipendono dalla posizione del simbolo stesso all'interno dell'input. Questo tipo di grammatica è la più utilizzata nei linguaggi di programmazione moderni, essendo molto più semplice rispetto a grammatiche dipendenti dal contesto.

(1): esempio di produzione che si può trovare in una grammatica context free.
(2): esempio di produzione che si può trovare in una grammatica context dependent, in cui i terminali possono apparire anche a sx.

\begin{equation} (1) \ \ \ \ \ \ \ \ \ \ \ \ \ A \rightarrow \alpha \end{equation} \begin{equation} (2) \ \ \ \ \beta A \gamma \rightarrow \beta \alpha \gamma \end{equation}

Quindi il principale motivo per cui non viene usato l'approccio "context dependent" nella realizzazione e programmazione dei parser sta principalmente nella complessità della sua realizzazione. Tuttavia i linguaggi di programmazione sono fortemente dipendenti dal contesto: si pensi ad esempio alla definizione di una variabile all'interno di una funzione oppure nella funzione main! Semplicemente i controlli sul contesto non vengono fatti in fase di parsing, ma in un secondo momento in maniera procedurale […].

2 Derivazioni

Il processo di derivazione consiste essenzialmente nell'applicare le produzioni della grammatica sull'assioma (o simbolo iniziale) per ottenere una sequenza formata da soli terminali. Il concetto è più facilmente assorbibile tramite un'esempio. Si consideri la seguente grammatica \(G_{n,m}\) (espressa in modo "compatto"):

  • \(S \rightarrow \epsilon|A\)
  • \(A \rightarrow a|aA|B\)
  • \(B \rightarrow bB|b\)

La seconda riga, ad esempio, si può leggere come: "La \(A\) può essere riscritta come \(a\), \(aA\), o \(B\)". Se analizzata correttamente, ci si accorge che questa grammatica genera tutte le stringhe del tipo \(a^{n}b^{m}\);

E' interessante notare che i simboli non terminali sono solo quelli che compaiono sulla sinistra, nella definizione della grammatica. Infatti, se uno di essi comparisse a dx e non a sx, allora non ci sarebbero regole di trasformazione per riscriverlo, quindi per definizione sarebbe un terminale.

Nel linguaggio che questa grammatica genera, è compresa la stringa ab, perchè partendo dall'assioma \(S\) (il primo nella lista nei termini di Sx) la si può ottenere applicando diverse derivazioni:

\begin{equation} S \Rightarrow A \Rightarrow aA \Rightarrow aB \Rightarrow ab. \end{equation}

Durante la lettura è bene ricordarsi di questa notazione:
\(\alpha \overset{\\*} \Rightarrow \beta\) = dalla forma di frase \(\alpha\) si può ottenere \(\beta\) attraverso un numero arbitrario di trasformazioni. Prendiamo come esempio anche un'altra grammatica a cui si farà riferimento in futuro, ossia

\begin{equation} G_{expr1} = E \rightarrow E+E|E \times E|(E)|number \end{equation}