Software is all about logic. Ohjelmointi on kerännyt mainetta Matikkaa ja hulluja yhtälöitä painavana Alana. Ja tietojenkäsittelytiede näyttää olevan tämän väärinkäsityksen ydin.

Toki matematiikkaa on jonkin verran ja kaavojakin on-mutta kenelläkään meistä ei oikeastaan tarvitse olla tohtorintutkintoa calculuksesta ymmärtääkseen, miten koneemme toimivat! Itse asiassa monet säännöt ja paradigmat, jotka opimme kirjoittaessamme koodia, ovat samoja sääntöjä ja paradigmoja, jotka pätevät monimutkaisiin tietojenkäsittelytieteen käsitteisiin. Joskus ne ideat ovat peräisin tietojenkäsittelytieteestä, emmekä tienneet sitä.

riippumatta siitä, mitä ohjelmointikieltä käytämme, kun useimmat meistä kirjoittavat koodiaan, pyrimme kapseloimaan erilliset asiat luokkiin, olioihin tai menetelmiin, tarkoituksellisesti erottelemaan, mitä koodimme eri osia koskee. Toisin sanoen, tiedämme, että se on yleensä hyvä asioita jakaa meidän koodi niin, että yksi luokka, objekti, tai menetelmä on vain huolissaan ja vastuussa yhdestä asiasta. Jos emme tekisi tätä, asiat voisivat mennä todella sotkuisiksi ja kietoutua yhteen sotkuiseksi verkoksi. Joskus näin edelleen tapahtuu, vaikka huolet erotettaisiin toisistaan.

käy ilmi, että jopa tietokoneidemme sisäiset toiminnot noudattavat hyvin samanlaisia suunnitteluparadigmoja. Esimerkiksi kääntäjällämme on siihen eri osia, ja jokainen osa vastaa yhden tietyn osan käsittelystä kokoamisprosessissa. Kohtasimme hieman tätä viime viikolla, kun saimme tietää parseri, joka on vastuussa luoda parse puita. Mutta jäsentäjä ei voi mitenkään saada tehtäväkseen kaikkea.

jäsentäjä tarvitsee apua kavereiltaan, ja on vihdoin aika oppia, keitä he ovat!

kun opimme jäsentämisestä äskettäin, kastoimme varpaamme kielioppiin, syntaksiin ja siihen, miten kääntäjä reagoi ja vastaa niihin asioihin ohjelmointikielellä. Mutta emme koskaan korostaneet, mitä Kääntäjä on! Kun pääsemme sisäisen toiminnan kokoelma prosessi, aiomme oppia paljon kääntäjä suunnittelu, joten se on elintärkeää meille ymmärtää, mitä me puhumme täällä.

kääntäjät voivat kuulostaa tavallaan pelottavilta, mutta heidän työnsä eivät oikeastaan ole liian monimutkaisia ymmärtää — varsinkin kun pilkotaan säveltäjän eri osat pureman kokoisiksi osiksi.

mutta aloitetaan ensin yksinkertaisimmalla mahdollisella määritelmällä. Kääntäjä on ohjelma, joka lukee koodimme (tai minkä tahansa koodin millä tahansa ohjelmointikielellä) ja kääntää sen toiselle kielelle.

yleisesti ottaen kääntäjä aikoo oikeastaan vain kääntää koodia korkean tason kielestä alemman tason kielelle. Alemman tason kieliä, joille Kääntäjä kääntää koodin, kutsutaan usein kokoonpanokoodiksi, konekoodiksi tai objektikoodiksi. On syytä mainita, että useimmat ohjelmoijat eivät oikeastaan käsittele tai kirjoita mitään konekoodia, vaan olemme riippuvaisia kääntäjästä, joka ottaa ohjelmamme ja kääntää ne konekoodiksi, jota tietokoneemme suorittaa suoritettavana ohjelmana.

voimme ajatella kääntäjiä välikätenä meidän, ohjelmoijien ja tietokoneidemme välillä, jotka voivat ajaa suoritettavia ohjelmia vain alemman tason kielillä.

kääntäjä tekee työn kääntäen mitä haluamme tapahtuvan tavalla, joka on koneidemme ymmärrettävissä ja suoritettavissa.

ilman kääntäjää joutuisimme kommunikoimaan tietokoneidemme kanssa kirjoittamalla konekoodia, joka on uskomattoman lukukelvotonta ja vaikeasti tulkittavaa. Koneen koodi voi usein vain näyttää joukko 0: n ja 1: n ihmisen silmään-se on kaikki binäärinen, Muistatko? – mikä tekee siitä erittäin vaikeaa lukea, kirjoittaa ja debug. Kääntäjä abstrahoi konekoodia meille ohjelmoijille, koska se teki meille hyvin helpoksi olla ajattelematta konekoodia ja kirjoittaa ohjelmia käyttäen paljon tyylikkäämpiä, selkeitä ja helppolukuisempia kieliä.

jatkamme mystisen kääntäjän purkamista lähiviikkojen aikana yhä enemmän, mikä toivottavasti tekee siitä vähemmän arvoituksen. Mutta nyt palataan käsillä olevaan kysymykseen: Mitkä ovat yksinkertaisimmat mahdolliset kääntäjän osat?

jokaisella kääntäjällä on eri vaiheet riippumatta siitä, miten se on suunniteltu. Näiden vaiheiden avulla voimme erottaa kääntäjän ainutlaatuiset osat.

olemme jo kohdanneet yhden vaiheen kokoamisseikkailuissamme, kun kuulimme hiljattain parseri-ja jäsenpuista. Tiedämme, että jäsentäminen on prosessi, jossa otetaan jonkin verran syötettä ja rakennetaan jäsentyspuu siitä, mitä joskus kutsutaan jäsentämiseksi. Kuten on käynyt ilmi, jäsennystyö on erityinen vaihe kokoamisprosessissa nimeltään syntaksianalyysi.

parseri ei kuitenkaan rakenna parsipuuta tyhjästä. Sillä on apua! Me ’ ll muistaa, että jäsennin annetaan joitakin tokens (kutsutaan myös terminaalit), ja se rakentaa jäsenpuu näistä tokens. Mutta mistä se saa nuo poletit? Parserin onneksi sen ei tarvitse toimia tyhjiössä, vaan sillä on jonkin verran apua.

tästä päästään toiseen kokoamisprosessin vaiheeseen, joka tulee ennen syntaksianalyysivaihetta: leksikaaliseen analyysivaiheeseen.

termi ”leksikaalinen” viittaa sanan merkitykseen erillään sen sisältävästä lauseesta ja riippumatta sen kieliopillisesta kontekstista. Jos yritämme arvata Oman merkityksemme pelkästään tämän määritelmän perusteella, voimme olettaa, että leksikaalinen analyysivaihe liittyy itse ohjelman yksittäisiin sanoihin/termeihin, eikä sillä ole mitään tekemistä sen lauseen kieliopin tai merkityksen kanssa, joka sisältää sanat.

leksikaalinen analyysivaihe on kokoamisprosessin ensimmäinen vaihe. Se ei tunne tai välitä lauseen kieliopista tai tekstin tai ohjelman merkityksestä;se tietää vain sanojen merkityksen.

leksikaalinen analyysi on tehtävä ennen kuin mitään lähdeohjelman koodia voidaan jäsentää. Ennen kuin jäsennin voi lukea sen, ohjelma täytyy ensin skannata, jakaa ja ryhmitellä yhteen tietyillä tavoilla.

kun viime viikolla aloimme tarkastella syntaksianalyysivaihetta, saimme tietää, että jäsennyspuu rakennetaan tarkastelemalla lauseen yksittäisiä osia ja pilkkomalla lausekkeita yksinkertaisempiin osiin. Mutta leksikaalisen analysointivaiheen aikana kääntäjä ei tiedä tai pääse käsiksi näihin ”yksittäisiin osiin”. Sen on sen sijaan ensin tunnistettava ja löydettävä ne ja sitten tehtävä työ pilkkomalla teksti yksittäisiin osiin.

esimerkiksi kun luemme Shakespearen lauseen, kuten To sleep, perchance to dream., tiedämme, että välilyönnit ja välimerkit jakavat lauseen ”sanat”. Tämä johtuu tietysti siitä, että meidät on koulutettu lukemaan lause,” lex ” sitä, ja jäsentämään sitä kielioppia varten.

mutta kääntäjälle sama lause saattaa näyttää tältä ensimmäisellä kerralla, kun se lukee sen: Tosleepperhachancetodream. Kun luemme tämän lauseen, meidän on hieman vaikeampi määrittää, mitä varsinaiset ”sanat” ovat! Kääntäjämme on varmasti samaa mieltä.

Joten, miten koneemme hoitaa tämän ongelman? Kokoamisprosessin leksikaalisessa analyysivaiheessa se tekee aina kaksi tärkeää asiaa: se skannaa koodin ja arvioi sen sitten.

skannauksen ja arvioinnin työ voidaan joskus niputtaa yhteen yhdeksi ohjelmaksi, tai se voi olla kaksi erillistä ohjelmaa, jotka riippuvat toisistaan; kyse on oikeastaan vain siitä, miten jokin yksittäinen complier sattui olemaan suunniteltu. Kääntäjän sisällä olevaa ohjelmaa, joka on vastuussa skannauksen ja arvioinnin tekemisestä, kutsutaan usein lekseriksi tai tokenizeriksi, ja koko leksikaalista analyysivaihetta kutsutaan joskus leksing-tai tokenizing-prosessiksi.

skannattaessa saatetaan lukea

ensimmäinen leksikaalisen analyysin kahdesta keskeisestä vaiheesta on skannaus. Voimme ajatella skannaus työn todella ”lukeminen” joitakin syötetekstiä. Muista, että tämä syöteteksti voi olla merkkijono, lause, ilmaisu tai jopa koko ohjelma! Sillä ei ole oikeastaan väliä, koska tässä vaiheessa prosessia, se on vain valtava möykky merkkejä, joka ei tarkoita mitään aivan vielä, ja on yksi yhtenäinen pala.

Katsotaanpa esimerkkiä, miten tämä tarkalleen tapahtuu. Käytämme alkuperäistä lausettamme, To sleep, perchance to dream., joka on lähdetekstimme tai lähdekoodimme. Kääntäjällemme tämä lähdeteksti luetaan syötetekstiksi, joka näyttää Tosleep,perchancetodream., joka on vain merkkijono, jota ei ole vielä tulkittu.

ensimmäinen asia, jonka kääntäjämme on tehtävä, on itse asiassa jakaa tuo tekstin möykky sen pienimpiin mahdollisiin paloihin, jolloin on paljon helpompi tunnistaa, missä tekstin möykky todellisuudessa on.

yksinkertaisin tapa sukeltaa jättiläismäinen kimpale tekstiä on lukea se hitaasti ja järjestelmällisesti, merkki kerrallaan. Ja juuri näin kääntäjä tekee.

usein skannauksen hoitaa erillinen ohjelma nimeltä skanneri, jonka ainoa tehtävä on tehdä lähdetiedoston / tekstin lukeminen merkki kerrallaan. Meidän skanneri, sillä ei ole väliä kuinka suuri tekstimme on; kaikki se näkee, kun se ”lukee” tiedostomme on yksi merkki kerrallaan.

Here ’ s what our Shakespearen lause would be read as by our scanner:

huomaamme, että To sleep, perchance to dream. on skannerimme mukaan jaettu yksittäisiin merkkeihin. Lisäksi jopa sanojen välejä käsitellään merkkeinä, kuten myös lauseemme välimerkkejä. Tämän jakson lopussa on myös hahmo, joka on erityisen kiinnostava: eof. Merkki ”tiedoston loppu”muistuttaa tabspace ja newline. Koska lähdetekstimme on vain yksi lause, kun skannerimme pääsee tiedoston loppuun (tässä tapauksessa lauseen loppuun), se lukee tiedoston loppuun ja käsittelee sitä merkkinä.

näin ollen, kun skannerimme luki syötetekstimme, se tulkitsi sen yksittäisinä merkkeinä, mikä johti tähän: .

nyt kun skannerimme on lukenut ja jakanut lähdetekstimme pienimpiin mahdollisiin osiin, on sen paljon helpompi selvittää lauseemme ”sanat”.

seuraavaksi skannerin pitää katsoa jakautuneet merkkinsä järjestyksessä ja selvittää, mitkä merkit ovat sanan osia ja mitkä eivät. Jokaiselle skannerin lukemalle merkille se merkitsee viivan ja paikan, jossa kyseinen merkki löytyi lähdetekstistä.

tässä oleva kuva havainnollistaa tätä prosessia Shakespearen lauseessamme. Voimme nähdä, että skannerimme merkitsee rivin ja sarakkeen jokaiselle lauseemme merkille. Voimme ajatella rivin ja sarakkeen esitys matriisi tai joukko merkkejä.

muista, että koska tiedostossamme on vain yksi rivi, kaikki elää rivillä 0. Kuitenkin, kun työskentelemme läpi lauseen, sarake kunkin merkin kasvaa. On myös syytä mainita, että koska skannerissamme lukee spacesnewlineseof ja kaikki välimerkit merkkeinä, nekin näkyvät merkistötaulussamme!

kun lähdeteksti on skannattu ja merkitty, kääntäjämme on valmis muuttamaan nämä merkit sanoiksi. Koska skanneri ei tiedä vain, missä tiedoston spacesnewlines ja eof ovat, vaan myös missä ne asuvat suhteessa niitä ympäröiviin muihin merkkeihin, se voi skannata merkit läpi ja jakaa ne tarpeen mukaan yksittäisiin merkkijonoihin.

esimerkissämme skanneri katsoo merkit T, sitten o ja sitten space. Kun se löytää avaruuden, se jakaa To omaksi sanakseen — yksinkertaisimman mahdollisen merkkiyhdistelmän ennen kuin skanneri kohtaa avaruuden.

se on samantapainen tarina seuraavaan löytämäänsä sanaan, joka on sleep. Tässä skenaariossa se kuitenkin lukee s-l-e-e-p ja sen jälkeen lukee ,, välimerkki. Koska tätä pilkkua reunustaa merkki (p) ja space jommallakummalla puolella, pilkkua itsessään pidetään”sanana”.

sekä sanaa sleep että välimerkkiä , kutsutaan lekseemeiksi, jotka ovat lähdetekstin substraatteja. Lekseemi on ryhmittely pienimmistä mahdollisista merkkien sekvensseistä lähdekoodissamme. Lähdetiedoston lekseemejä pidetään itse tiedoston yksittäisinä ”sanoina”. Kun skannerimme on lukenut tiedostomme yksittäiset merkit, se palauttaa joukon lekseemejä, jotka näyttävät tältä: .

huomaa, miten skannerimme otti syötteekseen möykyn tekstiä, jota se ei aluksi pystynyt lukemaan, ja jatkoi skannausta merkki kerrallaan, lukien samalla sisällön ja merkiten sen. Sitten se eteni jakaa merkkijono niiden pienin mahdollinen lexemes käyttämällä välilyöntejä ja välimerkit merkkien erotin.

kaikesta tästä työstä huolimatta tässä vaiheessa leksikaalista analyysivaihetta skannerimme ei kuitenkaan tiedä mitään näistä sanoista. Toki se jakaa tekstin erimuotoisiin ja-kokoisiin sanoihin, mutta mitä nuo sanat ovat, skannerilla ei ole aavistustakaan! Sanat voivat olla kirjaimellinen merkkijono tai välimerkki tai jotain aivan muuta!

skanneri ei tiedä mitään itse sanoista tai minkä ”tyypin” sanoista ne ovat. Se vain tietää, mihin sanat päättyvät ja alkavat itse tekstissä.

Tämä asettaa meidät leksikaalisen analyysin toiseen vaiheeseen: arviointiin. Kun olemme skannanneet tekstimme ja jakaneet lähdekoodin yksittäisiin lexeme — yksiköihin, meidän on arvioitava sanat, jotka skanneri palautti meille ja selvittää, millaisia sanoja olemme tekemisissä-erityisesti meidän on etsittävä tärkeitä sanoja, jotka tarkoittavat jotain erityistä kielellä, jota yritämme koota.

tärkeiden osien arviointi

kun olemme skannanneet lähdetekstimme ja tunnistaneet lekseemimme, meidän on tehtävä jotain lekseemillämme ”words”. Tämä on leksikaalisen analyysin arviointivaihe, jota usein kutsutaan complier designissa lexing-tai tokenizing our input-prosessiksi.

kun arvioimme skannattua koodiamme, kaikki mitä todella teemme on tarkastella lähemmin jokaista skannerimme luomaa lekseemiä. Meidän kääntäjä täytyy tarkastella jokaista lexeme sana ja päättää, millainen sana se on. Prosessi määrittää, millainen lexeme kunkin ”sana” tekstissämme on, miten kääntäjä kääntyy kunkin yksittäisen lexeme token, mikä tokenizing meidän tulomerkkijono.

törmäsimme poletteihin ensimmäisen kerran jo silloin, kun olimme tutustumassa parsepuihin. Tokenit ovat erikoissymboleita, jotka ovat kunkin ohjelmointikielen ytimessä. Tokenit, kuten (, ), +, -, if, else, then, kaikki auttavat kääntäjää ymmärtämään, miten lausekkeen eri osat ja eri elementit liittyvät toisiinsa. Jäsennin, joka on keskeinen syntaksianalyysivaiheessa, riippuu tokeneiden vastaanottamisesta jostain ja muuttaa ne sitten jäsennyspuuksi.

no, arvaa mitä? Olemme vihdoinkin keksineet ”jonnekin”! Kuten on käynyt ilmi, tokenit, jotka saavat lähetetään jäsennin luodaan leksikaalisen analyysin vaiheessa tokenizer, jota kutsutaan myös lexer.

joten miltä token tarkalleen näyttää? Token on melko yksinkertainen, ja on yleensä esitetty parina, joka koostuu token nimi, ja jokin arvo (joka on valinnainen).

esimerkiksi, jos tokenisoimme Shakespearen kielemme, päädyimme poletteihin, jotka olisivat lähinnä kielilitareita ja erottimia. Voisimme esittää lekseemin "dream” tokenina näin: <string literal, "dream">. Vastaavasti voisimme esittää lekseemin . tokenina, <separator, .>.

huomaamme, että jokainen näistä tokeneista ei muokkaa lekseemiä lainkaan — he vain lisäävät niihin lisätietoja. Token on lexeme tai lexical yksikkö yksityiskohtaisemmin; erityisesti, lisätty yksityiskohta kertoo meille, mikä luokka token (minkälainen ”sana”) olemme tekemisissä.

nyt kun olemme tokenisoineet Shakespearen lauseemme, voimme nähdä, että lähdetiedoston polettityypeissä ei ole kovin paljon vaihtelua. Lauseessamme oli vain merkkijonoja ja välimerkkejä — mutta se on vain jäävuoren huippu! On paljon muunlaisia ”sanoja”, että lekseemi voitaisiin luokitella.

tässä esitetty taulukko havainnollistaa joitakin yleisimpiä tokeneita, jotka kääntäjämme näkisi lukiessaan lähdetiedostoa jokseenkin millä tahansa ohjelmointikielellä. Näimme esimerkkejä literals, joka voi olla mikä tahansa merkkijono, numero tai logiikan/Boolen arvo, sekä separators, jotka ovat minkä tahansa tyyppisiä välimerkkejä, mukaan lukien henkselit ({}) ja sulut (()).

However, there are also keywords, which are terms that are reserved in the language (such as ifvarwhilereturn), as well as operators, which operate on arguments and return some value ( +-x/). Törmäsimme myös lekseemeihin, jotka voitaisiin tokenisoida nimellä identifiers, jotka ovat yleensä muuttuvia nimiä tai käyttäjän/ohjelmoijan kirjoittamia asioita viittaamaan johonkin muuhun, sekä , jotka voivat olla käyttäjän kirjoittamia rivi-tai blokkikommenteja.

alkuperäisessä lauseessamme näkyi vain kaksi esimerkkiä poleteista. Kirjoitetaan lause sen sijaan seuraavasti: var toSleep = "to dream";. Miten kääntäjämme lex voisi tämän Shakespearen version?

täällä nähdään, että meillä on laajempi valikoima poletteja. Meillä on keyword in var, jossa julistamme muuttujan, ja identifiertoSleep, jolla nimeämme muuttujan eli viittaamme tulevaan arvoon. Seuraavana on meidän =, joka on operator token, jota seuraa merkkijono kirjaimellinen "to dream". Lausekkeemme päättyy ; erotin, joka ilmaisee rivin lopun ja rajaa välilyönnit.

tärkeää huomata tokenisointiprosessissa on, että emme ole tokenisoimassa mitään välilyöntejä (välilyönnit, newlinet, välilehdet, rivin loppu jne.), eikä sen välittäminen jäsentäjälle. Muista, että vain kuponkia annetaan jäsennin ja päätyy jäsenpuu.

on myös syytä mainita, että eri kielillä on erilaisia merkkejä, jotka muodostavat välilyöntejä. Esimerkiksi joissakin tilanteissa Python – ohjelmointikieli käyttää sisennystä-välilehtiä ja välilyöntejä myöten-osoittaakseen, miten funktion laajuus muuttuu. Python-kääntäjän tokenisaattorin täytyy siis olla tietoinen siitä, että tietyissä tilanteissa tab tai space todella pitää tokenisoida sanana, koska se itse asiassa pitää välittää jäsentäjälle!

tämä tokenizerin osa on hyvä tapa verrata sitä, miten lexer / tokenizer eroaa skannerista. Vaikka skanneri on tietämätön, ja osaa vain hajottaa tekstin sen pienempiin mahdollisiin osiin (sen ”sanat”), lexer/tokenizer on paljon tietoisempi ja tarkempi verrattuna.

tokenizerin on tunnettava koottavan kielen koukerot ja spesifikaatiot. Jos tabs ovat tärkeitä, sen on tiedettävä se; jos newlines voi olla tiettyjä merkityksiä käännettävässä kielessä, tokenizerin on oltava tietoinen näistä yksityiskohdista. Toisaalta skanneri ei edes tiedä, mitä sen jakamat sanat edes ovat, saati mitä ne tarkoittavat.

komppaajan skanneri on huomattavasti kieliagnostisempi, kun taas tokenisaattorin täytyy olla määritelmänsä mukaan kielikohtainen.

nämä kaksi leksikaalisen analyysiprosessin osaa kulkevat käsi kädessä, ja ne ovat keskeisiä kokoamisprosessin ensimmäisessä vaiheessa. Eri kääntäjät on tietysti suunniteltu omilla ainutlaatuisilla tavoillaan. Jotkut kääntäjät tekevät skannauksen ja tokenizingin vaiheen yhdessä prosessissa ja yhtenä ohjelmana, kun taas toiset jakavat ne eri luokkiin, jolloin tokenizer kutsuu skanneriluokkaan, kun se suoritetaan.

kummassakin tapauksessa sanastoanalyysin vaihe on äärimmäisen tärkeä kokoamisen kannalta, koska syntaksianalyysivaihe riippuu siitä suoraan. Ja vaikka kääntäjän jokaisella osalla on omat erityiset roolinsa, he nojaavat toisiinsa ja ovat riippuvaisia toisistaan — aivan kuten hyvät ystävät aina tekevät.

resurssit

koska on olemassa monia erilaisia tapoja kirjoittaa ja suunnitella Kääntäjä, on myös monia erilaisia tapoja opettaa niitä. Jos teet tarpeeksi tutkimusta perusteista koostaminen, on melko selvää, että jotkut selitykset menevät paljon yksityiskohtaisemmin kuin toiset, joka voi olla tai ei ole hyödyllistä. Jos löydät itsesi haluavat oppia lisää, alla on erilaisia resursseja kääntäjät-jossa keskitytään leksikaalinen analyysi vaihe.

1. Luku 4 — Crafting Interpreters, Robert Nyström
2. Compiler Construction, professori Allan Gottlieb
3. Compiler Basics, professori James Alan Farrell
4. Writing a programming language — the Lexer, Andy Bileam
5. Notes on How Parsers and Compilers Work, Stephen Raymond Ferg
6. Mitä eroa on tokenilla ja lekseemillä?, StackOverflow