Formális nyelvtan

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

A formális nyelvtan informatikai értelemben egy absztrakt struktúra, amely pontosan leír egy formális nyelvet. A formális nyelveket, valamint az emberi nyelveket leíró nyelvtanok között bizonyos analógiák figyelhetők meg. A formális nyelvek és formális nyelvtanok vizsgálatának egyik legjelentősebb úttörője Noam Chomsky, akinek a munkássága egyaránt hatott a formális nyelvek és a természetes nyelvek kutatására is.

A formális nyelvtanok két fő kategóriába oszthatók: generatív és analitikus nyelvtanok.

• Egy generatív nyelvtan, a legismertebb kategória, azoknak a szabályoknak a halmaza, amelyekkel minden, a nyelvben lehetséges jelsorozat előállítható, azaz leírja, hogyan lehet előállítani egy átírási eljárással a kitüntetett kezdő szimbólumból a többi jelsorozatot a szabályokat egymás után alkalmazásával. A generatív nyelvtan a valóságban egy algoritmust formalizál, ami a nyelv összes jelsorozatát generálja.
• Egy analitikus nyelvtan, ellenpólusként, azoknak a szabályoknak a halmaza, amelyeknek egy bemenő jelsorozatra való egymás utáni alkalmazása (redukció vagy elemzés) végül egy logikai, boolean típusú eredményt ad, azaz "igen/nem" választ ad arra a kérdésre, hogy a bemenő jelsorozat a nyelvtannal leírt nyelvnek megfelel vagy sem. Egy analitikus nyelvtan a valóságban egy nyelv elemzőjének formalizált leírást adja meg.

Röviden, egy analitikus nyelvtan leírja, hogyan olvassuk a nyelvet, amíg egy generatív nyelvtan azt írja le, hogyan írjuk.

Generatív nyelvtanok

Egy generatív nyelvtan a jelsorozatok transzformációs szabályait leíró szabályok halmazából áll. A nyelvet alkotó jelsorozatok létrehozásához szükséges, hogy legyen egy egyedi „kezdő” szimbólum, ezután csak a szabályokat kell egymás után alkalmazni (bárhányszor, tetszés szerinti sorrendben) a kezdő szimbólum átalakítására. A nyelv azokból a jelsorozatokból áll, amelyeket az említett módon elő lehet állítani. A szabályok alkalmazásának megengedett lehetőségei közül bármilyen különleges sorrend alkalmazásával az átalakításokkal létrehozhatók jelsorozatok, de ha ezek közül a jelsorozatok közül egyet is többféleképpen is elő lehet állítani, akkor a nyelvtant kétértelműnek nevezik.

Tegyük fel például, hogy egy ábécéhez a '${\displaystyle a}$' és a '${\displaystyle b}$' szimbólumok tartoznak, a kezdő szimbólum pedig legyen az '${\displaystyle S}$' és adottak a következő szabályok:

1. ${\displaystyle S\longrightarrow aSb}$

2. ${\displaystyle S\longrightarrow ba}$

Kezdő szimbólumunk a „${\displaystyle S}$”, de ezután kiválaszthatjuk, hogy melyik szabályt alkalmazzuk a jelsorozat következő elemének előállításához. Ha az 1-es szabályt választjuk, akkor annak alapján az '${\displaystyle S}$' szimbólumot a '${\displaystyle aSb}$'-al helyettesítjük, eredményül tehát a „${\displaystyle aSb}$” jelsorozatot kapjuk. Ha most ismételten az 1-es szabály alkalmazását választjuk, akkor helyettesítjük az '${\displaystyle S}$' szimbólumot a '${\displaystyle aSb}$'-vel, és akkor a „${\displaystyle aaSbb}$” jelsorozatot kapjuk. Ezt az eljárást addig ismételhetjük, amíg az ábécé szimbólumai megengedik (esetünkben '${\displaystyle a}$' és '${\displaystyle b}$'). Befejezve a példát, most válasszuk a 2-es szabályt, helyettesítsük az '${\displaystyle S}$' szimbólumot a '${\displaystyle ba}$' jelsorozattal, eredményül pedig a „${\displaystyle aababb}$” jelsorozatot kapjuk, és ezzel be is fejeztük.

Az adott szimbólumokat használva a fentieket sokkal egyszerűbb formában is leírhatjuk: ${\displaystyle S\longrightarrow aSb\longrightarrow aaSbb\longrightarrow aababb}$.

A nyelvtan által meghatározott nyelv nem lesz más, mint az összes olyan jelsorozat halmaza, amelyeket ezzel az eljárással elő tudunk állítani: ${\displaystyle \left\{ba,abab,aababb,aaababbb,...\right\}}$.

Formális definíció

Noam Chomsky az 1950-es években javasolta először a generatív nyelvtanok klasszikus formalizálását, ami szerint egy G nyelvtan a következő komponensekből áll:

• ${\displaystyle N}$ a nem-terminális szimbólumok véges halmaza;
• ${\displaystyle \Sigma }$ a terminális szimbólumok véges halmaza, aminek nincs közös része ${\displaystyle N}$-nel;
• ${\displaystyle P}$ a produkciós szabályok véges halmaza, ahol a szabályok a következő formában adottak

${\displaystyle (\Sigma \cup N)^{*}}$ beli jelsorozat ${\displaystyle \longrightarrow }$ ${\displaystyle (\Sigma \cup N)^{*}}$-beli jelsorozat

(ahol ${\displaystyle {}^{*}}$ a Kleene-csillag és ${\displaystyle \cup }$ az unió művelet) azzal a megkötéssel, hogy a szabály bal oldalának (bal oldali rész a ${\displaystyle \longrightarrow }$ előtt) legalább egy nem-terminális szimbólumot tartalmaznia kell.

• Az ${\displaystyle N}$ halmazhoz tartozó ${\displaystyle S}$ szimbólum, ami a kezdő szimbólumot jelöli.

Gyakran a ${\displaystyle G}$ formális nyelvtan jelölésé a ${\displaystyle (N,\Sigma ,P,S)}$ négyessel történik.

A ${\displaystyle G=(N,\Sigma ,P,S)}$, formális nyelvtannal meghatározott nyelvet jelölik a ${\displaystyle {\boldsymbol {L}}(G)}$ szimbólummal is. Ezzel meghatároznak minden olyan, a ${\displaystyle \Sigma }$ halmazból generálható jelsorozatot, amelyeket a ${\displaystyle P}$ halmazban lévő produkciós szabályok egymásutáni alkalmazásával a ${\displaystyle S}$ kezdő szimbólumot kezdőként alkalmazva létrehozható, addig, amíg a nem-terminális szimbólumok készlete rendelkezésre áll.

Példa

A következő példáknál a formális nyelvet a halmaz-felépítő jelölés használatával határozzuk meg.

Például, tételezzük fel a ${\displaystyle G}$ nyelvtanról, hogy a következőkből áll:

${\displaystyle N=\left\{S,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b,c\right\}}$, ${\displaystyle P}$ pedig a következő produkciós szabályokat tartalmazza:

1. ${\displaystyle S\longrightarrow aBSc}$

2. ${\displaystyle S\longrightarrow abc}$

3. ${\displaystyle Ba\longrightarrow aB}$

4. ${\displaystyle Bb\longrightarrow bb}$,

és az ${\displaystyle S}$ nem-terminális szimbólum a kezdő szimbólum.

Néhány példa arra, hogyan származtathatók a jelsorozatok a ${\displaystyle {\boldsymbol {L}}(G)}$ nyelvben:

• ${\displaystyle {\boldsymbol {S}}\longrightarrow (2)abc}$
• ${\displaystyle {\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (2)a{\boldsymbol {Ba}}bcc\longrightarrow (3)aa{\boldsymbol {Bb}}cc\longrightarrow (4)aabbcc}$
• ${\displaystyle {\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (1)aBaB{\boldsymbol {S}}cc\longrightarrow (2)a{\boldsymbol {Ba}}Babccc\longrightarrow (3)aaB{\boldsymbol {Ba}}bccc\longrightarrow (3)aa{\boldsymbol {Ba}}Bbccc}$${\displaystyle \longrightarrow (3)aaaB{\boldsymbol {Bb}}ccc\longrightarrow (4)aaa{\boldsymbol {Bb}}bccc\longrightarrow (4)aaabbbccc}$

(a jelsorozatok előállításánál használt produkciós szabály azonosítója a zárójelben van, a helyettesíthető rész pedig vastagon szedett).

Egyértelmű, hogy a fenti nyelvtan meghatározza a ${\displaystyle \left\{a^{n}b^{n}c^{n}|n>0\right\}}$ nyelvet, ahol ${\displaystyle a^{n}}$ jelöli azt a jelsorozatot, amely n darab ${\displaystyle a}$-ból áll. Következésképpen, az egész nyelv bármilyen pozitív számú 'a'-t követő azonos számú 'b'-ből és azonos számú 'c'-ből álló jelsorozatból áll.

A generatív formális nyelvtanok identikusak a Lindenmayer rendszerekkel (L-rendszerek), kivéve, hogy az L-rendszerekben nincsen különbség a terminálisok és s nem-terminálisok között, valamint az L-rendszerek megszorítást tartalmaznak a szabályok alkalmazásának sorrendjére, és az L-rendszerek nem állnak le, ezért végtelen jelsorozat szekvenciákat generálnak.

A Chomsky-féle hierarchia

Amikor az 1950-es években Noam Chomsky először formalizálta a generatív nyelvtanokat, akkor négy típusba sorolta be azokat. Ezek a csoportok ma Chomsky-féle hierarchiaként ismertek. Az egyes típusok között a különbség a produkciós szabályok szigorúságában jelenik meg. Két fontos típus a környezetfüggetlen nyelvtanok és a szabályos nyelvtanok. Azok a nyelvek, amelyek valamilyen nyelvtannal leírhatók azok az úgynevezett környezetfüggetlen nyelvek illetőleg a szabályos nyelvek. Habár kevésbé hatékonyak, mint a megkötés nélküli nyelvtanok, amelyek ténylegesen le tudnak írni bármilyen nyelvet, amelyek a Turing-gépekkel elfogadhatóak, ezen megkötések miatt inkább az ilyen nyelvtanok hatékonyan elemzők segítségével valósíthatók meg. Például, a környezetfüggetlen nyelvtanok a jól ismert algoritmusokat megvalósító LL elemzők és LR elemzők segítségével elemezhetők hatékonyan.

	Nyelvtanok	Nyelvek	Automaták	Produkciós szabályok
0. nyelvosztály	Rekurzívan megszámlálható	Rekurzívan megszámlálható	Turing-gép	Nincs megkötés
1. nyelvosztály	környezetfüggő	környezetfüggő	Korlátos nem determinisztikus Turing-gép	${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$
2. nyelvosztály	környezetfüggetlen	környezetfüggetlen	Nem determinisztikus veremautomata	${\displaystyle A\rightarrow \gamma }$
3. nyelvosztály	Szabályos	Szabályos	Véges determinisztikus automata	${\displaystyle A\rightarrow a}$ és egyébként ${\displaystyle A\rightarrow aB}$ vagy ${\displaystyle A\rightarrow Ba}$

Környezetfüggetlen nyelvtanok

A környezetfüggetlen nyelvtanok esetében, a produkciós szabályok bal oldalán csak egy egymagában álló nem-terminális szimbólum lehet. Az előzőekben meghatározott nyelv nem volt környezetfüggetlen nyelv. Környezetfüggetlen nyelv viszont a ${\displaystyle \left\{a^{n}b^{n}|n>0\right\}}$ (bármely pozitív számú 'a'-t azonos számú 'b' követ) nyelv, amelynek ${\displaystyle G2}$ a nyelvtana és az ${\displaystyle N=\left\{S\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, és ${\displaystyle S}$ a kezdő szimbólumok határoznak meg, valamint a következő produkciós szabályok:

1. ${\displaystyle S\longrightarrow aSb}$

2. ${\displaystyle S\longrightarrow ab}$

Reguláris (szabályos) nyelvtanok

A reguláris nyelvtanokban, a bal oldalon szintén csak egy egyedülálló nem-terminális szimbólum állhat, de most a jobb oldalra is megkötést kell tenni: lehet üres, lehet egyetlen terminális szimbólum és lehet egy egyedül álló terminális szimbólumot követő nem-terminális szimbólum. (Néha egy tágabb meghatározás használatos: megengedett egy eset a következők közül: vagy terminálisok hosszabb jelsorozata vagy egy egyedül álló, önálló nem-terminális.)

Az előzőekben meghatározott nyelv nem reguláris, de a ${\displaystyle \left\{a^{n}b^{m}|m,n>0\right\}}$ nyelv (bármilyen pozitív számú 'a'-kat követő bármilyen pozitív számú 'b'-k, ahol a számok különbözőek is lehetnek) már reguláris, és meghatározható a ${\displaystyle G3}$ nyelvtannal, ami az ${\displaystyle N=\left\{S,A,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, és a ${\displaystyle S}$ kezdő szimbólummal, valamint a következő produkciós szabályokkal van meghatározva:

1. ${\displaystyle S\longrightarrow aA}$

2. ${\displaystyle A\longrightarrow aA}$

3. ${\displaystyle A\longrightarrow bB}$

4. ${\displaystyle B\longrightarrow bB}$

5. ${\displaystyle B\longrightarrow \epsilon }$

A gyakorlatban a reguláris nyelvtanok leírására reguláris kifejezéseket (szabályos kifejezéseket) használnak.

Szabályos- és környezetfüggetlen nyelvek összehasonlítása

A produkció szabályok különbözősége oldaláról a kétfajta nyelv közötti alapvető különbség az ${\displaystyle \left\{a^{n}b^{n}|n>0\right\}}$ (környezetfüggetlen) és az ${\displaystyle \left\{a^{n}b^{m}|n,m>0\right\}}$ (szabályos) között az, hogy a környezetfüggetlen nyelv esetén az 'a'-k és a 'b'-k száma azonos kell, hogy legyen. Ennélfogva, bármilyen automata segítségével történő környezetfüggetlen nyelv felismerésének megkísérlésekor elengedhetetlenül szükséges, hogy több információt kell figyelembe venni, mint a szabályos nyelv esetében. A továbbiakban nem kell foglalkoznunk az 'a'-k vagy a 'b'-k számával, viszont fel kell tételeznünk, hogy a számuk nullánál nagyobb.

A részleteket lásd a környezetfüggetlen nyelv és szabályos nyelv szócikkek alatt.

A generatív nyelvtanok egyéb formái

A formális nyelvtanok eredeti Chomsky-féle hierarchiájának legtöbb kiterjesztésének és változatának kifejlesztését a nyelvészek és a számítógép-tudomány képviselői nemrégen végezték el, mindketten általában azzal a céllal, hogy az elemzők teljesítményét megnöveljék. Természetesen ezek a célok sajátságos eredményeket hoztak: minél kifejezőbb nyelvtani formalizmusok, az automatizált eszközök egyre nehezebben használhatók az elemzéseknél. A nyelvtanok néhány formája ezen sajátos eredményekre tekintettel került kifejlesztésre:

• Fa-szomszédos nyelvtanok megnövelik a konvencionális generatív nyelvtanok kifejező képességét azzal, hogy megengedik az elemzési szabályok, pontosabban az elemzési fa átírását a stringek helyett.
• Affix nyelvtanok és attribútum nyelvtanok megengedik a szabályok átírását szemantikai attribútumok és operátok hatására, amivel egyrészt megnő a nyelvtan kifejezőképessége, másrészt hatékonyabb nyelvi elemző és fordító eszközök készíthetők.

Analitikus nyelvtanok

Habár a rendelkezésre álló elemző algoritmusokkal foglalkozó irodalom igen terjedelmes, ezek közül az algoritmusok közül a legtöbb azt feltételezi, hogy az elemzendő nyelv leírása egy generatív formális nyelvtant jelent, és az a cél, hogy átalakítsa ezt a generatív nyelvtant egy működő elemzővé. Egy másik lehetséges megközelítés a nyelvet elsődlegesen egy analitikus nyelvtannal formalizálja, amely sokkal közvetlenebb kapcsolatot biztosít az elemző és az elemzendő nyelv struktúrája között. Az analitikus nyelvtanokkal történő formalizálást mutatja be a következő néhány példa:

• The Language Machine közvetlenül valósít meg korlátozások nélküli analitikus nyelvtanokat. A helyettesítési szabályok alkalmazásával vezérelhető a bemenetek és kimenetek közötti kapcsolat, illetve a rendszer viselkedése. A rendszer előállít úgynevezett lm-diagramot is, amely megmutatja, mi történik a korlátozások nélküli analitikus nyelvtan szabályainak alkalmazásakor.
• fentről-lefelé elemző nyelv (TDPL, az angol Top-Down Parser Language rövidítése): a nagyon minimalista analitikus nyelvtan kifejlesztése az 1970-es években történt, amikor a top-down elemzők viselkedést tanulmányozták.
• Parsing expression nyelvtanok (PEGs): a TDPL egy újkeletű általánosításával tervezett gyakorlati megvalósítás a compiler írók számára.
• Kapcsolati nyelvtanok: nyelvészeti célokra kifejlesztett analitikus nyelvtan, amely a szintaktikai struktúrát szópárok kapcsolatainak alapján hozza létre.