Formális nyelvtan
A Wikipédiából, a szabad lexikonból.
A formális nyelvtan informatikai értelemben egy absztrakt struktúra, amely pontosan leír egy formális nyelvet pl. a szabályok halmaza, amely matematikailag egy (általában véges) ábécén értelmezett véges hosszúságú jelsorozatok (általában végtelen) halmazával ábrázolható.
A formális nyelvek, valamint az emberi nyelveket leíró nyelvtanok között bizonyos analógiák figyelhetők meg.
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 is 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 analitikus nyelvtan azt írja le, hogyan írjuk.
Tartalomjegyzék |
[szerkesztés] 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 jelsorozatotk, de ha ezek közül a jelsorozatok közül egyet is több féle ké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 'a' és a 'b' szimbólumok tartoznak, a kezdő szimbólum pedig legyen az 'S' és adottak a következő szabályok:
- 1.

- 2.

Kezdő szimbólumunk a "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 'S' szimbólumot a 'aSb'-al helyettesítjük, eredményül tehát a "aSb" jelsorozatot kapjuk. Ha most ismételten az 1-es szabály alkalmazását választjuk, akkor helyettesítjük az 'S' szimbólumot a 'aSb'-al, és akkor a "aaSbb" jelsorozatot kapjuk. Ezt az eljárást addig ismételhetjük, amíg az ábécé szimbólumai megengedik (esetünkben 'a' és 'b'). Befejezve a pldát, most válasszuk a 2-es szabályt, helyettesítsük az 'S' szimbólumot a 'ba' jelsorozattal, eredményül pedig a "aababb", jelsorozatot kapjuk, és ezzel be is fejeztük.
Az adott szimbólumokat használva feltieket sokkal egyszerűbb formában is leírhatjuk:
.
A nyelvtan által meghatározott nyelv nem lesz más, mint az összes olyan jelsorozat halmaza, amelyeket a ezzel az eljárással elő tudunk állítani:
.
[szerkesztés] Formális definíció
Noam Chomsky az 1950-es években javasolta először a generatív nyelvtanok klasszikus formalizálást, ami szerint egy G nyelvtan a következő komponensekből áll:
- N a nem-terminális szimbólumok véges halmaza;
- Σ a terminális szimbólumok véges halmaza, aminek nincs közös része N-el;
- P a produkciós szabályok véges halmaza, ahol a szabályok a következő formában adottak
-
beli jelsorozat
beli jelsorozat
- (ahol * a Kleene star és
az unió művelet) azzal a megkötéssel, hogy a szabály bal oldalának (bal oldali rész a
előtt) legalább egy nem-terminális szimbólumot tartalmaznia kell.
- Az N halmazhoz tartozó S szimbólum, ami a kezdő szimbólumot jelöli.
Gyakran a G formális nyelvtan jelölésé a (N,Σ,P,S) négyessel történik.
A G = (N,Σ,P,S), formális nyelvtannal meghatározott nyelvet jelölik a
szimbólummal is. Ezzel meghatároznak minden olyan, a Σ halmazból generálható jelsorozatot, ammelyeket a P halmazban lévő produkciós szabályok egymásutáni alkalmazásával a S kezdő szimbólumot kezdőként alkalmazva létrehozható, addig, amíg a nem-terminális szimbólumok készlete rendelkezésre áll.
[szerkesztés] 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 G nyevtanról, hogy a következőkből áll:
,
, P pedig a következő produkciós szabályokat tartalmazza
- 1.

- 2.

- 3.

- 4.

és az S nem-terminális szimbólum a kezdő szimbólum.
Néhény példa arra, hogyan származtathatók a jelsorozatok a
nyelvben:
(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
nyelvet, ahol an jelöli azt a jelsorozatot, amely n darab 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ánák sorrendjére, és az L-rendszerek nem állnak le, ezért végtelen jelsorozat szekvenciákat generálnak.
[szerkesztés] 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 hierachiaké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örnyezet független nyelvtanok és a szabályos nyelvtanok. Azok a nyelvek, amelyek valamilyen nyelvtannal leírhatók azok az úgynevezett környezet független nyelvek illetőleg a szabályos nyelvek. Habár kevésbé hatékonyak, mint a megkötés nélküli nyelvtanok, amelyek tenyleges 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örnyezet függetelen nyelvtanok a jól ismert algoritmusokat megvalósító LL elemzők és LR elemzők segítségevl elemezhetők hatékonyan.
| Nyelvtan | Nyelvek | Automaták | Produkciós szabályok |
|---|---|---|---|
| Type-0 | Rekurzívan megszámlálható | Turing-gép | Nincs megkötés |
| Type-1 | környezet függő | Korlátos nem determinisztikus Turing-gép | ![]() |
| Type-2 | környezet független | Nem determinisztikus pushdown automata | ![]() |
| Type-3 | Szabályos | Véges automata | ésegyébként |
[szerkesztés] Környezet független nyelvtanok
A környezet fü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örnyezet független nyelv. Környezet független nyelv viszont a
(bármely pozitív számú 'a'-t azonos számú 'b' követ) nyelv, amelynek G2 a nyelvtana és az
,
, és S a kezdő szimbólumok határoznak meg, valamint a követekező produkciós szabályok:
- 1.

- 2.

[szerkesztés] Szabályos, reguláris nyelvtanok
A szabályos nyelvtanokban, a bal oldanlon szintén csak egy egyedülálló nem-terminális szimbólum állhat, de most a jobb oldbalra is megkötést kell tenni: lehet üres, lehet egyetlen terminális szimbólum, lehet egy egyedül álló terminális szimbólumot követő nem-terminális szimbólum, és más eset nem megengedett. (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 szabályos, de a
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 szabályos, és meghatározható a G3 nyelvvel, ami az
,
, és a S kezdő szimbólummal, valamint a következő produkciós szabályokkal van meghatározva:
- 1.

- 2.

- 3.

- 4.

- 5.

A gyakorlatban a szabályos nyelvtanok leírására szabályos kifejezéseket használnak.
[szerkesztés] Szabályos- és környezet független nyelvek összehasonlítása
A produkció szabályok különbözősége oldaláról a két fajta nyelv közötti alapvető különbség az
(környezet független) és az
(szabályos) között az, hogy a környezet fü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örnyezet fü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 fogalakoznunk 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örnyezet független nyelv és szabályos nyelv szócikkek alatt.
[szerkesztés] A generatív nyelvtanok egyéb formái
Az fromális nyelvtanok eredeti Chomsky féle hierarchiájának legtöbb kiterjesztéseinek és változatainak kifejlesztését a nyelvészek és a számitó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ágok erdményekt hoztak: minél kifejezőbb nyelvatani 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 tekinetettel 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 szementikai 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 frodító eszközök készíthetők.
[szerkesztés] Analitikus nyelvtanok
Habár a rendelkezésre álló elemző algoritusokkal 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 nyelvtanat 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ását mutat 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 ugynevezett lm-diagramot is, amely megmutatja mi történik ha a korlátozások néküli analitikus nyelvtan szabályai alkalmazásra kerülnek.
- 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.
[szerkesztés] Lásd még
- Konkrét szintaxis fa
- Absztrakt szintaxis fa
- Kétértelmű nyelvtan






és



Based on work by