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 $\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 $\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 \Sigma ^{*}\ |\ \eta \in R(M_{X},q)\land \eta \ {\overset {*}{\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).