Süntaksi analüüs: kompilaatori ülalt alla ja alt üles sõelumise tüübid
Mis on süntaksianalüüs?
Süntaksi analüüs on kompilaatori kavandamise protsessi teine faas, mille käigus kontrollitakse antud sisendstringi formaalse grammatika reeglite ja struktuuri kinnitamiseks. See analüüsib süntaktilist struktuuri ja kontrollib, kas antud sisend on programmeerimiskeele õiges süntaksis või mitte.
Süntaksianalüüs kompilaatori kujundamise protsessis tuleb pärast leksikaalanalüüsi etappi. Seda tuntakse ka kui parsipuu või süntaksipuu. Parsipuu töötatakse välja eelnevalt määratletud keele grammatika abil. Süntaksianalüsaator kontrollib ka seda, kas antud programm vastab kontekstivaba grammatika reeglitele. Kui see rahuldab, loob parser selle lähteprogrammi sõelumispuu. Vastasel juhul kuvab see veateateid.
Miks vajate süntaksianalüsaatorit?
- Kontrollige, kas kood on grammatiliselt õige
- Süntaktiline analüsaator aitab teil koodile reegleid rakendada
- Aitab teil veenduda, et igal avamisklambril on vastav sulgemistasakaal
- Igal deklaratsioonil on tüüp ja see tüüp peab olema olemas
Tähtis süntaksianalüsaatori terminoloogia
Olulised süntaksianalüüsi protsessis kasutatavad terminoloogiad:
- Lause: Lause on märkide rühm mõne tähestiku kohal.
- Lekseem: Lekseem on keele madalaima taseme süntaktiline üksus (nt kogusumma, algus).
- Märk: Märk on vaid lekseemide kategooria.
- Märksõnad ja reserveeritud sõnad – See on identifikaator, mida kasutatakse avalduse süntaksi fikseeritud osana. See on reserveeritud sõna, mida ei saa kasutada muutuja nime ega identifikaatorina.
- Mürasõnad – Mürasõnad on valikulised, mis lisatakse lausesse, et parandada lause loetavust.
- Kommentaarid – See on dokumentatsiooni väga oluline osa. Enamasti kuvatakse /* */ või//Tühi (tühikud)
- Piiritlejad – See on süntaktiline element, mis tähistab mõne süntaktilise üksuse algust või lõppu. Nagu väide või väljend, "algus"…"lõpp" või {}.
- Tähemärkide komplekt - ASCII, Unicode
- Identifikaatorid – See on pikkuse piirangud, mis aitavad teil lause loetavust vähendada.
- Operator sümboleid – + ja – sooritavad kaks aritmeetilist põhitehet.
- Keele süntaktilised elemendid
Miks me vajame parsimist?
Parsimine kontrollib ka seda, kas sisendstring on korralikult vormistatud, ja kui mitte, lükkab selle tagasi.
Järgmised on olulised ülesanded, mida parser kompilaatori kujundamisel täidab:
- Aitab tuvastada igat tüüpi süntaksivigu
- Leidke asukoht, kus viga ilmnes
- Vea selge ja täpne kirjeldus.
- Jätkamiseks ja koodist täiendavate vigade leidmiseks taastage veast.
- Ei tohiks mõjutada "õigete" programmide koostamist.
- Parsimine peab kehtetud tekstid tagasi lükkama, teatades süntaksivigadest
Parsimise tehnikad
Parsimise tehnikad jagunevad kahte erinevasse rühma:
- Ülevalt alla sõelumine,
- Alt-üles sõelumine
Ülevalt alla sõelumine
Ülalt-alla sõelumisel algab parsipuu ehitamine juurest ja liigub seejärel lehtede poole.
Ülevalt alla sõelumise kahte tüüpi on:
- Ennustav sõelumine:
Ennustav sõelumine võib ennustada, millist tootmist tuleks konkreetse sisendstringi asendamiseks kasutada. Ennustav parser kasutab ettevaatepunkti, mis osutab järgmistele sisendsümbolitele. Selle sõelumistehnika puhul ei ole tagasiminek probleem. Seda tuntakse kui LL(1) Parser
- Rekursiivse laskumise parsimine:
See sõelumistehnika parsib rekursiivselt sisendit prase puu loomiseks. See koosneb mitmest väikesest funktsioonist, üks iga grammatika mitteterminali jaoks.
Alt-üles sõelumine
Kompilaatori disaini alt üles sõelumisel algab parsipuu ehitamine lahkumisest ja seejärel liigub see juure poole. Seda nimetatakse ka nihke-vähendamise parsimiseks. Seda tüüpi parsimine kompilaatori kujunduses luuakse mõne kasutamise abil tarkvaravahendid.
Viga – taastamismeetodid
Levinud vead, mis esinevad süsteemitarkvara parsimisel
- Leksikaalne: valesti sisestatud identifikaatori nimi
- Süntaktiline: tasakaalustamata sulg või puuduv semikoolon
- Semantiline: sobimatu väärtuse määramine
- loogiline: lõpmatu silmus ja kättesaamatu kood
Parser peaks suutma tuvastada kõik programmis leitud vead ja sellest teatama. Seega, kui ilmnes viga, parser. See peaks sellega hakkama saama ja jätkama ülejäänud sisendi sõelumist. Programmil võib kompileerimisprotsessi erinevates etappides esineda järgmist tüüpi vigu. Parseris saab rakendada viit levinud vea taastamise meetodit
Väljavõtte režiimi taastamine
- Kui parseris ilmneb tõrge, aitab see teil teha parandusmeetmeid. See võimaldab ülejäänud sisendeid ja olekuid edasi sõeluda.
- Näiteks puuduva semikooloni lisamine toimub avalduse režiimi taastamise meetodil. Kuid parsi kujundaja peab olema nende muudatuste tegemisel ettevaatlik, kuna üks vale parandus võib viia lõputu tsüklini.
Paanikarežiimi taastamine
- Kui parseris ilmneb tõrge, ignoreerib see režiim ülejäänud lauset ega töötle sisendit vigasest sisendist eraldajani, nagu semikoolon. See on lihtne vea taastamise meetod.
- Seda tüüpi taastamismeetodi puhul lükkab parser sisendsümbolid ükshaaval tagasi, kuni leitakse üks määratud sünkroonimislubade rühm. Sünkroonimismärgid kasutavad tavaliselt eraldajaid nagu või.
Fraasitaseme taastamine
- Kompilaator parandab programmi märke sisestades või kustutades. See võimaldab sellel sõeluda sealt, kus see oli. See korrigeerib ülejäänud sisendit. See võib asendada ülejäänud sisendi eesliite mõne stringiga, mis aitab parseril protsessi jätkata.
Viga lavastused
- Vigade tootmise taastamine laiendab keele grammatikat, mis genereerib vigased konstruktsioonid. Seejärel teostab parser selle konstruktsiooni veadiagnostika.
Globaalne parandus
- Kompilaator peaks vale sisendstringi töötlemisel tegema võimalikult vähe muudatusi. Vale sisendstringi a ja grammatika c korral otsivad algoritmid seotud stringi b jaoks parsipuud. Nagu mõned sisestused, kustutamised ja žetoonidest tehtud muudatused, mida on vaja b-ks muutmiseks, on nii vähe kui võimalik.
Grammatika
Grammatika on struktuurireeglite kogum, mis kirjeldavad keelt. Grammatika määrab igale lausele struktuuri. See termin viitab ka nende reeglite uurimisele ja see fail hõlmab morfoloogiat, fonoloogiat ja süntaksit. See on võimeline kirjeldama paljusid süntaksist programmeerimiskeeled.
Vormi grammatika reeglid
- Mitteterminali sümbol peaks olema vähemalt ühest toodangust vasakul
- Eesmärgi sümbolit ei tohi kunagi kuvada ühegi toodangu ::= paremal pool
- Reegel on rekursiivne, kui selle RHS-is on LHS
Märgistuskonventsioonid
Märgistuskokkulepete sümbolit võib näidata, lisades elemendi nurksulgudesse. See on suvaline elemendi esinemisjuhtude jada, mida saab näidata, lisades elemendi sulgudesse, millele järgneb tärni sümbol { … }*.
See on alternatiiv, mis võib kasutada sümbolit ühes reeglis. Vajadusel võib selle lisada sulgudesse ([,] ).
Kahte tüüpi tähistuskokkulepete ala terminal ja mitteterminal
1. Terminalid:
- Tähestiku väikesed tähed, näiteks a, b, c,
- Operator sümbolid nagu +,-, * jne.
- Kirjavahemärgid, näiteks sulud, räsi, koma
- 0, 1, …, 9 numbrit
- Paksus kirjas stringid, nagu id või kui, mis tahes, mis tähistab ühte terminali sümbolit
2. Mitteterminalid:
- Suured tähed nagu A, B, C
- Väiketähelised kaldkirjas nimed: väljend või mõni
Kontekst Tasuta grammatika
CFG on vasakpoolne rekursiivne grammatika, millel on vähemalt üks seda tüüpi produktsioon. Kontekstivaba grammatika reeglid on peamiselt rekursiivsed. Süntaksianalüsaator kontrollib, kas konkreetne programm vastab kõigile kontekstivaba grammatika reeglitele või mitte. Kui see vastab, võivad need reeglid süntaksianalüsaatorid luua selle programmi jaoks sõelumispuu.
expression -> expression -+ term expression -> expression – term expression-> term term -> term * factor term -> expression/ factor term -> factor factor factor -> ( expression ) factor -> id
Grammatika tuletus
Grammatikatuletus on grammatikareeglite jada, mis teisendab algussümboli stringiks. Tuletus tõestab, et string kuulub grammatika keelde.
Vasakpoolseim tuletis
Kui sisendi sentsiaalne vorm skannitakse ja asendatakse vasakult paremale järjestuses, nimetatakse seda vasakpoolseimaks tuletamiseks. Vasakpoolseima tuletise abil tuletatud lausevormi nimetatakse vasakpoolseks lausevormiks.
Parempoolne tuletis
Parempoolseim tuletus skannib ja asenda sisend tootmisreeglitega, paremalt vasakule, järjestus. Seda tuntakse parempoolseima tuletusena. Parempoolsemast tuletusest tuletatud lausevormi nimetatakse parempoolseks lausevormiks.
Süntaks vs leksikaalanalüsaator
Süntaksianalüsaator | Leksikaalne analüsaator |
---|---|
Süntaksianalüsaator tegeleb peamiselt keele rekursiivsete konstruktsioonidega. | Leksikaalanalüsaator hõlbustab süntaksianalüsaatori ülesannet. |
Süntaksianalüsaator töötab lähteprogrammis olevate märkide peal, et tuvastada programmeerimiskeeles tähendusrikkaid struktuure. | Leksikaalne analüsaator tunneb ära lähteprogrammis oleva märgi. |
See saab leksikaalanalüsaatoritelt sisendeid märkide kujul. | Ta vastutab poolt tarnitud märgi kehtivuse eest
süntaksi analüsaator |
Süntaksianalüsaatorite kasutamise puudused
- See ei määra kunagi, kas märk on kehtiv või mitte
- Not aitab teil kindlaks teha, kas loatüübiga tehtud toiming on kehtiv või mitte
- Te ei saa otsustada, et märk deklareeritakse ja initsialiseeritakse enne selle kasutamist
kokkuvõte
- Süntaksianalüüs on kompilaatori kavandamise protsessi teine faas, mis tuleb pärast leksikaalset analüüsi
- Süntaktiline analüsaator aitab teil koodile reegleid rakendada
- Lause, lekseem, märk, märksõnad ja reserveeritud sõnad, mürasõnad, kommentaarid, eraldajad, märgikomplekt, identifikaatorid on mõned olulised terminid, mida kasutatakse kompilaatori koostamise süntaksianalüüsis
- Parse kontrollib, kas sisendstring on korralikult vormistatud, ja kui mitte, lükkab selle tagasi
- Parsimise tehnikad on jagatud kahte erinevasse rühma: ülalt-alla sõelumine, alt-üles sõelumine
- Leksikaalsed, süntaktilised, semantilised ja loogilised on mõned levinumad vead, mis esinevad sõelumismeetodil
- Grammatika on struktuurireeglite kogum, mis kirjeldavad keelt
- Märgistuskokkulepete sümbolit võib näidata, lisades elemendi nurksulgudesse
- CFG on vasakpoolne rekursiivne grammatika, millel on vähemalt üks seda tüüpi produktsioon
- Grammatikatuletus on grammatikareeglite jada, mis teisendab algussümboli stringiks
- Süntaksianalüsaator tegeleb peamiselt keele rekursiivsete konstruktsioonidega, leksikaalanalüsaator aga hõlbustab süntaksianalüsaatori ülesannet DB-süsteemid
- Süntaksianalüsaatori meetodi puuduseks on see, et see ei määra kunagi, kas märk on kehtiv või mitte