Analiza sintakse: Vrste raščlanjivanja kompilatora odozgo prema dolje i odozdo prema gore
Što je analiza sintakse?
Analiza sintakse je druga faza procesa dizajna prevoditelja u kojoj se dani ulazni niz provjerava radi potvrde pravila i strukture formalne gramatike. Analizira sintaktičku strukturu i provjerava je li dani unos u ispravnoj sintaksi programskog jezika ili ne.
Analiza sintakse u procesu dizajna prevoditelja dolazi nakon faze leksičke analize. Također je poznato kao Stablo sintakse ili Stablo sintakse. Stablo raščlanjivanja razvijeno je uz pomoć unaprijed definirane gramatike jezika. Analizator sintakse također provjerava ispunjava li dati program pravila koja implicira kontekstno-slobodna gramatika. Ako zadovoljava, raščlanjivač zatim stvara stablo raščlanjivanja tog izvornog programa. U suprotnom će prikazati poruke o pogrešci.

Zašto vam je potreban analizator sintakse?
- Provjerite je li kod gramatički valjan
- Sintaktički analizator pomaže vam da primijenite pravila na kôd
- Pomaže vam da provjerite ima li svaka otvarajuća zagrada odgovarajuću završnu bilancu
- Svaka deklaracija ima tip i taj tip mora postojati
Važna terminologija analizatora sintakse
Važne terminologije koje se koriste u procesu analize sintakse:
- Rečenica: Rečenica je skupina znakova iznad neke abecede.
- Leksem: Leksem je sintaktička jedinica najniže razine jezika (npr. ukupno, početak).
- Token: Leksem je samo kategorija leksema.
- Ključne riječi i rezervirane riječi – To je identifikator koji se koristi kao fiksni dio sintakse izjave. To je rezervirana riječ koju ne možete koristiti kao naziv varijable ili identifikator.
- Bučne riječi – Riječi smetnji nisu obavezne i umeću se u izjavu kako bi se poboljšala čitljivost rečenice.
- Komentari – To je vrlo važan dio dokumentacije. Uglavnom se prikazuje kao /* */ ili//prazno (razmaci)
- Razdjelnici – To je sintaktički element koji označava početak ili kraj neke sintaktičke jedinice. Poput izjave ili izraza, “početak”…”kraj” ili {}.
- Skup znakova – ASCII, Unicode
- identifikatori – To je ograničenje duljine koje vam pomaže smanjiti čitljivost rečenice.
- Operator simboli – + i – izvode dvije osnovne aritmetičke operacije.
- Sintaktički elementi jezika
Zašto nam je potrebna analiza?
Analiza također provjerava je li ulazni niz dobro oblikovan, a ako nije, odbacuje ga.
Slijede važni zadaci koje obavlja parser u dizajnu prevoditelja:
- Pomaže vam otkriti sve vrste sintaktičkih pogrešaka
- Pronađite poziciju na kojoj je došlo do pogreške
- Jasan i točan opis greške.
- Oporavak od pogreške za nastavak i pronalaženje daljnjih pogrešaka u kodu.
- Ne bi trebalo utjecati na kompilaciju "ispravnih" programa.
- Analiza mora odbaciti nevažeće tekstove prijavom sintaktičkih pogrešaka
Tehnike raščlanjivanja
Tehnike raščlanjivanja podijeljene su u dvije različite skupine:
- Raščlanjivanje odozgo prema dolje,
- Raščlanjivanje odozdo prema gore
Raščlanjivanje odozgo prema dolje
U konstrukciji raščlanjivanja od vrha prema dolje, stablo raščlanjivanja počinje od korijena i zatim se nastavlja prema listovima.
Dvije su vrste raščlanjivanja odozgo prema dolje:
- Prediktivno analiziranje:
Prediktivno analiziranje može predvidjeti koja bi se proizvodnja trebala koristiti za zamjenu određenog ulaznog niza. Prediktivni parser koristi točku unaprijed, koja pokazuje prema sljedećim ulaznim simbolima. Vraćanje unatrag nije problem s ovom tehnikom raščlanjivanja. Poznat je kao LL(1) parser
- Raščlanjivanje rekurzivnog spuštanja:
Ova tehnika raščlanjivanja rekurzivno raščlanjuje ulaz kako bi se napravilo prazno stablo. Sastoji se od nekoliko malih funkcija, po jedna za svaki neterminal u gramatici.
Raščlanjivanje odozdo prema gore
U raščlanjivanju odozdo prema gore u dizajnu prevoditelja, konstrukcija stabla raščlanjivanja počinje odlaskom, a zatim se obrađuje prema korijenu. Također se naziva i shift-reduce parsiranje. Ova vrsta raščlanjivanja u dizajnu prevoditelja stvorena je uz pomoć nekih programski alati.
Pogreška – Metode oporavka
Uobičajene pogreške koje se javljaju prilikom analize u softveru sustava
- leksički: Naziv netočno upisanog identifikatora
- Sintaktički: neuravnotežena zagrada ili nedostaje točka-zarez
- Semantički: nekompatibilna dodjela vrijednosti
- logičan: Beskonačna petlja i nedostupan kod
Parser bi trebao moći otkriti i prijaviti svaku pogrešku pronađenu u programu. Dakle, kad god se dogodi greška, parser. Trebao bi to moći obraditi i nastaviti analizirati preostali unos. Program može imati sljedeće vrste grešaka u različitim fazama procesa kompilacije. Postoji pet uobičajenih metoda za oporavak od pogreške koje se mogu implementirati u parser
Oporavak načina izjave
- U slučaju kada parser naiđe na pogrešku, pomaže vam da poduzmete korektivne korake. Ovo omogućuje raščlanjivanje ostatka unosa i stanja unaprijed.
- Na primjer, dodavanje točke sa zarezom koji nedostaje dolazi u načinu oporavka izraza. Međutim, dizajneri raščlambe moraju biti oprezni dok unose ove promjene jer jedna pogrešna korekcija može dovesti do beskonačne petlje.
Panic-Mode oporavak
- U slučaju kada parser naiđe na pogrešku, ovaj način rada zanemaruje ostatak naredbe i ne obrađuje unos od pogrešnog unosa do graničnika, kao što je točka-zarez. Ovo je jednostavna metoda ispravljanja pogreške.
- U ovoj vrsti metode oporavka, parser odbija ulazne simbole jedan po jedan dok se ne pronađe jedna određena skupina sinkronizirajućih tokena. Tokeni za sinkronizaciju općenito koriste razdjelnike poput ili.
Oporavak na razini fraze
- Kompajler ispravlja program umetanjem ili brisanjem tokena. To mu omogućuje da nastavi s analizom od mjesta gdje je bio. Izvodi korekciju na preostalom ulazu. Može zamijeniti prefiks preostalog unosa nekim nizom, što pomaže parseru da nastavi proces.
Error Productions
- Oporavak proizvodnje pogreške proširuje gramatiku za jezik koji generira pogrešne konstrukcije. Parser zatim izvodi dijagnostiku pogreške o toj konstrukciji.
Globalna korekcija
- Prevodilac bi trebao napraviti što manji broj promjena dok obrađuje netočan ulazni niz. S obzirom na pogrešan ulazni niz a i gramatiku c, algoritmi će tražiti stablo analize za povezani niz b. Poput nekih umetanja, brisanja i izmjena tokena potrebnih za transformaciju an u b je što je moguće manje.
Gramatika
Gramatika je skup strukturnih pravila koja opisuju jezik. Gramatike dodjeljuju strukturu svakoj rečenici. Ovaj se izraz također odnosi na proučavanje ovih pravila, a ova datoteka uključuje morfologiju, fonologiju i sintaksu. Sposoban je opisati mnoge sintakse programski jezici.
Pravila gramatike oblika
- Simbol koji nije terminal trebao bi se pojaviti lijevo od najmanje jedne proizvodnje
- Simbol cilja nikada ne bi trebao biti prikazan desno od::= bilo koje proizvodnje
- Pravilo je rekurzivno ako se LHS pojavljuje u njegovom RHS-u
Notacijske konvencije
Konvencijski simbol označavanja može se označiti zatvaranjem elementa u uglate zagrade. To je proizvoljan niz instanci elementa koji se može naznačiti stavljanjem elementa u zagrade iza kojih slijedi simbol zvjezdice, { … }*.
To je izbor alternative koja može koristiti simbol unutar jednog pravila. Može se staviti u zagradu ([,] ) kada je potrebno.
Dvije vrste notacijskih konvencija u području terminala i neterminala
1. Terminali:
- Mala slova u abecedi kao što su a, b, c,
- Operaili simbole kao što su +,-, * itd.
- Interpunkcijski simboli kao što su zagrade, hash, zarez
- 0, 1, …, 9 znamenki
- Podebljani nizovi kao što su id ili if, bilo što što predstavlja jedan simbol terminala
2.Neterminali:
- Velika slova kao što su A, B, C
- Imena u kurzivu malim slovima: izraz ili neki
Gramatika bez konteksta
CFG je lijevo-rekurzivna gramatika koja ima barem jednu proizvodnju tog tipa. Pravila u gramatici bez konteksta su uglavnom rekurzivna. Analizator sintakse provjerava zadovoljava li određeni program sva pravila gramatike bez konteksta ili ne. Ako se ispuni, ovi analizatori sintakse pravila mogu stvoriti stablo analize za taj program.
expression -> expression -+ term expression -> expression – term expression-> term term -> term * factor term -> expression/ factor term -> factor factor factor -> ( expression ) factor -> id
Gramatička derivacija
Gramatička derivacija je niz gramatičkih pravila koja transformiraju početni simbol u niz. Izvođenje dokazuje da niz pripada jeziku gramatike.
Krajnja lijeva derivacija
Kada se rečenični oblik unosa skenira i zamijeni u nizu slijeva nadesno, to je poznato kao krajnje lijevo izvođenje. Rečenični oblik koji je izveden krajnjom lijevom derivacijom naziva se lijevorečenički oblik.
Krajnja desna derivacija
Skeniranje krajnje desne derivacije i zamjena unosa produkcijskim pravilima, s desna na lijevo, slijedom. Poznato je kao krajnja desna derivacija. Rečenički oblik koji je izveden iz krajnje desne derivacije poznat je kao desnorečenički oblik.
Sintaksa nasuprot leksičkom analizatoru
Analizator sintakse | Leksički analizator |
---|---|
Analizator sintakse uglavnom se bavi rekurzivnim konstruktima jezika. | Leksički analizator olakšava zadatak analizatoru sintakse. |
Analizator sintakse radi na tokenima u izvornom programu kako bi prepoznao smislene strukture u programskom jeziku. | Leksički analizator prepoznaje token u izvornom programu. |
Prima ulazne podatke, u obliku tokena, od leksičkih analizatora. | Odgovoran je za valjanost tokena koji isporučuje
analizator sintakse |
Nedostaci korištenja analizatora sintakse
- Nikada neće utvrditi je li token valjan ili ne
- Not vam pomaže da odredite je li operacija izvedena na vrsti tokena važeća ili ne
- Ne možete odlučiti da je token deklariran i inicijaliziran prije nego se počne koristiti
rezime
- Analiza sintakse je druga faza procesa dizajna prevoditelja koja dolazi nakon leksičke analize
- Sintaktički analizator pomaže vam da primijenite pravila na kôd
- Rečenica, leksem, token, ključne riječi i rezervirane riječi, riječi smetnje, komentari, razdjelnici, skup znakova, identifikatori neki su od važnih pojmova koji se koriste u analizi sintakse u konstrukciji prevoditelja
- Parse provjerava je li ulazni niz dobro oblikovan, a ako nije, odbacuje ga
- Tehnike raščlanjivanja podijeljene su u dvije različite skupine: raščlanjivanje odozgo prema dolje, raščlanjivanje odozdo prema gore
- Leksičke, sintaktičke, semantičke i logičke neke su uobičajene pogreške koje se javljaju tijekom metode raščlambe
- Gramatika je skup strukturnih pravila koja opisuju jezik
- Konvencijski simbol označavanja može se označiti zatvaranjem elementa u uglate zagrade
- CFG je lijevo-rekurzivna gramatika koja ima barem jednu proizvodnju tog tipa
- Gramatička derivacija je niz gramatičkih pravila koja transformiraju početni simbol u niz
- Analizator sintakse uglavnom se bavi rekurzivnim konstruktima jezika, dok leksički analizator olakšava zadatak analizatoru sintakse u DBMS
- Nedostatak metode analizatora sintakse je taj što nikada neće utvrditi je li token valjan ili ne