Elemző (informatika)

A Wikipédiából, a szabad lexikonból.

Az informatika a nyelvi elemzés alatt egy bejövő jelsorozat (olvasás fájlból vagy a klaviatúráról, például) elemzési folyamatát érti, amelyet azért hajt végre, hogy eldöntse, az adott nyelvtani struktúrája megfelel-e egy adott formális nyelvtannak. Az elemző egy számítógép program amely elvégzi ezt a feladatot. A folyamat nevét, az elemzést azonos értelemben használják a nyelvtanok és a nyelvészet. Az elemezhető kifejezést általában olyan szövegekre vagy adatokra használják, amelyeket számítógép program sikeresen tud elemezni.

Az elemzés folyamán a bejövő szöveget az elemző egy adatstruktúrává alakítja át, általában ez egy fa struktúra, amely alkalmas későbbi feldolgozásra, és megőrzi a forrásban lévő esetleges hierarchiákat. Általában az elemző két lépésben dolgozik, első lépésben azonosítja a jelentéssel bíró alapelemeket a bejövő szövegben, aztán épül fel az elemzési fa az azonosított alapelemekből.

Tartalomjegyzék

[szerkesztés] Emberi nyelvek

Néhány gépi fordító és természetes nyelv feldolgozó rendszer az emberi nyelvet számítógépes programmal elemzi. A emberi nyelvben lévő mondatok programokkal egyszerűen nem elemezhetők, mivel a helyettesítések kétértelmű struktúrák kialakulásához vezetnek, az emberi nyelvek nem környezet függetlensége miatt.

[szerkesztés] Programozási nyelvek

Az elemzők legelterjedtebb felhasználási területe a számítógépes programozási nyelvek elemzése. Ez egyszerűen a szabályos nyelvtanok alapján történik. A trendek szerint a programnyelvek elemzői környezet független nyelvtanokon alapulnak, ezért gyorsak és hatékonyak lehetnek. Viszont, a környezet független nyelvtan miatt korlátozott a nyelv kifejezőkézsége, mivel ez a nyelvtan csak korlátozott számú nyelvet tud leírni. Ez az oka közvetlenül annak is, hogy a nyelv korlátozottan képes emlékezni. Ez azért van, mert a nyelvtan nem tud visszaemlékezni egy hosszú bejövő jelsorozat elemzést megelőző konstrukciókra; ezért szükséges általában a neveket a rájuk való hivatkozás előtt deklarálni. A nagyobb "teljesítményű" nyelvtanok viszont nem elemezhetők hatékonyan. Fentiek alapján elfogadott az a stratégia, hogy környezet független nyelvre olyan "laza" elemzőt hozzanak létre, amelyek képes a nyelv által nyújtott lehetséges konstrukciók bővebb halmazát elfogadni (esetenként elfogadni érvényleten konstrukciót is); és később az el nem fogadható konstrukciók kiszűrésére. Általában egyszerű meghatározni egy környezet független nyelvtant, amelybe beletartozik minden elfogadhatónak tartott nyelvi konstrukció, ugyanakkor gyakran lehetetlen azt a környezet független nyelvtant létrehozni, csak a kívánatos konstrukciókat engedi meg.

Az elemzőket ma már ritkán írják kézzel, egyre gyakrabban használnak elemző generátor programokat.

[szerkesztés] A folyamant áttekintése

A következőkben elemzett példa egyszerre mutatja a nyelvi elemzés két nyelvani szintjét: a lexikait és a szintaktikait.

Az első lépés a alapelemek generálása, vagy a lexikai elemzés. Például, egy számológép program inputjaként a következő karakter-sorozat érkezik be: "12*(3+4)^2". A lexikai elemző a bemenetből a következő alapelemeket generálja: 12, *, (, 3, +, 4, ), ^ és 2. Ezek azok az alapelemek amelyek az aritmetikai kifejezések körében konkrét jelentéssel bírnak. Az elemző tartalmaz olyan szabályokat, amelyek mutatják, hogy például a *, +, ^, ( and ) karakterek egy új alapelem kezdetét jelzik, ezért nincsen értelme az olyan alapelemek létrehozásának, mint például "12*" vagy "(3".

A következő lépés a szintaktikai elemzés, vagy a szintaktikai analízis, amely azt ellenőrzi, hogy az alapelemek az egyes kifejezésekben a megengedett formában helyezkednek-e el. Ez általában egy környezet független nyelvtanra való hivatkozást jelent, amely rekurzív módon definiálja, hofy az adott alapelemek milyen sorrendben kell, hogy megjelenjenek egy aritmetikei kifejezésben.

Az utolsó fázisban szemantikus elemzés vagy analízis következik, amely megadja, hogy az adott kifejezés érvényes-e, és végrehajtja a megfelelő akciót. Estetünkben ez azt jelenti, hogy a számológép kiértékeli a kifejezést, és megadja az eredményét, egy compiler esetében pedig a generálódnak azok a gépi kódú utasítások, amelyek az adott kifejezést kiszámítják.

[szerkesztés] Elemzők típusai

Alapjában véve egy elemzőnek az a feladata, hogy meghatározza, hogy leszármaztatható-e, és ha igen, milyen módon a adott bejövő string a kezdő szimbólumból a formális nyelvtan szabaályainak alkalmzásával. Ez lényegében a következő két módon történik:

  • Top-down elemzés – A felülről-lefelé elemző a kezdő szimbólumtól elindulva megpróbálja azt úgy átalakítani, hogy a bejövő jelsorozatot kapja eredményül. A megoldáshoz az elemző a legnagyobb elemből indul ki, és próbálja azt egyre kisebb darabokra tördelni. Az LL elemzők a legjobb példák a felülről-lefelé elemzőkre.
  • Bottom-up elemzés – A lentről-felfelé elemző a bejövő karakterlácból indulva próbál eljutni a kezdő szimbólumhoz. A mogoldáshoz az elemző megkísérli azonosítani az alapelemeket, majd keresi azokat az elemeket, amelyek az azonosított elemeket tartalmazzák, és így tovább. Az LR elemzők a legjobb példák a lentről-felfelé elemzőkre.

Egy másik megkülömböztés alapján a döntő az, hogy az elemző a legbaloldalibb származtatás vagy a legjobboldalibb származtatás elvét követi (lásd környezet független nyelvtan). Általában az LL típusú elemzők a a legbaloldalib származtatás és a LR típusú elemzők általában a legjobboldalibb származtatás elvét követik (bár néha ez fordítva is lehet).

[szerkesztés] Példák elemzőkre

[szerkesztés] Top-down elemzők

A fentről-lefelé elemzést top-down elemző használó elemzők közé tartoznak:

  • Rekurzívan ereszkedő elemző
  • LL elemző
  • Packrat elemző
  • Unger elemző

[szerkesztés] Bottom-up elemzők

A fentről-lefelé elmzést bottom-up elemző használó elemzők közé tartoznak:

  • LR elemző
    • SLR elemző
    • LALR elemző
    • Kanonikus LR elemző
    • GLR elemző
  • Earley elemző
  • CYK elemző

[szerkesztés] Külső hivatkozások