Bezkontextová gramatika

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 3. ledna 2022; ověření vyžaduje 1 úpravu .

Bezkontextová gramatika ( CS-grammar , bezkontextová gramatika ) je speciální případ formální gramatiky (typ 2 podle Chomského hierarchie ), ve které jsou levé části všech produkcí jediné neterminály (objekty označující jakoukoli podstatu jazyk (například: vzorec, aritmetický výraz, příkaz) a nemá specifický symbolický význam). Význam pojmu "bezkontextový" je ten, že je možné aplikovat produkci na neterminál, a navíc bez ohledu na kontext tohoto neterminálu (na rozdíl od obecného případu neomezené Chomského gramatiky).

Jazyk , který lze specifikovat pomocí CFG, se nazývá bezkontextový jazyk nebo CFL.

Ve skutečnosti je KS-gramatika další formou BNF .

Aplikace

COP-gramatiky mají velké využití v informatice . Nastavují gramatickou strukturu většiny programovacích jazyků , strukturovaná data atd. (viz gramatický rozbor )

K analýze COP-gramatiky stačí zásobníkový automat , k analýze non-COP-gramatiky může být vyžadován Turingův kompletní stroj .

Typy CS gramatik

LL gramatika
Gramatika LALR (viz: LALR(1) )
LR gramatika
SLR gramatika (viz: SLR(1) )

Rozpoznávače

Existují dvě různé třídy rozpoznávačů (automaty pro rozpoznávání) jazyků CF. Jejich názvy souvisejí s pořadím, ve kterém je sestaven výstupní strom. Všechny rozpoznávače zpravidla čtou vstupní znakový řetězec zleva doprava, protože takový zápis se očekává při psaní zdrojového kódu programů.

Downstream resolvery

Překladače shora dolů, které generují levé výstupní řetězce a sestavují výstupní strom shora dolů.

Používají modifikace algoritmu s výběrem alternativ. Při jejich vytváření se používá metoda, která umožňuje v každém kroku MP-automatu jednoznačně vybrat jednu a pouze jednu alternativu (krok „vysunutí“ se u tohoto automatu provádí vždy jednoznačně).

Vzestupní rozpoznávači

Překladače zdola nahoru, které generují řetězce výstupu pro pravou ruku a vytvářejí výstupní strom zdola nahoru.

Upstream rozpoznávače používají modifikace algoritmu shift-fold (nebo shift-fold, což je stejný). Při jejich vytváření se používají metody, které umožňují v každém kroku rozšířeného MP-automatu jednoznačně zvolit mezi provedením „posunu“ („přenosu“) nebo „konvoluce“ a při provedení konvoluce lze jednoznačně zvolit pravidlo kterým bude konvoluce provedena. Algoritmus "posun-konvoluce".

Příklady

Příklady SF-gramatiky a jejich odpovídajících SF-jazyků:

Překlopit slovo

Dáno vzorcem $L=\{w\in \Sigma ^{*}|w=w^{R}\}$

Terminály: písmena abecedy ; $\Sigma$
Neterminál: ; $S$
Produkty: $S\rightarrow \alpha S\alpha \,|\,\alpha \,|\,\varepsilon ,\alpha \in \Sigma$
Počáteční neterminál je . $S$

Vnořené závorky

Terminály: a ; $($ $)$
nekoncový: ; $S$
produkty: ; $S\šipka doprava (S)\střed \varepsilon$
počáteční nekoncový - . $S$

Tato gramatika určuje jazyk vnořených závorek . $\{\left(^{n}\right)^{n}\mid n\geq 0\}$

Dickův jazyk

Aritmetický výraz

Terminály: '+', '-', '*', '/', '(', ')', 'x'
neterminály: <výraz>, <termín>, <násobič>
produkty:

<výraz> → <výraz> + <výraz>, <výraz> → <výraz> - <výraz>, <výraz> → <výraz>, <term> → <term> * <multiplikátor>, <term> → <term> / <multiplikátor>, <term> → <multiplikátor>, <multiplikátor> → ( <výraz> ), <multiplikátor> → x,

počáteční neterminál: <výraz>.

Tato gramatika definuje aritmetický výraz obsahující nejjednodušší aritmetické operace s proměnnou x. Pokud nahradíme terminál 'x' neterminálním <číslo>, dostaneme gramatiku, která specifikuje aritmetický výraz sestávající z operací sčítání, odčítání, násobení a dělení na celých číslech.

Omezení COP gramatiky

Ne všechny jazyky lze definovat pomocí CF-gramatiky. Nejjednodušší způsob, jak to dokázat, je následující: COP-gramatiky tvoří spočetnou množinu, zatímco mohutnost množiny všech jazyků je kontinuum . Konstruktivní důkaz téže skutečnosti lze získat např. na základě toho, že jazyk { a n b n c n | n ≥1} není bez kontextu; nezdá se však, že by existoval krátký důkaz tohoto druhého tvrzení: publikované důkazy se opírají o větu růstu pro bezkontextové jazyky.

Zobecnění

Gramatika sčítání stromů zobecňuje bezkontextovou gramatiku v tom, že základní jednotkou v pravidlech odvozování jsou stromy, nikoli jednotlivé znaky.

Viz také

Literatura

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Belousov A. I., Tkachev S. B. Diskrétní matematika. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus