Differenza tra l'analisi dall'alto verso il basso e il basso
Share
Il differenza fondamentale tra l'analisi in alto e in basso è che il dall'alto al basso l'analisi esegue l'analisi dal simbolo di inizio alla stringa di input mentre l'analisi in basso esegue l'analisi dalla stringa di input al simbolo iniziale. Inoltre, un'altra importante differenza tra l'analisi top-down e bottom-up è che l'analisi top-down usa la maggior parte delle derivazioni e l'analisi bottom-down utilizza la maggior parte della derivazione..
I linguaggi di alto livello aiutano a scrivere programmi per computer. Sono più facili da capire dal programmatore ma non dal computer. Pertanto, il programma di alto livello viene convertito in codice macchina. Il compito del compilatore è convertire il codice sorgente leggibile dall'uomo in codice macchina leggibile dalla macchina. Un programma passa attraverso diversi passaggi per convertire in codice macchina. L'intero processo è chiamato sistema di elaborazione del linguaggio. Uno di questi è la compilation. L'analizzatore di sintassi o il parser si trova nel compilatore e svolge l'attività di analisi.
CONTENUTO
1. Panoramica e differenza chiave
2. Che cos'è l'analisi top-down
3. Che cos'è l'analisi in basso
4. Confronto fianco a fianco - Analisi dall'alto verso il basso e verso il basso in forma tabulare
5. Sommario
Che cos'è l'analisi top-down?
Ogni linguaggio di programmazione ha un insieme di regole per rappresentare la lingua. L'analizzatore di sintassi o l'analisi prende la stringa di input e verifica se è conforme alle produzioni grammaticali. In altre parole, la grammatica dovrebbe produrre quella stringa usando un albero di analisi.
Nell'analisi top-down, l'analisi avviene dal simbolo di partenza e raggiungerà la stringa di input specificata. Considera le seguenti regole di produzione della grammatica. La stringa di input (w) è cad.
S -> cAd
A -> ab / a
L'albero di analisi dopo aver eseguito l'analisi dall'alto verso il basso è il seguente.
Figura 01: Parse Tree 1 con l'analisi Top Down
S produce c A d e A produce a b. La stringa è cabd. Non è la stringa richiesta. Quindi, è necessario fare il backtracking, ovvero utilizzare le altre alternative.
Allo stesso modo, S produce c A d. L'applicazione dell'altra opzione per A darà a. Ora fornisce la stringa richiesta. Pertanto, il parser accetta questa stringa di input. L'albero di analisi dopo aver eseguito l'analisi dall'alto verso il basso è il seguente.
Figura 02: Parse Tree 2 con analisi Top Down
Quando la stringa di input (w) è abbcde
Considera le seguenti regole di produzione della grammatica.
S -> aABe
A -> Abc / b
B -> d
In alto verso il basso l'analisi,
S -> aABe (Sostituendo A -> Abc)
S -> aAbcBe (Sostituendo A -> b)
S -> abbcBe (Sostituisci B -> d)
S -> abbcde
La sostituzione inizia prima con la variabile più a sinistra e poi con la successiva a destra e così via. Pertanto, segue un metodo di derivazione più a sinistra. Inoltre, è importante decidere quale regola di produzione scegliere quando c'è una variabile.
Che cos'è l'analisi in basso?
In fondo, l'analisi avviene nell'altro modo. L'analisi avviene dalla stringa di input al simbolo iniziale. Considera le seguenti regole di produzione grammaticale e lascia che la stringa di input sia w ɛ cad
S -> cAd
A -> ab / a
L'albero di analisi dopo aver eseguito l'analisi dal basso è il seguente.
Figura 03: Parse Tree con analisi in basso
La stringa data è cad. La a viene generata da A. Le lettere c, A e d si combinano per ottenere il simbolo iniziale S.
Quando la stringa di input (w) è abbcde
Considera le seguenti regole di produzione della grammatica.
S -> aABe
A -> Abc / b
B -> d
Nell'analisi in basso,
S -> aABe (Sostituendo B -> d)
S -> aAde (Sostituendo A -> Abc)
S -> aAbcde (Substuting A -> b)
S -> abbcde
La sostituzione inizia prima con la variabile più a destra, quindi passa alla posizione successiva a sinistra e così via. Pertanto, segue un metodo di derivazione mot di sinistra.
Qual è la differenza tra l'analisi Top Down e Bottom Up?
L'analisi top-down è una strategia di analisi che innanzitutto analizza il livello più alto dell'albero di analisi e analizza l'albero di analisi utilizzando le regole di una grammatica formale. L'analisi in basso è una strategia di analisi che prima guarda il livello più basso dell'albero di analisi e lavora sull'albero di analisi utilizzando le regole di una grammatica formale. L'analisi si verifica dal simbolo iniziale alla stringa di input, nell'analisi in basso. D'altra parte, l'analisi si verifica dalla stringa di input al simbolo iniziale, nell'analisi in basso.
Inoltre, la decisione principale nell'analisi top down è selezionare quale regola di produzione utilizzare per costruire la stringa mentre la decisione principale nell'analisi in basso è selezionare quando utilizzare una regola di produzione per ridurre la stringa per ottenere il simbolo iniziale. Inoltre, l'analisi dall'alto verso il basso utilizza la maggior parte della derivazione sinistra e l'analisi in basso utilizza la maggior parte della derivazione.
Riepilogo: analisi dall'alto verso il basso e inferiore
La differenza tra l'analisi top down e bottom up è che l'analisi top down esegue l'analisi dal simbolo staring alla stringa di input mentre l'analisi bottom down esegue l'analisi dalla stringa di input al simbolo di partenza.
Riferimento:
1. "Compiler Design Lecture 5 - Introduction to Parsers and LL (1) Parsing." Compiler Design Lecture 5 - Introduction to Parsers and LL (1) Parsing, Gate Lectures di Ravindrababu Ravula, 22 maggio 2014. Disponibile qui
