Sto leggendo una spiegazione (impressionante "Parsing Techniques" di D.Grune e CJHJacobs; p.292 nella 2a edizione) su come costruire un parser LR (1), e sono nella fase di costruzione del NFA iniziale. Quello che non capisco è come ottenere / calcolare un simbolo lookahead.
Ecco l'esempio del libro, la grammatica:
S -> E
E -> E - T
E -> T
T -> ( E )
T -> n
n
è terminale. Le transizioni "strane" per me sono la sequenza:
1) S -> . E eof
2) E -> . E - T eof
3) E -> . E - T -
4) E -> E . - T -
5) E -> E - . T -
(Nota: nella tabella sopra, i numeri di stato sono in primo piano e il simbolo lookahead è alla fine.)
Ciò che mi imbarazza è che la transizione da (4) a (5) significa leggere -
token, giusto? Quindi, com'è che -
è ancora un simbolo di lookahead e ancora più importante perché eof
non è più un simbolo di lookahead? Dopotutto in un input come n - n eof
c'è solo un simbolo -
.
Il mio ingenuo pensiero mi dice (5) dovrebbe essere scritto come:
5) E -> E - . T - eof
E un'altra cosa: n
è terminale. Perché non è usato affatto come simbolo di lookahead? Voglio dire - ci aspettiamo di vedere -
o (
, è ok, ma la mancanza di n
significa che siamo sicuri che non apparirà in input?
Aggiornamento : dopo ulteriori letture sono solo più confuso ;-) I.e. cos'è veramente un aspetto? Perché vedo uno stato simile a (p.292, 2a colonna, 2a riga):
E -> E . - T eof
Lookahead dice eof
ma l'input in entrata dice -
. Non è una contraddizione? E non è solo in questo libro.