torsdag 24. februar 2011 DSL PingLang C#
Dette er del 4 i en dokumentarserie hvor jeg går gjennom hvordan man implementerer et såkalt domenespesifikt språk (DSL). Vil du se språket i aksjon kan du ta en titt på teaseren.
I del 1 ble du introdusert for mitt nye språk PingLang. I del 2 utviklet jeg en lexer, som tok som innput en PingLang-fil og returnerte en liste med token-objekter. Og i del 3 tok vi et lite steg tilbake og du fikk se en formell definisjon av syntaksen i PingLang. Nå er det på tide å implementere parseren, som tar token-listen fra del 2 og produserer det vi kaller for et abstrakt syntakstre (AST).
En parser har to oppgaver. For det første skal den validere koden den parser, og melde fra om eventuelle syntaks-feil. Om syntaksen er ok må parseren i tillegg produsere en representasjon av koden som det er lett å jobbe videre med. Denne strukturen kalles et abstrakt syntakstre (AST). Studer illustrasjonen ovenfor for å forstå hva en AST inneholder, det sier mer enn jeg kan gjøre med tusen ord.
Selve implementasjonen av AST er en veldig enkel, rekursiv klasse som inneholder en referanse til den tokenen den representerer, samt en liste med undernoder.
10 public class AST 11 { 12 public Token Token {get; private set;} 13 public List<AST> Children {get; private set;} 14 15 public AST(Token token) 16 { 17 Token = token; 18 Children = new List<AST>(); 19 } 20 }
Parseren er en såkalt Recursive Descent Parser. Implementasjonen har jeg delt i to: En baseklasse som inneholder generelle metoder som kan gjenbrukes i andre parsere, og en konkret PingLang-parser. Baseklassen har jeg ikke gjengitt her, men du kan ta en titt på den på GitHub om du vil.
Den konkrete parseren er mer interessant. Den inneholder metoder som direkte mapper mot reglene fra grammar’en i del 3. Ta for eksempel regelen som sier at et PingLang-program består av null eller flere actors, muligens etterfulgt av det jeg kalte for en T (ett eller flere linjeskift eller semikolon), og avsluttet med et EOF-token.
Denne regelen er implementert i parseren i form av metoden Program:
11 /// <summary> 12 /// program : actor* T? EOF ; 13 /// </summary> 14 protected override void Program() 15 { 16 SetRoot(new Token(Tokens.PROGRAM, "")); 17 18 UntilToken(Tokens.EOF, () => 19 { 20 Actor(); 21 Consume_T(); 22 }); 23 }
SetRoot og UntilToken er hjelpemetoder fra baseklassen, men det som skjer her er at AST’ens rot-node settes til å være et PROGRAM-token, og så looper jeg over det jeg forventer å være actors inntil jeg finner en EOF-token.
La oss ta en regel til; her er koden for actorBody, og regelen er dokumentert i BNF-form i metodens kommentar:
41 /// <summary> 42 /// actorBody : T? (listenStmt|countStmt|whenBlock)* . ; 43 /// </summary> 44 private void ActorBody() 45 { 46 Consume_T(); 47 DoUntilToken(Tokens.ACTOR_END, () => 48 { 49 PreserveCurrentNode(() => 50 { 51 switch (CurrentToken.Type) 52 { 53 case Tokens.LISTEN: ListenStmt(); break; 54 case Tokens.COUNT: CountStmt(); break; 55 case Tokens.WHEN: WhenBlock(); break; 56 default: ThrowParseException("Unexpected actor body"); break; 57 } 58 }); 59 }); 60 }
Det er ikke nødvendig at du skjønner detaljene her før du får behov for å implementere din egen parser. Min bruk av lambda-uttrykk bør gjøre koden leser-vennlig, men detaljene er godt skjult. Prinsippet er at enhver regel fra grammaren har en tilsvarende metode i parseren. Dette er den beste måten å implementere en ryddig parser på.
Legg også merke til at ActorBody vil validere input i form av at den vil kaste en exception om den støter på en token-type den ikke forventer.
La oss se på en av undernodene til ActorBody også, f.eks. CountStmt:
72 /// <summary> 73 /// countStmt : COUNT INT unit T? ; 74 /// </summary> 75 private void CountStmt() 76 { 77 AddCurrentTokenAndSetAsCurrentNode(Tokens.COUNT); 78 AddCurrentToken(Tokens.INT); 79 Unit(); 80 Consume_T(); 81 }
CountStmt består av to eller tre terminals (angitt med store bokstaver) og én underregel (unit). La oss dykke ned i implementasjonen av unit også:
83 /// <summary> 84 /// unit : 'second'|'seconds' ; 85 /// </summary> 86 private void Unit() 87 { 88 if (IsCurrentOneOf("second", "seconds")) 89 AddCurrentToken(Tokens.ID); 90 else 91 ThrowParseException("Unexpected unit literal"); 92 }
Her ser du hvordan parseren validerer at en av de gyldige beskrivelsene av en unit er brukt.
Jeg håper dette var en ok smakebit på en parserimplementasjon. Jeg har ikke forklart særlig nøye hvordan parseren fungerer, men en slik beskrivelse kan du finne mange andre steder. Og velger du å benytte en parser generator vil du ikke måtte implementere din egen engang – den vil da bare basere seg på grammaren du definerer.
Det viktige er at parseren validerer kildekoden, og at den produserer et tre som vi kan jobbe videre med når vi skal kjøre programmet.
Den fullstendige parseren kan du se her.
For ordens skyld vil jeg ta med et par tester også. En parser er svært godt egnet for enhetstesting, og jeg ville aldri forsøkt å implementere en uten.
I det første eksempelet kontrollerer jeg at parseren klarer å finne en syntaks-feil i en liten PingLang-kodesnutt.
78 [Test] 79 public void Test_unexpected_event() 80 { 81 typeof(Exception).ShouldBeThrownBy(() => 82 { 83 var parser = new Parser(new Lexer(Tokens.All)); 84 parser.ConstructTree( 85 @"Pinger 86 listen on port 9876 87 when earthquake print ""Foo""." 88 ); 89 }, 90 ex => ex.Message.Equals("Unexpected event spec <ID,\"earthquake\">")); 91 }
Den neste testen parser et gyldig PingLang-program, og her kontrollerer jeg den resulterende AST’en.
14 [Test] 15 public void Tiny() 16 { 17 var parser = new Parser(new Lexer(Tokens.All)); 18 parser.ConstructTree( 19 @"Ponger when pinged print ""Pong""." 20 ); 21 parser.AST.Children.Count.ShouldEqual(1); 22 var actor = parser.AST.Children[0]; 23 actor.Token.Type.ShouldEqual(Tokens.ID); 24 actor.Token.Text.ShouldEqual("Ponger"); 25 26 var eventHandler = actor.Children[0]; 27 eventHandler.Token.Type.ShouldEqual(Tokens.WHEN); 28 eventHandler.Children[0].Token.Type.ShouldEqual(Tokens.PINGED); 29 eventHandler.Children[1].Token.Type.ShouldEqual(Tokens.PRINT); 30 eventHandler.Children[1].Children[0].Token.Text.ShouldEqual("\"Pong\""); 31 }
Parseren er nå ferdig, men foreløpig har vi kun brydd oss med syntaksen i PingLang, og ikke snakket så mye om semantikk – dvs. hva syntaksen betyr. Videre i denne serien vil jeg fortelle deg hva en semantisk modell er for noe, hvordan vi kan lage en slik basert på AST’en, og hvordan den kan brukes til å utføre programmererens intensjon.