Szintaxis elemzés: fordító felülről lefelé és alulról felfelé elemzési típusai

A szintaktikai elemzés a fordítótervezési folyamatban a Lexical elemzési fázis után jön. Más néven elemzőfa vagy szintaxisfa. Az elemzési fa a nyelv előre definiált nyelvtana segítségével készült. A szintaktikai elemző azt is ellenőrzi, hogy egy adott program megfelel-e a környezetfüggetlen nyelvtan által megkövetelt szabályoknak. Ha megfelel, az elemző létrehozza a forrásprogram értelmező fáját. Ellenkező esetben hibaüzeneteket jelenít meg.

Miért van szüksége a Syntax Analyserre?

• Ellenőrizze, hogy a kód nyelvtanilag érvényes-e
• A szintaktikai elemző segít szabályokat alkalmazni a kódra
• Segít megbizonyosodni arról, hogy minden nyitómerevítőnek megfelelő záróegyenlege van
• Minden deklarációnak van egy típusa, és a típusnak léteznie kell

Fontos szintaktikai elemző terminológia

A szintaktikai elemzési folyamatban használt fontos terminológiák:

• Mondat: A mondat egy karaktercsoport valamilyen ábécé fölött.

• Lexéma: A lexéma a nyelv legalacsonyabb szintaktikai egysége (pl. összesen, kezdet).

• Jelképes: A token csak a lexémák kategóriája.

• Kulcsszavak és fenntartott szavak – Ez egy azonosító, amelyet egy utasítás szintaxisának rögzített részeként használnak. Ez egy fenntartott szó, amelyet nem használhat változónévként vagy azonosítóként.

• Zajos szavak – A zajszavak nem kötelezőek, amelyek a mondat olvashatóságának javítása érdekében kerülnek beillesztésre az utasításba.

• Hozzászólások – Nagyon fontos része a dokumentációnak. Leginkább a, /* */ vagy//Üres (szóközök) jelzéssel jelenik meg

• Elhatárolók – Ez egy szintaktikai elem, amely egy szintaktikai egység kezdetét vagy végét jelöli. Mint egy állítás vagy kifejezés, „begin”…”end” vagy {}.

• Karakterkészlet – ASCII, Unicode

• azonosítók – Ez egy hosszkorlátozás, amely segít csökkenteni a mondat olvashatóságát.

• Operator szimbólumok – + és – két alapvető aritmetikai műveletet hajt végre.
• A nyelv szintaktikai elemei

Miért van szükségünk elemzésre?

Az elemzés azt is ellenőrzi, hogy a bemeneti karakterlánc megfelelő-e, és ha nem, akkor elutasítja.

A következő fontos feladatokat láthatja, amelyeket az értelmező hajt végre a fordítótervezés során:

• Segít minden típusú szintaktikai hiba észlelésében
• Keresse meg azt a helyet, ahol a hiba történt
• A hiba világos és pontos leírása.
• Helyreállítás hibából a folytatáshoz és a további hibák kereséséhez a kódban.
• Nem befolyásolhatja a „helyes” programok fordítását.
• Az elemzésnek el kell utasítania az érvénytelen szövegeket a szintaktikai hibák jelentésével

Elemzési technikák

Az elemzési technikák két csoportra oszthatók:

• Felülről lefelé történő elemzés,
• Alulról felfelé irányuló elemzés

Felülről lefelé történő elemzés

A felülről lefelé irányuló elemzés során az elemzőfa felépítése a gyökérnél kezdődik, majd a levelek felé halad.

A felülről lefelé történő elemzés két típusa:

1. Prediktív elemzés:

A prediktív elemzés megjósolhatja, hogy melyik produkciót kell használni az adott bemeneti karakterlánc helyettesítésére. A prediktív elemző előretekintési pontot használ, amely a következő bemeneti szimbólumok felé mutat. A visszalépés nem jelent problémát ennél az elemzési technikánál. LL(1) Parser néven ismert

2. Rekurzív leszármazási elemzés:

Ez az elemzési technika rekurzív módon elemzi a bemenetet, hogy prase fát hozzon létre. Több kis függvényből áll, egyet a nyelvtan minden nemterminálisához.

Alulról felfelé irányuló elemzés

A fordítói tervezésben az alulról felfelé történő elemzésben az elemzőfa felépítése a kihagyással kezdődik, majd a gyökér felé halad. Eltolás-csökkentésnek is nevezik. Ez a fajta elemzés a fordítótervben néhány felhasználásával jön létre szoftverek.

Hiba – Helyreállítási módszerek

A rendszerszoftver elemzése során előforduló gyakori hibák

• Lexikális: Helytelenül beírt azonosító neve
• Szintaktikai: kiegyensúlyozatlan zárójel vagy hiányzó pontosvessző
• Szemantikai: inkompatibilis érték hozzárendelés
• logikus: Végtelen hurok és nem elérhető kód

Az elemzőnek képesnek kell lennie a programban talált hibák észlelésére és jelentésére. Tehát, ha hiba történt, az elemző. Képesnek kell lennie kezelni és folytatni a fennmaradó bemenet elemzését. Egy program a következő típusú hibákat tartalmazhatja a fordítási folyamat különböző szakaszaiban. Öt általános hiba-helyreállítási módszer létezik, amelyeket az elemzőben lehet megvalósítani

Kimutatás mód helyreállítása

• Abban az esetben, ha az elemző hibát észlel, segít a helyesbítő lépések megtételében. Ez lehetővé teszi a többi bemenet és állapot előre történő elemzését.
• Például egy hiányzó pontosvessző hozzáadása az utasításmódú helyreállítási módszerrel történik. Az elemzés tervezőjének azonban óvatosnak kell lennie a változtatások végrehajtása során, mivel egy rossz javítás végtelen ciklushoz vezethet.

Pánik mód helyreállítása

• Abban az esetben, ha az elemző hibába ütközik, ez a mód figyelmen kívül hagyja az utasítás többi részét, és nem dolgozza fel a hibás beviteltől a határolóig, például a pontosvesszőig. Ez egy egyszerű hibaelhárítási módszer.
• Az ilyen típusú helyreállítási módszerben az elemző egyenként utasítja el a bemeneti szimbólumokat, amíg meg nem találja a szinkronizáló tokenek egyetlen kijelölt csoportját. A szinkronizáló tokenek általában olyan elválasztójeleket használnak, mint a vagy.

Kifejezésszintű helyreállítás

• A fordító tokenek beszúrásával vagy törlésével javítja a programot. Ez lehetővé teszi az elemzést onnan, ahol volt. Korrekciót hajt végre a fennmaradó bemeneten. Lecserélheti a fennmaradó bemenet előtagját valamilyen karakterláncra, ami segít az elemzőnek a folyamat folytatásában.

Error Productions

• A hibatermelés helyreállítása kibővíti a hibás konstrukciókat előállító nyelv nyelvtanát. Az elemző ezután hibadiagnosztikát végez az adott konstrukcióval kapcsolatban.

Globális korrekció

• A fordítónak a lehető legkevesebb változtatást kell végrehajtania, miközben hibás bemeneti karakterláncot dolgoz fel. Helytelen a bemeneti karakterlánc és c nyelvtan esetén az algoritmusok egy elemzőfát keresnek a kapcsolódó b karakterlánchoz. Mint egyes beszúrások, törlések és tokenek módosításai, amelyek az an b-vé alakításához szükségesek, a lehető legkevesebb.

Nyelvtan

A nyelvtan egy nyelvet leíró szerkezeti szabályok összessége. A nyelvtan bármely mondathoz struktúrát rendel. Ez a kifejezés ezen szabályok tanulmányozására is utal, és ez a fájl magában foglalja a morfológiát, a fonológiát és a szintaxist. Számos szintaxist képes leírni programozási nyelvek.

A formanyelvtan szabályai

• A nem terminál szimbólumnak legalább egy produkciótól balra kell megjelennie
• A cél szimbólum soha nem jelenhet meg egyetlen produkció::= jobb oldalán sem
• Egy szabály rekurzív, ha az LHS megjelenik az RHS-ben

Jelölési konvenciók

A jelölési konvenciók szimbóluma az elem szögletes zárójelben való feltüntetésével jelezhető. Ez az elem tetszőleges előfordulási sorozata, amelyet úgy lehet jelezni, hogy az elemet kapcsos zárójelek közé egy csillag szimbólum követi, { … }*.

Ez egy olyan alternatíva választása, amely használhatja a szimbólumot az egyetlen szabályon belül. Szükség esetén zárójelbe ([,] ) kerülhet.

Kétféle jelölési konvenció terület: terminál és nem terminál

1. Terminálok:

• Kisbetűk az ábécében, például a, b, c,
• Operator szimbólumok, például +,-, * stb.
• Írásjelek, például zárójel, hash, vessző
• 0, 1, …, 9 számjegy
• Félkövér karakterláncok, például id vagy if, bármi, ami egyetlen terminál szimbólumot jelent

2. Nem terminálok:

• Nagybetűk, például A, B, C
• Kisbetűs dőlt nevek: a kifejezés vagy néhány

Context Free Grammar

A CFG egy balra rekurzív nyelvtan, amelynek legalább egy ilyen típusú produkciója van. A környezetfüggetlen nyelvtan szabályai főként rekurzívak. A szintaktikai elemző ellenőrzi, hogy az adott program megfelel-e a kontextusmentes nyelvtan összes szabályának, vagy sem. Ha megfelel, ezek a szabályok szintaktikai elemzői létrehozhatnak egy elemzőfát az adott programhoz.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Nyelvtani származtatás

A nyelvtani levezetés egy nyelvtani szabály sorozata, amely a kezdőszimbólumot karakterláncsá alakítja. Levezetés bizonyítja, hogy a karakterlánc a nyelvtan nyelvéhez tartozik.

A bal szélső Származtatás

Amikor a bemenet mondatos formáját balról jobbra sorrendben szkenneljük és lecseréljük, azt bal szélső levezetésnek nevezzük. A bal szélső levezetéssel levezetett mondatformát baloldali mondatformának nevezzük.

Jobb oldali származék

A jobb szélső levezetési szkennelés, és cserélje ki a bemenetet termelési szabályokkal, jobbról balra, sorrendben. Jobb szélső származékként ismert. A jobb szélső levezetésből származó mondatformát jobb mondatformának nevezzük.

Szintaxis kontra Lexical Analyzer

Szintaxis elemző	Lexikai elemző
A szintaktikai elemző főként a nyelv rekurzív konstrukcióival foglalkozik.	A lexikális elemző megkönnyíti a szintaktikai elemző feladatát.
A szintaktikai elemző a forrásprogramban lévő tokeneken dolgozik, hogy felismerje a programozási nyelv értelmes struktúráit.	A lexikális elemző felismeri a tokent egy forrásprogramban.
Tokenek formájában bemeneteket kap a lexikális elemzőktől.	Felelős az általa biztosított token érvényességéért a szintaktikai elemző

A szintaktikai elemzők használatának hátrányai

• Soha nem fogja eldönteni, hogy egy token érvényes-e vagy sem
• A Not segít annak meghatározásában, hogy egy tokentípuson végrehajtott művelet érvényes-e vagy sem
• Nem döntheti el, hogy a tokent deklarálja és inicializálja a használat előtt

Összegzésként

• A szintaktikai elemzés a fordítótervezési folyamat második fázisa, amely a lexikális elemzés után következik
• A szintaktikai elemző segít szabályokat alkalmazni a kódra
• Mondat, Lexéma, Token, Kulcsszavak és fenntartott szavak, Zajszavak, Megjegyzések, Határolók, Karakterkészlet, Az azonosítók néhány fontos kifejezés, amelyet a fordítói szintaxiselemzésben használnak.
• Az elemzés ellenőrzi, hogy a bemeneti karakterlánc megfelelő-e, és ha nem, akkor elutasítja
• Az elemzési technikák két különböző csoportra oszthatók: felülről lefelé történő elemzésre, alulról felfelé történő elemzésre
• A lexikai, szintaktikai, szemantikai és logikai néhány gyakori hiba az elemzési módszer során
• A nyelvtan egy nyelvet leíró szerkezeti szabályok összessége
• A jelölési konvenciók szimbóluma az elem szögletes zárójelben való feltüntetésével jelezhető
• A CFG egy balra rekurzív nyelvtan, amelynek legalább egy ilyen típusú produkciója van
• A nyelvtani levezetés egy nyelvtani szabály sorozata, amely a kezdőszimbólumot karakterláncsá alakítja
• A szintaktikai elemző főként a nyelv rekurzív konstrukcióival foglalkozik, míg a lexikális elemző megkönnyíti a szintaktikai elemző feladatát. DBMS
• A Syntax Analyzer módszer hátránya, hogy soha nem fogja meghatározni, hogy egy token érvényes-e vagy sem