Progettazione del compilatore - Tipi di analisi

Gli analizzatori di sintassi seguono regole di produzione definite mediante grammatica libera dal contesto. Il modo in cui vengono implementate le regole di produzione (derivazione) divide l'analisi in due tipi: analisi top-down e analisi bottom-up.

Analisi dall'alto verso il basso

Quando il parser inizia a costruire l'albero di analisi dal simbolo di inizio e quindi cerca di trasformare il simbolo di inizio nell'input, viene chiamato analisi dall'alto verso il basso.

  • Recursive descent parsing: È una forma comune di analisi top-down. Si chiama ricorsivo in quanto utilizza procedure ricorsive per elaborare l'input. L'analisi della discesa ricorsiva soffre di backtracking.

  • Backtracking: Significa che, se una derivazione di una produzione fallisce, l'analizzatore di sintassi riavvia il processo utilizzando diverse regole della stessa produzione. Questa tecnica può elaborare la stringa di input più di una volta per determinare la produzione corretta.

Analisi dal basso verso l'alto

Come suggerisce il nome, l'analisi dal basso verso l'alto inizia con i simboli di input e cerca di costruire l'albero di analisi fino al simbolo di inizio.

Example:

Stringa di input: a + b * c

Regole di produzione:

S → E
E → E + T
E → E * T
E → T
T → id

Cominciamo l'analisi dal basso verso l'alto

a + b * c

Leggi l'input e controlla se qualche produzione corrisponde con l'input:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S