Linguaggi context free
Analizzatori sintattici e alberi
di analisi
E E * E ( E ) id E +
E id id 2
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche Context Free
•  Una grammatica CF ha produzioni del tipo
X → α con X ∈ N e α ∈ (T ∪ N)*
▫  sono “libere dal contesto” perché la sostituzione di X è indipendente dal
contesto in cui si trova. E’ sempre possibile sostituire X con α
βXγ ⇒
βαγ
G
∀ β,γ ∈ (T ∪ N)*
▫  permettono di definire linguaggi abbastanza espressivi come i linguaggi
di programmazione, le espressioni aritmetiche e… le espressioni regolari
3
Marco Maggini
Grammatiche CF –
Tecnologie per l'elaborazione del
linguaggio
espressioni artimetiche
E → “numero”
E→(E)
E → E + E E → E – E T = {“numero”,(,),+,-,*,/}
N = {E}
E → E * E E → E / E ▫  La grammatica definisce la struttura delle espressioni aritmetiche in
modo ricorsivo
▫  Il simbolo terminale “numero” corrisponde ad un insieme di stringhe che
si possono descrivere con una RE
▫  A partire da simbolo E si possono generare tutte le espressioni
aritmetiche possibili
4
Marco Maggini
Grammatiche CF -
Tecnologie per l'elaborazione del
linguaggio
esempio
S → aB
A → bAA T = {a,b}
S → bA
B → b
N = {S,A,B}
A → a
B →bS A →aS
B →aBB •  In genere è complesso descrivere in modo compatto qual è il
linguaggio definito da una grammatica
▫  Nel caso dell’esempio L(G) è il linguaggio che in base alla scelta del
simbolo di start
* w tale che w ha un ugual numero di a e b
  S ⇒
* w tale che w ha un numero di a maggiore di 1 rispetto a quello di b
  A ⇒
* w tale che w ha un numero di b maggiore di 1 rispetto a quello di a
  B ⇒
▫  La dimostrazione si fa per induzione
5
Marco Maggini
Gramatiche CF –
Tecnologie per l'elaborazione del
linguaggio
esempio: dimostrazione
•  Per |w| = 1 le uniche derivazioni possibili sono
* ae B⇒
* b
▫  A ⇒
•  Si suppone che le ipotesi siano vere per |w|=k-1
* w può essere ottenuta da
▫  S ⇒
  S → aB dove aB = a w1 con |w1| = k-1 e B ⇒ w1.
Per ipotesi di induzione w1 ha 1 b in più e quindi w ha lo stesso numero di a e b
  S → bA dove bA = b w1 con |w1| = k-1 e A ⇒ w1.
Per ipotesi di induzione w1 ha 1 a in più e quindi w ha lo stesso numero di a e b
▫  A ⇒ w può essere ottenuta da
  A → aS dove aS = a w1 con |w1| = k-1 e S ⇒ w1.
Per ipotesi di induzione w1 ha lo stesso numero di a e b e quindi w ha 1 a in più
  A → bAA dove bAA = b w1w2 con |w1| < k-1 |w2| < k-1 e A ⇒ w1, A ⇒ w2.
Per ipotesi di induzione w1, w2 hanno 1 a in più delle b e quindi in totale c’è 1 a
in più in w
* w si procede in modo analogo
▫  B ⇒
6
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Alberi di analisi (parse tree)
•  La derivazione di ogni stringa appartenente ad un linguaggio
generato da una grammatica CF si può rappresentare con un albero
E → id
E E→(E)
E * E ( E ) id E + E E → E + E E → E – E E → E * E E → E / E id id (id+id)*id 7
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Parse tree - definizione
•  I nodi dell’albero di analisi sono etichettati dai simboli terminali o
non terminali
▫  I simboli terminali si trovano nelle foglie
▫  I simboli non terminali si trovano nei nodi interni
▫  La radice corrisponde al simbolo non terminale di start
•  Ogni nodo interno corrisponde esattamente ad una produzione
▫  Il nodo padre è il simbolo non terminale che viene espanso
▫  I nodi figli corrispondono ai simboli terminali e non terminali nella parte
destra della produzione. I figli sono ordinati nello stesso modo dei
rispettivi simboli nella stringa della produzione
•  La struttura di analisi è un albero per il fatto che le produzioni
hanno la struttura N→ α propria delle grammatiche CF
▫  La stringa analizzata è leggibile con una visita anticipata dell’albero che
considera solo i simboli terminali
8
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Parse tree e derivazioni
•  Un albero sintattico può essere visto come una rappresentazione di
una serie di derivazioni α1⇒α2⇒…. ⇒αn dove α1= A ∈ N
▫  Per ciascuna stringa αi la derivazione che produce αi+1 corrisponde
all’applicazione di una produzione e quindi all’espansione di un
sottoalbero in corrispondenza di un simbolo non terminale in αi
A
A
Xj → β tree
αk-1
X1
X2
tree
β=Y1Y2…Yr Xj
Xk
X1
produzione usata per derivare αk αk
X2
Xj
Y1
Y2
Xk
Yr
9
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Parse tree - esempio
•  L’albero di analisi risultante mostra quali sono le produzioni
* αn ma non l’ordine con cui
applicate per ottenere la derivazione α1⇒
sono state applicate
E ⇒ E*E
⇒ (E) * E ⇒ (E + E) * E ⇒ (id + E) * E ⇒ (id + E)* id ⇒ (id + id)*id E E E * E E E * E ( E ) E E * E ( E ) E +
E E E id E * E ( E ) E +
E E id E * E ( E ) id E +
E E * E ( E ) id E +
E id id 10
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche ambigue
•  Una grammatica è ambigua se è possibile costruire più di un albero
sintattico per descrivere la derivazione di una stessa stringa
appartenente al linguaggio
generazione di ()()() B B→(B)
B → B B B → ε B B B B B ( B ) ( B ) ( B ) ε ε B B B→(B)B
B ( B ) B B ε ( B ) ( B ) ε grammatica ambigua ε ε B → ε ( B ) ε B ( B ) ε B ( B ) B ε ε grammatica non ambigua 11
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche ambigue – problemi
•  In genere è complesso provare se una grammatica è ambigua
•  L’ambiguità può portare problemi in alcuni casi quando l’albero
sintattico è usato per interpretare sematicamente la stringa
E → id
E→(E)
E → E + E E → E * E E → - E E ⇒ E + E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id id+id*id E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id 12
Marco Maggini
Grammatiche ambigue –
id OK espressioni 1
E E E Tecnologie per l'elaborazione del
linguaggio
E + E id * E E id id E E * + E id id KO •  La grammatica non modella la precedenza degli operatori aritmetici
▫  Se si usasse l’albero a destra per valutare l’espressione il valore non
sarebbe corretto (si effettua prima la somma)
▫  Il problema può essere risolto con una modellazione più precisa ovvero
definendo una grammatica che considera gli operatori in modo diverso
  Si introducono più categorie sintattiche per raggruppare le singole parti
dell’espressione nel modo corretto
13
Marco Maggini
Grammatiche ambigue –
Tecnologie per l'elaborazione del
linguaggio
espressioni 2
•  Si introducono tre categorie sintattiche
▫  F – fattore: è un singolo operando o espressione fra ()
▫  T – termine: è un prodotto/quoziente di fattori
▫  E – espressioni: è la somma/sottrazione di termini
E→E+T|E–T|T
T→T*F|T/F|F
F → ( E ) | id
•  L’uso di produzioni del tipo E→ E + T impone che i termini siano raggruppati da sinistra a destra (es. 1+2+3 → (1+2)+3 ) 14
Marco Maggini
Grammatiche ambigue -
Tecnologie per l'elaborazione del
linguaggio
espressioni
id+id*id derivazione con sostituzione a sinistra E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + T * F ⇒ id + F * F ⇒ id + id * F ⇒ id + id * id E E E→E+T|E–T|T
T→T*F|T/F|F
F → ( E ) | id
T + T T F F id id * F id OK 15
Marco Maggini
Ambiguità –
Tecnologie per l'elaborazione del
linguaggio
if… then… else
<stmt> → if <expr> then <stmt>
<stmt> → if <expr> then <stmt> else <stmt>
<stmt> → “instruction” ….
•  La grammatica è ambigua perché “if E1 then if E2 then S1 else S2” ha
due alberi di analisi validi
<stmt>
<stmt>
if <expr> then <stmt>
if <expr> then <stmt>
E1
if <expr> then <stmt> else <stmt>
E2
S1
S2
E1
else
if <expr> then <stmt>
E2
S1
<stmt>
S2
16
Marco Maggini
Ambiguità –
Tecnologie per l'elaborazione del
linguaggio
“if.. then.. else” non ambiguo
•  L’ambiguità deriva dal fatto che la grammatica non permette una
chiara associazione fra “else” e gli “if” presenti
▫  La regola normalmente usata è che l’else si riferisca all’if più vicino
<stmt>
<stmt> → <stmt_c> | <stmt_u>
<stmt_c> → if <expr> then <stmt_c> else <stmt_c>
<stmt_c> → “instruction” ….
<stmt_u>
if <expr> then <stmt>
<stmt_u>→ if <expr> then <stmt>
<stmt_u>→ if <expr> then <stmt_c> else <stmt_u>
<stmt_u>
E1
if <expr>then<stmt_c> else <stmt_u>
fra then-else possono solo trovarsi
espressioni if-then-else complete E2
S1
S2
17
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Produzioni equivalenti
•  Si possono riscrivere alcune produzioni in modo da ottenere una
*
grammatica
equivalente (che genera lo stesso linguaggio) ma in cui
le produzioni rispettano tutte alcune strutture
▫  Eliminazione della ricorsione a sinistra
Una grammatica è ricorsiva a sinistra se esiste un simbolo non terminale
+
A per il quale esiste una derivazione A ⇒
Aα dove α (T ∪ N)*
Produzione
semplice
A→Aα
A → β A’
A → β
A’ → α A’ | ε
genera le stringhe
A → β αn
18
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Ricorsione a sinistra
•  La ricorsione a sinistra nelle produzioni si può eliminare
semplicemente anche nel caso più generale
A → A α1 | Aα2 | … | Aαm
A → β1 A’ | β2 A’ | …. | βn A’
A → β1 | β2 | …… | βn
A’ → α1 A’ | α2 A’ | …. | αm A’ | ε
•  Per eliminare la ricorsione a sinistra che riguarda derivazioni a uno
o più passi esiste comunque un algoritmo
▫  L’eliminazione della ricorsione a sinistra semplifica la realizzazione di
parser che analizzano la stringa da sinistra a destra
▫  La ricorsione a destra realizza un’espansione delle stringhe verso destra
19
Marco Maggini
Ricorsione a sinistra -
Tecnologie per l'elaborazione del
linguaggio
esempio
•  Si elimina la ricorsione a sinistra per la grammatica delle espressioni
aritmetiche
E→E+T|T
α = +T β = T
E’ → + TE’ | ε
T → T * F | F
F → (E) | id
E → TE’
α = *F β = F
T → FT’
T’ → * FT’ | ε
F → (E) | id
20
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Fattorizzazione a sinistra
•  La fattorizzazione a sinistra è una trasformazione delle produzioni
che genera una grammatica equivalente
A → α β1 | α β2 | … | α βn
A → α A’
A’ → β1 | β2 | … | βn
▫  Nelle produzioni si assume che β1, β2, … ,βn non abbiano un prefisso in
comune
▫  Nell’ottica di un’analisi della stringa da sinistra a destra la fattorizzazione
permette una prima decisione con l’espansione di α rimandando la scelta
di quale espandere fra β1, β2, … ,βn al passo successivo
21
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi discendente (top-down)
•  L’analisi discendente è un algoritmo che mira a costruire l’albero di
analisi a partire dalla radice, creando i nodi in ordine anticipato
•  L’analisi discendente ricorsiva
▫  In genere necessità di backtracking – quando ci sono più opzioni nella
scelta della produzione da applicare, si prova con la prima e si tentano
quelle seguenti in caso di fallimento
▫  La grammatica definisce un insieme di funzioni mutuamente ricorsive
ciascuna delle quali corrisponde ad una delle categorie sintattiche
(simboli non terminali)
▫  La chiamata di una delle funzioni corrisponde all’applicazione di una
produzione (espansione del simobolo non terminale)
▫  La funzione per il simbolo di start S legge una sequenza di ingresso e
produce il puntatore all’albero di analisi generato (nullo se la stringa in
ingresso non appartiene al linguaggio e si genera un errore di analisi)
22
Marco Maggini
Analisi top-down -
Tecnologie per l'elaborazione del
linguaggio
esempio
S → cAd
S()
A → ab | a
A()
backtracking
S()
w = cad
c cad
A()
S A d S()
S c d A a cad
b c cad
A()
S A d c S A a cad
•  Una grammatica ricorsiva a sinistra può generare un numero
infinito di espansioni in un parser top-down ricorsivo (si espande
all’infinito lo stesso simbolo)
d 23
Marco Maggini
Analisi top-down –
Tecnologie per l'elaborazione del
linguaggio
procedura di analisi 1
•  Si tiene traccia del prossimo simbolo della stringa di ingresso che
deve essere generato nell’albero di analisi
▫  Si restringe il numero di produzioni che possono essere applicate per
espandere un simbolo non terminale
•  Si espandono i nodi da sinistra a destra
▫  un simbolo terminale soddisfa l’obiettivo se coincide col prossimo
simbolo della sequenza di ingresso
▫  un simbolo non terminale soddisfa l’obiettivo se lo soddisfa la chiamata
alla funzione ricorsiva corrispondente
Stringa in ingresso
x1x2…..xn$
Cursore di ingresso
(simbolo di previsione)
24
Marco Maggini
Analisi top-down –
Tecnologie per l'elaborazione del
linguaggio
procedura di analisi 2
•  Quando si espande una produzione (si chiama la funzione ricorsiva
corrispondente) e si genera un simbolo terminale si verifica se
corrisponde a quello puntato dal cursore in ingresso
▫  Sì – si sposta il cursore in avanti e si procede nell’analisi
▫  No – si fallisce e si prova a soddisfare l’obiettivo precedente con una
nuova ipotesi (backtracking)
•  Se l’espansione introduce un simbolo non terminale T si chiama la
funzione ricorsiva corrispondente che crea il sottoalbero di analisi
che ha T come radice
25
Marco Maggini
Analisi top-down -
Tecnologie per l'elaborazione del
linguaggio
esempio
Node *B(int *lh, char *s) {
Node *b1,*b2;
cursore di ingresso
if(s[*lh]==‘(‘) {
stringa da analizzare
(*lh)++; b1 = B(lh,s);
if((s[*lh]==‘)‘)&&(b1!=NULL)){
(*lh)++; b2 = B(lh,s);
B→(B)B|ε
if(b2==NULL) {
freeTree(b1); return(NULL);
} else
B return tree4(‘B‘,tree0(‘(‘),b1,tree0(‘)’),b2);
} else {
freeTree(b1); return NULL;
b1 }
} else
return tree1(‘B’,tree0(‘e’));
}
) ( B ε b2 26
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analizzatori predittivi
•  Si elimina la ricorsione a sinistra
•  Si fattorizzano a sinistra le produzioni
▫  Per alcune grammatiche si può costruire un parser predittivo che non
effettua il backtracking durante l’analisi
▫  Il simbolo terminale di previsione permette sempre di selezionare una
sola produzione da applicare
a
simbolo in
ingresso
A
non terminale
da espandere
A→α1|α2|….|αn
produzioni per A
27
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi predittiva
•  Per riconoscere quale pruduzione si applica si possono usare
diagrammi a stati che rappresentano le sequenze nel lato destro
delle produzioni
▫  Le transizioni fra gli stati possono avvenire in corrispondenza di un
simbolo terminale (si legge l’input) o non terminale (si chiama la
procedura corrispondente)
E → TE’
0
T
1
E’ → + TE’ | ε
3
+
4
T → FT’
7
F
8
T’ → * FT’ | ε
10
F → (E) | id
14
*
(
11
15
E’
T
ε
T’
F
ε
E
id
2
5
9
12
16
E
E’
T
T’
)
6
E’
13
T’
17
F
28
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi guidata da tabella
•  Si utilizza esplicitamente uno stack invece delle chiamate ricorsive
a + b $
simboli della
grammatica
T∪N
stringa da analizzare
X
albero
sintattico
Y
Z
$
stack
Tabella di
analisi
Tabella bidimensionale
M[A,s]
non terminale
terminale o $
29
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi con tabella - funzionamento
•  Lo stack inzialmente contiene il simbolo S
•  Il controllo determina l’azione da eseguire in base al simbolo in testa
allo stack (X) e al simbolo terminale in ingresso (a)
▫  Se X=a=$ il parser termina con successo
▫  Se X=a≠$ il parser estrae X dallo stack e avanza il cursore di ingresso di
una posizione (match del simbolo di previsione)
▫  X è un simbolo non terminale – si controlla M[X,a]
  Se corrisponde a una produzione si fa il push nello stack degli elementi della
stringa a destra
X → UVW push(W); push(V); push(U)
  Altrimenti si genera un errore di analisi
▫  Se X≠a e X è un simbolo terminale, allora si genera un errore di analisi
30
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi con tabella - esempio
E → TE’
stack
E’ → + TE’ | ε
$E
$E’T
$E’T’F
$E’T’id
$E’T’
$E’
$E’T+
$E’T
$E’T’F
$E’T’id
$E’T’
$E’T’F*
$E’T’F
$E’T’id
$E’T’
$E’
$
T → FT’
T’ → * FT’ | ε
F → (E) | id
id
E
E’
T
T’
TE’
F
id
+
*
(
)
$
TE’
+TE’
ε
FT’
ε
FT’
ε
*FT’
ε
(E)
ε
input
id+id*id$
id+id*id$
id+id*id$
id+id*id$
+id*id$
+id*id$
+id*id$
id*id$
id*id$
id*id$
*id$
*id$
id$
id$
$
$
$
output
E → TE’
T → FT’
F → id
T’ → ε
E’ → +TE’
T → FT’
F → id
T’ → *FT’
F → id
T’ → ε
E’ → ε
31
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi con tabella – costruzione 1
•  Si considerano due funzioni
▫  FIRST(α) è l’insieme dei simboli terminali che inziano le stringhe
generate a partire da α ∈ (T ∪ N)*
▫  FOLLOW(A) è l’insieme dei simboli terminali che possono apparire
subito alla destra del simbolo A ∈ N in una stringa derivata da S (esiste
una derivazione S⇒αAaβ con a ∈ T)
•  Calcolo di FIRST(x) x ∈ T ∪ N
▫  se x ∈ T allora FIRST(x) = {x}
▫  se x ∈ N ed esiste la produzione x→ε allora ε ∈ FIRST(x)
▫  se x ∈ N ed esiste la produzione x→Y1Y2…Yk
  a ∈ FIRST(x) se a ∈ FIRST(Yi) e ε ∈ FIRST(Yj) j=1,..,i-1 (Y1…Yi-1⇒ε)
  ε ∈ FIRST(x) se ε ∈ FIRST(Yj) j=1,..,k
In pratica si aggiungono a FIRST(x) gli elementi di FIRST(Yi) fino a che non si
incontra un Yi per il quale ε ∉ FIRST(Yi)
32
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi con tabella – costruzione 2
•  Calcolo di FIRST(α) α ∈ (T ∪ N)* con α = Y1Y2…Yk
▫  F = FIRST(Y1)
▫  for(i=1; i<k && ε ∉ FIRST(Yi);i++)
  F = F ∪ FIRST(Yi+1)
•  Calcolo di FOLLOW(A)
▫  $ ∈ FOLLOW(S)
▫  Se esiste la produzione B→αAβ tutti i simboli in FIRST(β) eccetto ε sono
in FOLLOW(A)
▫  Se esiste una produzione B→αA o B→αAβ e FIRST(β) contiene ε allora
tutto ciò che è in FOLLOW(A) è anche in FOLLOW(B)
33
Marco Maggini
Analisi con Tabella –
E → TE’
E’ → + TE’ | ε
T → FT’
Tecnologie per l'elaborazione del
linguaggio
esempio FIRST/FOLLOW
FIRST(E) = {(,id}
FIRST(T) = {(,id}
FIRST(F) = {(,id}
FIRST(E’) = {+,ε}
FIRST(T’) = {*,ε}
T’ → * FT’ | ε
FOLLOW(E) = {),$}
F → (E) | id
FOLLOW(T) = {),+,$}
FOLLOW(F) = {),*,+,$}
FOLLOW(E’) = {),$}
FOLLOW(T’) = {),+,$}
34
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi con tabella – costruzione
•  Gli elementi della tabella di analisi sono definiti da
▫  Se esiste la produzione A →α allora per ogni simbolo a in FIRST(α)
M[A,a] = {A →α}
Infatti se si è nello stato A e si legge a si dve espandere la produzione A in
α perché garantisce che venga generato il simbolo a
▫  Se ε ∈ FIRST(α) allora M[A,b] = {A →α} per ogni simbolo b in
FOLLOW(A)
Tiene conto del fatto che se α⇒ε allora il simbolo a deve essere generato
da qualche produzione in cui A compare seguito da un’altra espressione
che può generare a
35
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi con tabella – grammatiche ambigue
•  Il procedimento per la costruzione della tabella d’analisi può portare
a generare elementi della matrice M che contengono più alternative
S → i E t S S’ | a
S’ → eS | ε
FIRST(S) = {i,a}
FIRST(S’) = {e, ε}
FIRST(E) = {b}
E → b
grammatica per
if-then-else
FOLLOW(S) = {e,$}
FOLLOW(S’) = {e,$}
FOLLOW(E) = {t}
a
S
S’
E
b
e
a
i
t
$
iEtSS’
ε
eS
b
ε
36
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche LL(1)
•  Una grammatica che non ha definizioni multiple nella tabella di
analisi discendente si dice LL(1)
▫  Left-to-right nella scansione dell’ingresso
▫  Leftmost – si espande sempre il simbolo più a sinistra
▫  1 si usa un simbolo di previsione
•  Non tutte le grammatiche CF sono LL(1)
▫  Si deve eliminare la ricorsione a sinistra
▫  Si deve fattorizzare a sinistra
▫  Non è comunque detto di ottenere una grammatica LL(1)
37
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi ascendente (bottom-up)
•  L’albero di analisi viene costruito a partire dalle foglie verso la
radice
▫  Si riduce una stringa di ingresso al simbolo non terminale di scopo S
▫  Ad ogn passo una sottostringa che corrisponde al lato destro di una
produzione è rimpiazzata col simbolo terminale a sinistra
▫  si genera il corrispondente nodo dell’albero di analisi collegando i nodi
figli al padre
abbcde
sottostringhe a cui
S → aABe
si può applicare
aAbcde
A → Abc | b
A → b
aAde
B → d
B → d
aABe
S
38
Marco Maggini
Analisi bottom-up –
Tecnologie per l'elaborazione del
linguaggio
scelta delle riduzioni
S → aABe
A → Abc | b
S ⇒ aABe ⇒ aAde ⇒ aAbcde ⇒ abbcde B → d
•  Nell’esempio le riduzioni sono sempre scelte tenendo conto di una
derivazione della stringa in cui si sostituisce sempre il non terminale
più a destra
▫  l’approccio bottom-up riduce da sinistra a destra
•  Come si sceglie la sottostringa da ridurre?
▫  Si può prendere la più a sinistra che fa il match con il lato destro di una
produzione
▫  Non è detto che si riesca ad arrivare ad S (occorre il backtracking)
39
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analisi bottom-up –scelta delle riduzioni
•  Nell’esempio la scelta di ridurre al primo passo la sottostringa più a
sinistra ha permesso di completare l’analisi
▫  Non è in genere detto che questo accada….
▫  Se si sceglie in modo sbagliato si arriva ad un risultato intermedio in cui
non esistono sottostringhe che fanno match con almeno un lato destro di
una produzione
S → aABe
abbcde
A → Abc | b
B → d
se al secondo passo si
sceglie A → b
aAAcde
aAbcde
aAAcBe
non è più riducibile….
40
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Sottostringhe handle
•  Una sottostringa handle
▫  corrisponde al lato destro di una produzione A→β
▫  si può rimpiazzare con A nella stringa di partenza γ ottenendo un passo
* αAw ⇒ αβw (w contiene solo
della derivazione destra di γ da S S rm
⇒
simboli terminali perché la derivazione è destra - right most)
▫  Se la grammatica è ambigua la stessa sottostringa può appartenere a più
di un handle
S
A
α
β
handle
w
ridurre β in A
corrisponde ad
eliminare tutti i figli di
A dall’albero
41
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Riduzione
•  La procedura di riduzione mira a sostituire progressivamente
sottostringhe handle con il corrispondente simbolo non terminale
▫  Si parte dalla stringa di soli simboli terminali da analizzare
S = γ0 ⇒
γ ⇒ ….. ⇒
rm γ1⇒
rm γn-1⇒
rm γn = w
rm 2rm
▫  Si sotituisce l’handle βn in γn utilizzando la produzione An→βn in modo
tale che γn-1 = αn-1Awn-1
▫  Si ripete il processo fino ad ottenere S
•  Questa procedura ha due problemi correlati da risolvere
▫  Come determinare la sottostringa da ridurre
▫  Come scegliere la produzione corretta per la riduzione
42
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analizzatore bottom-up con stack
•  Si utilizza uno stack per i risultati intermedi (frontiera dell’albero)
▫  il parser inserisce simboli nello stack a partire dalla stringa in ingresso w
fino a che non viene individuato un handle β in cima allo stack
▫  Il parser riduce l’handle β al simbolo non terminale A corrispondente
▫  L’analisi si ferma con successo quando lo stack contiene solo il simbolo S
e la stringa in ingresso è vuota
•  Le azioni che il parser può eseguire sono
▫  SPOSTA (shift) – il prossimo simbolo di w è inserito nello stack
▫  RIDUCI (reduce) – viene riconosciuta una stringa handle in testa allo
stack e si rimpiazza col simbolo non terminale corrispondente
▫  ACCETTA – fine con successo dell’analisi
▫  ERRORE – l’analizzatore genera un errore di sintassi
43
Marco Maggini
Analisi bottom-up -
Tecnologie per l'elaborazione del
linguaggio
esempio
E → id
stack
input
output
E→(E)
$
$id
$E
$E+
$E+id
$E+E
$E+E*
$E+E*id
$E+E*E
$E+E
$E
id+id*i$
+id*id$
+id*id$
id*id$
*id$
*id$
id$
$
$
$
$
SHIFT
REDUCE E → id
SHIFT
SHIFT
REDUCE E → id
SHIFT (*)
SHIFT
REDUCE E → id
REDUCE E → E*E
REDUCE E → E+E
ACCEPT
E → E + E E → E * E id+id*id •  La grammatica è ambigua ed esiste un’altra riduzione possibile
▫  Esiste un conflitto SHIFT/REDUCE in (*) che è stato risolto con SHIFT
▫  Si poteva anche applicare REDUCE E → E+E 44
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Analizzatori bottom-up - conflitti
•  Il parsing ascendente con stack senza backtracking non può essere
applicato a tutte le grammatiche CF
▫  Noto il contenuto dello stack e il prossimo simbolo in ingresso
  C’è un conflitto SHIFT/REDUCE
  Non si riesce a decidere quale riduzione fare in un insieme di riduzioni possibili
•  Le azioni del parser ascendente con stack si possono determinare in
modo univoco solo se la grammatica ha date proprietà
▫  Analizzatori con operatori a precedenza
  Corrispondono a grammatiche molto particolari (grammatiche ad operatori) in
cui non esistono produzioni del tipo A→ε e per qualsiasi produzione A→β in β
non esistono due simboli non terminali adiacenti (esiste sempre un “operatore”
in mezzo). Es. espressioni aritmetiche.
▫  Analizzatori LR (Left-to-right Right-most-derivation)
45
Marco Maggini
Analizzatori LR(k)
Tecnologie per l'elaborazione del
linguaggio
46
Marco Maggini
Analizzatori LR(k) -
Tecnologie per l'elaborazione del
linguaggio
struttura
a
ToS
stato - simbolo
a1 … … ai .. an $
Sm
stringa da analizzare
albero
sintattico
Xm
Sm-1
Xm-1
Tabelle di analisi
..
..
$
stack
AZIONE
GOTO
AZIONE[S,a]
GOTO[S,A]
47
Marco Maggini
Analizzatori LR –
Tecnologie per l'elaborazione del
linguaggio
schema di funzionamento 1
•  Nello stack è memorizzata una stringa di coppie simbolo-stato
S0X1S1X2S2….XmSm
▫  Ciascun stato riassume l’informazione contenuta nello stack al di sotto di
esso ai fini del riconoscimento degli handle
▫  L’azione del parser è determinata dallo stato in testa allo stack e dal
simbolo corrente (Tos,a)
▫  Nell’implementazione i simboli del linguaggio Xi∈ (T ∪ N) non sono
strettamente necessari (lo stato già memorizza l’elaborazione della loro
sequenza)
▫  La configurazione del parser è data dal contenuto dello stack e dalla parte
di ingresso ancora da espandere
S0X1S1X2S2….XmSmaiai+1…..an$
48
Marco Maggini
Analizzatori LR –
Tecnologie per l'elaborazione del
linguaggio
schema di funzionamento 2
•  La configurazione rappresenta una stringa derivata con sostituzione
a destra
già espanso
X1X2….Xmaiai+1…..an$
da espandere
▫  Il controllo dell’analizzatore LR termina l’azione da compiere in base allo
stato Sm in testa allo stack e al simbolo corrente ai
1.  AZIONE[Sm,ai]=SHIFT S (PUSH ai, PUSH S)
La nuova configurazione è
a
S0X1S1X2S2….XmSmaiS ai+1…..an$
ToS
49
Marco Maggini
Analizzatori LR –
Tecnologie per l'elaborazione del
linguaggio
schema di funzionamento 3
2.  AZIONE[Sm,ai]=REDUCE A → β
Si opera una riduzione che corrisponde alla nuova configurazione
a
S0X1S1X2S2….Xm-rSm-rAS ai…..an$
ToS
dove S = GOTO[Sm-r,A] e r=|β| β=Xm-r+1….Xm
3.  AZIONE[Sm,ai]=ACCEPT
L’analisi è completata con successo
4.  AZIONE[Sm,ai]=ERROR
Si è rilevato un errore e si chiama la procedura di gestione degli errori
50
Marco Maggini
Analisi LR –
un esempio 1
AZIONE
1 E → E+T
2 E → T
3 T → T*F
4 T → F
5 F → (E)
6 F → id
s# = shift #nuovo stato
r# = reduce #produzione
Tecnologie per l'elaborazione del
linguaggio
stato id
0
1
2
3
4
5
6
7
8
9
10
11
+
*
s5
(
GOTO
)
$
s4
s6
r2
r4
s7
r4
s5
r2
r4
r6
s5
s5
r6
s7
r3
r5
s11
r1
r3
r5
F
1
2
3
8
2
3
9
3
10
r6
s4
s4
s6
r1
r3
r5
T
Ac
r2
r4
s4
r6
E
r1
r3
r5
51
Marco Maggini
Analisi LR –
stack
0|
0|id|5|
0|F|3|
0|T|2|
0|T|2|*|7|
0|T|2|*|7|id|5|
0|T|2|*|7|F|10|
0|T|2|
0|E|1|
0|E|1|+|6|
0|E|1|+|6|id|5|
0|E|1|+|6|F|3|
0|E|1|+|6|T|9|
0|E|1|
Tecnologie per l'elaborazione del
linguaggio
un esempio 2
input
id*id+id$
*id+id$
*id+id$
*id+id$
id+id$
+id$
+id$
+id$
+id$
id$
$
$
$
$
AZIONE
SHIFT 5
REDUCE 6
REDUCE 4
SHIFT 7
SHIFT 5
REDUCE 6
REDUCE 3
REDUCE 2
SHIFT 6
SHIFT 5
REDUCE 6
REDUCE 4
REDUCE 1
ACCEPT
riduzione
GOTO
F→id
T→F
G[0,F]=3
G[0,T]=2
F→id
T→T*F
E→T
G[7,F]=10
G[0,T]=2
G[0,E]=1
F→id
T→F
E→E+T
G[6,F]=3
G[6,T]=9
G[0,E]=1
52
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche LR - definizione
•  Una grammatica LR è una grammatica per la quale si riescono a
costruire le tabelle AZIONE e GOTO per un analizzatore LR
▫  Esistono grammatiche CF che non sono LR
▫  Una grammatica è LR se il parser SHIFT/REDUCE riesce a riconoscere
le sottostringhe handle quando compaiono in testa allo stack (per fare
questo basta lo stato)
  Per riconoscere un handle sullo stack si può usare un automa a stati finiti che
analizza i simboli contenuti nello stack e dice quale è l’handle in testa
  Questo meccanismo è implementato nella tabella GOTO
  Lo stato nella testa dello stack è lo stato di questo automa riconoscitore dopo
aver elaborato la stringa di simboli dalla base alla testa dello stack
53
Marco Maggini
Grammatiche LR -
Tecnologie per l'elaborazione del
linguaggio
proprietà
•  Le grammatiche LR(k) sono più generali di quelle LL(k)
▫  Le grammatiche LR(k) richiedono di riconoscere, con k simboli di
previsione, il lato destro di una produzione (l’handle) A→ β dopo aver
visto tutto quello che è derivato da β
▫  Le grammatiche LL(k) richiedono di riconoscere una produzione in base
ai primi k simboli di ciò che si può derivare dalla sua parte destra
•  Come si costruiscono le tabelle di analisi?
▫  Si considera un caso semplice, quello delle Simple LR (SLR) che non
copre tutte le grammatiche LR
54
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche SLR
•  Un elemento LR(0) di una grammatica G è una produzione annotata
con un punto () che individua una posizione nel lato destro
#i A → xyz
A → xyz (i,0)
A → xyz (i,1)
A → xyz (i,2)
A → xyz (i,3)
▫  Un elemento è individuato dalla coppia di indici (#produzione,posizione)
▫  Un elemento tiene traccia di quanta parte del lato destro di una
produzione è stata vista fino ad un certo punto dell’analisi
•  La costruzione delle tabelle di analisi parte dalla costruzione di un
automa a stati finiti che riconosce i prefissi associabili alle
produzioni in una derivazione destra
55
Marco Maggini
Grammatiche SLR –
Tecnologie per l'elaborazione del
linguaggio
elementi
•  Gli elementi definiti a partire da ciascuna produzione possono
essere visti come stati di un automa a stati finiti
A→αxβ
A→αBβ
x
ε
A→αxβ
B→γ
si accetta l’input x per
avanzare di un passo nel
riconoscimento di αxβ
soddisfare B significa
applicare ogni sua
espansione
▫  Si introduce un nuovo simbolo di partenza S’ e la produzione S’ →S (è la
riduzione che determina l’accettazione della stringa)
▫  Si costruisce l’automa che riconosce i lati destri delle produzioni
56
Marco Maggini
Grammatiche SLR –
ε
ε
E’→E
E→E+T
ε
ε
1
E’ → E
2-3 E → E+T| T
E’→E
T
esempio 1
E→E+T
+
E→E+T
F
T→F
ε
ε
2
ε
ε
T
T→T*F
7
id
F→id
ε
(
F→(E)
ε
6-7 F → (E) | id
F
4
T→T*F
F→(E)
E
ε
F→(E)
*
T→T*F
F→id
ε
T→T*F
E→T
4-5 T → T*F | F
E→E+T
ε
T→F
ε
3
T
ε
5
E→T
E
1
E
Tecnologie per l'elaborazione del
linguaggio
)
6
F→(E)
ε
57
Marco Maggini
Grammatiche SLR –
ε
eliminazione delle
ε-transizioni
ε
E’→E
E→E+T
ε
ε
E’→E
T
E→E+T
+
E→E+T
ε
F
T→F
ε
ε
ε
ε
T
T→T*F
7
id
F→id
T→T*F
F
T→T*F
F→id
ε
ε
(
F→(E)
ε
F→(E)
E
ε
F→(E)
*
4
E→E+T
2
T→T*F
3
T
ε
T→F
E→T
I0={[E’→E],[E→T],
[E→E+T],[T→F],
[T→T*F],[F→id],
[F→(E)]}
esempio 2
ε
5
E→T
E
1
E
Tecnologie per l'elaborazione del
linguaggio
)
6
F→(E)
ε
58
Marco Maggini
Grammatiche SLR –
esempio 3
I0={[E’→E],[E→T],
[E→E+T],[T→F],
[T→T*F],[F→id],
[F→(E)]}
F
E
E→E+T
I1
I0
T→F
I3
I5
F→id
I5={[F→id]}
E’→E
dagli stati in I1,I2,
I3, I5 non ci sono
ε-transizioni
I3={[T→F]}
id
T
I1={[E→E+T],[E’→E]}
Tecnologie per l'elaborazione del
linguaggio
T→T*F
E→T
I2
I2={[E→T],[T→T*F]}
(
I4
I4 va determinato
con eliminazione
di ε-transizioni
59
Marco Maggini
Grammatiche SLR –
ε
eliminazione delle
ε-transizioni per lo
stato F→(E)
ε
E’→E
E→E+T
ε
ε
E’→E
T
E→E+T
+
E→E+T
ε
F
T→F
ε
ε
ε
ε
T
T→T*F
7
id
F→id
T→T*F
F
T→T*F
F→id
ε
ε
(
F→(E)
ε
F→(E)
E
ε
F→(E)
*
4
E→E+T
2
T→T*F
3
T
ε
T→F
E→T
I4={[F→(E)],[E→E+T],
[E→T],[T→F],
[T→T*F],[F→id],
[F→(E)]}
esempio 4
ε
5
E→T
E
1
E
Tecnologie per l'elaborazione del
linguaggio
)
6
F→(E)
ε
60
Marco Maggini
Grammatiche SLR –
ε
transizioni da
I1={[E→E+T],[E’→E]}
E’→E
ε
E→E+T
ε
ε
E’→E
T
E→E+T
+
E→E+T
ε
F
T→F
ε
ε
ε
ε
T
T→T*F
7
id
F→id
T→T*F
F
4
T→T*F
F→id
ε
ε
(
F→(E)
ε
F→(E)
E
ε
F→(E)
*
I6={ [E→E+T],[T→F],
[T→T*F],[F→id],
[F→(E)]}
E→E+T
2
T→T*F
3
T
ε
T→F
E→T
La transizione con +
definisce
esempio 5
ε
5
E→T
E
1
E
Tecnologie per l'elaborazione del
linguaggio
)
6
F→(E)
ε
61
Marco Maggini
Grammatiche SLR –
transizioni da
I6={ [E→E+T],[T→F],
[T→T*F],[F→id],
[F→(E)]}
E’→E
ε
ε
E→E+T
E’→E
I3
5
ε
ε
E→T
E
1
E
T
ε
E→E+T
+
E→E+T
3
ε
T→F
F
T
T→T*F
T→T*F
F
4
T→T*F
7
I5
ε
id
F→id
F→id
ε
ε
(
F→(E)
ε
F→(E)
I4 E
ε
F→(E)
*
I9={ [E→E+T],[T→T*F]}
E→E+T
2
T→T*F
ε
T
ε
ε
E→T
La transizione con
T definisce
esempio 6
T→F
ε
Tecnologie per l'elaborazione del
linguaggio
)
6
F→(E)
ε
62
Marco Maggini
Grammatiche SLR –
ε
transizioni da
I2={[E→T],[T→T*F]}
E’→E
ε
E→E+T
ε
ε
E’→E
T
E→E+T
+
E→E+T
ε
F
T→F
ε
ε
ε
ε
T
T→T*F
7
id
F→id
T→T*F
F
4
T→T*F
F→id
ε
ε
(
F→(E)
ε
F→(E)
E
ε
F→(E)
*
I7={ [T→T*F],[F→id],
[F→(E)]}
E→E+T
2
T→T*F
3
T
ε
T→F
E→T
La transizione con *
definisce
esempio 7
ε
5
E→T
E
1
E
Tecnologie per l'elaborazione del
linguaggio
)
6
F→(E)
ε
63
Marco Maggini
Grammatiche SLR –
La transizione con E
definisce
ε
I8={ [E→E+T],[F→(E)]}
E’→E
ε
E→E+T
ε
ε
E’→E
I3
5
E→T
E
1
E
T
ε
E→E+T
+
E→E+T
ε
I2
E→E+T
2
ε
T→F
F
T
T→T*F
*
T→T*F
F
4
T
ε
T→T*F
7
I5
ε
id
F→id
ε
T→T*F
transizioni da
I4={[F→(E)],[E→E+T],
[E→T],[T→F],
[T→T*F],[F→id],
[F→(E)]}
I8
ε
E→T
3
esempio 8
T→F
ε
Tecnologie per l'elaborazione del
linguaggio
(
F→(E)
ε
F→id
ε
I4
F→(E)
E
ε
I8
F→(E)
)
6
F→(E)
ε
64
Marco Maggini
Grammatiche SLR –
ε
transizioni da
I7={ [T→T*F],[F→id],
[F→(E)]}
E’→E
ε
E→E+T
ε
ε
E’→E
T
3
E→E+T
+
E→E+T
T
E→E+T
2
ε
T→F
ε
F
T→F
ε
ε
ε
T
T→T*F
ε
id
F→id
ε
(
F→(E)
ε
T→T*F
I10
4
F
T→T*F
F→id
ε
I4
F→(E)
E
ε
F→(E)
*
I10={ [T→T*F]}
7
I5
T→T*F
E→T
La transizione con F
definisce
esempio 9
ε
5
E→T
E
1
E
Tecnologie per l'elaborazione del
linguaggio
)
6
F→(E)
ε
65
Marco Maggini
Grammatiche SLR –
ε
transizioni da
I8={ [E→E+T],[F→(E)]}
E’→E
ε
E→E+T
ε
ε
E’→E
T
E→E+T
+
E→E+T
ε
F
T→F
ε
ε
3
T
T→T*F
2
ε
7
id
F→id
T→T*F
F
4
T→T*F
F→id
ε
ε
(
F→(E)
ε
F→(E)
E
ε
F→(E)
*
I11={ [F→(E)]}
E→E+T
I6
T→T*F
ε
T
ε
T→F
E→T
La transizione con )
definisce
esempio 10
ε
5
E→T
E
1
E
Tecnologie per l'elaborazione del
linguaggio
I11
6
)
F→(E)
ε
66
Marco Maggini
Grammatiche SRL –
Tecnologie per l'elaborazione del
linguaggio
esempio 11
I0={[E’→E],[E→T],[E→E+T],[T→F],[T→T*F],[F→id],[F→(E)]}
I1={[E→E+T],[E’→E]}
I2={[E→T],[T→T*F]}
I3={[T→F]}
I4={[F→(E)],[E→E+T],[E→T],[T→F],[T→T*F],[F→id],[F→(E)]}
I5={[F→id]}
I6={ [E→E+T],[T→F],[T→T*F],[F→id],[F→(E)]}
I7={ [T→T*F],[F→id],[F→(E)]}
I8={ [E→E+T],[F→(E)]}
I9={ [E→E+T],[T→T*F]}
I10={ [T→T*F]}
I11={ [F→(E)]}
67
Marco Maggini
Grammatiche SRL –
stato id
*
T
F
4
1
2
3
5
4
8
2
3
6
5
4
9
3
7
5
4
5
1
(
)
esempio 12
E
0
+
Tecnologie per l'elaborazione del
linguaggio
6
2
7
3
4
5
8
9
10
11
6
10
11
7
Tabella di transizione
di stato
68
Marco Maggini
Tabelle di analisi –
Tecnologie per l'elaborazione del
linguaggio
costruzione AZIONE
•  A partire dall’automa deterministico che riconosce i prefissi dei lati
destri delle produzioni è possibile ottenere le tabelle di analisi
AZIONE e GOTO
▫  Gli stati dell’automa C={I0,I1,…,In} corrispondono agli stati 0,1,..n usati
dall’analizzatore
•  Le azioni per lo stato i sono definite come segue
▫  Se [A→αaγ] ∈ Ii e nell’automa esiste la transizione Ii→Ij per ingresso
a∈T allora AZIONE[i,a]=SHIFT j (si passa nel nuovo stato dell’automa e
non è ancora completato il match con il lato destro di una produzione)
▫  Se [A→α] ∈ Ii allora AZIONE[i,a]=REDUCE A→α per ogni simbolo a in
FOLLOW(A)
▫  Se [S’→S] ∈ Ii allora AZIONE[i,$]=ACCEPT
69
Marco Maggini
Tabelle di analisi –
Tecnologie per l'elaborazione del
linguaggio
costruzione GOTO
•  La tabella GOTO è costruita considerando per ogni stato le
transizioni per simboli non terminali
▫  Se esiste la transizione Ii→Ij per ingresso A∈N allora GOTO[i,A]=j
•  Lo stato iniziale è quello contenente [S’→S]
•  Le componenti non definite corrispondono ad errori
•  Le tabelle costruite con questo algoritmo si dicono SLR(1)
▫  Una grammatica che ammette un parser SLR(1) si dice SLR(1)
70
Marco Maggini
Tabelle di analisi I0={[E’→E],
[E→T],
[E→E+T],
[T→F],
[T→T*F],
[F→id],
[F→(E)]}
I1
E
I0
I2
T
F
(
id
I3
Tecnologie per l'elaborazione del
linguaggio
esempio
I1={[E→E+T],[E’→E]}
+
I1
I6
AZIONE[0,id] = SHIFT 4
AZIONE[1,$] = ACCEPT
AZIONE[0,(] = SHIFT 5
AZIONE[1,+] = SHIFT 6
GOTO[0,E] = 1
GOTO[0,T] = 2
GOTO[0,F] = 3
I2={[E→T],[T→T*F]}
I2
*
I7
FOLLOW(E)={$,+,)}
AZIONE[2,*] = SHIFT 7
AZIONE[2,$] = REDUCE E→T
I4
AZIONE[2,)] = REDUCE E→T
I5
AZIONE[2,+] = REDUCE E→T
71
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche non SLR(1)
•  La costruzione delle tabelle per un analizzatore SLR(1) fallisce
quando c’è un conflitto nella definizione di una componente
•  Per linguaggi più generali di SLR(1) si possono costruire
▫  Tabelle canoniche LR
▫  Tabelle LALR (LookAhead LR)
•  I problemi nascono quando ci sono più riduzioni possibili e si deve
evitare di applicare riduzioni errate che richiederebbero il
backtracking
▫  Una soluzione è usare uno stato più informativo che memorizza
esplicitamente i simboli che possono seguire un handle α per cui è
ammessa la riduzione A → α
72
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche LR
•  Si definiscono gli elementi LR(1) come coppie
[A → αβ,a]
▫  L’elemento di lookahead a ha effetto solo per gli elementi della forma
[A → α,a] dove si prevede la riduzione solo se il prossimo simbolo è a
▫  Infatti non è detto che la riduzione sia applicabile per tutti gli elementi in
FOLLOW(A) come ipotizzato nella costruzione delle tabelle SLR
•  Un analizzatore canonico LR ha molti più stati degli analizzatori
SLR e LALR
•  I generatori automatici di parser sintattici generano analizzatori
LALR