Analisi sintattica (linguaggi formali)

In questa lezione introdurremo gli analizzatori di sintassi o parser, cioè gli algoritmi che analizzano una stringa e generano il suo albero di sintassi secondo un dato linguaggio. Se la stringa non appartiene al linguaggio il parser deve accorgersene e segnalare l'evento.

Parser

Più formalmente, data una grammatica $G$ un analizzatore di sintassi o parser deve leggere una stringa sorgente $x$ e:

• se $x\in L(G)$: accettare la stringa e produrre un albero di sintassi o una derivazione;
• se $x\notin L(G)$: rifiutare la stringa e segnalare l'errore.
• se $x$ è una proposizione ambigua della grammatica $G$, il parser deve segnalare il problema (alcuni parser generano tutti i possibili alberi di sintassi, altri segnalano solo un errore)

Questo componente è solitamente il primo step dell'esecuzione di un compilatore dopo lo scanner.

Distinguiamo principalmente due approcci alla scrittura di un algoritmo di parsing:

• Bottom-Up: costruisce l'albero per riduzioni a partire dalle foglie fino alla radice (derivazioni a sinistra);
• Top-Down: costruisce l'albero per espansioni a partire dalla radice fino alle foglie (derivazioni a destra);

Grammatiche come reti di automi a stati finiti

Quando le grammatiche libere dal contesto rappresentano algoritmi di parsing, risulta molto utile trasformarle in reti di automi a stati finiti o rete di macchine a stati finiti(termine generalmente usato in inglese net of finite machines); questo porta a numerosi vantaggi che verranno presentati più avanti nella lezione.

Definiamo ora in maniera sufficientemente formale le reti di automi a stati finiti, aggiungendo anche altre definizioni necessarie:

• come solito, sia $\mathrm{\Sigma }$ l'alfabeto terminale, $V$ il non-terminale e $S\in V$ l'assioma della grammatica $G$;
• per ogni terminale esiste una regola $A\to \alpha$ e $\alpha$ è una RE sull'alfabeto $\mathrm{\Sigma }\cup V$; indichiamo il linguaggio generato da queste RE con i simboli $R_S,R_A,...$ rispettivamente dalla RE della regola di $S$, di $A$ e così via...
• i simboli $M_S,M_A,...$ rappresentano le macchine a stati finiti che accettano i linguaggi rispettivamente $R_S,R_A,...$
• per evitare confusione, ogni macchina possiede stati con nomi diversi. In particolare alla macchina $M_S$ saranno assegnati gli stati $0_S,1_S,...$, alla macchina $M_A$ gli stati $0_A,1_A,...$ e così via, in modo da mantenere gli stati tra le macchine ben disgiunti;
• definiamo inoltre $R(M_X,q)$ il linguaggio generato dalla macchina $M_X$ se lo stato iniziale è imposto essere un certo stato $q$; ovviamente se lo stato è il consueto stato iniziale risulta $R(M_X,q_0)=R_X$;
• l'insieme di tutte le macchine $M_S,M_A,...$ è detto rete di macchine a stati finiti e si indica con $M$.

Viste le regole qui sopra deifnite, il linguaggio generato dalla rete di macchine a stati finiti è lo stesso della grammatica $L(M)=L(G)$.

Visto che i linguaggi $R(M_X,q)$ (e anche $R_X$) potrebbe contenere simboli non terminali, definiamo il linguaggio terminale generato da una macchina della rete a partire da un certo stato:

$L(M_X,q)=\{y\in {\mathrm{\Sigma }}^{*}|\eta \in R(M_X,q)\wedge \eta \stackrel{*}{\Rightarrow }y\}$

Si noti che essendo $S$ l'assioma:

$L(M_S,q_{0,S})=L(M)=L(G)$

Esempio

Data la seguente grammatica:

$S\to E\text{';'}(E\text{';'}{)}^{*}$

$E\to V\text{'='}C$

$C\to [+|-](\text{'1'}|\text{'2'}|\text{'3'}|...{)}^{+}$

$V\to (\text{'a'}|\text{'b'}|\text{'c'}|...{)}^2(\text{'a'}|\text{'b'}|\text{'c'}|...{)}^{*}$

Possiamo costruire la relativa rete:

Top-down LL (k)

In questa sezione presentiamo l'algoritmo di parsing top-down LL (K). Il "parametro" k indica la lunghezza in caratteri di quanto l'algoritmo può "guardare avanti" (questo concetto sarà ripreso più avanti).