Software is all about logic. Programmering har fått et rykte for å være et felt som er tungt på matte og galne ligninger. Og datavitenskap synes å være på kjernen i denne misforståelsen.Jo, det er litt matte og det er noen formler — men ingen av oss trenger faktisk Å ha Doktorgrader i kalkulator for at vi skal forstå hvordan maskinene våre fungerer! Faktisk er mange regler og paradigmer som vi lærer i ferd med å skrive kode, de samme reglene og paradigmene som gjelder for komplekse datavitenskapskonsepter. Og noen ganger stammer disse ideene faktisk fra datavitenskap,og vi visste det aldri.Uansett hvilket programmeringsspråk vi bruker, når de fleste av oss skriver koden vår, tar vi sikte på å innkapsle forskjellige ting i klasser, objekter eller metoder, og forsiktig skille ut hvilke forskjellige deler av koden vår er opptatt av. Med andre ord vet vi at det generelt er gode ting å dele opp koden vår slik at en klasse, objekt eller metode bare er opptatt av og ansvarlig for en enkelt ting. Hvis vi ikke gjorde dette, kunne ting bli super rotete og sammenflettet til et rot av en web. Noen ganger skjer dette fortsatt, selv med separasjon av bekymringer.

som det viser seg, selv den indre driften av våre datamaskiner følger svært lignende design paradigmer. Vår kompilator har for eksempel forskjellige deler til den, og hver del er ansvarlig for å håndtere en bestemt del av kompileringsprosessen. Vi møtte litt av denne forrige uke, da vi lærte om parseren, som er ansvarlig for å lage parsetrær. Men parseren kan ikke muligens være oppgave med alt.parseren trenger litt hjelp fra sine venner, og det er endelig tid for oss å lære hvem de er!Da vi lærte om parsing nylig, dyppet vi tærne i grammatikk, syntaks og hvordan kompilatoren reagerer og reagerer på disse tingene i et programmeringsspråk. Men vi har aldri virkelig fremhevet hva en kompilator er! Når vi kommer inn i det indre arbeidet i kompileringsprosessen, skal vi lære mye om kompilatordesign, så det er viktig for oss å forstå hva vi snakker om her.Kompilatorer kan høres litt skummelt ut, men jobbene deres er faktisk ikke for komplekse til å forstå-spesielt når vi bryter de forskjellige delene av en complier ned i bite-sized deler.

Men først, la oss starte med den enkleste definisjonen mulig. En kompilator er et program som leser koden vår (eller hvilken som helst kode, i et hvilket som helst programmeringsspråk), og oversetter den til et annet språk.

kompilator: en definisjon.

generelt sett vil en kompilator egentlig bare oversette kode fra et språk på høyt nivå til et språk på lavere nivå. Språkene på lavere nivå som en kompilator oversetter kode til, blir ofte referert til som samlingskode, maskinkode eller objektkode. Det er verdt å nevne at de fleste programmerere ikke egentlig arbeider med eller skriver noen maskinkode; heller, vi er avhengige av kompilatoren for å ta våre programmer og oversette dem til maskinkode, som er hva vår datamaskin vil kjøre som et kjørbart program.vi kan tenke på kompilatorer som mellommann mellom oss, programmerere, og våre datamaskiner, som bare kan kjøre kjørbare programmer i lavere nivå språk.

kompilatoren gjør arbeidet med å oversette hva vi ønsker skal skje på en måte som er forståelig og kjørbar av våre maskiner.

Uten kompilatoren ville vi bli tvunget til å kommunisere med datamaskinene våre ved å skrive maskinkode, noe som er utrolig uleselig og vanskelig å tyde. Maskinkode kan ofte bare se ut som en haug med 0 og 1 til det menneskelige øye — det er alt binært, husk? – som gjør det super vanskelig å lese, skrive og feilsøke — Kompilatoren abstraherte bort maskinkode for oss som programmerere, fordi det gjorde det veldig enkelt for oss å ikke tenke på maskinkode og skrive programmer ved hjelp av langt mer elegante, klare og lettleste språk.Vi vil fortsette å pakke ut mer og mer om den mystiske kompilatoren i løpet av de neste ukene, noe som forhåpentligvis vil gjøre det mindre av en gåte i prosessen. Men for nå, la oss komme tilbake til spørsmålet: hva er de enkleste mulige delene av en kompilator?

hver kompilator, uansett hvordan den kan utformes, har forskjellige faser. Disse fasene er hvordan vi kan skille de unike delene av kompilatoren.

Syntaksanalyse: fase en av en kompilator

vi har allerede møtt en av fasene i våre kompileringseventyr da vi nylig lærte om parseren og parsetrærne. Vi vet at parsing er prosessen med å ta noen innspill og bygge et parsetre ut av det, som noen ganger refereres til som parsing. Som det viser seg, er arbeidet med parsing spesifikk for en fase i kompileringsprosessen kalt syntaksanalyse.

parseren bygger Imidlertid ikke bare et parsetre ut av tynn luft. Det har litt hjelp! Vi husker at parseren er gitt noen tokens (også kalt terminaler), og det bygger et parsetre fra disse tokens. Men hvor får det disse tokens fra? Heldig for parseren, det trenger ikke å operere i et vakuum; i stedet har det litt hjelp.

dette bringer oss til en annen fase av kompileringsprosessen, en som kommer før syntaksanalysefasen: den leksikalske analysefasen.

de innledende fasene av en kompilator

begrepet»leksikalsk»refererer til betydningen av et ord isolert fra setningen som inneholder det, og uavhengig av dets grammatiske kontekst. Hvis vi prøver å gjette vår egen mening basert utelukkende på denne definisjonen, kan vi si at den leksikalske analysefasen har å gjøre med de enkelte ordene/begrepene i programmet selv, og ingenting å gjøre med grammatikken eller meningen med setningen som inneholder ordene.

den leksikalske analysefasen er det første trinnet i kompileringsprosessen. Det vet ikke eller bryr seg om grammatikken i en setning eller betydningen av en tekst eller et program; alt det vet om er meningen med ordene selv.

Leksikalsk analyse må skje før noen kode fra et kildeprogram kan analyseres. Før det kan leses av parseren, må et program først skannes, splittes opp og grupperes sammen på bestemte måter.

da vi begynte å se på syntaksanalysefasen i forrige uke, lærte vi at parsetreet er bygget ved å se på enkelte deler av setningen og bryte ned uttrykk i enklere deler. Men i den leksikalske analysefasen kjenner kompilatoren ikke eller har tilgang til disse «individuelle delene». Snarere må den først identifisere og finne dem, og deretter gjøre arbeidet med å splitte teksten i individuelle stykker.

for eksempel, når vi leser en setning fra Shakespeare som To sleep, perchance to dream., vet vi at mellomrom og tegnsetting deler opp» ordene » i en setning. Dette er selvfølgelig fordi vi har blitt trent til å lese en setning,» lex » den, og analysere den for grammatikk.

Men for en kompilator kan den samme setningen se slik ut første gang den leser den: Tosleepperhachancetodream. Når vi leser denne setningen, er det litt vanskeligere for oss å bestemme hva de faktiske «ordene» er! Jeg er sikker på at vår kompilator føler det samme.

Så, hvordan håndterer vår maskin dette problemet? Vel, i den leksikalske analysefasen av kompileringsprosessen, gjør den alltid to viktige ting: den skanner koden, og evaluerer den deretter.

De to trinnene av den leksikalske analyseprosessen!

arbeidet med skanning og evaluering kan noen ganger bli samlet sammen i ett enkelt program, eller det kan være to separate programmer som er avhengige av hverandre; det er egentlig bare et spørsmål om hvordan noen complier skjedde å være utformet. Programmet i kompilatoren som er ansvarlig for å gjøre arbeidet med skanning og evaluering blir ofte referert til som lexer eller tokenizer, og hele leksikalske analysefasen kalles noen ganger prosessen med lexing eller tokenizing.

for å skanne, muligens for å lese

den første av de to kjernetrinnene i leksikalsk analyse er skanning. Vi kan tenke på skanning som arbeidet med å faktisk «lese» noen inngangstekst. Husk at denne inndatateksten kan være en streng, setning, uttrykk eller til og med et helt program! Det spiller ingen rolle, for i denne fasen av prosessen er det bare en gigantisk blob av tegn som ikke betyr noe ennå, og er en sammenhengende del.

La oss se på et eksempel for å se hvordan akkurat dette skjer. Vi bruker vår opprinnelige setning, To sleep, perchance to dream., som er vår kildetekst eller kildekode. Til vår kompilator vil denne kildeteksten bli lest som inndatatekst som ser ut som Tosleep,perchancetodream., som bare er en streng tegn som ennå ikke er dechiffrert.

skanneprosessen, trinn 1.

det første vår kompilator må gjøre er faktisk å dele opp teksten i sine minste mulige stykker, noe som vil gjøre det mye lettere å identifisere hvor ordene i teksten faktisk er.

den enkleste måten å dykke opp en gigantisk del av teksten er ved å lese den sakte og systematisk, ett tegn om gangen. Og dette er akkurat hva kompilatoren gjør.

ofte håndteres skanneprosessen av et eget program kalt skanneren, hvis eneste jobb er å gjøre arbeidet med å lese en kildefil / tekst, ett tegn om gangen. Til vår skanner spiller det ingen rolle hvor stor teksten vår er; alt det vil se når det» leser » vår fil er ett tegn om gangen.

Her er hva Vår Shakespeare setning ville bli lest som av vår skanner:

skanningen prosess, trinn 2.

Vi vil legge merke til at To sleep, perchance to dream. er delt inn i individuelle tegn av skanneren vår. Dessuten, selv mellomrommene mellom ordene blir behandlet som tegn, som er tegnsetting i vår setning. Det er også et tegn på slutten av denne sekvensen som er spesielt interessant: eof. Dette er tegnet «end of file», og det ligner på tabspace og newline. Siden vår kildetekst er bare en enkelt setning, når skanneren kommer til slutten av filen (i dette tilfellet slutten av setningen), leser den slutten av filen og behandler den som et tegn.

så, i virkeligheten, når skanneren leser vår inngangstekst, tolket den det som individuelle tegn som resulterte i dette: .

skanneprosessen, trinn 3.

Nå som skanneren vår har lest og delt opp kildeteksten i sine minste mulige deler, vil det ha en mye lettere tid å finne ut «ordene» i setningen vår.

deretter må skanneren se på sine splittede tegn i rekkefølge, og avgjøre hvilke tegn som er deler av et ord, og hvilke som ikke er. For hvert tegn som skanneren leser, markerer den linjen og posisjonen der tegnet ble funnet i kildeteksten.

bildet som vises her illustrerer denne prosessen for Vår Shakespeare setning. Vi kan se at skanneren vår markerer linjen og kolonnen for hvert tegn i setningen vår. Vi kan tenke på linje – og kolonnerepresentasjonen som en matrise eller en rekke tegn.

Husk at siden filen vår bare har en enkelt linje i den, lever alt på linje 0. Men når vi jobber oss gjennom setningen, øker kolonnen for hvert tegn. Det er også verdt å nevne at siden skanneren vår leser spacesnewlineseof, og all tegnsetting som tegn, vises de også i tegntabellen vår!

skanneprosessen, trinn 4.

når kildeteksten er skannet og merket, er kompilatoren vår klar til å gjøre disse tegnene til ord. Siden skanneren ikke bare vet hvor spacesnewlines og eof i filen er, men også hvor de bor i forhold til de andre tegnene som omgir dem, kan den skanne gjennom tegnene og dele dem i individuelle strenger etter behov.

i vårt eksempel vil skanneren se på tegnene T, deretter o, og deretter en space. Når den finner et mellomrom, vil den dele To i sitt eget ord – den enkleste kombinasjonen av tegn som er mulig før skanneren møter et mellomrom.

Det er en lignende historie for det neste ordet som den finner, som er sleep. Men i dette scenariet leser s-l-e-e-p, og leser deretter en ,, et skilletegn. Siden dette kommaet er flankert av et tegn (p) og en space på hver side, anses kommaet selv å være et «ord».

både ordet sleep og tegnsettingssymbolet , kalles lexemer, som er delstrenger kildeteksten. Et lexeme er en gruppering av de minste mulige sekvenser av tegn i kildekoden vår. Lexemene til en kildefil betraktes som de enkelte «ordene» i selve filen. Når skanneren er ferdig med å lese de enkelte tegnene i filen vår, vil den returnere et sett med lexemer som ser slik ut: .

skanningen prosess, trinn 5.

Legg merke til hvordan skanneren tok en blob av tekst som sin inngang, som den ikke kunne først lese, og fortsatte å skanne den en gang tegn om gangen, samtidig lese og merke det innholdet. Det fortsatte deretter å dele strengen i deres minste mulige lexemer ved å bruke mellomrom og tegnsetting mellom tegn som skilletegn.

til tross for alt dette arbeidet, på dette punktet i den leksikalske analysefasen, vet ikke skanneren noe om disse ordene. Jo, det deler opp teksten i ord av forskjellige former og størrelser, men så langt som disse ordene er, har skanneren ingen anelse! Ordene kan være en bokstavelig streng, eller de kan være et tegnsettingstegn, eller de kan være noe helt annet!

skanneren vet ingenting om ordene selv, eller hva «type» av ord de er. Det vet bare hvor ordene slutter og begynner i selve teksten.

dette setter oss opp for den andre fasen av leksikalsk analyse: evaluering. Når vi har skannet teksten vår og brutt opp kildekoden i individuelle lexeme-enheter, må vi evaluere ordene som skanneren returnerte til oss og finne ut hvilke typer ord vi har å gjøre med — spesielt må vi se etter viktige ord som betyr noe spesielt på språket vi prøver å kompilere.

Evaluere de viktige delene

Når vi er ferdig med å skanne vår kildetekst og identifisert våre lexemer, må vi gjøre noe med våre lexeme «ord». Dette er evalueringstrinnet for leksikalsk analyse, som ofte refereres til i komplisert design som prosessen med lexing eller tokenizing våre innspill.

hva betyr det for å evaluere den skannede koden?

når vi evaluerer vår skannede kode, er alt vi egentlig gjør, å se nærmere på hver av lexemene som skanneren vår genererte. Vår kompilator må se på hvert lexeme-ord og bestemme hva slags ord det er. Prosessen med å bestemme hva slags lexeme hvert «ord» i vår tekst er hvordan vår kompilator gjør hver enkelt lexeme til et token, og dermed tokeniserer vår inngangsstreng.

vi møtte først tokens tilbake da vi lærte om å analysere trær. Tokens er spesielle symboler som er i kjernen til hvert programmeringsspråk. Tokens, for eksempel (, ), +, -, if, else, then, hjelper alle en kompilator til å forstå hvordan ulike deler av et uttrykk og ulike elementer relaterer seg til hverandre. Parseren, som er sentral i syntaksanalysefasen, avhenger av å motta tokens fra et sted og gjør disse tokens til et parsetre.

Polletter: en definisjon.

vel, gjett hva? Vi har endelig funnet ut «et sted»! Som det viser seg, blir tokens som sendes til parseren generert i den leksikalske analysefasen av tokenizer, også kalt lexeren.

vår shakespeare-setning!

Så hvordan ser et token ut? Et token er ganske enkelt, og er vanligvis representert som et par, bestående av et token navn, og noen verdi (som er valgfritt).for eksempel, hvis vi tokeniserte Vår Shakespeare-streng, ville vi ende opp med tokens som for det meste ville være strenglitteraler og separatorer. Vi kunne representere lexemet "dream” som et token som så: <string literal, "dream">. På samme måte kan vi representere lexemet . som token, <separator, .>.

Vi vil legge merke til at hver av disse tokens ikke endrer lexemet i det hele tatt-de legger ganske enkelt til tilleggsinformasjon for dem. Et token er lexeme eller leksikalsk enhet med flere detaljer; spesielt forteller den ekstra detalj oss hvilken kategori av token (hvilken type «ord») vi har å gjøre med.

Nå som vi har tokenisert Vår Shakespeare-setning, kan vi se at det ikke er så mye variasjon i typer tokens i kildefilen vår. Vår setning hadde bare strenger og tegnsetting i det — men det er bare toppen av token isfjellet! Det er mange andre typer » ord » som et lexeme kan kategoriseres i.

tokens funnet i vår kildekode.

tabellen som vises her illustrerer noen av de vanligste tokens som vår kompilator ville se når du leser en kildefil i stort sett alle programmeringsspråk. Vi så eksempler på literals, som kan være hvilken som helst streng, tall eller logikk/boolsk verdi, samt separators, som er en hvilken som helst type tegnsetting, inkludert braces ({}) og parenteser (()).

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/). Vi kan også møte lexemer som kan tokeniseres som identifiers, som vanligvis er variable navn eller ting skrevet av brukeren / programmereren for å referere til noe annet, samt , som kan være linje eller blokkere kommentarer skrevet av brukeren.

vår opprinnelige setning viste oss bare to eksempler på tokens. La oss omskrive vår setning til i stedet lese: var toSleep = "to dream";. Hvordan kan vår kompilator lex denne versjonen Av Shakespeare?

lexer tokenize denne setningen?

Her ser vi at vi har et større utvalg av tokens. Vi har en keyword i var, der vi erklærer en variabel, og en identifiertoSleep, som er måten vi navngir vår variabel på, eller refererer til verdien som kommer. Neste er vår =, som er en operator token, etterfulgt av strengen bokstavelig "to dream". Vår uttalelse avsluttes med en; separator, som angir slutten av en linje og avgrenser mellomrom.En viktig ting å merke seg om tokeniseringsprosessen er at vi heller ikke tokeniserer noen mellomrom (mellomrom, linjer, faner, slutten av linjen, etc.), og heller ikke sende den videre til parseren. Husk at bare tokens blir gitt til parseren og vil ende opp i parsetreet.

det er også verdt å nevne at forskjellige språk vil ha forskjellige tegn som utgjør som mellomrom. For eksempel, i Noen situasjoner bruker Programmeringsspråket Python innrykk-inkludert faner og mellomrom — for å indikere hvordan omfanget av en funksjon endres. Så, Python-kompilatorens tokenizer må være klar over det faktum at i visse situasjoner må en tab eller space faktisk trenger å bli tokenisert som et ord, fordi det faktisk må sendes til parseren!

lexer vs skanneren.

dette aspektet av tokenizer er en god måte å kontrastere hvordan en lexer / tokenizer er forskjellig fra en skanner. Mens en skanner er uvitende, og bare vet hvordan man bryter opp en tekst i sine mindre mulige deler (dens «ord»), er en lexer/tokenizer mye mer oppmerksom og mer presis i sammenligning.

tokenizer trenger å vite intricacies og spesifikasjoner av språket som blir kompilert. Hvis tabs er viktig, må den vite det; hvis newlines kan ha visse betydninger på språket som kompileres, må tokenizer være oppmerksom på disse detaljene. På den annen side vet skanneren ikke engang hva ordene som den deler selv er, mye mindre hva de betyr.

skanneren til en komplikator er langt mer språkagnostisk, mens en tokenizer må være språkspesifikk per definisjon.

Disse to delene av den leksikalske analyseprosessen går hånd i hånd, og de er sentrale i første fase av kompileringsprosessen. Selvfølgelig er forskjellige komplikatorer utformet på sine egne unike måter. Noen kompilatorer gjør trinnet med å skanne og tokenisere i en enkelt prosess og som et enkelt program, mens andre vil dele dem opp i forskjellige klasser, i så fall vil tokenizer ringe til skannerklassen når den kjøres.

Leksikalsk analyse: en rask visuell oppsummering!

i begge tilfeller er trinnet med leksikalsk analyse super viktig for kompilering, fordi syntaksanalysefasen avhenger direkte av den. Og selv om hver del av kompilatoren har sine egne spesifikke roller, lener de seg på hverandre og er avhengige av hverandre — akkurat som gode venner alltid gjør.

Ressurser

Siden det er mange forskjellige måter å skrive og designe en kompilator På, er det også mange forskjellige måter å lære dem på. Hvis du gjør nok forskning på grunnleggende om kompilering, blir det ganske klart at noen forklaringer går langt mer detaljert enn andre, noe som kanskje eller ikke kan være nyttig. Hvis du finner deg selv som ønsker å lære mer, er det en rekke ressurser på kompilatorer-med fokus på leksikalsk analysefase.

1. Kapittel 4-Laging Tolker, Robert Nystrom
2. Kompilator Konstruksjon, Professor Allan Gottlieb
3. Kompilator Grunnleggende, Professor James Alan Farrell
4. Skrive et programmeringsspråk-The Lexer, Andy Bilaam
5. Notater Om Hvordan Parsere Og Kompilatorer Arbeid, Stephen Raymond Ferg
6. hva er forskjellen mellom et token og en lexeme?, StackOverflow