Syntaksianalyysi: Kääntäjän ylhäältä alas ja alhaalta ylös jäsennystyypit

Syntaksianalyysi kääntäjäsuunnitteluprosessissa tulee leksisen analyysivaiheen jälkeen. Se tunnetaan myös jäsennyspuuna tai syntaksipuuna. Jäsennyspuu on kehitetty kielen ennalta määritellyn kieliopin avulla. Syntaksianalysaattori tarkistaa myös, täyttääkö tietty ohjelma yhteydettömän kieliopin ehdot. Jos se tyydyttää, jäsentäjä luo sitten kyseisen lähdeohjelman jäsennyspuun. Muussa tapauksessa se näyttää virheilmoituksia.

Miksi tarvitset syntaksianalysaattoria?

• Tarkista, onko koodi kieliopillisesti oikein
• Syntaktinen analysaattori auttaa sinua soveltamaan sääntöjä koodiin
• Auttaa varmistamaan, että jokaisella avaustuella on vastaava sulkemistapa
• Jokaisella ilmoituksella on tyyppi ja että tyypin on oltava olemassa

Tärkeää syntaksianalysaattorin terminologiaa

Tärkeitä syntaksianalyysiprosessissa käytettyjä terminologioita:

• Tuomita: Lause on merkkiryhmä joidenkin aakkosten yli.

• Lekseema: Lekseema on kielen alimman tason syntaktinen yksikkö (esim. summa, alku).

• Token: Tunnus on vain lekseemiluokka.

• Avainsanat ja varatut sanat – Se on tunniste, jota käytetään lauseen syntaksin kiinteänä osana. Se on varattu sana, jota et voi käyttää muuttujan nimenä tai tunnisteena.

• Melu sanat – Melusanat ovat valinnaisia, ja ne lisätään lauseeseen parantamaan lauseen luettavuutta.

• Kommentit – Se on erittäin tärkeä osa dokumentaatiota. Useimmiten se näkyy merkinnällä /* */ tai//Tyhjä (välilyönnit)

• Erottimet – Se on syntaktinen elementti, joka merkitsee jonkin syntaktisen yksikön alkua tai loppua. Kuten lause tai ilmaus, "alkaa"…"loppuu" tai {}.

• Merkistö – ASCII, Unicode

• tunnisteet – Se on pituuden rajoitus, joka auttaa sinua vähentämään lauseen luettavuutta.

• Operator-symbolit – + ja – suorittaa kaksi aritmeettista perusoperaatiota.
• Kielen syntaktiset elementit

Miksi tarvitsemme jäsentämistä?

Jäsennys myös tarkistaa, että syötemerkkijono on hyvin muotoiltu, ja jos ei, hylkää se.

Seuraavat ovat tärkeitä tehtäviä, jotka jäsentäjä suorittaa kääntäjän suunnittelussa:

• Auttaa sinua havaitsemaan kaiken tyyppiset syntaksivirheet
• Etsi paikka, jossa virhe tapahtui
• Selkeä ja tarkka kuvaus virheestä.
• Palaa virheestä jatkaaksesi ja etsiäksesi lisää virheitä koodista.
• Ei pitäisi vaikuttaa "oikeiden" ohjelmien kääntämiseen.
• Jäsenen on hylättävä virheelliset tekstit ilmoittamalla syntaksivirheistä

Jäsennystekniikat

Jäsennystekniikat on jaettu kahteen eri ryhmään:

• Ylhäältä alas -jäsennys,
• Alhaalta ylös -jäsennys

Ylhäältä alas -jäsennys

Ylhäältä alas -jäsennyksessä jäsennyspuun rakentaminen alkaa juuresta ja etenee sitten lehtiä kohti.

Kaksi ylhäältä alas -jäsennystyyppiä ovat:

1. Ennakoiva jäsennys:

Ennustava jäsennys voi ennustaa, millä tuotannolla tietty syöttömerkkijono korvataan. Ennustava jäsentäjä käyttää ennakoivaa pistettä, joka osoittaa kohti seuraavia syötesymboleja. Peruutus ei ole ongelma tässä jäsennystekniikassa. Se tunnetaan nimellä LL(1) Parser

2. Rekursiivisen laskeutumisen jäsentäminen:

Tämä jäsennystekniikka jäsentää rekursiivisesti syötteen ja muodostaa prase-puun. Se koostuu useista pienistä funktioista, yksi kullekin kieliopin ei-terminaalille.

Alhaalta ylös -jäsennys

Kääntäjäsuunnittelun alhaalta ylös -jäsennysvaiheessa jäsennyspuun rakentaminen alkaa lehdestä ja etenee sitten juurensa kohti. Sitä kutsutaan myös shift-reduce jäsennykseksi. Tämän tyyppinen jäsentäminen kääntäjäsuunnittelussa on luotu joidenkin avulla ohjelmistotyökaluja.

Virhe – palautusmenetelmät

Yleiset virheet, joita esiintyy järjestelmäohjelmiston jäsentämisessä

• leksikaalinen: Väärin kirjoitetun tunnisteen nimi
• Syntaktinen: epätasapainoinen sulkumerkki tai puuttuva puolipiste
• Semanttinen: yhteensopimaton arvonmääritys
• looginen: ääretön silmukka eikä tavoitettavissa oleva koodi

Jäsentimen tulee pystyä havaitsemaan ja raportoimaan kaikki ohjelmassa löydetyt virheet. Joten aina kun virhe tapahtui jäsentäjä. Sen pitäisi pystyä käsittelemään sitä ja jatkamaan jäljellä olevan syötteen jäsentämistä. Ohjelmassa voi olla seuraavan tyyppisiä virheitä käännösprosessin eri vaiheissa. On olemassa viisi yleistä virheenpalautusmenetelmää, jotka voidaan toteuttaa jäsentimessä

Lausuntotilan palautus

• Jos jäsentäjä kohtaa virheen, se auttaa korjaamaan toimenpiteitä. Tämä mahdollistaa muiden syötteiden ja tilojen jäsentämisen eteenpäin.
• Esimerkiksi puuttuvan puolipisteen lisääminen tapahtuu lauseketilan palautusmenetelmässä. Jäsennyssuunnittelijan on kuitenkin oltava varovainen tehdessään näitä muutoksia, koska yksi väärä korjaus voi johtaa äärettömään silmukkaan.

Paniikkitilan palautuminen

• Jos jäsentäjä kohtaa virheen, tämä tila jättää huomioimatta muun käskyn eikä käsittele syötettä virheellisestä syötteestä erottimeen, kuten puolipisteeseen. Tämä on yksinkertainen virheenpalautusmenetelmä.
• Tämän tyyppisessä palautusmenetelmässä jäsentäjä hylkää syöttösymbolit yksitellen, kunnes löydetään yksi määrätty ryhmä synkronointitokeneita. Synkronointimerkit käyttävät yleensä erottimia, kuten tai.

Ilmaustason palautus

• Kääntäjä korjaa ohjelman lisäämällä tai poistamalla tunnuksia. Tämä mahdollistaa sen jäsentämisen siitä, missä se oli. Se suorittaa korjauksen jäljellä olevalle tulolle. Se voi korvata jäljellä olevan syötteen etuliitteen jollain merkkijonolla, mikä auttaa jäsentäjää jatkamaan prosessia.

Virhetuotanto

• Virheiden tuotannon palautus laajentaa virheelliset konstruktit luovan kielen kielioppia. Jäsentäjä suorittaa sitten virhediagnoosin kyseiselle konstruktille.

Globaali korjaus

• Kääntäjän tulisi tehdä vähemmän muutoksia kuin mahdollista, kun se käsittelee virheellistä syötemerkkijonoa. Jos syötemerkkijono a ja kielioppi c ovat virheellisiä, algoritmit etsivät jäsennyspuuta liittyvälle merkkijonolle b. Kuten jotkin lisäykset, poistot ja muokkaukset, jotka on tehty merkkien muuntamiseen b:ksi, on mahdollisimman vähän.

Kielioppi

Kielioppi on joukko rakenteellisia sääntöjä, jotka kuvaavat kieltä. Kieliopit antavat rakenteen mille tahansa lauseelle. Tämä termi viittaa myös näiden sääntöjen tutkimiseen, ja tämä tiedosto sisältää morfologian, fonologian ja syntaksin. Se pystyy kuvaamaan monia, syntaksia ohjelmointikielet.

Lomakekieliopin säännöt

• Muun kuin terminaalin symbolin tulee näkyä vähintään yhden tuotannon vasemmalla puolella
• Tavoitesymbolia ei saa koskaan näyttää minkään tuotannon::=:n oikealla puolella
• Sääntö on rekursiivinen, jos LHS näkyy sen RHS:ssä

Merkintäsäännöt

Merkintätapasymboli voidaan osoittaa liittämällä elementti hakasulkeisiin. Se on mielivaltainen elementin esiintymien sarja, joka voidaan ilmaista merkitsemällä elementti aaltosulkeisiin ja sen jälkeen tähtimerkkiin, { … }*.

Se on vaihtoehdon valinta, joka voi käyttää symbolia yksittäisessä säännössä. Se voidaan tarvittaessa sulkea suluilla ([,] ).

Kahden tyyppisiä merkintäkäytäntöjä ovat terminaalit ja muut kuin päätelaitteet

1. Päätteet:

• Pienet kirjaimet aakkosissa, kuten a, b, c,
• Operator-symbolit, kuten +,-, * jne.
• Välimerkit, kuten sulut, hash, pilkku
• 0, 1, …, 9 numeroa
• Lihavoidut merkkijonot, kuten id tai jos, mikä tahansa, joka edustaa yhtä päätesymbolia

2. Ei-päätelaitteet:

• Isot kirjaimet, kuten A, B, C
• Pienet kursiiviset nimet: lauseke tai jokin

Konteksti Ilmainen kielioppi

CFG on vasemmanpuoleinen rekursiivinen kielioppi, jossa on vähintään yksi tämän tyyppinen tuotanto. Kontekstittoman kieliopin säännöt ovat pääosin rekursiivisia. Syntaksianalysaattori tarkistaa, täyttääkö tietty ohjelma kaikki kontekstittoman kieliopin säännöt vai ei. Jos se täyttää, nämä sääntöjen syntaksianalysaattorit voivat luoda jäsennyspuun kyseiselle ohjelmalle.

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

Kieliopin johtaminen

Kieliopin johtaminen on kielioppisäännön sarja, joka muuntaa aloitussymbolin merkkijonoksi. Johdannainen todistaa, että merkkijono kuuluu kieliopin kieleen.

Vasemmanpuoleisin johdannainen

Kun syötteen lausemuoto skannataan ja korvataan järjestyksessä vasemmalta oikealle, sitä kutsutaan vasemmanpuoleisimmaksi johtamiseksi. Vasemmanpuoleisella johdannaisella johdettua lausemuotoa kutsutaan vasemmanpuoleiseksi lausemuodoksi.

Oikeanpuoleisin Johdannainen

Oikeanpuoleisin johdannainen skannaa ja korvaa syöte tuotantosäännöillä, oikealta vasemmalle, sarja. Se tunnetaan oikeanpuoleisena johdannaisena. Oikeanpuoleisesta johdannaisesta johdettu lausemuoto tunnetaan oikeanpuoleisena lausemuotona.

Syntaksi vs. Lexical Analyzer

Syntaksianalysaattori	Leksinen analysaattori
Syntaksianalysaattori käsittelee pääasiassa kielen rekursiivisia rakenteita.	Leksikaalinen analysaattori helpottaa syntaksianalysaattorin työtä.
Syntaksianalysaattori toimii lähdeohjelman tunnisteilla tunnistaakseen ohjelmointikielen merkitykselliset rakenteet.	Leksikaalinen analysaattori tunnistaa lähdeohjelman tunnuksen.
Se vastaanottaa syötteitä sanakkeiden muodossa leksikaalisista analysaattoreista.	Se on vastuussa toimittaman tunnuksen voimassaolosta syntaksianalysaattori

Syntaksianalysaattoreiden käytön haitat

• Se ei koskaan määritä, onko tunnus kelvollinen vai ei
• Ei auttaa sinua määrittämään, onko tunnukselle suoritettu toiminto kelvollinen vai ei
• Et voi päättää, että tunnus ilmoitetaan ja alustetaan ennen kuin sitä käytetään

Yhteenveto

• Syntaksianalyysi on kääntäjän suunnitteluprosessin toinen vaihe, joka tulee leksikaalisen analyysin jälkeen
• Syntaktinen analysaattori auttaa sinua soveltamaan sääntöjä koodiin
• Lause, Lekseema, Token, Avainsanat ja varatut sanat, Kohinasanat, Kommentit, Erottimet, Merkistö, Tunnisteet ovat joitakin tärkeitä termejä, joita käytetään kääntäjän rakentamisen syntaksianalyysissä
• Jäsennys tarkistaa, että syötemerkkijono on hyvin muotoiltu, ja jos ei, hylkää se
• Jäsennystekniikat on jaettu kahteen eri ryhmään: Ylhäältä alas -jäsennys, Alhaalta ylös -jäsennys
• Leksiset, syntaktiset, semanttiset ja loogiset ovat joitain yleisiä virheitä, joita esiintyy jäsennysmenetelmän aikana
• Kielioppi on joukko rakenteellisia sääntöjä, jotka kuvaavat kieltä
• Merkintätapasymboli voidaan osoittaa liittämällä elementti hakasulkeisiin
• CFG on vasemmanpuoleinen rekursiivinen kielioppi, jossa on vähintään yksi tämän tyyppinen tuotanto
• Kieliopin johtaminen on kielioppisäännön sarja, joka muuntaa aloitussymbolin merkkijonoksi
• Syntaksianalysaattori käsittelee pääasiassa kielen rekursiivisia rakenteita, kun taas leksikaalinen analysaattori helpottaa syntaksianalysaattorin tehtävää DBMS
• Syntax-analysaattorimenetelmän haittapuoli on, että se ei koskaan määritä, onko merkki kelvollinen vai ei