Automaty i parsowanie pushdown

Parsowanie jest używane do wyprowadzenia ciągu znaków przy użyciu reguł produkcji gramatyki. Służy do sprawdzania dopuszczalności łańcucha. Kompilator służy do sprawdzania, czy ciąg jest poprawny składniowo. Parser pobiera dane wejściowe i buduje drzewo analizy.

Parser może być dwojakiego rodzaju -

Top-Down Parser - Analiza odgórna zaczyna się od góry z symbolem startu i wyprowadza łańcuch przy użyciu drzewa parsowania.
Bottom-Up Parser - Analiza oddolna zaczyna się od dołu ciągiem i dochodzi do symbolu początkowego przy użyciu drzewa parsowania.

Projekt parsera odgórnego

W przypadku analizowania z góry na dół, PDA ma następujące cztery typy przejść -

Popchnij nieterminal po lewej stronie produkcji na szczycie stosu i popchnij jego ciąg po prawej stronie.
Jeśli górny symbol stosu pasuje do odczytywanego symbolu wejściowego, należy go zdjąć.
Wsuń symbol początkowy „S” do stosu.
Jeśli ciąg wejściowy jest w pełni odczytany, a stos jest pusty, przejdź do stanu końcowego „F”.

Przykład

Zaprojektuj odgórny parser dla wyrażenia "x + y * z" dla gramatyki G z następującymi regułami produkcji -

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

Solution

Jeśli PDA to (Q, ∑, S, δ, q ₀ , I, F), to analiza odgórna wynosi -

(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)

Projekt parsera oddolnego

W przypadku analizy oddolnej PDA ma następujące cztery typy przejść -

Wepchnij bieżący symbol wejściowy do stosu.
Zastąp prawą stronę produkcji na górze stosu lewą stroną.
Jeśli wierzchołek elementu stosu pasuje do bieżącego symbolu wejściowego, zdejmij go.
Jeśli ciąg wejściowy jest w pełni odczytany i tylko jeśli symbol początkowy „S” pozostaje na stosie, zdejmij go i przejdź do stanu końcowego „F”.