3.3.2 Syntaktická analýza

Definice (Levá a pravá derivace)

Levá a pravá derivace

• Levá derivace v bezkontextové gramatice je taková derivace, která v každém kroku nahrazuje vždy ten neterminál, který je v dané větné formě nejvíce vlevo.
• Pravá derivace v bezkontextové gramatice je taková derivace, která v každém kroku nahrazuje vždy ten neterminál, který je v dané větné formě nejvíce vpravo.

Definice (Levý a pravý rozklad)

Levý a pravý rozklad

Předpokládáme, že pravidla v gramatice jsou očíslována.

• Levý rozklad věty \(w\) je posloupnost čísel pravidel použitých v levé derivaci.
• Pravý rozklad věty \(w\) je obrácená posloupnost čísel pravidel použitých v pravé derivaci.

Metody syntaktické analýzy

Syntaktická analýza je proces, který pro danou bezkontextovou gramatiku \(G\) a řetězec \(w\) určí, zdali \(w \in L(G)\). V kladném případě též získáme syntaktickou strukturu řetězce.

• Shora dolů (top-down): Nalezne případný levý rozklad dané věty.
• Zdola nahoru (bottom-up): Nalezne případný pravý rozklad dané věty.

Konstrukce analyzátoru metodou shora dolů

Metoda shora dolů (Top-down)

Pro danou bezkontextovou gramatiku \(G = (N, \Sigma, P, S)\) vytvoříme zásobníkový automat \(R = (\{q\}, \Sigma, N \cup \Sigma, \delta, q, S, \emptyset)\).

• Vrchol zásobníku: vlevo.
• Přijetí: prázdným zásobníkem.
• Operace:
  1. Expanze: Pro každé pravidlo \((A \to \alpha) \in P\) přidáme přechod \(\delta(q, \varepsilon, A) = \{(q, \alpha)\}\). (Neterminál na zásobníku nahradíme pravou stranou pravidla).
  2. Srovnání: Pro každý terminál \(a \in \Sigma\) přidáme přechod \(\delta(q, a, a) = \{(q, \varepsilon)\}\). (Terminál na vstupu se musí shodovat s terminálem na zásobníku).

Konstrukce analyzátoru metodou zdola nahoru

Metoda zdola nahoru (Bottom-up)

Pro danou bezkontextovou gramatiku \(G = (N, \Sigma, P, S)\) vytvoříme zásobníkový automat \(R = (\{q, r\}, \Sigma, N \cup \Sigma \cup \{Z_0\}, \delta, q, Z_0, \{r\})\).

• Vrchol zásobníku: vpravo (v kontextu zápisu na pásku, čteme "konec" zásobníku).
• Přijetí: přechodem do koncového stavu.
• Operace:
  1. Přesun (Shift): Pro každé \(a \in \Sigma\) máme přechod \(\delta(q, a, \varepsilon) = \{(q, a)\}\). (Načtení symbolu ze vstupu na zásobník).
  2. Redukce: Pro každé pravidlo \((A \to \alpha) \in P\) máme přechod \(\delta(q, \varepsilon, \alpha) = \{(q, A)\}\). (Řetězec \(\alpha\) na vrcholu zásobníku nahradíme neterminálem \(A\)).
  3. Přijetí: \(\delta(q, \varepsilon, S Z_0) = \{(r, \varepsilon)\}\). (Pokud na zásobníku zbyde jen počáteční neterminál a dno zásobníku, přijmeme).