Parsing 2, 03/11/22

Questa pagina riassume i concetti visti a lezione. Per quanto riguarda gli esempi pratici, vengono trattati in modo estensivo sulle slide.

1. Parsing Predittivi
2. Grammatiche NON LL(1)
3. First e Follow
   • First
   • Follow
4. Definizione Compatta
5. Tabella di Parsing

I parser a discesa ricorsiva possono risultare lenti per grammatiche estese, ma esistono anche altri approcci per la progettazione dei parser.

Un parser predittivo sceglie ad ogni passo la produzione corretta, effettuando un lookahead per soddisfare l'input.

In questo corso ci si occuperà di parser su grammatiche \(LL(1)\) \(\rightarrow\) (left-left 1), ossia grammatiche con solo derivazioni canoniche sinistre e che leggono l'input da sinistra verso destra, basandosi su un lookahead di 1 carattere. Infatti implementare un lookahead di più caratteri diventa estremamente costoso dal punto di vista computazionale.

Lookahead di 1 significa che al parser basta conoscere il prossimo carattere di input per sapere quale produzione applicare.

E' quindi necessario riuscire a progettare delle grammatiche che possano essere compatibili con questa logica di parsing.

Una caratteristica che impedisce ad una grammatica di essere LL(1) è il fatto di avere prefissi comuni, ad esempio:

\begin{align} & A \rightarrow aB | aC \\ & B \rightarrow aB | B \\ & C \rightarrow aC | C \\ \end{align}

in questo caso, in presenza di un carattere di input \(a\), il parser non è in grado di decidere quale produzione applicare, se \(A \rightarrow aB\) oppure \(A \rightarrow aC\). Ma non sempre vedere questa caratteristica è immediato, quindi è necessario avere dei criteri specifici, elencati di seguito \(\Downarrow\)

---

Consideriamo la semplice produzione

\begin{equation} A \rightarrow \alpha|\beta \end{equation}

in cui α e β sono dei caratteri non terminali. Una grammatica non può essere LL(1) in questi casi:

• se \(\alpha \overset{*} \Rightarrow a\alpha'\) e \(\beta \overset{*} \Rightarrow a\beta'\), quindi se si presenta un prefisso comune dopo * derivazioni;
• se \(\alpha\) è nullificabile, quindi se \(\alpha \overset{*} \Rightarrow \epsilon\), allora \(\beta\) non deve esserlo, altrimenti il parser in caso di bisogno non saprebbe come eliminare il carattere non terminale A.
• se \(\alpha\) è nullificabile, e \(\beta \overset{*} \Rightarrow a\beta'\), allora non si vuole che \(S \overset{*} \Rightarrow \gamma_{1}Aa\gamma_{2}\). Infatti se ci si trova \(\Rightarrow \gamma_{1}Aa\gamma_{2}\), e si vuole matchare un carattere \(a\) (sviluppando il carattere non terminale A, dato che \(\gamma_{1}\) e \(\gamma_{2}\) sequenze di caratteri non terminali), si possono fare due scelte:
  1. \(A \rightarrow \alpha \rightarrow \epsilon\);
  2. \(A \rightarrow \beta \rightarrow a\beta'\);

  in entrambi i casi si otterrebbe un match con \(a\), quindi ci sarebbe indecisione e indeterminismo.

Quando si parla di grammatiche LL(\(k\)) e di parsing predittivo, è utile creare dei livelli di astrazione, per agevolare lo studio e la notazione.

Si dice FIRST(α) l'insieme dei simboli terminali con cui può iniziare una frase derivabile da \(\alpha\).

Si dice FOLLOW(A) l'insieme dei simboli terminali che posso trovare subito dopo A applicando delle derivazioni.

Viste le precedenti definizioni di First e Follow, si può affermare che in una grammatica LL(1) in cui esistono due produzioni

\begin{align} & A \rightarrow \alpha \\ & A \rightarrow \beta \end{align}

sono vere le seguenti affermazioni:

1. FIRST(\(\alpha\)) \(\cap\) FIRST(\(\beta\)) \(= \{\}\);
2. FIRST (\(\beta\)) \(\cap\) FOLLOW(\(A\)) \(= \{\}\);

che semplicemente riassumono i concetti spiegati prima tramite gli esempi. E' sempre bene ricordare che una grammatica è LL(\(k\)) quando non presenta ricorsioni a sinistra;

Ora l'idea è quella di usare le nozioni apprese sui FOLLOW e i FIRST per costruire una tabella di parsing, in modo da avere un "ruleset" specifico per ogni situazione in cui il parser si trova in un generico momento, in modo da fargli sempre fare la scelta corretta. In particolare, per ogni "prossimo" simbolo di input e per ogni simbolo non terminale in cui ci si trova, si specifica quale produzione usare. Questo si traduce in una tabella in cui:

• Gli indici di riga sono i non terminali;
• Gli indici di colonna sono i simboli di input, quindi i terminali;
• Le caselle indicano che produzione usare in ogni situazione;

---