Software is all about logic. Programmering har fått ett rykte om att vara ett fält som är tungt på matte och galna ekvationer. Och datavetenskap verkar vara kärnan i denna missuppfattning.

Visst, det finns lite matematik och det finns några formler — men ingen av oss behöver faktiskt ha doktorander i kalkylen för att vi ska förstå hur våra maskiner fungerar! Faktum är att många av de regler och paradigmer som vi lär oss i processen att skriva kod är samma regler och paradigmer som gäller för komplexa datavetenskapliga begrepp. Och ibland kommer dessa tankar faktiskt från datavetenskap,och vi visste aldrig det.

oavsett vilket programmeringsspråk vi använder, när de flesta av oss skriver vår kod, strävar vi efter att inkapsla olika saker i klasser, objekt eller metoder, avsiktligt separera vilka olika delar av vår kod som berörs. Med andra ord vet vi att det i allmänhet är bra saker att dela upp vår kod så att en klass, objekt eller metod bara handlar om och ansvarar för en enda sak. Om vi inte gjorde det här kan saker bli super röriga och sammanflätade i en röra på en webb. Ibland händer detta fortfarande, även med separation av oro.

som det visar sig följer även de inre funktionerna i våra datorer mycket liknande designparadigmer. Vår kompilator har till exempel olika delar till den, och varje del ansvarar för att hantera en specifik del av kompileringsprocessen. Vi stötte på lite av den här förra veckan, när vi lärde oss om parsern, som är ansvarig för att skapa parsträd. Men tolken kan omöjligen få i uppdrag med allt.

parsern behöver lite hjälp från sina kompisar, och det är äntligen dags för oss att lära oss vem de är!

När vi lärde oss om parsing nyligen doppade vi tårna i grammatik, syntax och hur kompilatorn reagerar och svarar på dessa saker inom ett programmeringsspråk. Men vi lyfte aldrig riktigt fram vad exakt en kompilator är! När vi kommer in i det inre arbetet i kompileringsprocessen kommer vi att lära oss mycket om kompilatordesign, så det är viktigt för oss att förstå vad vi pratar om här.

kompilatorer kan låta lite skrämmande, men deras jobb är faktiskt inte för komplexa för att förstå — särskilt när vi bryter de olika delarna av en komplier ner i bitstora delar.

men först, låt oss börja med den enklaste definitionen som möjligt. En kompilator är ett program som läser vår kod (eller någon kod, i något programmeringsspråk) och översätter det till ett annat språk.

ompilator: en definition.

generellt sett kommer en kompilator egentligen bara att översätta kod från ett högnivåspråk till ett språk på lägre nivå. Språk på lägre nivå som en kompilator översätter kod till kallas ofta monteringskod, maskinkod eller objektkod. Det är värt att nämna att de flesta programmerare inte riktigt hanterar eller skriver någon maskinkod; snarare beror vi på kompilatorn för att ta våra program och översätta dem till maskinkod, vilket är vad vår dator kommer att köra som ett körbart program.

Vi kan tänka på kompilatorer som mellanhand mellan oss, programmerarna och våra datorer, som bara kan köra körbara program på språk på lägre nivå.

kompilatorn gör arbetet med att översätta vad vi vill hända på ett sätt som är förståeligt och körbart av våra maskiner.

utan kompilatorn skulle vi tvingas kommunicera med våra datorer genom att skriva maskinkod, vilket är otroligt oläsligt och svårt att dechiffrera. Maskinkod kan ofta bara se ut som en massa 0 och 1 för det mänskliga ögat-det är allt binärt, kom ihåg? – vilket gör det super svårt att läsa, skriva och felsöka. Kompilatorn abstraherade bort maskinkod för oss som programmerare, eftersom det gjorde det väldigt lätt för oss att inte tänka på maskinkod och skriva program med mycket mer eleganta, tydliga och lättlästa språk.

Vi fortsätter att packa upp mer och mer om den mystiska kompilatorn under de närmaste veckorna, vilket förhoppningsvis kommer att göra det mindre av en gåta i processen. Men för nu, låt oss komma tillbaka till frågan: Vilka är de enklaste möjliga delarna av en kompilator?

varje kompilator, oavsett hur den kan utformas, har olika faser. Dessa faser är hur vi kan skilja de unika delarna av kompilatorn.

Vi har redan stött på en av faserna i våra kompileringsäventyr när vi nyligen lärde oss om parser och parse träd. Vi vet att parsing är processen att ta lite input och bygga ett parsträd ur det, vilket ibland kallas parsing. Som det visar sig är analysarbetet specifikt för en fas i kompileringsprocessen som kallas syntaxanalys.

men parsern bygger inte bara ett parsträd ur tunn luft. Det har lite hjälp! Vi kommer ihåg att parsern ges några tokens (även kallade terminaler), och det bygger ett parsträd från dessa tokens. Men var får det dessa tokens från? Tur för parsern, det behöver inte fungera i vakuum; istället har det lite hjälp.

detta leder oss till en annan fas i kompileringsprocessen, en som kommer före syntaxanalysfasen: den lexikala analysfasen.

termen ”lexikal” avser betydelsen av ett ord isolerat från meningen som innehåller det och oavsett dess grammatiska sammanhang. Om vi försöker gissa vår egen mening baserad enbart på denna definition kan vi säga att den lexikala analysfasen har att göra med de enskilda orden/termerna i själva programmet och ingenting att göra med grammatiken eller meningen med meningen som innehåller orden.

den lexikala analysfasen är det första steget i kompileringsprocessen. Det vet inte eller bryr sig om grammatiken i en mening eller betydelsen av en text eller ett program; allt det vet om är betydelsen av orden själva.

lexikal analys måste ske innan någon kod från ett källprogram kan tolkas. Innan det kan läsas av tolkaren måste ETT program först skannas, delas upp och grupperas på vissa sätt.

När vi började titta på syntaxanalysfasen förra veckan lärde vi oss att parsträdet byggs genom att titta på enskilda delar av meningen och bryta ner uttryck i enklare delar. Men under den lexikala analysfasen vet kompilatorn inte eller har tillgång till dessa ”enskilda delar”. Snarare måste den först identifiera och hitta dem, och sedan göra arbetet med att dela upp texten i enskilda bitar.

När vi till exempel läser en mening från Shakespeare som To sleep, perchance to dream., vet vi att mellanslag och skiljetecken delar upp ”orden” i en mening. Detta är, självklart, eftersom vi har utbildats för att läsa en mening, ”lex” det, och tolka det för grammatik.

men för en kompilator kan samma mening se ut så här första gången den läser den: Tosleepperhachancetodream. När vi läser den här meningen är det lite svårare för oss att bestämma vad de faktiska ”orden” är! Jag är säker på att vår kompilator känner på samma sätt.

Så, hur hanterar vår maskin detta problem? Tja, under den lexiska analysfasen i kompileringsprocessen gör den alltid två viktiga saker: Den skannar koden och utvärderar den sedan.

arbetet med skanning och utvärdering kan ibland klumpas ihop i ett enda program, eller det kan vara två separata program som är beroende av varandra; det är egentligen bara en fråga om hur någon complier råkade utformas. Programmet inom kompilatorn som ansvarar för att göra arbetet med skanning och utvärdering kallas ofta lexer eller tokenizer, och hela lexikal analysfasen kallas ibland processen för lexing eller tokenizing.

för att skanna, för att läsa

det första av de två kärnstegen i lexikal analys är skanning. Vi kan tänka på skanning som arbetet med att faktiskt ”läsa” lite inmatningstext. Kom ihåg att den här inmatningstexten kan vara en sträng, mening, uttryck eller till och med ett helt program! Det spelar ingen roll, för i den här fasen av processen är det bara en jätte blob av tecken som inte betyder någonting ännu, och är en sammanhängande Bit.

Låt oss titta på ett exempel för att se hur exakt detta händer. Vi använder vår ursprungliga mening, To sleep, perchance to dream., som är vår källtext eller källkod. Till vår kompilator kommer denna källtext att läsas som inmatningstext som ser ut som Tosleep,perchancetodream., som bara är en sträng av tecken som ännu inte har dechiffrerats.

det första som vår kompilator måste göra är att faktiskt dela upp den texten i sina minsta möjliga bitar, vilket gör det mycket lättare att identifiera var orden i texten faktiskt är.

det enklaste sättet att dyka upp en jätte bit text är genom att läsa den långsamt och systematiskt, ett tecken i taget. Och det är precis vad kompilatorn gör.

ofta hanteras skanningsprocessen av ett separat program som kallas skannern, vars enda jobb det är att göra arbetet med att läsa en källfil/text, ett tecken i taget. För vår skanner spelar det ingen roll hur stor vår text är; allt det kommer att se när det ”läser” vår fil är ett tecken i taget.

här är vad vår Shakespeare-mening skulle läsas som av vår skanner:

process, steg 2.

vi märker att To sleep, perchance to dream. har delats upp i enskilda tecken av vår skanner. Dessutom behandlas även mellanrummen mellan orden som tecken, liksom skiljetecken i vår mening. Det finns också ett tecken i slutet av denna sekvens som är särskilt intressant: eof. Detta är tecknet ”end of file”, och det liknar tabspace och newline. Eftersom vår källtext bara är en enda mening, när vår skanner kommer till slutet av filen (i detta fall slutet på meningen), läser den Slutet på filen och behandlar den som ett tecken.

så i själva verket, när vår skanner läste vår inmatningstext, tolkade den den som enskilda tecken vilket resulterade i detta: .

nu när vår skanner har läst och delat upp vår källtext i sina minsta möjliga delar, kommer det att ha en mycket lättare tid att räkna ut” orden ” i vår mening.

därefter måste skannern titta på dess uppdelade tecken i ordning och bestämma vilka tecken som är delar av ett ord och vilka som inte är. För varje tecken som skannern läser markerar den linjen och positionen för var tecknet hittades i källtexten.

bilden som visas här illustrerar denna process för vår Shakespeare-mening. Vi kan se att vår skanner markerar linjen och kolumnen för varje tecken i vår mening. Vi kan tänka på linje-och kolumnrepresentationen som en matris eller en uppsättning tecken.

Kom ihåg att eftersom vår fil bara har en enda rad i den, lever allt på rad 0. Men när vi arbetar oss igenom meningen ökar kolumnen för varje tecken. Det är också värt att nämna att eftersom vår skanner läser spacesnewlineseof och alla skiljetecken som tecken, visas de också i vår karaktärstabell!

När källtexten har skannats och markerats är vår kompilator redo att förvandla dessa tecken till ord. Eftersom skannern inte bara vet var spacesnewlines och eof I filen är, men också där de bor i förhållande till de andra tecknen som omger dem, kan den skanna igenom tecknen och dela dem i enskilda strängar efter behov.

i vårt exempel kommer skannern att titta på tecknen T, sedan o och sedan a space. När den hittar ett mellanslag delar den upp To I sitt eget ord — den enklaste kombinationen av tecken som är möjliga innan skannern stöter på ett mellanslag.

det är en liknande historia för nästa ord som den hittar, vilket är sleep. I det här scenariot läser det emellertid s-l-e-e-p och läser sedan ett ,, ett skiljetecken. Eftersom detta kommatecken flankeras av ett tecken (p) och ett space på vardera sidan anses kommatecken i sig vara ett ”ord”.

både ordet sleep och interpunktionssymbolen , kallas lexemer, som är substrings källtexten. Ett lexeme är en gruppering av de minsta möjliga sekvenserna av tecken i vår källkod. Lexemerna i en källfil anses vara de enskilda” orden ” i själva filen. När vår skanner är klar med att läsa de enskilda tecknen i vår fil kommer den att returnera en uppsättning lexemer som ser ut så här: .

Lägg märke till hur vår skanner tog en klump av text som inmatning, som den inte kunde läsa först och fortsatte att skanna den en gång tecken i taget, samtidigt läsa och markera innehållet. Det fortsatte sedan att dela strängen i sina minsta möjliga lexem genom att använda mellanslag och skiljetecken mellan tecken som avgränsare.

trots allt detta arbete, vid denna tidpunkt i den lexikala analysfasen, vet vår skanner ingenting om dessa ord. Visst, det dela upp texten i ord av olika former och storlekar, men vad dessa ord är skannern har ingen aning! Orden kan vara en bokstavlig sträng, eller de kan vara ett skiljetecken, eller de kan vara något helt annat!

skannern vet ingenting om själva orden eller vilken ”typ” av ord de är. Det vet bara var orden slutar och börjar i själva texten.

detta sätter oss upp för den andra fasen av lexikal analys: utvärdering. När vi har skannat vår text och brutit upp källkoden i enskilda lexemenheter måste vi utvärdera orden som skannern återvände till oss och ta reda på vilka typer av ord vi har att göra med — i synnerhet måste vi leta efter viktiga ord som betyder något speciellt på det språk vi försöker kompilera.

utvärdera de viktiga delarna

När vi har skannat vår källtext och identifierat våra lexem, måste vi göra något med våra lexeme ”ord”. Detta är utvärderingssteget för lexikal analys, som ofta kallas i komplierdesign som processen att Lexa eller tokenisera vår input.

När vi utvärderar vår skannade kod är allt vi verkligen gör att titta närmare på var och en av de lexemer som vår skanner genererade. Vår kompilator måste titta på varje lexemord och bestämma vilken typ av ord det är. Processen att bestämma vilken typ av lexeme varje ”ord” i vår text är hur vår kompilator förvandlar varje enskilt lexeme till ett token och därigenom tokeniserar vår inmatningssträng.

vi stötte först på tokens tillbaka när vi lärde oss om parse träd. Tokens är speciella symboler som ligger i kärnan i varje programmeringsspråk. Tokens, som (, ), +, -, if, else, then, hjälper alla en kompilator att förstå hur olika delar av ett uttryck och olika element relaterar till varandra. Parsern, som är central för syntaxanalysfasen, beror på att ta emot tokens från någonstans och sedan förvandlar dessa tokens till ett parsträd.

Tja, gissa vad? Vi har äntligen räknat ut ”någonstans”! Som det visar sig genereras tokens som skickas till parsern i den lexikala analysfasen av tokenizer, även kallad lexer.

Så vad exakt ser en token ut? En token är ganska enkel och representeras vanligtvis som ett par, bestående av ett tokennamn och något värde (vilket är valfritt).

till exempel, om vi tokeniserar vår Shakespeare-sträng, skulle vi sluta med tokens som mestadels skulle vara strängbokstäver och separatorer. Vi kan representera lexeme "dream” som en token som så: <string literal, "dream">. På liknande sätt kan vi representera lexeme .som token, <separator, .>.

vi märker att var och en av dessa tokens inte ändrar lexemet alls — de lägger helt enkelt till ytterligare information till dem. En token är lexeme eller lexical unit med mer detaljer; specifikt berättar den extra detaljerna vilken kategori av token (vilken typ av ”ord”) vi har att göra med.

Nu när vi har tokeniserat vår Shakespeare-mening kan vi se att det inte finns så mycket variation i typerna av tokens i vår källfil. Vår mening hade bara strängar och skiljetecken i det — men det är bara toppen av token isberg! Det finns många andra typer av” ord ” som ett lexeme kan kategoriseras i.

tabellen som visas här illustrerar några av de vanligaste tokens som vår kompilator skulle se när man läser en källfil i stort sett alla programmeringsspråk. Vi såg exempel på literals, som kan vara vilken sträng, nummer eller logik/booleskt värde som helst, liksom separators, som är vilken typ av skiljetecken som helst, inklusive hängslen ({}) och parenteser (()div>).

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 också stöta på lexemer som kan tokeniseras som identifiers, som vanligtvis är variabla namn eller saker skrivna av användaren/programmeraren för att referera till något annat, liksom , som kan vara rad-eller blockkommentarer skrivna av användaren.

vår ursprungliga mening visade oss bara två exempel på tokens. Låt oss skriva om vår mening för att istället läsa: var toSleep = "to dream";. Hur kan vår kompilator lex denna version av Shakespeare?

lexer tokenize denna mening?

Här ser vi att vi har ett större utbud av tokens. Vi har ett keyword I var, där vi förklarar en variabel och ett identifiertoSleep, vilket är det sätt som vi namnger vår variabel eller refererar till det värde som kommer. Nästa är vår =, som är en operator token, följt av strängen literal "to dream". Vårt uttalande slutar med en; separator, vilket indikerar slutet på en rad och avgränsar blanksteg.

en viktig sak att notera om tokeniseringsprocessen är att vi varken tokeniserar något blanksteg (mellanslag, nyrader, flikar, radslut etc.), inte heller vidarebefordra den till parsern. Kom ihåg att endast tokens ges till parsern och kommer att hamna i parsträdet.

det är också värt att nämna att olika språk kommer att ha olika tecken som utgör whitespace. I vissa situationer använder Python-programmeringsspråket indrag-inklusive flikar och MELLANSLAG — för att ange hur omfattningen av en funktion ändras. Så måste Python-kompilatorns tokenizer vara medveten om att i vissa situationer måste ett tab eller space faktiskt tokeniseras som ett ord, eftersom det faktiskt behöver skickas till parsern!

begränsningar av lexer vs skannern.

denna aspekt av tokenizer är ett bra sätt att kontrastera hur en lexer/tokenizer skiljer sig från en skanner. Medan en skanner är okunnig och bara vet hur man bryter upp en text i sina mindre möjliga delar (dess ”ord”), är en lexer/tokenizer mycket mer medveten och mer exakt i jämförelse.

tokenizer behöver veta invecklingarna och specifikationerna för språket som sammanställs. Om tabsär viktiga, måste det veta det; om newlines kan ha vissa betydelser på språket som sammanställs, måste tokenizer vara medveten om dessa detaljer. Å andra sidan vet skannern inte ens vad orden som den delar till och med är, mycket mindre vad de menar.

skannern för en komplierare är mycket mer språk-agnostisk, medan en tokenizer måste vara språkspecifik per definition.

dessa två delar av den lexikala analysprocessen går hand i hand, och de är centrala för den första fasen av kompileringsprocessen. Naturligtvis är olika compliers utformade på sina egna unika sätt. Vissa kompilatorer gör steget att skanna och tokenisera i en enda process och som ett enda program, medan andra delar upp dem i olika klasser, i vilket fall tokenizer kommer att ringa ut till skannerklassen när den körs.

i båda fallen är steget med lexikal analys super viktigt för kompilering, eftersom syntaxanalysfasen direkt beror på den. Och även om varje del av kompilatorn har sina egna specifika roller, lutar de sig på varandra och är beroende av varandra — precis som goda vänner alltid gör.

resurser

eftersom det finns många olika sätt att skriva och designa en kompilator finns det också många olika sätt att lära dem. Om du gör tillräckligt med forskning om grunderna i sammanställningen blir det ganska tydligt att vissa förklaringar går in i mycket mer detaljer än andra, vilket kan eller inte kan vara till hjälp. Om du tycker att du vill lära dig mer, nedan finns en mängd resurser på kompilatorer — med fokus på den lexikala analysfasen.

1. Kapitel 4-Crafting tolkar, Robert Nystrom
2. kompilator konstruktion, Professor Allan Gottlieb
3. kompilator grunderna, Professor James Alan Farrell
4. skriva ett programmeringsspråk — Lexer, Andy Balaam
5. anteckningar om hur Parsers och kompilatorer fungerar, Stephen Raymond Ferg
6. vad är skillnaden mellan en token och en lexeme?, StackOverflow