Øyvind Fanebust (@oyvindfanebust) er et aktivt medlem av utviklermiljøet i Bergen. Han sitter blant annet i styret i NNUG, og er med og arrangerer Booster-konferansen (tidligere ROOTS).
Øyvind har en spesiell forkjærlighet for domenespesifike språk – såkalte DSL’er. I dagens blogpost demonstrerer han i detalj hvordan man ganske enkelt kan lage en DSL ved hjelp av en parserkombinator i C#.
Hvem er du?
Systemutvikler med lidenskap for alt som har med programvareutvikling å gjøre.
Hva er jobben din?
Lead developer hos Frende Forsikring AS.
Hva kan du?
Jobber mye med webapplikasjoner .NET / C#, der jeg jobber med alt fra å kartlegge behov, lage arkitektur og utvikle alle deler av løsningen. Har også en brennende interesse for domenespesifikke språk.
Hva liker du best med yrket ditt?
Å hele tiden måtte vri hjernen for å løse nye problemer.
Parsing av domenespesifikke språk med C# og Sprache
Language shapes the way we think, and determines what we can think about. - Benjamin Lee Whorf
Jeg har siden begynnelsen av oktober vært hjemme i pappaperm, så da Torbjørn spurte om jeg hadde lyst til å fylle en luke i julekalenderen hans tenkte jeg at jeg på en eller annen måte måtte klare å vinkle posten inn på dette temaet. Siden det andre temaet jeg hadde veldig lyst til å skrive noe om var domenespesifikke språk (DSL-er) bestemte jeg meg for å lage BabyTalk; et domenespesifikt språk for å programmere babysimulatorer.
En babysimulator er en dukke som vordende foreldre kan bruke til å forberede seg på å ta vare på en baby (se for eksempel RealCare Baby). En babysimulator kan for eksempel simulere barnegråt når babyen har et behov; for eksempel når babyen er sulten, og slutte å gråte når behovet er møtt; for eksempel når babyen har fått mat.
Et domenespesifikt språk kan i følge Martin Fowler defineres på følgende måte.
et programmeringsspråk med begrenset uttrykksfullhet fokusert på et bestemt domene
Vi skal altså lage et programmeringsspråk for et spesifikt domene, nemlig babysimulatorer. Språket kan utelukkende benyttes til å programmere babysimulatorer, en kan altså ikke generere Fibonacci-sekvenser med BabyTalk. Det er dette som menes med begrenset uttrykksfullhet. For en grundig innføring i alt som har med domenespesifikke språk å gjøre anbefaler jeg Fowler sin bok Domain Specific Languages. I løpet av posten kommer jeg til å lenke til teknikkene jeg har benyttet for å lage DSL-en.
Kravene til BabyTalk er følgende:
- En skal kunne definere et sett med tilstander babyen kan være i. Eksempler på slike tilstander er “glad”, “trøtt” eller “har full bleie”.
- En skal kunne definere overganger mellom tilstandene der en spesifiserer hvilke hendelser som gjør at babyen går over i en annen tilstand. For eksempel skal en kunne definere en overgang fra tilstanden “trøtt” der hendelsen “blir bysset” fører til at babyen går over i tilstanden “sover”.
- En skal kunne definere et tidsskjema over hendelser som oppstår i et gitt intervall. For eksempel må det være mulig å si at hendelsen “er søvnig” skal utløses hver 3. time eller hvert 30. minutt.
- Et viktig krav er at det må være relativt enkelt for en person med en viss teknisk innsikt både å forstå og skrive simulatorprogrammer.
Når en skal lage en DSL vil det i de fleste tilfeller være lurt å lage en såkalt semantisk modell. En semantisk modell er ikke så skummelt som det høres ut som, i bunn og grunn dreier det seg om noe så kjedelig som en API skrevet i språket som benyttes til å parse DSL-en. I vårt tilfelle er den semantiske modellen en objektmodell i C#.
Jeg har bestemt meg for å modellere BabyTalk som en tilstandsmaskin (State Machine). For å kunne lage en tilstandsmaskin som kan konfigurasjonstyres har jeg benyttet en teknikk som Martin Fowler kaller tilpassbar modell. Objektmodellen vår definerer et skjelett for tilstandsmaskinen og blir konfigurert av data fra DSL-skriptene.
I vår semantiske modell innkapsler State klassen en tilstand samt alle hendelser som utløser overgang til andre tilstander. Metoden “AddTransition” brukes til å konfigurere modellen med hendelser og tilstander som metoden “Trigger” bruker når den skal bytte til en annen tilstand.
public class State
{
public string Name { get; private set; }
private readonly Dictionary<string, State> _transitions;
public State(string name)
{
Name = name;
_transitions = new Dictionary<string, State>();
}
public void AddTransition(Transition transition)
{
_transitions.Add(transition.Event, transition.State);
}
public State Trigger(string @event)
{
if(!_transitions.ContainsKey(@event))
{
return this;
}
return _transitions[@event];
}
}
Baby klassen holder styr på hvilken tilstand babyen til en hver tid befinner seg i og har metoder for å trigge overganger mellom hendelser. Den holder også styr på tidsinnstilte hendelser ved hjelp av en “planlegger” (grensesnittet IScheduleEvents).
public class Baby
{
private readonly IScheduleEvents _scheduler;
public string Name { get; private set; }
public State State { get; set; }
public Baby(IScheduleEvents scheduler, string name)
{
_scheduler = scheduler;
_scheduler.EventTriggered += Trigger;
Name = name;
}
public void Trigger(string @event)
{
State = State.Trigger(@event);
}
public void ScheduleEvent(string @event, TimeSpan interval)
{
_scheduler.Schedule(@event, interval);
}
}
public interface IScheduleEvents
{
event Action<string> EventTriggered;
void Schedule(string @event, TimeSpan interval);
}
I det følgende eksempelet definerer vi den svært klossete babyen “Bumpy”. Bumpy har to tilstander; happy og angry. I tilstanden happy definerer vi en overgang til tilstanden angry når hendelsen head_bumped inntreffer. I tilstanden angry definerer vi en overgang tilbake til happy når hendelsen comforted inntreffer. Hendelsenhead_bumped inntreffer hvert tiende minutt. Bumpy sin tilstand er i utgangspunktet happy.
var happyState = new State("happy");
var angryState = new State("angry");
happyState.AddTransition("head_bumped", angryState);
angryState.AddTransition("comforted", happyState);
var baby = new Baby(_fakeScheduler, "Bumpy") { State = happyState };
baby.ScheduleEvent("head_bumped", TimeSpan.FromMinutes(10));
Dersom vi simulerer at hendelsen head_bumped blir trigget, ser vi at babyen går over i tilstanden angry.
_fakeScheduler.SimulateTriggeringOf("head_bumped");
Assert.That(baby.State.Name, Is.EqualTo("angry"));
Når babyen får trøst, med andre ord når hendelsen comforted inntreffer, går babyen tilbake til tilstanden happy.
baby.Trigger("comforted");
Assert.That(baby.State.Name, Is.EqualTo("happy"));
Modellen vår tilfredsstiller kravene om at en skal kunne definere hendelser, overganger og lage tidskjema. Måten vi definerer babysimulatoren på når vi bruker den semantiske modellen direkte gjør det derimot ikke særlig lett å forstå intensjonen bak koden, eller å skjønne hvordan alt henger sammen.
Her er en annen måte å definere den samme babysimulatoren på:
baby Bumpy
events
trigger head_bumped every 10 minutes
end
state happy
switch to angry when head_bumped
end
state angry
switch to happy when comforted
end
end
Definert som en DSL blir intensjonen bak koden straks mye klarere. Målet mitt er at at vi basert på denne syntaksen kan populere den semantiske modellen i eksempelet over. For å få til dette trenger vi en parser.
Å implementere en DSL
Det finnes flere alternative måter å parse en DSL på. En kan skrive en parser fra grunnen av, noe som ikke er spesielt vanskelig men krever en del repetativ kode og gjør det vanskelig å skjønne helheten. Et annet alternativ er å benytte en såkalt parser generator og få generert kode for en parser. Det finnes mange parsergeneratorer tilgjengelig og flere av de er svært kraftige. (Antlr er en mye brukt parser generator som er tilgjengelig både for Java og .NET). Problemet med parser generatorer er at de typisk krever et ekstra kompileringssteg for å generere parseren. Dette gjør at de kan være litt krøkkete å jobbe med. Et tredje alternativ er en parserkombinator og det er en slik løsning jeg har valgt å benytte i dette eksempelet.
En parserkombinator er en måte å bygge parsere på der en setter sammen stadig mer kompliserte parsere av enklere parsere. For eksempel kan en sette sammen en tekststrengparser og en tallparser til en parser som først matcher en tekststreng og så et tall. Parserkombinatorer er mye brukt i funksjonelle språk. Det mest kjente eksempelet jeg kan komme på er Parsec, en parserkombinator for Haskell (Parsec er også portet til blant annet F#).
Sprache er et parserkombinatorbibliotek som gjør det relativt enkelt å bygge parsere ved hjelp av C#. Selv om det ikke kan måle seg med tunge parser generatorer når en skal lage mer komplekse språk er det etter min mening velegnet til enkle domenespesifikke språk.
Sprache gjør det enkelt å parse strukturert tekst til en datastruktur som matcher strukturen på teksten. Det er derimot ikke fullt så lett å populere en struktur som ikke har samme hierarkiske oppbygning. Dette gjelder blant annet den semantiske modellen vår. Jeg velger derfor å bruke Sprache til å populere dataklasser som jeg deretter bruker til å fylle den semantiske modellen.
Når en skal skrive en parser synes jeg ofte at det er letterst å starte “innerst” og arbeide seg utover. Jeg begynner derfor med å definere paseren for en overgang til en ny tilstand basert på en hendelse.
switch to angry when head_bumped
Når jeg skal parse en overgang begynner jeg med å parse nøkkelordene “switch to”. I eksempelet under bruker jeg Sprache til å lage en parser som prøver å matche denne tekststrengen. Metoden “Token” gjør at parseren ignorerer eventuelle mellomrom før og etter tekststrengen.
Parse.String("switch to").Token()
Alle stikkord kan i grunn parses på akkurat samme måte så jeg lager en metode som tar inn en tekststreng og returenerer en parser.
private static Parser<IEnumerable<char>> Keyword(string keyword)
{
return Parse.String(keyword).Token();
}
Deretter trenger vi å matche navnet på tilstanden vi skal bytte til når hendelsen oppstår. Jeg ønsker at en tilstand skal identifiseres med bokstaver eller tall og benytter derfor den innebygde parseren “LetterOrDigit”. Identifikatoren kan også inneholde understrek, så jeg benytter metoden “Or” til å kombinere “LetterOrDigit” parseren med en parser som matcher understrek. Jeg ønsker at identifikatoren skal inneholde minst ett tegn og vil gjerne ha resultatet ut som en tekststreng. Dette får jeg til ved å benytte metodene “AtLeastOnce” og “Text”. Alle identifikatorer i BabyTalk har samme struktur. Jeg lagrer derfor denne parseren i en egen variabel.
var id = Parse.LetterOrDigit.Or(Parse.Char('_')).AtLeastOnce().Text().Token()
Parseren for “when” stikkordet lages på samme måte som parseren for “switch to” stikkordet. Da er vi klare for å sette sammen alt til en parser.
var transitionStatement = Keyword("switch to")
.Then(switchTo => id
.Then(stateName => Keyword("when")
.Then(when => id
.Then(eventName => Parse.Return(
new TransitionElement(stateName, eventName))))));
Jeg synes ikke at denne typen nøsting gir særlig lesbar kode. Noen smarte hoder har imidlertid funnet ut at ved å implementere Linq-metodene “From” og “Select” kan en utnytte C# sitt “syntaktiske sukker” for Linq-uttrykk. På denne måten kan parseren skrives sekvensielt og blir etter min mening mye mer lesbar.
var transitionStatement = from switchTo in Keyword("switch to")
from state in id
from when in Keyword("when")
from @event in id
select new TransitionElement(state, @event);
Nå som vi er ferdige med å parse overgangen kan vi gå videre til selve tilstanden.
state happy
...
...
end
Når vi skal parse seksjonen for en tilstand bruker vi mange av de samme teknikkene som over. I tillegg til å matche stikkordet “state” og navnet på tilstanden benytter vi her transitionStatement, parseren vi laget over. Metoden “Many” gjør at en vil forsøke denne parseren mange ganger og lagre overgangene i en enumerering. Resultatet er et element som representerer en tilstand med et sett hendelseslyttere.
var stateBlock = from state in Keyword("state")
from name in id
from transitions in transitionStatement.Many()
from end in Keyword("end")
select new StateElement(name, transitions);
Tidsinnstilte hendelser er ikke mye mer kompliserte å parse.
trigger head_bumped every 10 minutes
Intervallet for tidsinnstilte hendelser kan defineres enten i minutter eller timer. Her bruker vi “Or” metoden til å matche enten “minutes” eller “hours”.
var eventTriggerStatement =
from trigger in Keyword("trigger")
from @event in id
from every in Keyword("every")
from number in Parse.Number.Text().Token()
from timeType in (Keyword("minutes").Or(Keyword("hours"))).Text()
select new ScheduledEventElement(@event, timeType, int.Parse(number));
Hendelsesseksjonen ser omtrent ut som tilstandsseksjonen bare enda enklere.
events
...
...
end
Her benytter vi igjen metoden “Many” til å hente ut alle tidsintstilte hendelser.
var eventsBlock = from events in Keyword("events")
from statements in eventTriggerStatement.Many()
from end in Keyword("end")
select statements;
Da var tiden kommet til rotseksjonen “baby”.
baby Bumpy
...
...
end
Det eneste nye her er måten jeg gjør hendelsesblokken valgfri på. Siden en parser alltid er nødt til å returnere et resultat må jeg bruke metoden “Or” til å si at dersom “eventsBlock” parseren ikke matcher, skal en tom liste returneres. Jeg har laget en enkel utvidelsesmetode for parsere som returnerer enumerables. Dermed kan jeg i stedet gjøre et kall til metoden “Optional” på eventsBlock, noe jeg synes er litt mer lesbart.
var babyBlock = from baby in Keyword("baby")
from babyName in id
from eventTriggers in eventsBlock.Optional()
from states in stateBlock.Many()
from end in Keyword("end")
select new BabyElement(babyName, eventTriggers, states);
// ...
public static Parser<IEnumerable<T>> Optional<T>(this Parser<IEnumerable<T>> parser)
{
return parser.Or(Parse.Return(new T[0]));
}
Det eneste som gjenstår nå er å populere den semantiske modellen med resultatet av parsingen. Koden for å gjøre dette er i hovedsak nokså grei. Vi begynner med å definere en symboltabell med alle tilstandsobjektene. Jeg benytter en Dictionary der nøkkelen er navnet på tilstanden og verdien er selve tilstandsobjektet.
var stateSymbolTable = babyElement.StateElements.ToDictionary(s => s.Name, s => new State(s.Name));
Deretter opprettes babyobjektet og starttilstanden settes til den første definerte tilstanden.
var baby = new Baby(_scheduler, babyElement.Name){ State = stateSymbolTable[babyElement.InitialStateName]};
Tidsinnstilte hendelser legges til ved å løpe igjennom alle elementene og kalle metoden “Schedule” på den semantiske modellen.
foreach (var scheduledEventElement in babyElement.ScheduledEventElements)
{
var scheduledEvent = new ScheduledEvent(scheduledEventElement.Event, scheduledEventElement.Interval);
baby.Schedule(scheduledEvent);
}
Når vi skal opprette overgangene mellom tilstander benyttes symboltabellen til å slå opp kilde- og måltilstand.
foreach (var stateElement in babyElement.StateElements)
{
var state = stateSymbolTable[stateElement.Name];
foreach (var transitionElement in stateElement.TransitionElements)
{
var targetState = stateSymbolTable[transitionElement.StateName];
var transition = new Transition(transitionElement.Event, targetState);
state.AddTransition(transition);
}
}
Da kan vi omsider teste det ferdige resultatet.
var parser = new BabyParser();
var translator = new Translator(_fakeScheduler);
var babyElement = parser.ParseBaby(File.ReadAllText("Bumpy.bt"));
var baby = translator.Translate(babyElement);
Assert.That(baby.State.Name, Is.EqualTo("happy"));
_fakeScheduler.SimulateTriggeringOf("head_bumped");
Assert.That(baby.State.Name, Is.EqualTo("angry"));
baby.Trigger("comforted");
Assert.That(baby.State.Name, Is.EqualTo("happy"));
All kildekoden jeg benytter i denne posten er tilgjengelig på github.
Jeg håper at jeg med denne posten har vist at det ikke trenger å være særlig vanskelig å lage enkle parsere og at noen kanskje har blitt inspirert til å prøve å eksperimentere litt med domenespesifikke språk. Flere poster om temaet kommer forhåpentligvis til å dukke opp med jevne mellomrom på den nye bloggen min “The Domain Linguist”.
Programmeringsbloggen
