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 → idCominciamo l'analisi dal basso verso l'alto
a + b * cLeggi 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