Čo je to syntaxová analýza?
Syntaxová analýza je druhou fázou procesu návrhu kompilátora, v ktorej je daný vstupný reťazec kontrolovaný na potvrdenie pravidiel a štruktúry formálnej gramatiky. Analyzuje syntaktickú štruktúru a kontroluje, či je daný vstup v správnej syntaxi programovacieho jazyka alebo nie.
Syntaxová analýza v procese návrhu kompilátora prichádza po fáze lexikálnej analýzy. Je tiež známy ako Parse Tree alebo Syntax Tree. Parse Tree je vyvinutý pomocou vopred definovanej gramatiky jazyka. Analyzátor syntaxe tiež kontroluje, či daný program spĺňa pravidlá vyplývajúce z bezkontextovej gramatiky. Ak je to uspokojivé, syntaktický analyzátor potom vytvorí syntaktický strom tohto zdrojového programu. V opačnom prípade bude zobrazovať chybové správy.
V tomto návode sa naučíte
- Prečo potrebujete Syntax Analyzer?
- Dôležitá terminológia analyzátora syntaxe
- Prečo potrebujeme analýzu?
- Techniky syntaktickej analýzy
- Chyba - metódy obnovy
- Gramatika:
- Notačné dohovory
- Bezkontextová gramatika
- Gramatická derivácia
- Syntax vs. Lexical Analyzer
- Nevýhody používania syntaxových analyzátorov
Prečo potrebujete Syntax Analyzer?
- Skontrolujte, či je kód platný gramaticky
- Syntaktický analyzátor vám pomôže aplikovať pravidlá na kód
- Pomáha vám zaistiť, aby mala každá otváracia výstuha zodpovedajúcu záverečnú rovnováhu
- Každá deklarácia má typ a ten typ musí existovať
Dôležitá terminológia analyzátora syntaxe
Dôležité terminológie používané v procese syntaktickej analýzy:
- Veta: Veta je skupina znakov nad abecedou.
- Lexéma: Lexéma je syntaktická jednotka jazyka na najnižšej úrovni (napr. Celkom, začiatočný).
- Token: Token je iba kategória lexém.
- Kľúčové slová a vyhradené slová - Ide o identifikátor, ktorý sa používa ako pevná súčasť syntaxe výrazu . Je to vyhradené slovo, ktoré nemôžete použiť ako názov premennej alebo identifikátor.
- Šumové slová - Šumové slová sú voliteľné a vkladajú sa do výrazu na zlepšenie čitateľnosti vety.
- Poznámky - Je to veľmi dôležitá súčasť dokumentácie. Väčšinou sa zobrazuje podľa, / * * / alebo // prázdne (medzery)
- Oddeľovače - je to syntaktický prvok, ktorý označuje začiatok alebo koniec nejakej syntaktickej jednotky. Rovnako ako výrok alebo výraz „začnite“… „koniec“ alebo {}.
- Sada znakov - ASCII, Unicode
- Identifikátory - Jedná sa o obmedzenia dĺžky, ktoré vám pomôžu znížiť čitateľnosť vety.
- Symboly operátora - + a - vykonávajú dve základné aritmetické operácie.
- Syntaktické prvky jazyka
Prečo potrebujeme analýzu?
Analýza tiež skontroluje, či je vstupný reťazec správne tvarovaný, a ak nie, odmietnite ho.
Analyzátor pri návrhu kompilátora vykonáva dôležité úlohy:
- Pomáha vám odhaliť všetky typy chýb syntaxe
- Nájdite pozíciu, v ktorej sa vyskytla chyba
- Jasný a presný popis chyby.
- Obnova po chybe pokračuje a v kóde nájdete ďalšie chyby.
- Nemalo by to mať vplyv na kompiláciu „správnych“ programov.
- Analýza musí odmietnuť neplatné texty hlásením syntaktických chýb
Techniky syntaktickej analýzy
Techniky analýzy sú rozdelené do dvoch rôznych skupín:
- Analýza zhora nadol,
- Analýza zdola nahor
Analýza zhora nadol:
Pri analýze zhora nadol sa syntaktická analýza stromu začína od koreňa a potom pokračuje smerom k listom.
Dva typy analýzy zhora nadol sú:
- Prediktívna analýza:
Prediktívna analýza dokáže predpovedať, ktorá produkcia by sa mala použiť na nahradenie konkrétneho vstupného reťazca. Prediktívny syntaktický analyzátor používa výhľadový bod, ktorý ukazuje na ďalšie vstupné symboly. Spätné sledovanie nie je problém s touto technikou analýzy. Je známy ako analyzátor LL (1)
- Rekurzívna analýza zostupu:
Táto technika syntaktickej analýzy rekurzívne analyzuje vstup na vytvorenie prázového stromu. Skladá sa z niekoľkých malých funkcií, jedna pre každú terminál v gramatike.
Analýza zdola nahor:
Pri analýze zdola nahor v dizajne kompilátora začína konštrukcia syntaktického stromu s dovolenkou a potom sa spracuje smerom k jej koreňu. Nazýva sa to aj syntaktická analýza znižujúca posun. Tento typ syntaktickej analýzy v dizajne kompilátora sa vytvára pomocou niektorých softvérových nástrojov.
Chyba - metódy obnovy
Bežné chyby, ktoré sa vyskytujú pri analýze v systémovom softvéri
- Lexikálny : Názov nesprávne zadaného identifikátora
- Syntaktické : nevyvážená zátvorka alebo chýbajúci bodkočiarka
- Sémantické : nekompatibilné priradenie hodnoty
- Logické : Nekonečná slučka a nedosiahnuteľný kód
Analyzátor by mal byť schopný detekovať a hlásiť všetky chyby nájdené v programe. Takže kedykoľvek sa vyskytla chyba, syntaktický analyzátor. Malo by to byť schopné zvládnuť a pokračovať v analýze zvyšného vstupu. Program môže mať v rôznych fázach procesu kompilácie nasledujúce typy chýb. V analyzátore je možné implementovať päť bežných metód obnovy chyby
Obnova režimu výpisu
- V prípade, že syntaktický analyzátor zistí chybu, pomôže vám to podniknúť nápravné kroky. To umožňuje ostatným vstupom a stavom analyzovať dopredu.
- Napríklad pridanie chýbajúceho bodkočiarky prichádza v metóde obnovenia v režime výpisu. Návrhár syntaktických analýz však musí byť pri vykonávaní týchto zmien opatrný, pretože jedna nesprávna korekcia môže viesť k nekonečnej slučke.
Obnova v panickom režime
- V prípade, že syntaktický analyzátor zistí chybu, tento režim ignoruje zvyšok príkazu a nespracováva vstup z chybného vstupu do oddeľovača, ako je bodkočiarka. Toto je jednoduchá metóda obnovenia chyby.
- V tomto type metódy obnovy syntaktický analyzátor postupne odmieta vstupné symboly, kým sa nenájde jedna určená skupina synchronizačných tokenov. Synchronizačné tokeny zvyčajne používajú oddeľovače ako alebo.
Obnova na úrovni frázy:
- Kompilátor opraví program vložením alebo odstránením tokenov. To mu umožňuje pokračovať v analýze z miesta, kde bola. Vykoná korekciu na zostávajúcom vstupe. Môže nahradiť predponu zvyšného vstupu nejakým reťazcom, čo syntaktickému analyzátoru pomôže pokračovať v procese.
Produkcia chýb
- Obnova výroby po chybe rozšíri gramatiku pre jazyk, ktorý generuje chybné konštrukty. Analyzátor potom vykoná diagnostiku chýb o tomto konštrukte.
Globálna korekcia:
- Kompilátor by mal pri spracovaní nesprávneho vstupného reťazca vykonať čo najmenší počet zmien. Pri nesprávnom vstupnom reťazci a a gramatike c budú algoritmy hľadať syntaktický strom pre súvisiaci reťazec b. Rovnako ako niektoré vloženia, odstránenia a úpravy vyrobené z tokenov potrebných na transformáciu an na b sú čo najmenšie.
Gramatika:
Gramatika je súbor štrukturálnych pravidiel, ktoré popisujú jazyk. Gramatiky priraďujú štruktúre ľubovoľné vety. Tento výraz tiež označuje štúdium týchto pravidiel a tento súbor obsahuje morfológiu, fonológiu a syntax. Je schopný opísať veľa syntaxe programovacích jazykov.
Pravidlá formálnej gramatiky
- Non-terminálny symbol by sa mal objaviť vľavo od najmenej jednej produkcie
- Symbol cieľa by sa nikdy nemal zobrazovať napravo od :: = akejkoľvek produkcie
- Pravidlo je rekurzívne, ak sa v jeho RHS nachádza LHS
Notačné dohovory
Symbol notačnej konvencie možno označiť vložením prvku do hranatých zátvoriek. Je to ľubovoľná postupnosť inštancií prvku, ktorú je možné označiť uzavretím prvku do zložených zátvoriek, za ktorým nasleduje symbol hviezdičky, {…} *.
Je to výber alternatívy, ktorá môže používať symbol v rámci jednotného pravidla. V prípade potreby môže byť uzavretý zátvorkou ([,]).
Dva typy oblasti poznámkových konvencií: Terminál a Non-terminály
1. Terminály:
- Malé písmená v abecede, napríklad a, b, c,
- Symboly operátora ako +, -, * atď.
- Interpunkčné symboly, ako sú zátvorky, hash, čiarka
- 0, 1, ..., 9 číslic
- Odvážne reťazce ako id alebo if, čokoľvek, čo predstavuje jeden koncový symbol
2. Termináli:
- Veľké písmená ako A, B, C
- Názvy malých písmen: výraz alebo niektoré z nich
Bezkontextová gramatika
CFG je ľavo-rekurzívna gramatika, ktorá má aspoň jednu produkciu tohto typu. Pravidlá v bezkontextovej gramatike sú hlavne rekurzívne. Analyzátor syntaxe kontroluje, či konkrétny program spĺňa všetky pravidlá bezkontextovej gramatiky alebo nie. Ak to splní, môžu tieto analyzátory syntaxe pravidiel vytvoriť pre tento program syntaktický strom.
expression -> expression -+ termexpression -> expression - termexpression-> termterm -> term * factorterm -> expression/ factorterm -> factor factorfactor -> ( expression )factor -> id
Gramatická derivácia
Gramatická derivácia je postupnosť gramatického pravidla, ktorá transformuje začiatočný symbol na reťazec. Derivácia dokazuje, že reťazec patrí do jazyka gramatiky.
Derivácia úplne vľavo
Keď je sentenciálna forma vstupu skenovaná a nahradená v poradí zľava doprava, je známa ako derivácia úplne zľava. Sentenciálny formulár, ktorý je odvodený deriváciou úplne zľava, sa nazýva ľavostranný formulár.
Odvodenie úplne vpravo
Skenovanie derivácie úplne vpravo a nahradenie vstupu výrobnými pravidlami, sprava doľava, postupnosť. Je známa ako derivácia úplne vpravo. Senzitívna forma, ktorá je odvodená od derivácie úplne vpravo, sa nazýva esenciálna forma.
Syntax vs. Lexical Analyzer
|
Syntax Analyzer |
Lexikálny analyzátor |
|
Analyzátor syntaxe sa zaoberá hlavne rekurzívnymi konštruktmi jazyka. |
Lexikálny analyzátor uľahčuje úlohu syntaxového analyzátora. |
|
Analyzátor syntaxe pracuje na tokenoch v zdrojovom programe, aby rozpoznal zmysluplné štruktúry v programovacom jazyku. |
Lexikálny analyzátor rozpozná token v zdrojovom programe. |
|
Prijíma vstupy vo forme tokenov od lexikálnych analyzátorov. |
Zodpovedá za platnosť tokenu dodaného spoločnosťou analyzátor syntaxe |
Nevýhody používania syntaxových analyzátorov
- Nikdy neurčí, či je token platný alebo nie
- Nie vám pomôže zistiť, či je operácia vykonaná na type tokenu platná alebo nie
- Pred použitím sa nemôžete rozhodnúť, že je token deklarovaný a inicializovaný
Zhrnutie
- Syntaxová analýza je druhou fázou procesu návrhu kompilátora, ktorá nasleduje po lexikálnej analýze
- Syntaktický analyzátor vám pomôže aplikovať pravidlá na kód
- Veta, Lexéma, Token, Kľúčové slová a vyhradené slová, Šumové slová, Komentáre, Oddeľovače, Znaková sada, Identifikátory sú niektoré dôležité výrazy používané pri syntaktickej analýze v konštrukcii prekladača
- Parse skontroluje, či je vstupný reťazec správne tvarovaný, a ak nie, odmietnite ho
- Techniky analýzy sú rozdelené do dvoch rôznych skupín: analýza zhora nadol, analýza zdola nahor
- Lexikální, syntaktické, sémantické a logické sú niektoré bežné chyby, ktoré sa vyskytnú počas metódy syntaktickej analýzy
- Gramatika je súbor štrukturálnych pravidiel, ktoré popisujú jazyk
- Symbol notačnej konvencie možno označiť vložením prvku do hranatých zátvoriek
- CFG je ľavo-rekurzívna gramatika, ktorá má aspoň jednu produkciu tohto typu
- Gramatická derivácia je postupnosť gramatického pravidla, ktorá transformuje začiatočný symbol na reťazec
- Analyzátor syntaxe sa zaoberá hlavne rekurzívnymi konštruktmi jazyka, zatiaľ čo lexikálny analyzátor uľahčuje úlohu syntaktického analyzátora v DBMS
- Nevýhodou metódy Syntax analyzer je, že nikdy neurčí, či je token platný alebo nie