Formální gramatika

Formální gramatika , v teorii formálních jazyků , je abstraktní struktura , která popisuje formální jazyk přesným způsobem, to znamená, že je to systém pravidel, která matematicky vymezují množinu (obvykle nekonečnou) konečných sekvencí symbolů ( řetězců ) patřící také do hotové abecedy .

Formální gramatiky spadají do dvou hlavních kategorií: generativní a analytické .

Generativní gramatika , nejznámější žánr, je systém pravidel, podle kterých jsou všechny možné řetězce v jazyce, který má být popsán, generovány následným přepisováním řetězců začínajících předdefinovaným počátečním symbolem. Generativní gramatika ve skutečnosti formalizuje algoritmus, který generuje lingvistické řetězce.

Analytická gramatika je na druhé straně systém pravidel, který předpokládá libovolný řetězec jako vstup a který následně redukuje nebo analyzuje tento konečný vstupní řetězec tím, že logickou spojnici udělí jako výsledek typu „ano / ne“, který označuje, zda vstup řetězec je nebo není součástí jazyka popsaného gramatikou. Analytická gramatika ve skutečnosti popisuje lingvistický analyzátor .

Stručně řečeno, analytická gramatika popisuje, jak číst jazyk, zatímco generativní gramatika popisuje, jak jej psát .

Generativní gramatiky

Generativní gramatika se skládá ze systému pravidel pro transformaci řetězců. Abychom vygenerovali lingvistický řetězec, začneme řetězcem skládajícím se z jednoho úvodního symbolu a poté použijeme pravidla (libovolněkrá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 právních voleb provedená během tohoto přepisovacího procesu zaručuje konkrétní lingvistický řetězec, a pokud existuje více různých způsobů generování jednoho řetězce, pak se gramatika nazývá nejednoznačná gramatika .

Například pokud máme počáteční abecedu symbolů a následující výrobní pravidla: $\ Sigma = \ {a, b \}, N = \ {S \}, S$

$S \ až aSb$
$S \ do ba$

pak můžeme začít s " " a vybrat pravidlo, které se má použít. Zvolíme-li pravidlo 1, nahradíme výrazem a získáme „ “. Pokud znovu zvolíme pravidlo 1, nahradíme ' ' znakem ' ', abychom dostali " ". Tento proces se opakuje, dokud nemáme pouze terminální symboly. Na závěr našeho příkladu, pokud nyní zvolíme pravidlo 2, nahradíme ' ' za ' ', abychom dostali " ", a vše je hotovo. Tuto řadu voleb můžeme napsat stručněji pomocí symbolů :. Gramatický jazyk je systém všech řetězců, které lze generovat pomocí tohoto procesu :. $S.$ $S.$ $aSb$ $aSb$ $S.$ $aSb$ $aaSbb$ $S.$ $ba$ $aababb$ $S \ do aSb \ do aaSbb \ do aababb$ $\ vlevo \ {ba, abab, aababb, aaababbb, ... \ vpravo \}$

Formální definice

V klasické formalizaci generativních gramatik, kterou poprvé navrhl Noam Chomsky v 50. letech 20. století, se gramatika skládá ze čtyřnásobku , ve kterém ${\ mathcal {G}}$ ${\ mathcal {G}} = \ vlevo \ langle N, \ Sigma, P, S \ vpravo \ langle$

$Ne.$ jsou neterminální symboly, které lze přepsat
$\Sigma$ jsou koncové symboly disjunktní od $Ne.$
$S \ v N$ uvedený axiom je počáteční nekoncový symbol.
$P.$ jsou pravidla produkce, binární vztah konečné mohutnosti na , který normálně píšeme jako $(N \ cup \ Sigma) ^ {*} \ circ N \ circ (N \ cup \ Sigma) ^ {*} \ krát (N \ cup \ Sigma) ^ {*}$ $\ alfa \ až \ beta$
kde je Kleenova hvězda a je spojením symbolů s omezením, že levá část pravidla (např. levá část ) musí obsahovat alespoň jeden neterminální symbol. ${} ^ {{*}}$ $\ šálek$ $\ do$

Jazyk generovaný formální gramatikou , označovaný jako , je definován jako všechny ty řetězce su , které lze vygenerovat tak, že se začne axiomem a pak se iterativně aplikuje produktivní pravidla, dokud nebudou existovat žádné další neterminální symboly. ${\ mathcal {G}} = \ vlevo \ langle N, \ Sigma, P, S \ vpravo \ langle$ $L ({\ mathcal {G}})$ $\Sigma$ $S.$ $P.$

Říká se, že dvě gramatiky jsou si navzájem ekvivalentní tehdy a pouze tehdy, když generují stejný jazyk.

Příklad

Uvažujme například gramatiku s ,, skládající se z následujících produkčních pravidel $G.$ $N = \ vlevo \ {S, B \ vpravo \}$ $\ Sigma = \ vlevo \ {a, b, c \ vpravo \}$ $P.$

1.

S \ do aBSc

2.

S \ k abc

3.

Ba \ do aB

4.

Bb \ do bb

a nekoncový symbol jako počáteční symbol. Některé příklady odvození řetězců jsou: $S.$ $L ({\ mathcal {G}})$

${\ tučný symbol {S}} \ až (2) abc$
${\ boldsymbol {S}} \ to (1) aB {\ boldsymbol {S}} c \ to (2) a {\ boldsymbol {Ba}} bcc \ to (3) aa {\ boldsymbol {Bb}} cc \ až (4) aabbcc$
${\ boldsymbol {S}} \ do (1) aB {\ boldsymbol {S}} c \ do (1) aBaB {\ boldsymbol {S}} cc \ do (2) a {\ boldsymbol {Ba}} Babccc \ to (3) aaB {\ boldsymbol {Ba}} bccc \ to (3) aa {\ boldsymbol {Ba}} Bbccc$ $\ to (3) aaaB {\ boldsymbol {Bb}} ccc \ to (4) aaa {\ boldsymbol {Bb}} bccc \ to (4) aaabbbccc$

(kde jsou použitá výrobní pravidla uvedena v závorkách a nahrazený díl je vždy vyznačen tučně).

Gramatika definuje jazyk . $\ {a ^ {{n}} b ^ {{n}} c ^ {{n}} | n> 0 \, \}$

Formální generativní gramatiky jsou totožné s Lindenmayerovým systémem (L systémy), kromě toho, že L systémy nejsou charakterizovány rozlišením mezi terminálem a neterminálem , L systémy mají omezení v pořadí, ve kterém jsou pravidla aplikována, a L systémy mohou fungovat. navždy, generování nekonečné sekvence řetězců. Typicky je každý řetězec spojen se systémem bodů v prostoru a výstup systému L je definován jako hranice těchto systémů.

Chomského hierarchie

Když Noam Chomsky v 50. letech poprvé formalizoval generativní gramatiky, zařadil je do čtyř typů nyní známých jako Chomského hierarchie . Rozdíl mezi těmito typy je v tom, že mají přísná produkční pravidla a mohou vyjadřovat méně formálních jazyků. Dva důležité typy jsou: bezkontextové gramatiky (v italských bezkontextových gramatikách) a regulární gramatiky . Jazyky, které lze popsat takovou gramatikou, se nazývají bezkontextové jazyky a regulární jazyky . Ačkoli jsou mnohem méně výkonné než neomezující gramatiky, které mohou ve skutečnosti vyjádřit jakýkoli jazyk, který může Turingův stroj přijmout , jsou tyto dva omezené typy gramatik nejpoužívanější, protože použité analyzátory lze efektivně používat. Například pro nekontextové gramatiky existují dobře známé algoritmy pro generování LL analyzátorů a LR analyzátorů .

Kontextová gramatika (typ 2)

V bezkontextových nebo nekontextových gramatikách se levá strana produktivního pravidla může skládat pouze z jednoho nekoncového symbolu. Jazyk definovaný výše v příkladu není bezkontextový jazyk, ale jazyk je , protože jej lze definovat gramatikou s následujícími produkčními pravidly: ${a ^ {n} b ^ {n} | n> 0}$ ${\ mathcal {G}} _ {2} = \ vlevo \ langle N = \ {S \}, \ Sigma = \ {a, b \}, P, S \ vpravo \ rangle$

1.

S \ až aSb

2.

S \ k ab

Konkrétně gramatika tohoto příkladu je lineární , správná podmnožina bezkontextových gramatik, protože na pravé straně je pouze jeden neterminální symbol, když mohou mít více než jeden.

Regulární gramatiky (Typ 3)

V regulární gramatice je levá strana, stejně jako u nekontextových gramatik, pouze neterminálním symbolem; navíc je nyní koncová část omezena následujícím způsobem: může být null ( ), nebo může být ve tvaru nebo ve tvaru , s a patřící k a a (tj. může být null nebo a koncový symbol následovaný případně jedním symbolem neterminálovým). Někdy se používá širší definice: lze ustoupit delším řetězcům terminálů nebo nekoncovým symbolům, ale ničemu jinému, a přitom definovat stejnou lingvistickou klasifikaci. $\epsilon$ $na$ $aB$ $na$ $B.$ $Ne.$ $\Sigma$

Výše popsaný jazyk není regulární, místo toho jazyk (alespoň jedno „a“ následované alespoň jedním „b“, s „a“ a „b“ v obecně odlišných číslech) je a lze jej definovat pomocí gramatiky pomocí následující výrobní pravidla: $\ vlevo \ {a ^ {{n}} b ^ {{m}} | m, n> 0 \ vpravo \}$ ${\ mathcal {G}} _ {3} = \ vlevo \ langle N = \ {S, A, B \}, \ Sigma = \ {a, b \}, P, S \ vpravo \ úhel$

1.

S \ až aA

2.

A \ až aA

3.

A \ do bB

4.

B \ do bB

5.

B \ až \ epsilon

Jiné formy generativních gramatik

Jak lingvisté, tak počítačoví vědci se nedávno vyvinulo několik rozšíření a variací původní Chomskiovy hierarchie formálních gramatik, obvykle buď za účelem zvýšení vyjadřovací síly, nebo za účelem jejich zjednodušení, aby je bylo možné analyzovat nebo analyzovat. Tyto dva cíle samozřejmě směřují k rovnosti: čím expresivnější je gramatický formalismus, tím obtížnější je analyzovat nebo parsovat pomocí automatických nástrojů. Některé nedávno vyvinuté formy gramatiky zahrnují:

Stromová gramatika zvyšuje expresivitu konvenčních generativních gramatik tím, že ponechává prostor pro pravidla pro přepisování, aby fungovala na stromech analyzátoru namísto pouze řetězců.
Afissuální gramatika a atributivní gramatika vám umožňují přepisovat pravidla tak, aby byla obohacena o sémantické atributy a operace, užitečné jak pro zvýšení gramatické expresivity, tak pro vytváření praktických nástrojů lingvistického překladu.

Formálním gramatikám je věnována výroční konference.

Analytické gramatiky

Přestože existuje velké množství literatury o parsifikace algoritmů, většina z nich předpokládá, že jazyk je zpočátku popsán pomocí generativní formální gramatiky a že cílem je transformovat tuto generativní gramatiku na funkční parser . Alternativním přístupem je především formalizace jazyka z hlediska analytické gramatiky , která víceméně přímo odpovídá struktuře lingvistického parseru . Příklady formalismů analytické gramatiky jsou následující:

Top-Down Parsification Language (TDPL): Vysoce minimalistická analytická gramatika vyvinutá na počátku 70. let ke studiu chování top-down analyzátorů .
Parsification Expressive Grammar (PEGs): Novější zobecnění TDPL navržené na základě praktických potřeb expresivity programovacího jazyka a kompilátoru .
Linking Grammar : Forma analytické gramatiky určená pro lingvistiku , která odvozuje svou syntaktickou strukturu ze zkoumání pozičních vztahů mezi dvojicemi slov.

Bibliografie

Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Jazyky pro modelování složitosti , Milan, Franco Angeli Editore, 2003, ISBN 88-464-4470-1 .
Andrea de Prisco, Grammars and Automata ( JPG ), v MCmicrocomputer , n. 62, Řím, Technimedia, duben 1987, str. 154-156 , ISSN 1123-2714 ( WC ACNP ) . Přepis textu na digiTANTO.it .

Související položky

Externí odkazy

Konference o gramatikách