Analizzatori sintattici a discesa ricorsiva

Analizzatori sintattici a discesa ricorsiva
E’ uno schema di analizzatore che sfrutta la descrizione grammaticale in EBNF adatto a grammatiche
LL(1). Si basa sulla scrittura di procedure ricorsive ricavate direttamente dalle regole grammaticali.
IDEA
Ogni produzione viene interpretata come una procedura in cui la parte sinistra rappresenta il
nome e la parte destra la definizione (corpo) della procedura. Lo stack risulta implementato
implicitamente dal meccanismo di implementazione delle chiamate ricorsive.
Data una generica regola
X ! x1 | x2 | ...... | xn !
si distinguono due possibili strutture della procedura a seconda di quale delle due condizioni si verifichi
1. X# + " Cioé la variabile non genera "
2. X #+ "
Cioé la variabile genera "
Inoltre, si deve supporre l’esistenza di una routine che rende disponibile i caratteri che via via vengono
scanditi. Questa routine in genere è associata ad un analizzatore lessicale.
Analizzatori lessicali
Un analizzatore lessicale ha il compito di esaminare carattere per carattere la stringa in ingresso e
produrre una forma standard degli item di volta in volta individuati.
Tipicamente gli analizzatori lessicali vengono implementati con automi a stati finiti.
Esempio:
procedure somma (var S:integer);
!var i:integer;
! begin
!
S:=0;
!
for i:=1 to 10 do S:= S + i * 500;
end;
procedure somma ( var S : integer ) ; var i : integer ; begin
!
S := 0 ; for i := 1 to 10 do S := S + i * 500 ; end ;
In pratica l’analizzatore lessicale ha il compito di categorizzare le varie stringhe selezionate in
modo che ciascuna stringa rappresenti un unico item.
Ad esempio: alfa + pigreco * gamma
è come dire
i +i*i
Al momento dell’analisi sintattica interessa la struttura di una espressione e quindi la tipologia
degli operandi indicati.
Analizzatori sintattici a discesa ricorsiva
1. X # + "
! procedure X;
!
begin
!!
if cc in FIRST(x1) then {codice di x1 }
!!
else if cc in FIRST(x2) then {codice di x2 }
$ !
$ $
!!
!!
!
!
......
$
else if cc in FIRST(xn) then {codice di xn }
else ERRORE
end;
2. X #+ "
procedure X;
!
begin!
if cc in FIRST(x1) then {codice di x1 }
!!
else if cc in FIRST(x2) then {codice di x2 }
!!
! !
!!
!
......
else if cc in FIRST(xn) then {codice di xn }
else if not [ cc in FOLLOW(X)] then ERRORE
end;
- cc = carattere corrente
- per l’ipotesi
FIRST(xi)% FIRST(xj) = &
viene attivata una sola
parte destra
Esempio
Grammatica
E ! T E’ ! !
E’ ! + T E’ | "
T ! F T’
T’ ! *F T’ | "
F ! (E) | i
E ! T E’
!!
$
!
tabella codici di errore
1. omissione di operando
2. omissione di operatore
3. simbolo inatteso
4. carattere ‘) ‘omesso
5. simboli restanti
procedure E!
! if cc in FIRST (TE’)
! then T; E’!
!
! else ERRORE (1);
T ! F T’
procedure T
! if cc in FIRST (FT’)
! then F; T’ !
! else ERRORE (1);
E’ ! + T E’ | "
procedure E’
! if cc in FIRST (+TE’)
!
then NEXT (cc); T; E’
!
else if not [cc in FOLLOW(E’)] then ERRORE (2);
!
Esempio cont.
T’ ! *F T’ | "
F ! (E)
F! i
procedure T’
! if cc in FIRST (*FT’)
! then NEXT (cc); F; T’
!
! else if not [cc in FOLLOW(T’)] then ERRORE (3);
procedure F
! if cc in FIRST ((E))
! then NEXT (cc); E
!
if cc = ‘)’
!
then NEXT (cc)
else ERRORE (4)
else if cc in FIRST (i)
!
then NEXT (cc)
else ERRORE (1);
{main}
!!
!!
!
NEXT (cc);
E;
if cc <> $ then ERRORE (3)
Costruzione della tabella di guida
I due insiemi FIRST e FOLLOW possono essere impiegati per costruire una tabella avente nelle righe i
simboli non terminali e nelle colonne i simboli terminali che consente di guidare deterministicamente il
riconoscitore, così definita:
Per ogni regola X " x | x | ....| x si considerano gli insiemi FIRST di ciascun x e l’insieme FOLLOW(X).
1 2
n
i
• Per ogni terminale t # FIRST (xi ) si pone TAB [ X, t] = xi.
•
Se xj $*! si pone TAB [X,t] = ! per ogni terminale t # FOLLOW (X).
Con riferimento alla grammatica vista in precedenza:
FIRST
E
-
(
E’
+ -
T
(
T’
i
*
F
(
E
TE’
)
)
+
TAB[E, -] = -TE’
E " TE’
TAB[E, ( ] = TE’, TAB[E, i] = TE’
TAB [E’, $] = !, TAB[ E’, )] = !
E’ " !
- +
-
*
-TE’
(
)
$
e!
!
!
!
TE’
-TE’
FT’
FT’
!
i
E " -TE’
$ ) - + *
+TE’
T’
F
)
$
$ )
+
E’
T
$
$
i
i
FOLLOW
i
!
*FT’
(E)
Tabella di guida
Struttura del parser
Pila
Stringa
E$
-i+i*i$
-TE’$
TE’$
-i+i*i$
FT’E’$
i T’E’$
T’E’$
-i+i*i$
E’$
+TE’$
TE’$
-i+i*i$
FT’E’$
i T’E’$
T’E’$
-i+i*i$
* FT’E’$
FT’E’$
-i+i*i$
i T’E’$
T’E’$
-i+i*i$
E’$
$
Elemento indirizzato
TAB[E, -] = - TE’
TAB[T, i] = FT’
TAB[ F, i] = i
tabella di guida
i
E
TAB[T’,* ] = *FT’
TAB[F, i] = i
TAB[T’, $] = !
TAB[E’, $] = !
-
*
-TE’
+TE’
)
$
-TE’
!" !"
FT’
!"
i
(
TE’
FT’
T’
F
TAB[T, i] = FT’
TAB[F, i] = i
TE’
E’
T
TAB[T’, +] = !
TAB[E, +] = +TE‘
+
!"
*FT’
!" ! "
(E)
1. Se il simbolo al top della pila è un
terminale esso deve coincidere col
carattere in lettura. Tale carattere viene
rimosso dalla pila e si avanza il
puntatore di un carattere.
2. Se il simbolo al top della pila è un non
terminale esso viene espanso con una
parte destra individuata dalla tabella
e rimosso dalla pila.
Albero sintattico
E
-
E’
T
F
T’ +
i
!
T
E’
F
T’
!
i
#
F
T’
i
!
Macchina di Turing
Nastro di Input
.......... !
!
!
a
b
b
a
b
!
!
!
testina
st
sr
Unità
di
Controllo
qi
Q
qj
P
S/D/F
!
...........
Definizione Formale
Una macchina di Turing deterministica è una sestupla < !, ", Q, q0, Z, # >
$
! - Alfabeto esterno o dei simboli di nastro
" - Simbolo speciale che indica cella vuota
"%!
Nastro di Input
.......... !
!
a
!
b
b
!
a
b
!
!
!
testina
Q - Un insieme finito e non vuoto di stati
st
s
r
q0 - stato iniziale
!
Unità
di
Controllo
q0 % Q
# - Funzione (parziale) di transizione definita come:
!
!
Q
qj
!Z - Insieme di stati finali (halting states)
!
qi
# : (Q - Z) x ( ! & {" }) ' Q x ( ! & {" }) x {S, D, F}
avendo indicato con S uno spostamento a Sinistra della Testina, con D uno
spostamento a Destra e con F nessuno spostamento
P
S/D/F
...........
Configurazione di una MT
Una configurazione di una MT rappresenta la più piccola porzione di nastro contenente tutti i
simboli non ! includente la cella cui è posizionata la testina ad eccezione di qualche simbolo !
che si trova “immerso” in una stringa.
qi
!
abbreviata con
!
a
b
b
!
b
a
a qi b b ! b a
formalmente una configurazione è una stringa x q y in cui:
x " # (#$ !)*${%},
q " Q,
y " (#$ !)*#${!}
la condizione x = % equivale a dire che alla sinistra di q non vi è alcun simbolo ovvero
compaiono solo simboli !, mentre se y =!, sulla cella dove è puntata la testina ed alla
destra della testina compaiono simboli !.
Configurazioni notevoli
Configurazione iniziale
E’ caratterizzata dalla stringa
!
!
!!
x = !, q = q ,
0
x q y con
y " #+$ { % }
Configurazione finale
E’ caratterizzata dalla stringa x q y con
!!
x " # (#$ %)*${!},
q " Z,
y " (#$ %)*#${%}
Per come è definita la matrice di transizione &, una macchina che si trovi in una
configurazione finale non può effettuare ulteriori passi di computazione.
Ciclo di macchina o transizione
E’ il meccanismo di base per il passaggio da una configurazione i-esima ad una
configurazione i+1-esima. Ad ogni ciclo viene cambiato il simbolo contenuto nella cella
esaminata con un altro simbolo (eventualmente lo stesso), il simbolo di stato
(eventualmente lo stesso) e lo spostamento della testina a Sinistra (S) Destra (D)
oppure nessun movimento (F).
Ci |! Ci+1
Più formalmente:
1. Ci = x q a y
e se "(q,a) = (q’, a’, D) allora Ci+1 = x a’ q’ y
2. Ci = x q a
e se "(q,a) = (q’, a’, D) allora Ci+1 = x a’ q’ #
3. Ci = x a q b y
e se "(q,b) = (q’, b’, S) allora Ci+1 = x q’ a b’ y
4. Ci = q b y
e se "(q,b) = (q’, b’, S)
5. Ci = x q a y e se "(q,a) = (q’,a’, F)
allora Ci+1 = q’ # b’ y
allora
Ci+1 = x q’ a’ y
Computazione
Una successione di transizioni stabilisce una computazione o calcolo
C0 |!
C1 .......... |! Cn
Vedremo nel prosieguo come una computazione può essere infinita o arrestarsi in una
configurazione finale.