Formální gramatika je v informatice abstraktní struktura, která přesně popisuje formální jazyk, tj. soubor pravidel, který matematicky vymezuje (obvykle nekonečnou) soustavu řetězců konečné délky nad (obvykle konečnou) abecedou. Formální gramatiky jsou takto pojmenovány analogicky k gramatice v lidských jazycích.
Stručně řečeno, analytická gramatika popisuje, jak číst jazyk, zatímco generativní gramatika popisuje, jak psát.
Generativní gramatika se skládá ze sady pravidel pro transformaci řetězců. Chcete-li vygenerovat řetězec v jazyce, začnete řetězcem, který se skládá pouze z jednoho symbolu „start“, a poté postupně aplikujete pravidla (libovolně mnohokrát, v libovolném pořadí) pro přepsání tohoto řetězce. Jazyk se skládá ze všech řetězců, které lze tímto způsobem vygenerovat. Jakákoli konkrétní sekvence zákonných voleb provedených během tohoto procesu přepisování přináší jeden konkrétní řetězec v jazyce, a pokud existuje více různých způsobů vygenerování jednoho řetězce, pak se o gramatice říká, že je nejednoznačná.
pak začneme s „“, a můžeme si vybrat pravidlo, které se na něj bude vztahovat. Zvolíme-li pravidlo 1, nahradíme “ s “ a získáme „“. Zvolíme-li znovu pravidlo 1, nahradíme “ s “ a získáme „“. Tento proces se opakuje, dokud nebudeme mít pouze symboly z abecedy (tj. “ a “). Dokončíme náš příklad, zvolíme-li nyní pravidlo 2, nahradíme “ s “ a získáme „“, a je hotovo. Tuto sérii voleb můžeme napsat stručněji, pomocí symbolů: . Jazyk gramatiky je sada všech řetězců, které lze generovat pomocí tohoto procesu: .
V klasické formalizaci generativních gramatik, kterou poprvé navrhl Noam Chomsky v 50. letech, se gramatika G skládá z následujících složek:
Obvykle se taková formální gramatika jednoduše shrnuje jako čtyřčlenná.
Jazyk formální gramatiky , označovaný jako , je definován jako všechny ty řetězce nad, které lze vygenerovat tak, že začneme počátečním symbolem a poté aplikujeme výrobní pravidla tak dlouho, dokud nejsou přítomny žádné další neterminální symboly.
Pro tyto příklady jsou formální jazyky specifikovány pomocí notace set-builder.
Vezměme si například gramatiku s , , skládající se z následujících výrobních pravidel
a neterminální symbol jako počáteční symbol. Některé příklady derivace řetězců v jsou:
(pokud jsou použitá pravidla produkce uvedena v závorkách a nahrazená část je pokaždé vyznačena tučně).
Je jasné, že tato gramatika definuje jazyk, kde označuje řetězec n ‚s. Celý jazyk se tedy skládá z libovolného kladného čísla ‚a‘, za nímž následuje stejný počet ‚b‘ následovaný stejným počtem ‚c’s.
Generační formální gramatiky jsou totožné s Lindenmayerovými systémy (L-systémy), kromě toho, že L-systémy nejsou ovlivněny rozlišením mezi terminály a neterminály, L-systémy mají omezení pořadí, ve kterém jsou pravidla aplikována, a L-systémy mohou běžet věčně a generovat nekonečnou posloupnost řetězců. Typicky je každý řetězec spojen se sadou bodů v prostoru a „výstup“ L-systému je definován jako limit těchto množin.
Když Noam Chomsky v roce 1956 poprvé formalizoval generativní gramatiky, rozdělil je do čtyř typů, dnes známých jako Chomského hierarchie. Rozdíl mezi těmito typy je v tom, že mají stále přísnější výrobní pravidla a mohou vyjadřovat méně formálních jazyků. Dva důležité typy jsou bezkontextové gramatiky a běžné gramatiky. Jazyky, které lze popsat takovou gramatikou, se nazývají bezkontextové jazyky, respektive běžné jazyky. Ačkoli jsou mnohem méně výkonné než neomezené gramatiky, které mohou ve skutečnosti vyjadřovat jakýkoli jazyk, který může být přijat Turingovým strojem, jsou tyto dva omezené typy gramatik nejčastěji používány, protože parsery pro ně mohou být efektivně implementovány. Například pro bezkontextové gramatiky existují dobře známé algoritmy pro generování efektivních LL parserů a LR parserů.
V běžných gramatikách je levá strana opět pouze jedním neterminálním symbolem, ale nyní je omezena i pravá strana: Může to být nic, nebo jeden terminálový symbol, nebo jeden terminálový symbol následovaný neterminálním symbolem, ale nic jiného. (Někdy se používá širší definice: lze povolit delší řetězce terminálů nebo jednotlivé neterminály bez čehokoliv jiného, což usnadňuje označení jazyků a zároveň definuje stejnou třídu jazyků.)
(kde označuje prázdný řetězec, tj. řetězec délky 0).
V praxi se běžné gramatiky vyjadřují pomocí regulárních výrazů.
Běžné vs. bezkontextové jazyky
Kromě rozdílů ve výrobních pravidlech požadovaných pro generování obou jazyků je klíčovým rozdílem na vysoké úrovni mezi
(bezkontextový)
a
(pravidelný)
specifikace, že počet ‚a‘ a počet ‚b‘ musí být v bezkontextovém jazyce stejný. Tudíž každý automat, který se pokouší rozpoznat bezkontextový jazyk, musí nutně sledovat více informací než ten, který se pokouší rozpoznat běžný jazyk. Ten nemusí počítat počet ‚a‘ nebo ‚b‘, jen se musí ujistit, že je od každého více než nula.
Podrobnější informace naleznete v článku Bezkontextový jazyk a běžný jazyk.
Jiné formy generativních gramatik
Každoroční konference je věnována formálním gramatikám:
Ačkoli existuje ohromné množství literatury o algoritmech parsování, většina těchto algoritmů předpokládá, že jazyk, který má být parsován, je zpočátku popsán pomocí generativní formální gramatiky a že cílem je transformovat tuto generativní gramatiku do funkčního parseru. Alternativním přístupem je formalizace jazyka v první řadě ve smyslu analytické gramatiky, která příměji odpovídá struktuře parseru pro daný jazyk. Příklady analytických gramatických formalismů zahrnují následující: