Automi pushdown e analisi

L'analisi viene utilizzata per derivare una stringa utilizzando le regole di produzione di una grammatica. Viene utilizzato per verificare l'accettabilità di una stringa. Il compilatore viene utilizzato per verificare se una stringa è sintatticamente corretta. Un parser prende gli input e costruisce un albero di analisi.

Un parser può essere di due tipi:

Top-Down Parser - L'analisi dall'alto verso il basso inizia dall'alto con il simbolo di inizio e deriva una stringa utilizzando un albero di analisi.
Bottom-Up Parser - L'analisi bottom-up inizia dal basso con la stringa e arriva al simbolo di inizio utilizzando un albero di analisi.

Progettazione del parser top-down

Per l'analisi top-down, un PDA ha i seguenti quattro tipi di transizioni:

Posiziona il non terminale sul lato sinistro della produzione in cima alla pila e spingi la sua corda sul lato destro.
Se il simbolo in alto dello stack corrisponde al simbolo di input letto, aprilo.
Spingere il simbolo di inizio "S" nella pila.
Se la stringa di input è stata letta completamente e lo stack è vuoto, passare allo stato finale "F".

Esempio

Progettare un parser top-down per l'espressione "x + y * z" per la grammatica G con le seguenti regole di produzione:

P: S → S + X | X, X → X * Y | Y, Y → (S) | id

Solution

Se il PDA è (Q, ∑, S, δ, q ₀ , I, F), l'analisi top-down è -

(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)

⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)

⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)

Progettazione di un parser bottom-up

Per l'analisi dal basso verso l'alto, un PDA ha i seguenti quattro tipi di transizioni:

Inserisci il simbolo di input corrente nello stack.
Sostituisci il lato destro di una produzione in cima alla pila con il lato sinistro.
Se la parte superiore dell'elemento dello stack corrisponde al simbolo di input corrente, visualizzalo.
Se la stringa di input è completamente letta e solo se il simbolo di inizio "S" rimane nello stack, aprilo e vai allo stato finale "F".