Formální gramatika - Formal grammar

V teorii formálních jazyků , což je gramatiku (pokud je kontext neuvádí, často volal formální gramatiky pro přehlednost) popisuje vytvoření řetězce z jazyka, v abecedě , které jsou platné v souladu s jazykem jeho syntaxe . Gramatika nepopisuje význam řetězců ani to, co lze s nimi dělat v jakémkoli kontextu - pouze v jejich formě. Formální gramatika je definována jako sada produkčních pravidel pro řetězce ve formálním jazyce.

Teorie formálního jazyka, obor, který studuje formální gramatiky a jazyky, je oborem aplikované matematiky . Jeho aplikace se nacházejí v teoretické informatice , teoretické lingvistice , formální sémantice , matematické logice a dalších oblastech.

Formální gramatika je sada pravidel pro přepisování řetězců spolu se „počátečním symbolem“, ze kterého začíná přepisování. Proto je gramatika obvykle považována za generátor jazyků. Někdy jej však lze také použít jako základ pro „ rozpoznávač “ - funkci ve výpočtu, která určuje, zda daný řetězec patří do jazyka nebo je gramaticky nesprávný. K popisu těchto rozpoznávačů používá teorie formálního jazyka samostatné formalizmy, známé jako teorie automatů . Jedním ze zajímavých výsledků teorie automatů je, že není možné navrhnout rozpoznávač pro určité formální jazyky. Analýza je proces rozpoznávání výpovědi (řetězce v přirozených jazycích) rozložením na sadu symbolů a analýzou každého z nich proti gramatice jazyka. Většina jazyků má významy svých výpovědí strukturované podle své syntaxe - praxe známá jako kompoziční sémantika . Výsledkem je, že prvním krokem k popisu významu promluvy v jazyce je rozebrat ji po jednotlivých částech a podívat se na její analyzovanou formu ( ve výpočetní technice známou jako jeho parse tree a v generativní gramatice jako jeho hluboká struktura ).

Dějiny

Panini ‚s pojednání Astadyayi dává formální pravidla produkce a definice popsat formální gramatiky sanskrtu . Existují různá použití pojmů „forma“ a „formalismus“, která se postupem času měnila v závislosti na oblastech, s nimiž byl příslušný autor v kontaktu. Historický přehled konceptu je uveden v

Úvodní příklad

Gramatika se skládá hlavně ze sady produkčních pravidel a pravidel přepisování pro transformaci řetězců. Každé pravidlo určuje nahrazení konkrétního řetězce (jeho levé strany ) jiným (jeho pravé straně ). Pravidlo lze použít na každý řetězec, který obsahuje jeho levou stranu, a vytváří řetězec, ve kterém byl výskyt této levé strany nahrazen jeho pravou stranou.

Na rozdíl od semi-Thue systému , který je zcela definován těmito pravidly, gramatika dále rozlišuje mezi dvěma druhy symbolů: neterminální a terminální symboly; každá levá strana musí obsahovat alespoň jeden neterminální symbol. Rozlišuje také speciální neterminální symbol, který se nazývá počáteční symbol .

Jazyk generovaný gramatikou je definován jako sada všech řetězců bez jakýchkoli neterminálních symbolů, které lze generovat z řetězce skládajícího se z jednoho počátečního symbolu (případně opakovaným) uplatněním jeho pravidel jakýmkoli možným způsobem. Pokud existují v zásadě různé způsoby generování stejného jediného řetězce, říká se, že gramatika je nejednoznačná .

V následujících příkladech, terminální symboly jsou a b , a symbol start je S .

Příklad 1

Předpokládejme, že máme následující produkční pravidla:

1.
2.

pak začneme od S a můžeme si vybrat pravidlo, které se na něj použije. Pokud zvolíme pravidlo 1, získáme řetězec aSb . Budeme-li pak vyberte pravidlo 1 opět nahradíme S s ASB a získat řetězec aaSbb . Pokud bychom nyní mohou vybrat pravidlo 2, nahradíme S s ba a získat řetězec aababb , a je hotovo. Můžeme psát tuto řadu možností stručněji, pomocí symbolů: .

Jazykem gramatiky je nekonečná množina , kde se opakují časy (a zejména představují počet použití produkčního pravidla 1). Tato gramatika je bezkontextová (pouze jednotlivé neterminály se zobrazují jako levé strany) a jednoznačná.

Příklady 2 a 3

Předpokládejme, že pravidla jsou tato:

1.
2.
3.

Tato gramatika není bezkontextová kvůli pravidlu 3 a je nejednoznačná kvůli mnoha způsobům, kterými lze pravidlo 2 použít ke generování posloupností s.

Jazyk, který generuje, je však jednoduše sada všech neprázdných řetězců skládajících se z s / nebo s. Je to dobře vidět: vygenerovat z , použít ke generování dvakrát pravidlo 2 , potom dvakrát pravidlo 1 a k produkci pravidlo 3 jednou . To znamená, že můžeme generovat libovolné neprázdné sekvence s a poté je každý nahradit nebo podle libosti.

Stejný jazyk lze alternativně generovat bezkontextovou nejednoznačnou gramatikou; například běžná gramatika s pravidly

1.
2.
3.
4.

Formální definice

Syntaxe gramatik

V klasické formalizaci generativních gramatik, kterou poprvé navrhl Noam Chomsky v padesátých letech, sestává gramatika G z následujících komponent:

kde je hvězdný operátor Kleene a označuje sjednocenou množinu . To znamená, že každé produkční pravidlo se mapuje z jednoho řetězce symbolů na jiné, kde první řetězec („hlava“) obsahuje libovolný počet symbolů za předpokladu, že alespoň jeden z nich je neterminální. V případě, že druhý řetězec (dále jen „orgán“) se skládá pouze z prázdných strun -ie, že neobsahuje žádné symboly vůbec, může být označené speciální notace (často , e nebo ), aby nedošlo k záměně.
  • Rozlišující symbol, který je počátečním symbolem , který se také nazývá symbol věty .

Gramatika je formálně definována jako n-tice . Takové formální gramatice se v literatuře často říká systém přepisování nebo gramatika frázové struktury .

Některé matematické konstrukce týkající se formálních gramatik

Provoz gramatiky lze definovat z hlediska vztahů na řetězcích:

  • Vzhledem k gramatice je binární vztah (vyslovovaný jako „G odvozen v jednom kroku“) na řetězcích definován:
  • vztah (vyslovuje jako G odvodí v nula nebo více stupních ), je definován jako reflexivní tranzitivní uzavření všech
  • A sentenciální forma je členem, který lze odvodit v konečném počtu kroků od počátečního symbolu ; to znamená, že sentenční formulář je členem . Senciální forma, která neobsahuje žádné neterminální symboly (tj. Je členem ), se nazývá věta .
  • language of , označovaný jako je definován jako soubor vět postavený .

Všimněte si, že gramatika je ve skutečnosti systém semi-Thue , který přepisuje řetězce přesně stejným způsobem; jediný rozdíl je v tom, že rozlišujeme konkrétní neterminální symboly, které musí být přepsány v pravidlech přepisování, a zajímají se pouze o přepisy z určeného počátečního symbolu na řetězce bez neterminálních symbolů.

Příklad

U těchto příkladů jsou formální jazyky určeny pomocí notace set-builder .

Uvažujme gramatiku , kde , , je symbol start, a sestává z následujících pravidel produkce:

1.
2.
3.
4.

Tato gramatika definuje jazyk, kde označuje řetězec n po sobě jdoucích . Jazyk je tedy sada řetězců, která se skládá z 1 nebo více písmen, následovaných stejným počtem čísel , následovaných stejným počtem čísel .

Některé příklady odvození řetězců jsou:

(Poznámka k notaci: zní „Řetězec P generuje řetězec Q pomocí produkce i “ a vygenerovaná část je pokaždé označena tučně.)

Chomského hierarchie

Když Noam Chomsky v roce 1956 poprvé formalizoval generativní gramatiky, zařadil je do typů, nyní známých jako Chomskyho hierarchie . Rozdíl mezi těmito typy spočívá v tom, že mají stále přísnější produkční pravidla, a proto mohou vyjadřovat méně formálních jazyků. Dva důležité typy jsou bezkontextové gramatiky (typ 2) a běžné gramatiky (typ 3). Jazyky, které lze popsat pomocí takové gramatiky, se nazývají bezkontextové jazyky a běžné jazyky . Ačkoli jsou mnohem méně výkonné než neomezené gramatiky (typ 0), které ve skutečnosti mohou vyjadřovat jakýkoli jazyk, který může Turingův stroj přijmout , tyto dva omezené typy gramatik se nejčastěji používají, protože je lze efektivně implementovat analyzátory. Například všechny běžné jazyky lze rozpoznat pomocí stroje s konečným stavem a pro užitečné podmnožiny bezkontextových gramatik existují dobře známé algoritmy pro generování efektivních analyzátorů LL a analyzátory LR pro rozpoznávání odpovídajících jazyků, které tyto gramatiky generují.

Bezkontextové gramatiky

Bezkontextová gramatiky je gramatiky, v níž levá strana každé pravidlo výroby tvoří pouze jediný terminálního symbolu funkce. Toto omezení je nepodstatné; ne všechny jazyky lze generovat bezkontextovými gramatikami. Ty, které mohou být nazývány bezkontextové jazyky .

Výše definovaný jazyk není bezkontextový jazyk, což lze striktně dokázat pomocí čerpacího lemmatu pro bezkontextové jazyky , ale například jazyk (alespoň 1 následovaný stejným počtem znaků) je bezkontextový , jak to může být definována gramatiky s , , symbol startu a následujícími pravidly produkce:

1.
2.

Bezkontextový jazyk lze včas rozpoznat ( viz Big O notace ) pomocí algoritmu, jako je Earleyův rozpoznávač . To znamená, že pro každý bezkontextový jazyk lze vytvořit stroj, který vezme řetězec jako vstup a určí v čase, zda je řetězec členem jazyka, kde je délka řetězce. Deterministické bezkontextové jazyky jsou podmnožinou bezkontextových jazyků, které lze rozpoznat v lineárním čase. Existují různé algoritmy, které se zaměřují buď na tuto sadu jazyků, nebo na její podmnožinu.

Pravidelné gramatiky

V běžných gramatikách je levá strana opět pouze jedním neterminálním symbolem, ale nyní je omezena také pravá strana. Pravá strana může být prázdný řetězec nebo jediný koncový symbol nebo jediný koncový 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ých neterminálů bez čehokoli jiného, ​​což usnadňuje označování jazyků a přitom definuje stejnou třídu jazyků.)

Jazyk je definována výše, není pravidelné, ale jazyk (alespoň 1 a následně alespoň 1 , kde čísla se mohou lišit), je, jak to může být definována gramatiky s , , symbol startu a následujících pravidel produkce :

Všechny jazyky generované běžnou gramatikou mohou být včas rozpoznány strojem konečného stavu. Ačkoli se v praxi regulární gramatiky běžně vyjadřují pomocí regulárních výrazů , některé formy regulárního výrazu používané v praxi negenerují striktně regulární jazyky a nevykazují lineární výkon rozpoznávání kvůli těmto odchylkám.

Jiné formy generativních gramatik

Bylo vyvinuto mnoho rozšíření a variací na Chomského původní hierarchii formálních gramatik, a to jak lingvisty, tak počítačovými vědci, obvykle buď za účelem zvýšení jejich expresivní síly, nebo za účelem jejich snazší analýzy nebo analýzy. Některé formy vyvinutých gramatik zahrnují:

Rekurzivní gramatiky

Rekurzivní gramatika je gramatika, která obsahuje produkční pravidla, která jsou rekurzivní . Například gramatika pro bezkontextový jazyk je rekurzivní vlevo, pokud existuje neterminální symbol A, který lze vložit přes pravidla produkce, aby vytvořil řetězec s písmenem A jako symbolem úplně vlevo. Příkladem rekurzivní gramatiky je věta ve větě oddělená dvěma čárkami. Všechny typy gramatik v hierarchii Okoye mohou být rekurzivní.

Analytické gramatiky

Ačkoli existuje obrovské množství literatury o parsovacích algoritmech , většina z těchto algoritmů předpokládá, že jazyk, který má být analyzován, je zpočátku popsán pomocí generativní formální gramatiky a cílem je transformovat tuto generativní gramatiku na fungující parser. Přísně vzato generativní gramatika žádným způsobem neodpovídá algoritmu použitému k analýze jazyka a různé algoritmy mají různá omezení týkající se formy produkčních pravidel, která jsou považována za dobře formovaná.

Alternativním přístupem je v první řadě formalizace jazyka z hlediska analytické gramatiky, která přímo odpovídá struktuře a sémantice syntaktického analyzátoru jazyka. Mezi příklady formalizmů analytické gramatiky patří:

Viz také

Reference

externí odkazy