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.

Süntaksi analüüs
Süntaksianalüsaatori protsess

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

Parsimine kontrollib ka seda, kas sisendstring on korralikult vormistatud, ja kui mitte, lükkab selle tagasi.

Parsimine

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:

  1. 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

  1. 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