Come ottenere il simbolo lookahead durante la costruzione di LR (1) NFA per parser?

3

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.

    
posta greenoldman 29.11.2012 - 19:20
fonte

2 risposte

3

Un token lookahead è un carattere (o una sequenza di caratteri, è un token dopo tutto) definito come uno dei terminali o quei token che sono nel set FOLLOW. Guarda le possibili transizioni da Segui al prossimo PRIMO e considera che il prossimo token è probabilmente il token di eof a causa della natura dell'analisi di LR. (considera l'intero token successivo e i suoi sviluppi interiori, quindi l'analisi bottom-up.)

    
risposta data 29.11.2012 - 22:04
fonte
0

Considera l'espressione

A - B - C

Avresti E - B .- nel tuo stato di analisi. A quel punto, devi ridurre B a T, quindi ridurre E - T a E, lasciando E .- C come stato di analisi. (Sì, è sciatto.)

    
risposta data 29.11.2012 - 22:14
fonte

Leggi altre domande sui tag