ARTIKLEN HER ER UNDER UDARBEJDELSE OG BLIVER MÅSKE ALDRIG FÆRDIG!!! (SKRIV GERNE TIL MIG, HVIS DU VIL HAVE AT ARTIKLEN BLIVER FÆRDIG!)Indledning
Med denne artikel lægger jeg virkeligt hovedet på blokken og viser alverden hvor usigeligt lidt jeg ved om basale ting indenfor datalogien. Min eneste trøst er, at rigtigt mange andre der også enten arbejder eller har arbejdet professionelt som software udviklere ved lige så lidt eller endnu mindre. Jeg skriver denne artikel på dansk fordi jeg lige nu er ved at prøve at se om min svage hjerne kan kapere at lære så teoretiske ting som compiler teori eller ej. Hvis ikke, tja, så kan jeg jo altid tage denne artikel ned igen. Men skulle det lykkes, så håber jeg på, at denne artikel kan være med til at hjælpe nogle danske udviklere til at forstå hvor enkelt og ligetil det hele egentligt er omkring scannere, parsere og compiler konstruktion - emner som har optaget mig meget i mange år, men som jeg aldrig før har haft tid og/eller energi til at prøve at skrive om.
Jeg vil tilstræbe at igennem hele beskrivelsen bruge de engelske udtryk eftersom det er dem som man får brug for at kende, når man kaster sig i lag med en eller flere af bøgerne fra litteraturlisten i bunden af artiklen.
Har du kommentarer eller spørgsmål, så
skriv gerne til mig.
Baggrund
Det er utroligt almindeligt indenfor software udvikling, at man skal forsøge at opnå en programmatisk forståelse af et eller andet dataformat. Det kan være et hvilket som helst dataformat; det kan være en binær objektfil, en tekstuel logfil, et script i et proprietært programmeringssprog eller noget helt, helt andet. I alle disse tilfælde står man med det problem, at man skal fortolke og forstå og oftest også fejlfinde inddataformatet. Dertil kan man flikke en ad-hoc, yderst grim og meget uvidende løsning sammen - som er set så ufatteligt mange gange igennem tiden - eller man kan tage sig lidt tid til at lære sig lidt basal teori om compiler konstruktion. Gør man det sidste, vil man næsten sikkert få en meget, meget mere effektiv og også meget, meget mere vedligeholdelsesvenlig løsning end hvad man ellers kan flikke sammen i selvskab med
strcmp() og andre mareridtsagtige metoder.
Indføring
Når man skal fortolke et inddataformat, hvad enten det er binært eller tekst, stammer fra en fil eller er del af en netværkssession, så gælder der, at det normalt giver mening at skelne imellem "bogstaver" (bytes, tegn), "ord" (tegnsekvenser, kommandokoder) og "sætninger" (sekvenser af ord). Tag f. eks. følgende C program:
extern int printf(const char *format, ...);
int main(int argc, const char *[])
{
int result = 0;
printf("Hello world!\n");
return result;
}
Forsøger man sig at fortolke ovenstående ved hjælp af
strcmp() og
strchr(), så finder man lynhurtigt ud af, at det er helt og aldeles umuligt at lave andet end de allermest simple sprog ved hjælp af en sådan teknik. Men forsøger man sig i stedet med de officielt foreskrevne metoder til at analysere og forstå tekster med, så vil man lynhurtigt finde, at det slet ikke er så svært igen. Faktisk er hele delen med at opnå en rudimentær forståelse, ikke den dybere forståelse, af en given datafil, med en eller anden form for harmonisk og fornuftig syntaks, utroligt triviel, når man først man har forstået de basale ting jeg her fremlægger.
Tricket er ganske enkelt: at inddele processen i faser hvoraf hver enkelt fase øger abstraktionsniveauet således at man gradvist opnår en højere, mere abstrakt forståelse af inddata:
scanner -> parser -> checker [-> generator -> optimizer]
Ovenstående viser den vanlige følge af trin i processen med at lave en compiler. Lad os lige gå hvert trin igennem:
- Scanneren, også kaldet "lexical analysis", sørger for at omdanne sekvenser af tegn til meningsfyldte ord.
- Parseren sørger for at omdanne sekvenser af ord til "sætninger" (egt. noder i et internt træ der repræsenterer hele inddatafilen).
- Checkeren, også kaldet type-checkeren, sørger for at validere noderne og dermed hele træet således at man efter dette trin ved at input er 100 procent korrekt.
- Her kunne der så være et valgfrit trin vi kan kalde "AST optimizer", hvis opgave er at lave optimeringer direkte på det syntakstræ der repræsenterer inddata.
- Generatoren, også kaldet code generatoren, står for at lave den kode som compileren omdanner sine kildefiler til: f. eks. assembler eller et andet sprog.
- Optimizeren står for at optimere den ofte meget naivt genererede kode således at denne kommer til at køre så effektivt som overhovedet muligt.
I denne artikel skal vi dog kun beskæftige os med trin 1, 2 og muligvis lidt trin 3. Resten er forholdsvist enkelt og kan læses om i snart sagt enhver bog om compilere. Det kan de tre første trin dog også, men de er langt, langt mere brugbare for den almindelige software udvikler end de andre trin er. Og denne artikel henvender sig til enhver programmør der gerne vil udvide sin værktøjskasse lidt uden at tage sig en cand. scient. grad i datalogi.
Scanneren
Scanneren er den komponent der omdanner en sekvens af tegn til en sekvens af ord. Her kunne jeg supplere med lidt ligegyldigt teoretisk lir om alfabeter med mystiske græske navne og regler beskrevet i uforståelig pseudo-matematik. Men formålet med denne artikel er, at være så klar og ligetil som muligt, så det vil jeg helt holde mig fra.
Lad os tage et kig på det program vi så på ovenfor:
extern int printf(const char *format, ...);
int main(int argc, const char *[])
{
int result = 0;
printf("Hello world!\n");
return result;
}
Scannerens opgave er ganske enkelt at omdanne
tegnsekvensen som ovenstående program er, til en sekvens af ord. Bemærk gerne at jeg med overlæg har skrevet
extern int printf(const char *format, ...); i stedet for at inkludere
stdio.h. Årsagen til det er ganske enkelt, at det meget simplificerer min forklaring af hvilke ord der kommer ud af scanneren som følge af at den tygger ovenstående program igennem (her følger der et ord på hver linje):
extern
int
printf
(
const
char
*
format
,
...
)
;
int
main
(
int
argc
,
const
char
*
argv
)
{
(og så videre)
Bemærk her nogle ting:
- Et ord kan bestå af hvilken som helst tegn; her er ord der består af "(" og "printf" og "," og så videre.
- Et ord er en logisk afgrænset ting som ikke kan inddeles i noget mindre uden at man havner på niveauet hvor man kigger på enkelte tegn.
- Et ord løser halvdelen af éns opgave med at forstå teksten: har man først fået inddelt den i ord, så er resten af arbejdet nærmest ligetil.
- Kommentarer, linjeadskillelsestegn og mellemrum forsvinder undervejs; dem æder scanneren simpelthen fordi de blot gør hele arbejdet med at forstå teksten sværere.
Regulære udtryk
Du har måske stødt på
regulære udtryk før under navnet
regular expressions. Et regulært udtryk er et simpelt udtryk for hvordan man kan genkende ting og sager i f. eks. tekst. Følgende basale regulære udtryk findes:
ab Sammenkædning af 'a' og 'b' til strengen 'ab'.
a|b Valg mellem 'a' og 'b' (enten eller, ikke begge to!).
a? Nul eller en forekomst af 'a'.
a* Nul eller flere forekomster af 'a'.
a+ En eller flere forekomster af 'a'.
Ved hjælp af ovenstående kan man med programmer som
grep søge efter bestemte ord indenfor de ganske snævre rammer af hvad et regulært udtryk kan udtrykke:
grep "foo|bar" myfile.txt Finder alle forekomster af enten "foo" eller "bar" i filen "myfile.txt".
grep "(foo)+" myfile.txt Finder alle forekomster af "foo", "foofoo", "foofoofoo", etc. i filen.
grep "a?b*c+" myfile.txt Finder alle sekvenser der matcher det angivne regulære udtryk.
Regulære udtryk er meget anvendte i den første del af compileren, scanneren, fordi de lige akkurat er stærke nok til at beskrive ords struktur med, men de kan ikke bruges i parseren fordi de ikke er stærke nok til at beskrive hele (valide) sætninger. F. eks. kan man med regulære udtryk ikke sige at antallet af begyndende parenteser (() skal være lig antallet af lukkende parenteser ()) - for at kunne sige eller kræve dette, skal man op i den klasse af sprog der hedder
context free languages (sammenhængsfrie sprog).
Nondeterministic Finite Automata
Titlen dækker over noget som vi kort kan kalde
endelige ikke-deterministiske automater (NFA). Hvad er en NFA så? En NFA er en lille bitte specialiseret computer som kun har til formål at genkende ord i et sprog. Eller, rettere, at afgøre om en given sekvens af tegn består af valide ord. NFA'er kan bruges til at opdele en given datastrøm i dens bestanddele - de ord som datastrømmen består af.
Fra NFA til DFA
For at omdanne en NFA til en DFA bruger man en forholdsvist enkel algoritme som jeg nu vil forsøge at beskrive i pseudokode. Jeg hader intenst når dataloger kaster om sig med pseudo-matematiske algoritmer som ingen andre end dem selv kan forstå. Langt bedre er, at udtrykke algoritmen i ligetil pseudokode. Første trin i processen med at omdanne en NFA til en DFA er, at lave en meget uoptimal konvertering fra NFA til DFA hvorefter man så optimerer resultatet indtil det er meget effektivt:
Parseren
Parseren er den komponent der tager en strøm af ord, som scanneren har skabt, og omdanne denne til en strøm af sætninger som parseren så typisk udtrykker som et Abstrakt Syntakstræ (AST). Parseren er noget af det mest trivielle kode man kan skrive overhovedet, men personligt synes jeg at det er mega skægt at skrive parsere, så jeg har fået skrevet en del igennem årene.
Litteratur
Her følger den litteratur om compiler konstruktion som jeg selv er indehaver af:
- Building Your Own Compiler With C++, Holmes. Denne bog består mest af programlistninger til programmer man ikke længere kan få fat i.
- Compilers - Principles, Techniques, & Tools, Aho, Lam, Sethi og Ullman. Dette er den såkaldte Dragebog (pga. nogle udgaver har en drage på omslaget). Denne bog er alt for hyper-teoretisk for min smag, men alligevel bliver man nødt til at tage den frem i ny og næ da den nok er den mest komplette af bøgerne.
- Crafting a Compiler, Fischer, Cytron og LeBlanc. Dette er en solid krabat der bruger meget tid på at forklare den grundlæggende teori men samtidigt bevarer et praktisk forhold til problemstillingerne i forbindelse med at lave en compiler.
- Engineering a Compiler, 2. Edition, Cooper og Torczon. Dette er nok min p.t. yndlingsbog om compilerkonstruktion da den er meget stor og meget omfattende og alligevel formår at undgå den hyper-teoretiske stil som ses i Dragebogen.
- Modern Compiler Design, Grune, Bal, Jabobs og Langendoen. Denne bog har jeg ikke fået kigget meget i men den er vist ret god mht. optimeringsteknikker.
- Modern Compiler Implementation in Java, Appel. Også en god lille bog der bruger Java (næsten lig C#) som udviklingssprog, hvilket giver ganske pæn kode. Bogen er også ganske nem at forstå, synes jeg, hvorfor jeg allerede har haft glæde af den.
- Object-Oriented Compiler Construction, Holmes. Denne bog har jeg endnu ikke fået kigget på men kildekoden til den er ikke længere til at skaffe.
- Programming Language Processors in Java, Watt og Brown. Dette er en rigtigt god lille bog der bruger de nyeste landvindinger udi datalogien til at udvikle en lille compiler for et lille bitte sprog. Dette er min favoritbog, også selvom den skal suppleres med f. eks. Crafting a Compiler for at få maksimalt udbytte.
- Writing Compilers and Interpreters - A Software Engineering Approach, Mak. Dette er en super bog om at skrive oversættere, fortolkere og debuggere. Den har den sjældne egenskab at forfatteren faktisk kan kode pæn og elegant kode; typisk er akademiske værker så fjernt fra virkeligheden at det kræver sit hyr at forstå dem.