Grammatiche ll(k)

Le grammatiche $LL(k)$ sono grammatiche che risultano deterministiche al patto di poter “sbirciare” $k$ simboli di input, caso eccellente quello in cui $k=1$

Starter symbols set

Lo starter symbols set di una riscrittura $\alpha$ e l’insieme:

$$ SS(\alpha) = {a \in VT | \alpha \rightarrow a\beta }, con \space \alpha \in V^+, \beta \in V^* $$

Ovvero l’insieme di simboli terminali iniziali delle produzioni che coinvolgono il metasimbolo $\alpha$ sulla sinistra

Come ottenere una grammatica $ll(1)$

Condizione necessaria (sufficiente per le grammatiche senza $\epsilon -rules$) per far si che una grammatica sia $LL(1)$ e che gli starter symbols (ovvero gli elementi iniziali della parte destra di una produzione) di un metasimbolo siano tutti diversi fra loro

Il problema delle $\epsilon$

Le grammatiche che presentano produzioni in grado di annullare un metasimbolo non sono considerate dalla definizione di starter symbols set, dato che in caso di produzione vuota e necessario considerare il metasimbolo successivo per verificare il determinismo della produzione

$$ S \rightarrow AB|c $$ $$ A \rightarrow a|\epsilon $$ $$ B \rightarrow b|dc $$

In questa grammatica lo starter symbols set di $S$ e dipendente anche dal metasimbolo $B$ perché e necessario considerare che il metasimbolo $A$ può essere eliminato

Director symbols set

Per ovviare a questo problema si estende la nozione di starter symbols set, dato l’insieme $SS(\alpha)$ e l’insieme $FOLLOW(A)$ definito:

$$ FOLLOW(A) = {a \in VT | S \rightarrow \gamma Aa\beta}, con \space \gamma,\beta \in V^* $$

Ovvero l’insieme dei simboli terminali che compaiono come primi in caso di annullamento delle produzioni precedenti

Il director symbol set e dato da

$$ DS(A\rightarrow \alpha) = trunc_1(FIRST(\alpha)\bullet FOLLOW(A)) $$

Ovvero la troncatura a un carattere della concatenazione dei due insiemi.

Come ottenere una grammatica $ll(1)$

Condizione necessaria e sufficiente per ottenere una grammatica $LL(1)$ e che il director symbols set relativi alle produzioni siano disgiunti

Grammatiche $ll(1)$ il problema della il problema della ricorsione sinistra

Le grammatiche $LL(k)$ non sono compatibili con la ricorsione a sinistra delle produzioni $A \rightarrow A\alpha | a$, che tuttavia può essere sempre rimossa a patto di poter fare a meno della sua capacita espressiva (no necessita di dare una semantica alla frase)

Questa problematica può essere risolta adottando tecniche di analisi più avanzate come le grammatiche LR(k)