Analisi LL

In informatica , l' analisi LL è un'analisi sintattica top- down per alcune grammatiche non contestuali , chiamate grammatiche LL . Analizza una parola di ingresso da sinistra verso destra ( L EFT a destra in inglese) e costruisce una derivazione a sinistra ( L eftmost derivazione in lingua inglese). L'albero della sintassi viene costruito dalla radice e poi giù nell'albero.

L'analisi LL esegue un singolo passaggio sulla parola in ingresso. Un'analisi LL è chiamata analisi LL ( k ) quando utilizza una finestra di k lessemi per decidere come costruire l'albero della sintassi della parola in ingresso.

Architettura di un analizzatore LL

Di seguito viene descritta un'analisi top- down derivata a sinistra basata su una tabella di analisi . La nozione di derivazione a sinistra significa che durante il processo di applicazione delle regole è il non terminale più a sinistra che viene scelto e riscritto. Questo aspetto si traduce nell'utilizzo di uno stack nell'algoritmo dell'analizzatore.

Caso generale per un'analisi LL (1)

L'analizzatore è composto da:

un buffer di input, contenente la stringa di caratteri da analizzare e dotato di due operazioni: leggere il carattere corrente e passare al carattere successivo;
uno stack su cui mettere i terminali e non terminali della grammatica che restano da analizzare;
una tabella di analisi che dice quale regola usare (se presente) in base ai simboli in cima allo stack e al lessema seguente.

Il parser applica la regola trovata nella tabella facendo corrispondere la parte superiore dello stack (riga) con il simbolo corrente nel buffer di input (colonna).

Quando inizia l'analisi, lo stack contiene due simboli:

[ S, $ ]

Dove "$" è un simbolo per il fondo dello stack e la fine del buffer di input, e "S" è l'assioma della grammatica.
Il parser proverà a riscrivere il contenuto del suo stack in quello che vede nel buffer di input. Tuttavia, tiene in pila solo ciò che deve essere riscritto.

Calcolo della tabella di analisi

Sia una grammatica algebrica (dove V indica l'insieme di variabili o simboli non terminali, A l'alfabeto terminale o insieme di simboli terminali, P l'insieme di regole, S l'assioma della grammatica che è una regola di P). Per calcolare la tabella di analisi , introduciamo le funzioni , e . ${\ displaystyle G = (V, A, S, P)}$ ${\ displaystyle Eps}$ ${\ displaystyle Premier}$ ${\ displaystyle Next}$

Eps

Per ogni espressione , è vero se è cancellabile, che equivale a dire è vero se (l'espressione riscrive nella stringa vuota ) ed è falso altrimenti. Questo calcolo corrisponde a quello delle regole ε , come nel caso della conversione nella forma normale di Chomsky . ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Eps (\ alpha)}$ $\alfa$ ${\ displaystyle \ alpha ~ {\ xrightarrow {*}} ~ \ varepsilon}$ $\alfa$ $\ varepsilon$

Primo

Per ogni espressione , definiamo come l'insieme di terminali che probabilmente inizieranno una parola derivata da α. Più formalmente: ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Premier (\ alpha)}$

Premier(\alpha )=\{a\in A^{*}\mid \exists \beta \in (V\cup A)^{*},\alpha {\xrightarrow {*}}a\beta \}

Se è così . ${\ displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Premier (\ alpha) = \ varnothing}$

seguente

Per ogni espressione , definiamo come l'insieme di terminali che probabilmente seguiranno una parola derivata da α. Più formalmente: ${\ displaystyle \ alpha \ in (V \ cup A) ^ {+}}$ ${\ displaystyle Avanti (\ alpha)}$

Suivant(\alpha )=\{a\in Premier(\gamma )\mid \exists \beta ,\gamma \in (V\cup A)^{*},S{\xrightarrow {*}}\beta \alpha \gamma \}

Allora sì . Aggiungiamo anche il simbolo '$' a tutti , in modo da poter indicare la fine del codice. ${\ displaystyle \ alpha = \ varepsilon}$ ${\ displaystyle Next (\ alpha) = \ varnothing}$ ${\ displaystyle \ {\ alpha \ in (V \ cup A) ^ {+} \ mid \ exist \ beta \ in (V \ cup A) ^ {*} S {\ xrightarrow {*}} \ beta \ alpha \ }}$

Riempimento della tabella di analisi

La tabella di analisi è una matrice bidimensionale, le cui righe sono indicizzate da Non terminali e le colonne da Terminali . Il riempimento viene eseguito come tale:

Pour toute règle de la forme X→α Pour tout a∈Premier(α) Ajouter X→α à la case d'indice (a,X) Si Eps(α) vaut vrai Alors Pour tout b∈Suivant(α) Ajouter X→α à la case d'indice (b,X) Fin pour Fin pour Fin pour

Esempio senza regola ε

Inizializzazione

Per spiegare come funziona, useremo la seguente grammatica:

{\ displaystyle S \ to F}

{\ displaystyle S \ to (S + F)}

{\ displaystyle F \ to 1}

e analizza la stringa successiva

(1 + 1)

Calcoliamo Eps:

Nessuna regola dà , quindi nessun Eps (α) è sempre falso. $\ varepsilon$

Calcoliamo Prime:

Premier(F) = { 1 } Premier((S + F)) = { (} Premier(1) = { 1 }

Calcoliamo la tabella di analisi:

On prend S → F, Premier(F) = { 1 } donc on ajoute '

S\to F

' à la case (S , 1). On prend S → (S + F), Premier((S + F)) = { (} donc on ajoute '

S\to (S+F)

' à la case (S , (). On prend F → 1, Premier(1)= { 1 } donc on ajoute '

F\to 1

' à la case (F , 1).

	(	)	1	+	$
S	${\ displaystyle S \ to (S + F)}$	-	${\ displaystyle S \ to F}$	-	-
F	-	-	${\ displaystyle F \ to 1}$	-	-

Analisi delle parole ${\ displaystyle (1 + 1)}$
Il parser legge la prima "(" dal buffer di input e la parte superiore dello stack (la "S"). Guardando la tabella, sa che deve applicare la regola " "; ora deve riscrivere la "S" in '(S + F)' nella sua pila e scrivi la regola applicata all'output. La pila diventa (la parte superiore della pila è a sinistra, i simboli sono separati da virgole): ${\ displaystyle S \ to (S + F)}$ [ (, S, +, F, ), $ ] Possiamo notare che la S non terminale sarà disimpilata e quindi riscritta prima di F. È effettivamente la non terminale più a sinistra nel termine '(S + F)'. Questo illustra la nozione di derivazione sinistra . Nel passaggio successivo, poiché la parte superiore dello stack e il buffer presentano entrambi il terminale "(", questo simbolo viene estratto e rimosso dal buffer di input. Lo stack diventa: [ S, +, F, ), $ ] Ora il buffer ha il simbolo "1" e la parte superiore della pila è "S". Secondo la tabella, l'analizzatore applica la regola " " che pone "F" in cima alla pila. L'analizzatore visualizza la regola applicata sull'output. Lo stack diventa: ${\ displaystyle S \ to F}$ [ F, +, F, ), $ ] Poiché il buffer ha sempre il simbolo '1' la regola da applicare in base alla tabella è ' '. L'analizzatore visualizza la regola applicata sull'output. Lo stack diventa: ${\ displaystyle F \ to 1}$ [ 1, +, F, ), $ ] Durante i due passaggi successivi (per i simboli "1" e "+") il simbolo della testina del buffer corrisponde alla parte superiore dello stack. Ciascuno viene rimosso dal buffer e non impilato. Lo stack diventa: [ F, ), $ ] Per gli ultimi 3 passaggi, la "F" verrà sostituita in pila da "1", la regola " " verrà quindi scritta in uscita. Quindi "1" e ")" vengono rimossi dal buffer di input e dallo stack. L'analisi quindi termina perché rimane solo "$" nello stack e nel buffer di input. In questo caso, il parser accetta la stringa e visualizza l'elenco sull'output: ${\ displaystyle F \ to 1}$ [ , , , ] ${\ displaystyle S \ rightarrow (S + F)}$ ${\ displaystyle S \ to F}$ ${\ displaystyle F \ to 1}$ ${\ displaystyle F \ to 1}$ Che è effettivamente un ramo a sinistra della catena di partenza. Vediamo che una derivazione a sinistra della catena è: S → (S + F) → (F + F) → (1 + F) → (1 + 1)

Osservazioni

Come si può vedere, il parser esegue tre tipi di passaggi a seconda della parte superiore dello stack (non terminale, terminale, simbolo '$'):

se la parte superiore dello stack è un simbolo non terminale, allora cerca nella tabella di analisi in base a quel simbolo non terminale e il simbolo nel buffer di input quale regola usare per sostituirlo nello stack. Il numero della regola viene scritto sull'output. Se la tabella di analisi dice che non esiste una regola di corrispondenza, allora emette un errore e si ferma;
se la parte superiore dello stack è un simbolo di terminale, lo confronta con il simbolo nel buffer di input. Se sono uguali, li rimuove, altrimenti genera un errore e si ferma;
se la parte superiore dello stack è "$" e il buffer di input contiene anche "$", il parser dice di aver analizzato la stringa correttamente, altrimenti genera un errore. In entrambi i casi si ferma.

Questi passaggi vengono ripetuti fino all'arresto dell'analizzatore; avrà analizzato correttamente la stringa e scriverà una derivata a sinistra della stringa sull'output, oppure avrà emesso un errore.

Esempio con regola ε

Inizializzazione

Per spiegare come funziona, useremo la seguente grammatica semplificata di LISP / Scheme:

{\ displaystyle S \ to (L)}

{\ displaystyle S \ to a}

{\ displaystyle L \ to SL}

{\ displaystyle L \ to \ varepsilon}

e analizza la stringa successiva

{\ displaystyle (a ())}

Calcoliamo Eps:

Solo L può essere cancellato, quindi vero e falso negli altri casi. ${\ displaystyle EPS (\ varepsilon) = EPS (L) =}$

Calcoliamo Prime:

Premier(a) = { a } Premier((L)) = { (} Premier(SL) = { (, a } Premier(ε) = ∅

Calcoliamo quanto segue:

Suivant(S) = { $, a, (, ) } Suivant(L) = { ) }

Calcoliamo la tabella di analisi:

On prend S → (L), Premier((L)) = { (} donc on ajoute '

S\to (L)

' à la case (S , (). On prend S → a, Premier(a) = { a } donc on ajoute '

S\to a

' à la case (S , a). On prend L → SL, Premier(SL)={ (, a } donc on ajoute '

L\to SL

' aux cases (L , () et (L, a). On prend L → ε, Premier(ε) = ∅ et Eps(ε) = vrai et Suivant(L)={ ) }, donc on ajoute '

L\to \varepsilon

' à la case (L ,)).

	(	)	a	$
S	${\ displaystyle S \ to (L)}$	-	${\ displaystyle S \ to a}$	-
L	${\ displaystyle L \ to SL}$	${\ displaystyle L \ to \ varepsilon}$	${\ displaystyle L \ to SL}$	-

Come promemoria, l'analizzatore gestisce uno stack e un buffer di input che può fornire i simboli della stringa di caratteri. Leggere il buffer non significa passare al simbolo successivo. Leggere il buffer significa solo accedere al simbolo corrente. Si passa al simbolo successivo nel buffer solo quando il simbolo non impilato è un terminale uguale al simbolo corrente del buffer. Questa uguaglianza traduce il fatto che nel passaggio corrente la stringa letta è conforme alla grammatica. L'avanzamento nel buffer non è reversibile (l'analizzatore non torna mai indietro nella catena). Questo può essere rappresentato da una testina di lettura provvista di memoria. Man mano che questa testina di lettura avanza nel buffer, la memoria memorizza il carattere letto. Questa memoria può essere consultata tutte le volte che vuoi. Questa consultazione corrisponde all'operazione di lettura del buffer. La testina di riproduzione può avanzare al seguente simbolo: ciò che viene definito avanzamento nel buffer.

Analisi delle parole ${\ displaystyle (a ())}$
[ S, $ ] Il parser legge la prima "(" dal buffer di input e apre la parte superiore dello stack (la "S"). Guardando la tabella, sa che deve applicare la regola 1; ora deve riscrivere la "S" in '(L)' nella sua pila, quindi la pila diventa: [ (, L,), $ ] In cima alla pila c'è il simbolo del terminale '('. Poiché corrisponde al simbolo corrente del buffer (quindi la stringa segue, per il momento, la grammatica) questo simbolo viene spuntato e avanza al simbolo successivo in il buffer che è 'a' Lo stack è diventato: [ L,), $ ] Si apre "L" e legge la lettera "a", deve applicare la regola 3; riscrive la "L" in "SL": [S, L,), $ ] Si apre "S" e legge la lettera "a", deve applicare la regola 2; riscrive la "S" in "a" quindi in un passaggio aggiuntivo rimuove la "a" a causa della corrispondenza con la parte superiore della pila. Dopodiché il simbolo del buffer corrente è il secondo '(' e lo stack è diventato: [ L,), $ ] Ora fa apparire la "L" e legge la lettera "(", riscrive la "L" in "SL" (regola 3) quindi la "S" in "(L)" (regola 1), quindi può rimuovere il '('. Il simbolo corrente è il primo ')' e la pila è diventata: [ L,), L,), $ ] Fa apparire la "L" e legge la lettera ")", quindi può rimuovere la "L" usando la regola 4, quindi può rimuovere la ")". Il simbolo corrente è il secondo ')' e la pila è diventata: [ L,), $ ] Allo stesso modo di prima, la Regola 4 gli consente di rimuovere la "L" e può quindi rimuovere la ")". La pila è diventata vuota: [ $ ] L'algoritmo quindi conclude positivamente e applicando la sequenza derivativa sinistra: $S\rightarrow (L)\rightarrow (SL)\rightarrow (aL)\rightarrow (aSL)\rightarrow (a(L)L)\rightarrow (a()L)\rightarrow (a())$ .

Generatori di parser LL ( k )

ANTLR : (en) Sito ufficiale
Coco / R : (en) Sito ufficiale
JavaCC : (en) Sito ufficiale
PCCTS : vecchio nome di ANTLR, (it) sito archiviato
Modulo Ocaml Genlex : (en) Sito ufficiale

Note e riferimenti

Romain Legendre e François Schwarzentruber, Compilation: Lexical and syntactic analysis - from text to its structure in computer science , Paris, Ellipses ,31 marzo 2015, 312 p. ( ISBN 978-2-340-00366-8 ).