Bezkontextová gramatika

z Wikipédie, slobodnej encyklopédie

Bezkontextová gramatika je frázová gramatika, ktorej prepisovacie pravidlá majú tvar Xw, kde X je neterminál a w je ľubovoľná vetná forma. Názov bezkontextová vychádza z toho, že neterminály sa prepisujú bez ohľadu na kontext, v ktorom sa nachádzajú.

Bezkontextovými gramatikami sa veľmi často popisujú bežné programovacie jazyky, hoci tieto sú málokedy bezkontextové (napr. Pascal alebo C). Bezkontextové jazyky však vieme pomerne efektívne parsovať a konštrukcie, ktoré nie sú bezkontextové (napr. deklarácie a používanie premenných) sa ošetrujú zvlášť.

Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatika Jazyk Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.