PingLang del 2: En Lexer


fredag 4. februar 2011 DSL PingLang C#

I del 1 ble du introdusert for det nye språket PingLang. Nå som vi har en ide om hvordan det skal se ut og hva det skal kunne gjøre så kan vi så smått begynne å implementere. Alle eksterne DSLer og andre programmeringsspråk må parses, det vil si at kildekoden til et program må analyseres for å finne struktur og mening. Og det aller første steget når man parser kode kalles leksikalsk analyse.

Leksikalsk analyse går ut på å sette sammen enkelttegn i kildekoden til ord som har betydning i språket. Til å gjøre dette implementerer vi det som ofte kalles en Lexer, men som også går under navnene Scanner og Tokenizer. Resultatet er en liste med tokens.

lexer

I dette prosjektet implementerer jeg min egen lexer, og det anbefales gjerne for alle som har lyst til å begynne med språkutvikling. Når man forstår grunnprinsippene har man derimot muligheten til å bruke verktøy som gjør mesteparten av jobben for en – såkalte parsergeneratorer. I gode gamledager brukte man ofte to programmer som heter henholdsvis Lex og Yacc, hvor Lex genererte en Lexer. I dag finnes det mange andre verktøy, og ett jeg har sett litt på er ANTLR. Men det er ikke vanskelig å implementere leksing og parsing selv, og det gir også størst kontroll.

Implementasjon

(PS: Steder i kildekoden hvor jeg bruker mye backslash og hermetegn kan bli litt rare pga. måten min fantastiske blogmotor parser teksten. I bunn av denne artikkelen finner du linker til alle filene, slik at du kan se dem i all sin prakt på Github.)

Jeg har valgt å bruke et pattern som heter Regex Table Lexer. Det er en helt generell lexer som tar som innput teksten/kildekoden som skal skannes og en tabell/liste med regulære uttrykk og token-typer. Token er en veldig enkel klasse med bare to properties: Type (jeg har valgt å bruke en int for å spesifisere type) og Text (som er en streng).

 9     public class Token
10     {
11         public Token(int type, string text)
12         {
13             Text = text;
14             Type = type;
15         }
16         public int Type { get; set; }
17         public string Text { get; set; }
18 
19         public override string ToString()
20         {
21             return string.Format("<{0},\"{1}\">",
22                 Tokens.TokenNames[Type],
23                 Text.Replace("\n", "\\n").Replace("\r", "\\r"));
24         }
25     }

En liste med Tokens er altså resultatet av den leksikalske analusen. Lexeren kommer også til å bruke noe jeg har kalt en TokenRecognizer, som er en mapping mellom en token-type og et regulært uttrykk. I tillegg kan jeg spesifisere om tokenet skal inkluderes i resultatet eller ikke ved å sette output-parameteren. Typiske tokens som ikke skal inkluderes kan være blanke tegn og kommentarer.

 9     public class TokenRecognizer
10     {
11         public TokenRecognizer(int tokenType, string regexPattern, bool output)
12         {
13             TokenType = tokenType;
14             Output = output;
15             Pattern = new Regex(regexPattern, RegexOptions.Compiled);
16 
17         }
18         public Regex Pattern { get; private set; }
19         public bool Output { get; private set; }
20         public int TokenType { get; private set; }
21     }

Og da er vi klare for å ta en titt på selve lexeren..

10     public class Lexer
11     {
12         private readonly IEnumerable<TokenRecognizer> _recognizers;
13         private string _inputBuffer;
14 
15         public Lexer(IEnumerable<TokenRecognizer> recognizers)
16         {
17             _recognizers = recognizers;
18         }
19 
20         // Will contain the result of the scan
21         public List<Token> Tokens { get; private set; }
22 
23         public void Tokenize(string input)
24         {
25             _inputBuffer = input;
26             Tokens = new List<Token>();
27 
28             while (MatchToken()); // Loop until MatchToken returns false
29 
30             // End the token stream with a special End Of File token
31             Tokens.Add(new Token(PingLang.Core.Lexing.Tokens.EOF, ""));
32         }
33 
34         private bool MatchToken()
35         {
36             foreach (var recognizer in _recognizers)
37             {
38                 var match = recognizer.Pattern.Match(_inputBuffer);
39                 if (match.Success)
40                 {
41                     if (recognizer.Output)
42                         Tokens.Add(new Token(recognizer.TokenType, match.Value));
43 
44                     // Consume the matched token from input
45                     _inputBuffer = _inputBuffer.Substring(match.Length);
46                     return true;
47                 }
48             }
49             return false;
50         }
51     }

Man oppretter Lexeren ved å sende inn en liste med TokenRecognizers. Man kaller så metoden Tokenize, og sender inn kildekoden som argument. Tokenize vil kalle metoden MatchToken inntil denne returnerer false, fordi den ikke klarer å matche flere tokens i input. Jeg legger så til et avsluttende EOF (end of file) token.

Det er verdt å merke seg at MatchToken vil loope over alle recognizerne, og vil godta det første treffet det finner. Det vil si at recognizernes rekkefølge har en betydning. Har man f.eks. et uttrykk som skal matche strengen “>>” og et annet som skal matche “>”, så er det avgjørende at det første kommer først.

Regex Table Lexer er som sagt en generell metode som kan brukes til å analysere mange språk. Men vær oppmerksom på at det er enkelte syntakser algoritmen ikke egner seg like godt for. Python f.eks., hvor innrykk har betydning for strukturen, lexes best på andre måter.

PingLang tokens

Vi står nå igjen med definisjonen av de spesifike token-typene for PingLang-språket, og recognizerne som Lexeren vil bruke. Det er på sin plass å advare deg om at koden for dette ikke er spesielt fin å se på. Den er ikke spesielt objektorientert, og inneholder mye repitisjon. Den fungerer derimot bra, og jeg bruker et lite triks som gjør at jeg ikke blir gal av det du skal se nå. Selve koden ser du på Github: Tokens.cs.

For å unngå problemet med repitisjon hadde det vært ideelt å hatt makroer i C#, slik at jeg kunne generert koden i filen Tokens.cs. C# har ikke makroer, men vi har et lite brukt verktøy som heter Text Template Transformation Toolkit (T4). Hvis jeg legger til en fil i prosjektet mitt som jeg kaller Tokens.tt, vil denne generere en Tokens.cs fil hver gang jeg lagrer. Og denne teknikken fungerte fint i dette tilfellet. Her er et lite utdrag fra tt-filen min, som er selve spesifikasjonen av token-typene i PingLang.

 37   TokenInfo[] tokens = new TokenInfo[]{
 38     new TokenInfo { token = "EOF" },
 39     new TokenInfo { token = "WS",         regex = "^([ \\t])+", dont_include = true },
 40     new TokenInfo { token = "T" ,         regex = "^[\r\n;]+"},
 41     new TokenInfo { token = "ACTOR_END" , regex = "^\\."},
 42     new TokenInfo { token = "LISTEN" ,    regex = "^listen on port"},
 43     new TokenInfo { token = "WHEN" ,      regex = "^when"},
 44     new TokenInfo { token = "MESSAGE" ,   regex = "^message"},
 45     new TokenInfo { token = "PRINT" ,     regex = "^print"},
 46     new TokenInfo { token = "PINGED" ,    regex = "^pinged"},
 47     new TokenInfo { token = "STARTING" ,  regex = "^starting"},
 48     new TokenInfo { token = "PING" ,      regex = "^ping"},
 49     new TokenInfo { token = "WAIT" ,      regex = "^wait"},
 50     new TokenInfo { token = "SEND" ,      regex = "^send"},
 51     new TokenInfo { token = "TO_PORT" ,   regex = "^to port"},
 52     new TokenInfo { token = "ERROR" ,     regex = "^error"},
 53     new TokenInfo { token = "COUNT" ,     regex = "^count every"},
 54     new TokenInfo { token = "RESET" ,     regex = "^reset counter"},
 55     new TokenInfo { token = "COUNTER" ,   regex = "^counter"},
 56     new TokenInfo { token = "END" ,       regex = "^end"},
 57     new TokenInfo { token = "GT" ,        regex = "^\\>"},
 58     new TokenInfo { token = "ID" ,        regex = "^([a-zA-Z])+([\\w\\-])*"},
 59     new TokenInfo { token = "COMMENT" ,   regex = "^[(\\/\\/)#][^\\r\\n]*", dont_include = true },
 60     new TokenInfo { token = "INT" ,       regex = "^(\\d)+"},
 61     new TokenInfo { token = "STRING" ,    regex = "^\"[^\\r\\n\"]*\""},
 62     new TokenInfo { token = "PROGRAM" }
 63   };

Og da er egentlig lexeren ferdig. Vil du se flere detaljer, og kanskje bruke dette som utgangspunkt for din egen lexer, kan du ta en titt på github her, hvor du finner alle filene.

Til slutt to ord om testing. En lexer egner seg utmerket til enhetstester, og det anbefales på det sterkeste. I blogposten om strømlinjeformede enhetstester inkluderte jeg en test av en lexer. For den faktiske testkoden av PingLang-lexeren kan du se her.

Opprummering

I del 2 har vi tatt første steg for å implementere PingLang, som var å lage en Lexer. Man må ikke gjøre dette for hånd – det finnes mange verktøy som kan hjelpe deg – men det er ikke vanskelig å gjøre selv heller. Lexeren tar tekst skrevet i språket vi lager, og returnerer en liste med ord eller byggestener, såkalte tokens, som vi kan jobbe videre med. Denne listen vil gjøre det enklere for oss å analysere den faktiske meningen i koden. I de neste artiklene i serien vil vi gjøre nettopp dette.


comments powered by Disqus