Elemző (informatika)

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ő (parser) egy számítógépes program, amely elvégzi ezt a feladatot. A folyamat nevét, az elemzést azonos értelemben használják a formális nyelvtanokban és a nyelvészetben. Az elemezhető kifejezést általában olyan szövegekre vagy adatokra használják, amelyeket számítógépes program sikeresen tud elemezni, azaz képes a szöveget generáló transzformáció-sorozatot reprodukálni, kiszámítani, egy adott formális nyelvtani szabályhalmaz alapján.

Az elemzés folyamán a bejövő szöveget az elemző egy adatstruktúrává alakítja át, általában ez egy fastruktú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.

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örnyezetfüggetlensége miatt.

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örnyezetfüggetlen nyelvtanokon alapulnak, ezért gyorsak és hatékonyak lehetnek. Viszont, a környezetfüggetlen nyelvtan miatt korlátozott a nyelv kifejezőkészsé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örnyezetfü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énytelen konstrukciót is); és később az el nem fogadható konstrukciók kiszűrésére. Általában egyszerű meghatározni egy környezetfüggetlen nyelvtant, amelybe beletartozik minden elfogadhatónak tartott nyelvi konstrukció, ugyanakkor gyakran lehetetlen azt a környezetfü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.

A folyamat áttekintése

A következőkben elemzett példa egyszerre mutatja a nyelvi elemzés két nyelvtani 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örnyezetfüggetlen nyelvtanra való hivatkozást jelent, amely rekurzív módon definiálja, hogy az adott alapelemek milyen sorrendben kell, hogy megjelenjenek egy aritmetikai 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. Esetü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.

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ő karakterlánc a kezdő szimbólumból a formális nyelvtan szabályainak alkalmazá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áncból indulva próbál eljutni a kezdő szimbólumhoz. A megoldá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önbözteté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örnyezetfüggetlen nyelvtan). Általában az LL típusú elemzők a legbaloldalibb 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).

Példák elemzőkre

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ő

Bottom-up elemzők

A fentről-lefelé elemzé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ő

További információk

• UCalc Fast Math Parser Egy kereskedelmi kifejezés elemző
• muParser Nyílt forráskódú elemző, matematikai kifejezésekhez
• Parsing Techniques – A Practical Guide Elemzési technikák – gyakorlati kézikönyv Dick Grune és Ceriel J.H. Jacobs tollából.