Bezkontextové jazyky

BI-SPOL.21-2

Bezkontextové jazyky:

  • Bezkontextové gramatiky, zásobníkové automaty a jejich varianty.
  • Modely syntaktické analýzy bezkontextových jazyků.

Hierarchie jazyků

../../Attachments/Pasted image 20260602113326.png

Bezkontextový jazyk

  • Je to formální jazyk, který lze přijmout zásobníkovým automatem
  • Je to formální jazyk, který lze generovat bezkontextovou gramatikou
  • Jsou uzavřené pro: sjednocení, zřetězení, iteraci
  • Nejsou uzavřené pro: průnik, doplněk, rozdíl

Příklady bezkontextových jazyků:

Bezkontextové gramatiky (BG)

(univerzální definice jako u regulární gramatiky)

#definice Gramatika je uspořádaná čtveřice , kde:
  • - konečná množina neterminálů
  • též - konečná množina terminálů
  • - množina přepisovacích pravidel
  • - počáteční symbol (neterminál) gramatiky (též větný/startovací symbol)
  • Je to formalismus pro generování jazyka
#definice Gramatika je bezkontextová, jestliže každé pravidlo má tvar
  • , kde
  • Například jazyk
  • lze generovat gramatikou

Zásobníkové automaty (ZA)

  • Prakticky konečný automat se zásobníkem
  • Nedeterministický ZA je výpočetně silnější než deterministický
  • DZA přijme řetězec, pokud přečte celý řetězec, a skončí buď v koncovém stavu, nebo s prázdným zásobníkem
#definice (Nedeterministický) zásobníkový automat je sedmice
  • - konečná množina vnitřních stavů
  • - konečná vstupní abeceda
  • ! - konečná neprázdná abeceda zásobníku
  • ! - zobrazení
    (množina všech koncových podmnožin množiny )
  • - počáteční stav
  • ! - počáteční symbol na zásobníku
  • - množina koncových stavů

../../Attachments/Pasted image 20260602122849.png

Vrchol zásobníku

  • Může být vlevo nebo vpravo
  • Výchozí varianta je s vrcholem vlevo

Mějme vstup:
../../Attachments/Pasted image 20260602123716.png

Pokud řekneme, že je vrchol vlevo:

  • Přechod na symbol
  • Pop
  • Pop
  • Push
  • Push

Pokud řekneme, že je vrchol vpravo:

  • Přechod na symbol
  • Pop
  • Pop
  • Push
  • Push

Syntaktická analýza

  • Proces, který pro BG a řetězec určí, zdali (zda-li řetězec náleží do jazyka této gramatiky)
  • Převedeme-li BG na ZA, můžeme tento automat použít k syntaktické analýze
  • Metody syntaktické analýzy:
    • Shora dolů (top-down) - nalezne levý rozklad (posloupnost čísel pravidel použitých v levé derivaci)
    • Zdola nahoru (bottom-up) - nalezne pravý rozklad (posloupnost čísel pravidel použitých v pravé derivaci)

Shora dolů

  • Má jen 1 stav
  • Přijímá prázdným zásobníkem
  • Na začátku je na zásobníku počáteční neterminál, tedy
  • Vrchol zásobníku uvažujeme vlevo
  • Provádí 2 operace:
    • Expanzi - Pokud je na vrcholu zásobníku neterminál, vyndám ho a nahradím pravidlem gramatiky
    • Srovnání - Pokud je na vrcholu terminál, vyndám ho a zároveň přečtu ze vstupu

../../Attachments/Pasted image 20260602133120.png

Zdola nahoru

  • Má 2 stavy
  • Přijímá přechodem do koncového stavu
  • Na začátku je na zásobníku jen počáteční symbol
  • Vrchol zásobníku uvažujeme vpravo
  • Provádí 3 operace:
    • Redukci - Pokud je na vrcholu zásobníku pravá strana pravidla, vyndám a nahradím příslušným neterminálem
    • Přesun - Přečtu terminál ze vstupu a vložím na zásobník
    • Přijetí - Na zásobníku je počáteční neterminál - vyndám spolu s počátečním symbolem a přejdu do koncového stavu

../../Attachments/Pasted image 20260602134128.png

Vytvořeno: 27. 5. 2026, 11:17
Poslední aktualizace: 9. 6. 2026, 12:17