Formální gramatika

Formální gramatika nebo jen gramatika v teorii formálních jazyků je způsob, jak popsat formální jazyk, to znamená vybrat určitou podmnožinu z množiny všech slov nějaké konečné abecedy . Existují generativní a rozpoznávací (nebo analytické ) gramatiky - první nastavuje pravidla, pomocí kterých můžete sestavit libovolné slovo jazyka, a druhá vám umožňuje z daného slova určit, zda je v jazyce obsaženo nebo ne.

Podmínky

Terminál (symbol terminálu) je objekt, který je přímo přítomen ve slovech jazyka odpovídajícího gramatice a má specifický, neměnný význam (zobecnění pojmu „písmena“). Ve formálních jazycích používaných na počítači jsou všechny nebo část standardních znaků ASCII - latinská písmena, čísla a speciální znaky - obvykle brány jako terminály .
Neterminální (neterminální symbol) je objekt označující nějakou jazykovou entitu (například: vzorec, aritmetický výraz, příkaz) a nemá specifickou symbolickou hodnotu.

Generativní gramatiky

Slova jazyka daného gramatikou jsou všechny sekvence terminálů, které jsou na výstupu (generovány) z počátečního neterminálu podle pravidel výstupu.

Pro nastavení gramatiky je potřeba nastavit abecedy terminálů a neterminálů, sadu odvozovacích pravidel a také vybrat počáteční v sadě neterminálů.

Gramatika je tedy definována následujícími vlastnostmi:

$\Sigma$ — sada ( abeceda ) koncových symbolů
N je množina ( abeceda ) nekoncových symbolů
P je sada pravidel tvaru: "levá strana" "pravá strana", kde: $\šipka doprava$
- "levá strana" je neprázdná sekvence terminálů a neterminálů obsahující alespoň jeden neterminál
- "pravá strana" - libovolná sekvence terminálů a neterminálů
S je počáteční (nebo počáteční) symbol gramatiky z množiny neterminálů.

Závěr

Výstupem je posloupnost řádků skládající se z terminálů a neterminálů, kde první řádek je řádek skládající se z jednoho počátečního neterminálu a každý následující řádek je získán z předchozího nahrazením některého podřetězce podle jednoho (libovolného) pravidel. Poslední řetězec je řetězec sestávající výhradně z terminálů, a je tedy slovem daného jazyka.

Existence odvozeniny pro určité slovo je kritériem pro jeho příslušnost k jazyku definovanému danou gramatikou.

Typy gramatik

Podle Chomského hierarchie jsou gramatiky rozděleny do 4 typů, přičemž každá následující je omezenější podmnožinou předchozí (ale také se snáze analyzuje):

typ 0. neomezené gramatiky - jsou možná jakákoli pravidla
typ 1. kontextově citlivé gramatiky - levá část může obsahovat jeden neterminál obklopený "kontextem" (sekvence znaků, které jsou přítomny ve stejné podobě v pravé části); samotný neterminál je nahrazen neprázdným sledem znaků na pravé straně.
typ 2. bezkontextové gramatiky — levou část tvoří jeden neterminál.
typ 3. regulární gramatiky jsou jednodušší, ekvivalentní konečným automatům .

Kromě toho existují:

Nezkracovací gramatiky . Každé pravidlo takové gramatiky má tvar , kde . Délka pravé strany pravidla není menší než délka levé [1] . $\alpha \šipka doprava \beta$ $|\alpha |\leqslant |\beta |$
Lineární gramatiky . Každé pravidlo takové gramatiky má tvar , nebo , to znamená, že pravá strana pravidla nemůže obsahovat více než jeden výskyt neterminálu [2] . $A\rightarrow uBv$ $A\šipka doprava u$

Aplikace

Bezkontextové gramatiky jsou široce používány k definování gramatické struktury v gramatické analýze .
Regulární gramatiky (ve formě regulárních výrazů ) jsou široce používány jako šablony pro textové vyhledávání, členění a substituci, včetně lexikální analýzy .

Příkladem jsou aritmetické výrazy

Zvažte jednoduchý jazyk, který definuje omezenou podmnožinu aritmetických vzorců sestávající z přirozených čísel , závorek a aritmetických znamének. Stojí za zmínku, že zde v každém pravidle na levé straně šipky je pouze jeden neterminálový symbol. Takové gramatiky se nazývají bezkontextové . $\šipka doprava$

Terminálová abeceda:

\Sigma

= {'0','1','2','3','4','5','6','7','8','9','+','-', '*','/','(',')'}

Neterminální abeceda:

{ FORMULA, SIGN, NUMBER, NUMBER }

pravidla:

1. VZORCE VZORCE ZNAK VZORCE

\na

(vzorec má dva vzorce spojené znaménkem) 2. ČÍSLO VZORCE

\na

(vzorec je číslo) 3. VZOREC ( VZOREC )

\na

(vzorec je vzorec v závorkách) 4. SIGN + | - | * | /

\na

(znaménko je plus nebo mínus, nebo násobení nebo dělení) 5. ČÍSLICE ( číslo

\na

je číslo) 6. ČÍSLO ČÍSLO ČÍSLO

\na

(číslo je číslo a číslo) 7. ČÍSLO 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

\na

(číslice je 0 nebo 1 nebo ... 9)

Počáteční neterminál:

VZOREC

závěr :

Odvoďme vzorec (12+5) pomocí uvedených odvozovacích pravidel. Pro názornost jsou strany každé náhrady znázorněny po dvojicích, u každého páru je vyměněná část podtržena.

FORMULA (Vzorec)

{\stackrel {3}{\to ))

( FORMULA ) ( FORMULA SIGN FORMULA )

{\stackrel {1}{\to ))

(VZOREC ZNAČKOVÝ VZORCE) (Vzorec + VZOREC)

{\stackrel {4}{\to ))

( VZOREC + VZOREC ) ( VZOREC + ČÍSLO )

{\stackrel {2}{\to ))

( VZOREC + ČÍSLO ) ( VZOREC + ČÍSLO )

{\stackrel {5}{\to ))

( VZORCE + ČÍSLO ) ( VZORCE + 5 )

{\stackrel {7}{\to ))

( VZORCE + 5) ( ČÍSLO + 5)

{\stackrel {2}{\to ))

( ČÍSLO + 5) ( ČÍSLO + 5)

{\stackrel {6}{\to ))

( ČÍSLICE + 5) ( ČÍSLICE + 5)

{\stackrel {5}{\to ))

( ČÍSLICE + 5) ( 1 ČÍSLICE + 5)

{\stackrel {7}{\to ))

(1 ČÍSLICE + 5) (1 2 + 5)

{\stackrel {7}{\to ))

Analytické gramatiky

Generativní gramatiky nejsou jediným druhem gramatik, ale jsou nejběžnější v programovacích aplikacích. Na rozdíl od generativních gramatik definuje analytická (rozpoznávací) gramatika algoritmus, který umožňuje určit, zda dané slovo patří do daného jazyka. Například jakýkoli regulární jazyk lze rozpoznat pomocí gramatiky definované stavovým automatem a jakoukoli bezkontextovou gramatiku lze rozpoznat pomocí automatu založeného na zásobníku . Pokud slovo patří do jazyka, pak takový automat konstruuje svůj výstup v explicitní formě, což umožňuje analyzovat sémantiku tohoto slova.

Viz také

JFLAP - simulátor automatů, Turingovy stroje, gramatiky
rozebrat
Nejednoznačná gramatika
Minimální problém s gramatikou
Gramatika s frázovou strukturou

Poznámky

↑ Diskrétní matematika, 2006 , str. 486.
↑ Diskrétní matematika, 2006 , str. 487.

Literatura

Belousov A. I., Tkachev S. B. Diskrétní matematika. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .
Gladkiy A. V. Formální gramatiky a jazyky. — M .: Nauka, 1973.
Kasyanov VN Přednášky o teorii formálních jazyků, automatech a výpočetní složitosti. - Novosibirsk: NGU, 1995. - 112 s.
Chomsky N., Miller J. Úvod do formální analýzy přirozených jazyků // Kybernetická sbírka / Ed. A.A. Lyapunova a O.B. Lupanova. — M .: Mir, 1965.
Gross M., Lanten A. Teorie formálních gramatik. — M .: Mir, 1971. — 296 s.

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