CAP. 3 ANALISI SINTATTICA
•
•
•
•
3.1 Il ruolo dell'analizzatore sintattico
3.2 Le grammatiche
3.3 L’analisi discendente
3.4 L’analisi ascendante
Traduzione cap3 1
3.1 Il ruolo dell'analizzatore sintattico
unità lessicale
programma
iniziale
analizzatore
lessicale
analizzatore
sintattico
albero di analisi (sintattico)
richiesta
tabella dei
simboli
Ruolo centrale della parte frontale:
attiva l'analizzatore lessicale con richieste
verifica la correzzione sintattica
costruisce l'albero di analisi
prepara e anticipa la traduzione
gestisce gli errori comuni di sintassi.
Traduzione cap3 2
Tipi di analizzatori sintattici:
• metodi universali (Cocke-Younger-Kasami),
permettono un'analisi di qualsiasi grammatica algebrica,
ma complessità in O(n3);
• metodi lineari in O(n), su certe grammatiche:
analisi discendente, più intuitiva, ben adatta a grammatiche
simplici;
analisi ascendente, più sofisticata, più utilizzata dai
generatori automatici di analizzatori sintattici,
poichè necessita poche adattazioni della grammatica.
Trattamento degli errori:
• diagnosi (messagi);
• continuazione dell'analisi:
"modo panico", fino a risincronizzazione;
correzione (difficile se l’errore è avvenuta molto prima della
detezione;
regole di errori, integrate alla sintassi (grammatica).
Traduzione cap3 3
3.2 Le grammatiche
Sintassi specificata da regole grammaticali.
• Simboli terminali (= unità lessicali) alfabeto A;
• Simboli intermedi o variabili (= categorie grammaticali)
alfabeto X;
• Regole grammaticali x  w , dove x  X e w  (AX)*
w è una parole, anche vuota.
Esempi :
instr  if expr then instr else instr
frase  soggetto verbo complemento
• Assioma (= programma)
Linguaggio generato = parole terminali derivate dall'assioma.
Traduzione cap3 4
Esempio: Espressioni aritmetiche
E  number
E(E)
EE+E
EE–E
EE*E
EE/E
Albero d'analisi di 3*(6+2)
E
E
*
E
(
E
)
+
E
3 number
E
6 number
2 number
I valori espliciti sono attributi delle unità lessicali.
L’associazione alle unità lessicali è realizzata dall’analizzatore
lessicale.
Traduzione cap3 5
Grammatica precedente ambigua
Grammatica non ambigua per espressioni aritmetiche
(operatori suffissi):
E  EE + | EE – | EE * | EE / | number
Grammatica non ambigua per expressioni aritmetiche:
E  E +T | E –T | T
T  T *F | T /F | F
F  ( E ) | number
Scelta: associatività a sinistra
precedenza di * e / su + et –
Traduzione cap3 6
Analisi sintattica:
Data una parola terminale, determinare se è, sì o no, generata
dalla grammatica; in caso di sì, produrre un albero d'analisi.
• Metodo universale: provare tutte le derivazioni partendo
dall’assioma, fino a trovare la parola. Regole di lunghezza
(dopo modificazioni) permettono di eliminare le derivazioni
che non possono convenire.
• Metodo discendente (descesa recursiva): una procedura per
variabile, i terminali servono a scegliere la regola (previsione)
e alla validazione.
• Metodo ascendante: la parola è letta (spostamento) fino ad
identificare regole, che vengono ridotte (riduzione).
Traduzione cap3 7
3.3 L’analisi discendente
Una procedura per variabile.
Problema: ricorsività diretta a sinistra;
necessità di una trasformazione per eliminarla.
Grammatica iniziale
E  E +T | T
T  T *F | F
F  (E ) | number
Grammatica modificata
A  E$
(produzione aumentata)
E  TG
G  +TG | 
T  FU
U  *FU | 
F  (E ) | number
Procedure corrispondenti: supponiamo che due procedure
sono già scritte:
• prevision ritorna l’unità lessicale seguente senza rimuoverla;
• match(x) legge l’unità lessicale seguente, la rimuove e segnala
un errore se non vale x.
Traduzione cap3 8
procedure expression ;
begin writeln(‘E->TG’) ;
term ; moreterm
end ;
procedure moreterm ;
begin
if prevision = plus then
begin writeln(‘G->+TG’) ;
match(plus) ;
term ; moreterm
end
else writeln(‘G->epsilon’)
end ;
procedure expression ;
begin writeln(‘E->TG’) ;
term ;
while prevision = plus do
begin
writeln(‘G->+TG’) ;
match(plus) ;
term
end ;
writeln(‘G->epsilon’)
end ;
Raggruppando e eliminando la
ricorsività terminale
Traduzione cap3 9
procedure term ;
begin writeln(‘T->FU’);
factor ;
while prevision = mult do
begin writeln(‘U->*FU’) ;
match(mult) ;
factor
end ;
writeln(‘U->epsilon’)
end ;
procedure factor ;
begin
if prevision = open then
begin writeln(‘F->(E)’) ;
match(open) ;
expression ;
match(close)
end
else if prevision = number then
begin writeln(‘F->number’);
match(number)
end
else writeln(‘error’)
procedure analysis ;
end ;
begin writeln(‘A->E$’) ;
expression ; match(dollar) ; writeln(‘success’)
end ;
Il fallimento dell’analisi è trattato da match(x).
Traduzione cap3 10
Funzioni FIRST e NEXT
x
FIRST(x)
NEXT(x)
FIRST(x) = insieme dei terminali che possono cominciare
una derivazione da x.
NEXT(x) = insieme dei terminali che possono seguire x in
una derivazione
Traduzione cap3 11
Calcolo di FIRST:
Un grafo è costruito fra tutti i simboli grammaticali.
Freccia da x verso y ssi x  y , e è annullabile.
Qui,  contiene solo variabili,  senza restrizione (anche ).
FIRST(x) = { a terminale | esiste un cammino da x fino a a } ;
se x è annulabile, si aggiunge  a FIRST(x).
Esempio con la grammatica precedente: Annulabili: G e U
Grafo:
A
E
T
F
(
G
number
+
U
*
FIRST(A) = FIRST(E) = FIRST(T) = FIRST(F) = { (, number }
FIRST(G) = {+, } FIRST(U) = { *, }
La funzione FIRST è estesa a tutte le parole:
FIRST(xu) = FIRST(x) se x non è annullabile
{}FIRST(x) \  }  FIRST(u) se x è annullabile
Traduzione cap3 12
Calcolo di NEXT:
Un grafo è costruito fra tutti i simboli grammaticali.
Freccia da x verso y sse
• esiste z  x , y è terminale e y  FIRST() ;
• esiste y  x e  è annullabile.
Qui,  e  sono parole qualsiasi (anche ).
NEXT(x) = { a terminale | esiste un cammino da x fino a a }.
Esempio con la grammatica precedente:
F
*
Grafo:
NEXT non è definito per l'assioma della
produzione aumentata (qui A).
U T
+
G
E
$
)
NEXT(G) = NEXT(E) = { $, ) }
NEXT(U) = NEXT(T) = { +, $, ) }
NEXT(F) = { *, +, $, ) }
Traduzione cap3 13
Con FIRST e NEXT si possono caratterizzare le grammatiche
analizzabili in modo discendente, usando un solo simbolo
di previsione a:
a
parte già
analizzata
simbolo di
previsione
parte ancora
da analizzare
Grammatiche LL(1).
Sia a il simbolo di previsione e x la variabile da riscrivere.
Utilizzare la regola x  se a  FIRST();
Se  è annullabile, utilizzare la regola x  se a  NEXT(x).
La grammatica è LL(1) quando, per ogni x, una sola regola
soddisfa una delle condizioni sopraddette.
Traduzione cap3 14
Tabella di analisi LL(1):
n $
1
2
3
3
4
4
6 5
6
6
7
8
+ *
E
G
T
U
F
(
1
)
0 A  E$
1 E  TG
2 G  +TG
3G
4 T  FU
5 U  *FU
6U
7F(E)
8 F  number
I vuoti nella tabella corrispondono a errori sintattici.
La tabella specifica i collegamenti nelle procedure del programma
di analisi per discesa ricorsiva.
Può anche essere usato come il dato di un programma universale
di analisi discendente non ricorsiva.
Traduzione cap3 15
3.4 L’analisi ascendante
Si utilizza uno pila e un automa. Le transizioni di esso
dipendono dal simbolo seguente:
oppure
• si mette uno stato sulla pila (push) e si rimuove il simbolo
di previsione (spostamento);
o
• si rimuove dalla pila un numero di stati uguale alla lunghezza
della regola riconosciuta (pop) e si mette sulla pila un nuovo
stato (riduzione).
pila
parte analizzata parte non analizzata
Traduzione cap3 16
Esempio: espressioni aritmetiche
0 A  E$
FIRST:
1 E  E +T
A
E
T
F
2ET
3 T  T *F
NEXT:
4TF
5 F  (E )
F
T
E
$
6Fn
+
*
)
(
n
Calcolo degli stati: regole marcate (items);
Lo stato iniziale contiene la produzione aumentata con il marchio
in posizione iniziale;
Se uno stato contiene l'item x  u •yv, contiene anche tutti
gli items y  •w (chiusura di un item) ;
Se uno stato contiene l'item x  u •yv, c'è una transizione con il
simbolo y sullo stato che contiene x  uy •v.
Traduzione cap3 17
stato 0
stato 1
A  •E$
E  •E +T
E  •T
T  •T *F
T  •F
F  •(E )
F  •n
E
A  E •$
E  E • +T
$
+
stato 2
T
ET•
T  T • *F
F
stato 3
*
stato 4
Fn•
n
(
F  (•E )
E  •E +T
E  •T
T  •T *F
T  •F
F  •(E )
F  •n
E  E + •T
T  •T *F
T  •F
F  •( E )
F  •n
T  T * •F
F  •(E )
F  •n
(
stato 5
stato 6
stato 7
TF•
n
ACCETTATA
E
T
F
stato 8
F  (E •)
E  E • +T
T
F
(
n
F
(
n
)
+
stato 9
E  E +T •
T  T • *F
3
4
5
*
7
stato 10
T  T *F •
4
5
stato 11
F  (E )•
6
2
3
Automa costruito dalla grammatica precedente
Traduzione cap3 18
Fonzionamento del automa:
All'inizio, la pila contiene lo stato 0.
Si legge il simbolo seguente del testo da analizzare; l'ultimo
stato sulla pila e questo simbolo indicano al automa il
numero dello stato da mettere sulla pila (spostamento).
Quando uno stato contiene un item di tipo x  u •, si possono
rimuovere dalla pila gli ultimi |u| stati; si legge il nuovo stato
sulla pila; questo, con x, indica al automa un nuovo stato,
che si sostituisce sulla pila a quelli rimossi (riduzione).
In certi casi, più di una possibilità esiste: si dice che c'è un
conflitto spostamento-riduzione o riduzione–riduzione;
Il caso più generale è quando lo stesso stato contiene
x  u •, y  v •, z  r •st, dove s è un simbolo terminale.
Il conflitto può essere tolto se NEXT(x), NEXT(y) e {s} sono
disgiunti.
Se è il caso, si dice che la grammatica è SLR(1).
Traduzione cap3 19
La sequenza delle reduzioni costituisce una derivazione della parola
da analizzare, a partire dalla fine, dalla destra verso la sinistra.
Esempio: L'unico conflitto si trova nello stato 9. È tolto dal esame di
NEXT(E).
0
1
2
3
4
5
6
7
8
9
10
11
n
d5
d5
d5
d5
+
*
d6
r2
r4
d7
r4
r6
r6
d6
r1
r3
r5
d7
r3
r5
(
d4
d4
d4
d4
)
$
r2
r4
A
r2
r4
r6
r6
d11
r1
r3
r5
r1
r3
r5
E
d1
T
d2
F
d3
d8
d2
d3
d9
d3
d10
Tabella di analisi SLR(1) delle espressioni aritmetiche
Traduzione cap3 20
Esempio: (3 + 2) * 4 $
pila
0
04
045
043
042
048
0486
04865
04863
04869
048
0 4 8 11
03
02
parte non
analizzata
(3 + 2) * 4 $
3 + 2) * 4 $
+ 2) * 4 $
+ 2) * 4 $
+ 2) * 4 $
+ 2) * 4 $
2) * 4 $
)*4$
)*4$
)*4$
)*4$
*4$
*4$
*4$
regola
Fn
TF
ET
pila
027
0275
0 2 7 10
02
01
parte non
analizzata
4$
$
$
$
$
regola
Fn
T T *F
ET
ACCET.
Derivazione ottenuta:
Fn
TF
E  E +T
F  (E )
TF
E T T *F T * 4 F * 4
 (E) * 4  (E + T) * 4
(E + F) * 4 (E + 2) * 4
(T + 2) * 4 (F + 2) * 4
(3 + 2) * 4
Traduzione cap3 21
Certe volte, i conflitti non possono essere tolti dall'esame degli
insiemi NEXT. Si può allora tenere conto dei caratteri che
possono seguire una variabile durante la costruzione.
Se l’automa costruito così non ha più conflitti, si dice che la
grammatica è LR(1).
Maggiore problema: il numero degli stati può diventare troppo
grande.
Compromesso: sull'automa simplice costruito precedentemente,
si può definire dinamicamente l'insieme dei caratteri che
possono seguire una variabile. Nei casi di reduzioni, questi
insiemi si sostituiscono agli insiemi NEXT del caso SLR(1).
Se allora i conflitti sono tolti, si dice che la grammatica è LALR(1).
Questo metodo è usato da YACC.
LR(1)  LALR(1)  SLR(1)
Traduzione cap3 22
Regola di propagazione della previsione:
item x  u •yv (z)
da per chiusura y  •w (FIRST(vz))
per transizione x  uy •v (z)
Si costruisce il grafo di dipendenza degli items. I caratteri di
previsione ammissibili sono calcolati seguendo quel grafo.
stato 0
A  •E$
E  •E +T
E  •T
T  •T *F
T  •F
F  •(E )
F  •n
( )
($, +)
($, +)
($, +, *)
($, +, *)
($, +, *)
($, +, *)
T
stato 2
ET•
($, +)
T  T • *F ($, +, *)
conflitto tolto
Per questa grammatica, stesso risultato con LALR(1) o con SLR(1).
Traduzione cap3 23
Uso dell'ambiguità:
0 A  E$
1 E  E +E
2 E  E *E
3 E  (E )
4En
Grammatica ambigua per
espressioni aritmetiche
NEXT(E ) = {$, +, *, )}
L'ambiguità impedisce un'analisi sia discendente che ascendente.
Le tecniche precedenti non possono togliere i conflitti.
Traduzione cap3 24
stato 0
stato 1
E
A  •E$
E  •E +E
E  •E *E
E  •(E )
(
E  •n
n
(
stato 9
En•
n
A  E •$
E  E •+E
E  E •*E
stato 2
E  (•E )
E  •E +E
E  •E *E
E  •(E )
E  •n
$
stato 3
+
E  E + •E
E  •E +E
E  •E *E
E  •(E )
E  •n
*
stato 4
E  E * •E
E  •E +E
E  •E *E
E  •(E )
E  •n
E
stato 5
E  (E •)
E  E •+E
E  E •*E
stato 6
ACCETTATA
E  E +E •
E  E •+E
E  E •*E
E
(
n
+
*
3
4
2
9
stato 7
E  E *E •
E  E •+E
E  E •*E
E
(
n
+
*
3
4
2
9
stato 8
E  (E ) •
)
+
*
3
4
Traduzione cap3 25
stato 6
E  E +E •
E  E •+E
E  E •*E
Conflitti spostamento-riduzione
Con $, ), niente conflitto, si riduce
Con +, si riduce poichè + associativo a sinistra
Con *, si sposta poichè * ha precedenza su +
stato 7
E  E *E •
E  E •+E
E  E •*E
Con $, ), niente conflitto, si riduce
Con +, si riduce poichè * ha precedenza su +
Con *, si riduce poichè * associativo a sinistra
Regole di precedenza per togliere i conflitti spostamento-riduzione
Se conflitto tra x  u op1y • e x  u •op2y
1) op1 ha precedenza su op2, si riduce;
2) op2 ha precedenza su op1, si sposta;
3) op1 e op2 hanno stessa precedenza:
3.1) associatività a sinistra, si riduce;
3.2) associatività a destra, si sposta;
3.3) niente associatività, segnalare un errore.
Traduzione cap3 26
Gestione degli errori: Grammatica ambigua precedente
Esempi di correzione
possibile. Correzioni
in corsivo
0
1
2
3
4
5
6
7
8
9
n
d9
3
d9
d9
d9
3
r1
r2
r3
r4
+
1
d3
1
1
1
d3
r1
r2
r3
r4
*
1
d4
1
1
1
d4
d4
r2
r3
r4
(
d2
3
d2
d2
d2
3
r1
r2
r3
r4
)
2
2
2
2
2
d8
r1
r2
r3
r4
$
1
A
1
1
1
4
r1
r2
r3
r4
E
d1
d5
d6
d7
Azioni correttrici:
1 Inserire un n fittivo (e dunque porre 9 sulla pila)
e segnalare "missing number"
2 Togliere ) dal testo e segnalare "extra closing parenthesis"
3 Inserire un + fittivo (e dunque porre 3 sulla pila)
e segnalare "missing operator"
4 Inserire un ) fittivo (e dunque porre 8 sulla pila)
e segnalare "missing closing parenthesis".
Traduzione cap3 27
Scarica

Document