torsdag 17. februar 2011 DSL PingLang
Før jeg fortsetter implementasjonen av PingLang er det på tide å snakke litt om grammars – dvs. hvordan man kan beskrive syntaksen til et programmeringsspråk på en presis og formell måte. Dette er ikke noe du må gjøre for å kunne implementere et språk. For enkle språk eksisterer gjerne syntaks-reglene i hodet på utvikleren, og det kan fungere helt greit. Men en grammar kan fungere som en slags pseudo-kode, og kan gjøre det enklere å implementere språket.
For å spesifisere en grammar bruker man en notasjon som kalles Backus-Naur Form (BNF). Backus (som jeg skrev om i julekalenderen, luke 13) utviklet BNF for å spesifisere programmeringsspråket ALGOL, og hans notasjon har siden blitt en standard for å spesifisere syntaks.
Om man ønsker å bruke en såkalt parser generator for gjøre implementasjonen av et språk/DSL enklere, vil man som regel bruke BNF som et språk for å drive genereringen. Jeg gjør ikke det for PingLang, men BNF-reglene jeg skriver her vil som sagt hjelpe meg mye når jeg programmerer parseren for hånd.
Så la oss ta en titt på grammar’en til PingLang. Om vi begynner forsiktig så har vi først har vi en liste med såkalte terminals som i praksis utgjør alle nøkkelordene i PingLang.
LISTEN : 'listen on port' ; COUNT : 'count every' ; STARTING : 'starting' ; ERROR : 'error' ; PINGED : 'pinged' ; MESSAGE : 'message' ; COUNTER : 'counter' ; GT : '>' ; PRINT : 'print' ; PING : 'ping' ; RESET : 'reset counter' ; WAIT : 'wait' ; SEND : 'send' ; TO_PORT : 'to port' ;
Hvis du mener du har sett denne listen før så har du helt rett. Dette er nemlig en del av listen over mulige tokens som jeg implementerte da jeg lagde lexeren i PingLang del 2. Men det mangler noen terminals – dette var kun de som består av konstante tekststrenger. I tillegg har vi disse:
ID : ('a'..'z'|'A'..'Z')+ (\w|\-)* ;
STRING : '\"' [any char not newline]* '\"' ;
INT : '0'..'9'+ ;
T : (\r|\n|;)+ ;
Her sier jeg f.eks. at en identifikator (ID) i PingLang består av en bokstav mellom a og z, etterfulgt av et vilkårlig antall bokstaver, tall eller bindestreker. Jeg sier at en streng er alt mellom to hermetegn, sålenge det ikke er et linjeskift. Et tall (INT) er ett eller flere siffer.
Den litt spesielle terminatoren T har jeg definert til å være en eller flere linjeskift og/eller semikolon. Dette vil gjøre det litt vanskeligere å parse koden, men vil gi oss litt mere fleksibilitet når vi skal kode i PingLang. Du vil se igjen T’en i mange regler nedenfor, men forsøk å ikke henge deg for mye opp i det. De er der for å sørge for at programmereren kan legge inn et vilkårlig antall linjeskift der hvor det er naturlig.
Videre har vi et par terminals som vil bli forkastet av av lexeren, nemlig whitespace (WS) og kommentarer (COMMENT). En kommentar er noe som begynner med enten to backslasher eller et hash-symbol (både C og Ruby-stil tillat altså), og som fortsetter til første linjeskift.
WS : ( |\t)+ ; COMMENT : (\\\\|#) [any char not newline]* ;
Jeg håper du ser hvordan disse reglene begynner å gi språket vårt form. Nå følger de reglene som ikke er terminals. Disse er det ikke lexeren som er ansvarlig for – de vil bli brukt til å implementere resten av parseren (i neste del i serien).
Her er den aller første regelen, som definerer hvordan et PingLang-program ser ut:
program : actor* T? EOF ;
Et program er altså null eller flere actors, muligens etterfulgt av en T (definert tidligere som en eller flere linjeskift og/eller semikolon), etterfulgt av EOF (end of file). Vi trenger så å vite hva en actor er:
actor : T? ID actorBody ;
En actor består muligens av en T, etterfulgt av en ID (navnet på actoren), etterfulgt av en actorBody. Vi går videre til actorBody:
actorBody : T? (listenStmt|countStmt|whenBlock)* . ;
En actorBody består igjen muligens av en T, etterfulgt av null eller flere av tre ulike elementer: en listen-definisjon, en count-definisjon, eller en when-block. Til slutt avsluttes actorBody av et punktum.
Vi må fortsette å grave oss ned i reglene til vi kommer til terminals. Listen-definisjonen (listenStmt) er et eksempel på en slik regel:
listenStmt : LISTEN INT T? ;
Den begynner med en LISTEN terminal, som vi tidligere har definert til å være strenger “listen on port”. Deretter kommer et tall (INT), muligens etterfulgt av en T.
Og slik fortsetter vi til vi har definert hele språket..
countStmt : COUNT INT unit T? ;
unit : 'second'|'seconds' ;
whenBlock : WHEN eventSpec eventBody ;
eventSpec : STARTING
| ERROR
| PINGED
| MESSAGE
| COUNTER GT INT ;
eventBody : action
| action T
| T+ (action T)+ END T+ ;
action : PRINT printArgs
| PING INT
| RESET
| WAIT INT unit
| SEND STRING TO_PORT INT ;
printArgs : (INT|STRING|MESSAGE|COUNTER)* ;
Og det var det hele. Ut fra denne BNF-definisjonen kan du utlede hvordan alle gyldige PingLang-programmer kan se ut. Reglene sier ingen ting om hva de ulike tingene betyr - altså semantikken i språket – kun hva som er tillat syntaks.
Jeg står over å forklare i detalj hvordan BNF fungerer, men håper du forstod det grunnleggende. Disse reglene vil vi ta med oss videre i neste artikkel hvor jeg skal implementere PingLang-parseren. Er du interessert i å se flere grammars kan du ta en titt på Grammar Downloads, hvor du finner et hav av eksempler.