Progettazione del compilatore - Parser bottom-up

L'analisi dal basso verso l'alto inizia dai nodi foglia di un albero e lavora verso l'alto fino a raggiungere il nodo radice. Qui partiamo da una frase e poi applichiamo le regole di produzione in modo inverso per arrivare al simbolo di inizio. L'immagine fornita di seguito mostra i parser bottom-up disponibili.

Shift-Reduce Parsing

L'analisi Shift-reduce utilizza due passaggi unici per l'analisi bottom-up. Questi passaggi sono noti come shift-step e reduce-step.

• Shift step: La fase di spostamento si riferisce all'avanzamento del puntatore di input al simbolo di input successivo, chiamato simbolo di spostamento. Questo simbolo viene inserito nella pila. Il simbolo spostato viene trattato come un singolo nodo dell'albero di analisi.

• Reduce step: Quando il parser trova una regola grammaticale completa (RHS) e la sostituisce in (LHS), è nota come reduce-step. Ciò si verifica quando la parte superiore dello stack contiene un handle. Per ridurre, viene eseguita una funzione POP sulla pila che si solleva dalla maniglia e la sostituisce con il simbolo non terminale LHS.

LR Parser

Il parser LR è un parser non ricorsivo, shift-reduce, bottom-up. Utilizza un'ampia classe di grammatica senza contesto che la rende la tecnica di analisi della sintassi più efficiente. I parser LR sono anche conosciuti come parser LR (k), dove L sta per scansione da sinistra a destra del flusso di input; R sta per la costruzione della derivazione più a destra al contrario e k denota il numero di simboli di lookahead per prendere decisioni.

Sono disponibili tre algoritmi ampiamente utilizzati per la costruzione di un parser LR:

• SLR (1) - Parser LR semplice:
  • Funziona sulla più piccola classe di grammatica
  • Pochi stati, quindi tavolino molto piccolo
  • Costruzione semplice e veloce
• LR (1) - LR Parser:
  • Funziona sul set completo di LR (1) Grammar
  • Genera una tabella di grandi dimensioni e un numero elevato di stati
  • Costruzione lenta
• LALR (1) - Parser LR Look-Ahead:
  • Funziona su dimensioni intermedie della grammatica
  • Il numero di stati è lo stesso di SLR (1)

Algoritmo di analisi LR

Qui descriviamo un algoritmo scheletro di un parser LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL contro LR

LL	LR
Esegue una derivazione più a sinistra.	Esegue una derivazione più a destra al contrario.
Inizia con la radice non terminale nello stack.	Termina con la radice non terminale nello stack.
Termina quando la pila è vuota.	Inizia con una pila vuota.
Utilizza lo stack per designare ciò che è ancora da aspettarsi.	Usa lo stack per designare ciò che è già stato visto.
Costruisce l'albero di analisi dall'alto verso il basso.	Costruisce l'albero di analisi dal basso verso l'alto.
Estrae continuamente un non terminale dalla pila e spinge il lato destro corrispondente.	Prova a riconoscere un lato destro sulla pila, lo apre e spinge il corrispondente non terminale.
Espande i non terminali.	Riduce i non terminali.
Legge i terminali quando ne estrae uno dallo stack.	Legge i terminali mentre li spinge sullo stack.
Preordinare l'attraversamento dell'albero di analisi.	Attraversamento post-ordine dell'albero di analisi.