Esercizio 9.3.4, questa volta anche corretto
Proviamo a ricavare l'automa simbolico per questa grammatica, magari anche senza fare errori :
- S -> aSb | ab
Partiamo dallo stato 0, che ha come kernel [S' -> .S, {$}].
Il nostro sistema all'inizio sarà quindi:
- x_0 = {$}
Vediamo subito che dobbiamo calcolare la chiusura; il lookahead set degli item della chiusura sarà calcolato come first(β∆) e in questo caso abbiamo β = ε, per cui lo stato avrà i seguenti item:
- [S' -> .S, x_0]
- [S -> .aSb, x_0]
- [S -> .ab, x_0]
Le transizioni che troviamo sono:
- tau(0, S)
- tau(0, a)
Il kernel [S' -> S, x_1] è nuovo, per cui creiamo un nuovo stato da tau(0, S).
Questo stato contiene l'accepting item.
Il sistema di equazioni è
- x_0 = {$}
- x_1 = x_0
x_1 = x_0 perché il ∆ set viene aggiornato SOLO durante il calcolo della chiusura o quando una transizione mi porta in uno stato già incontrato.
Il kernel è nuovo, per cui creiamo un nuovo stato da tau(0, a).
Il kernel:
- [S -> a.Sb, x_2]
- [S -> a.b, x_3]
Aggiorniamo il sistema:
- x_0 = {$}
- x_1 = x_0
- x_2 = x_0
- x_3 = x_0
Adesso dobbiamo calcolare la chiusura per il primo item del kernel e dobbiamo fare attenzione: è durante la chiusura che eventualmente aggiorniamo il lookahead set, e in questo caso dobbiamo farlo.
Alla fine, lo stato è fatto così:
- [S -> a.Sb, x_2]
- [S -> a.b, x_3]
- [S -> .aSb, {b}]
- [S -> .ab, {b}]
Abbiamo trovato queste transizioni:
- tau(2, S)
- tau(2, a)
- tau(2, b)
Il kernel [S -> a.Sb, x_4] è nuovo, per cui creiamo un nuovo stato da tau(2, S).
Aggiorniamo il sistema:
- x_0 = {$}
- x_1 = x_0
- x_2 = x_0
- x_3 = x_0
- x_4 = x_2
Non calcoliamo nessuna chiusura, troviamo una transizione tau(3, 6)
Da tau(2,a) avremmo un kernel con questa forma:
- [S -> .aSb, x_5], x_5 = {b}
- [S -> .ab, x_6], x_6 = {b}
Ma la componente LR(0) (cioè il primo elemento della coppia) del kernel è uguale a quella delo stato 2 che abbiamo già incontrato, quindi la procedura ci dice di non creare un nuovo stato ma aggiornare i ∆ set dello stato 2.
Il sistema è quindi:
- x_0 = {$}
- x_1 = x_0
- x_2 = x_0 u {b}
- x_3 = x_0 u {b}
- x_4 = x_2
Da tau(2, b) che deriva da [S -> a.b, x_3] abbiamo un kernel non ancora visto.
- [S -> ab., x_5]
Questo è un reducing item.
Aggiorniamo il sistema:
- x_0 = {$}
- x_1 = x_0
- x_2 = x_0 u {b}
- x_3 = x_0 u {b}
- x_4 = x_2
- x_5 = x_3
Da tau(3, b) che deriva da [S -> aS.b, x_4] abbiamo un kernel non ancora visto.
- [S -> aSb., x_6]
Questo è un reducing item.
Aggiorniamo il sistema:
- x_0 = {$}
- x_1 = x_0
- x_2 = x_0 u {b}
- x_3 = x_0 u {b}
- x_4 = x_2
- x_5 = x_3
- x_6 = x_4
Adesso che abbiamo terminato l'analisi di tutte le possibili transizioni possiamo risolvere il sistema dei ∆ set effettivi.
A questo punto sarà sufficiente sostituire i ∆ set ai simboli x_i per vedere gli stati che compongono l'automa merged nella loro forma effettiva.