V lingvistice a informatice je bezkontextová gramatika (CFG) formální gramatika, ve které má každé produkční pravidlo tvar
kde V je neterminální symbol a w je řetězec složený z terminálů a/nebo neterminálů. Termín „bezkontextový“ vychází ze skutečnosti, že neterminál V lze vždy nahradit symbolem w bez ohledu na kontext, v němž se vyskytuje. Formální jazyk je bezkontextový, pokud existuje bezkontextová gramatika, která jej generuje.
Bezkontextové gramatiky jsou dostatečně výkonné pro popis syntaxe většiny programovacích jazyků; ve skutečnosti je syntaxe většiny programovacích jazyků specifikována pomocí bezkontextových gramatik. Na druhou stranu jsou bezkontextové gramatiky dostatečně jednoduché na to, aby umožnily konstrukci efektivních parsovacích algoritmů, které pro daný řetězec určí, zda a jak jej lze z gramatiky vygenerovat. Příkladem takového algoritmu je Earleyho parser, zatímco LR a LL parsery se zabývají pouze restriktivnějšími podmnožinami bezkontextových gramatik.
BNF (Backus-Naurův tvar) je nejběžnější notace používaná pro vyjádření bezkontextových gramatik.
Ne všechny formální jazyky jsou bezkontextové – známým protipříkladem je , množina řetězců obsahující určitý počet písmen a, za nimiž následuje stejný počet písmen b a stejný počet písmen c.
Tento konkrétní jazyk lze generovat pomocí gramatiky parsovacích výrazů, což je relativně nový formalismus, který se hodí zejména pro programovací jazyky.
Stejně jako jakoukoli jinou formální gramatiku lze i bezkontextovou gramatiku G definovat jako čtyřnásobek:
Jednoduchá bezkontextová gramatika je
Zde je bezkontextová gramatika pro syntakticky správné infixové algebraické výrazy v proměnných x, y a z:
Tato gramatika může například generovat řetězec „( x + y ) * x – z * y / ( x + x )“.
Bezkontextová gramatika pro jazyk složený ze všech řetězců nad {a,b}, které obsahují různý počet a a b, je následující
Zde T může generovat všechny řetězce se stejným počtem a jako b, U generuje všechny řetězce s více a než b a V generuje všechny řetězce s méně a než b.
Dalším příkladem bezkontextového jazyka je . Nejedná se o regulární jazyk, ale je bezkontextový, protože jej lze generovat pomocí následující CFG (Context Free Grammar):
Bezkontextové gramatiky se neomezují pouze na matematické („formální“) jazyky.
Gramatika lojbštiny, umělého mluveného jazyka s obrovskou vyjadřovací schopností, je také bezkontextová a jednoznačná.
Nedávno bylo navrženo, že třída tamilské poezie zvaná Venpa se řídí bezkontextovou gramatikou.
Odvození a syntaktické stromy
Existují dva běžné způsoby, jak popsat, jak lze daný řetězec odvodit od počátečního symbolu dané gramatiky. Nejjednodušší způsob je vypsat po sobě jdoucí řetězce symbolů, které začínají počátečním symbolem a končí daným řetězcem, a pravidla, která byla použita. Pokud zavedeme strategii typu „vždy nejdříve nahradit nejlevější neterminál“, pak pro bezkontextové gramatiky je seznam aplikovaných pravidel gramatiky sám o sobě dostačující. Tomu se říká nejlevější derivace řetězce. Vezmeme-li například následující gramatiku:
a řetězce „1 + 1 + a“, pak levou derivací tohoto řetězce je seznam [ (1), (1), (2), (2), (3) ]. Analogicky je pravá derivace definována jako seznam, který dostaneme, pokud vždy nejprve nahradíme nejpravější neterminál. V tomto případě by to mohl být seznam [ (1), (3), (1), (2), (2)].
Rozdíl mezi odvozováním zleva a zprava je důležitý, protože ve většině parserů je transformace vstupu definována tak, že pro každé gramatické pravidlo je uveden kus kódu, který se provede vždy, když je pravidlo použito. Proto je důležité vědět, zda parser určuje nejlevější nebo nejpravější derivaci, protože to určuje pořadí, v jakém budou kousky kódu provedeny. Příklad viz parsery LL a parsery LR.
Odvození také v jistém smyslu ukládá hierarchickou strukturu řetězci, který je odvozen. Například struktura řetězce „1 + 1 + a“ by podle nejlevější derivace byla následující:
kde { … }S označuje podřetězec rozpoznaný jako patřící do S. Tuto hierarchii lze také chápat jako strom:
Tento strom se nazývá konkrétní syntaktický strom (viz také abstraktní syntaktický strom) řetězce. V tomto případě prezentovaná nejlevější a nejpravější derivace definují tentýž syntaktický strom, avšak je možná ještě jedna (nejlevější) derivace téhož řetězce
a ten definuje následující syntaktický strom:
Pokud pro určité řetězce v jazyce gramatiky existuje více než jeden strom rozboru, pak se o gramatice říká, že je nejednoznačná. Takové gramatiky se obvykle obtížně rozebírají, protože parser se nemůže vždy rozhodnout, které pravidlo gramatiky má použít.
Každou bezkontextovou gramatiku, která negeneruje prázdný řetězec, lze transformovat na ekvivalentní gramatiku v Chomského normální formě nebo Greibachově normální formě. „Ekvivalentní“ zde znamená, že obě gramatiky generují stejný jazyk.
Vzhledem k obzvláště jednoduché podobě produkčních pravidel v gramatikách Chomského normální formy má tato normální forma teoretické i praktické důsledky. Například při zadání bezkontextové gramatiky lze pomocí Chomského normální formy zkonstruovat algoritmus s polynomiálním časem, který rozhodne, zda daný řetězec patří do jazyka reprezentovaného touto gramatikou, či nikoli (algoritmus CYK).
Ačkoli některé operace s bezkontextovými gramatikami jsou vzhledem k jejich omezené síle rozhodnutelné, CFG mají zajímavé nerozhodnutelné problémy. Jedním z nejjednodušších a nejcitovanějších je problém rozhodování, zda CFG akceptuje jazyk všech řetězců. Na tento problém lze ukázat redukci ze známého nerozhodnutelného problému určení, zda Turingův stroj akceptuje určitý vstup. Redukce používá pojem historie výpočtů, řetězce popisujícího celý výpočet Turingova stroje. Můžeme zkonstruovat CFG, která vygeneruje všechny řetězce, které nejsou akceptujícími historiemi výpočtů pro určitý Turingův stroj na určitém vstupu, a tedy bude akceptovat všechny řetězce pouze v případě, že stroj tento vstup neakceptuje.
V důsledku toho je také nerozhodnutelné, zda dvě CFG popisují stejný jazyk, protože nemůžeme ani rozhodnout, zda je CFG ekvivalentní triviální CFG rozhodující o jazyku všech řetězců.
Na druhou stranu problém určení, zda CFG akceptuje alespoň jeden řetězec, je rozhodnutelný.