DSL z prawdziwego zdarzenia: gramatyka DSLa i wstęp do kompilatora

Ostatnio poszedłem na łatwiznę i przedstawiłem najłatwiejszy z możliwych parser DSLa. Zgodnie z obietnicą, dzisiaj zabieram się za stworzenie wykonywalnego języka DSL z prawdziwego zdarzenia. Tym razem pracę zaczynam bardziej profesjonalnie, bo od sformułowania formalnej definicji jego składni.

W poprzednim poście podałem przykładowy scenariusz użycia DSLExecutora (aplikacja wykonująca operacje matematyczne i logująca komunikaty). Pseudokod zapisu podanego przez użytkownika wyglądał tak:

 
log("Calculating...") 
sub(add(1, 2), 3) 

Taki zapis przypomina “normalne” języki programowania. Aby pokazać, że DSLExecutor pozwala na stworzenie języka przypominającego pełnoprawny język programowania, postanowiłem zaimplementować parser właśnie takiej składni. Aby jednak nie zakopać się w mnogości znaków specjalnych i rodzajów leksemów, przyjmę kilka uproszczeń.

Ale po kolei. W przytoczonym pseudokodzie można wyróżnić takie oto rodzaje konstrukcji:

• Literał, np. 1, 3,
• Wywołanie funkcji, np. add(1, 2),
• Zestaw instrukcji, czyli cały zapis.

Zdefiniujmy każdy z nich.

Literały

W przypadku literałów przewiduję dwa problemy:

Wsparcie zapisu różnych typów danych

W C# mamy do czynienia z bogatą składnią literałów. Wartości różnych typów zapisujemy w różny sposób – zapis literału definiuje jego typ. Przykłady:

• stringi: "tekst", @"tekst",
• liczby: 1, 1.0, 1.0d, 1d, 1D, 1f, 1m, 0x01,
• funkcje: (a, b) => a + b, (a, b) => { return a + b; },
• inne: true, 'c', '\u0001'…

Ktoś się nieźle napracował implementując parsowanie tego wszystkiego. Zauważmy, że większość z powyższych literałów tworzą grupy tych samych wartości tych samych typów (oba napisy, wszystkie double, obie funkcje). Ja nie potrzebuję aż tak wygodnej składni – chcę rozpoznawać literały jak najłatwiej. Dlatego postanowiłem, że każdy literał będzie zapisywany w ten sam sposób: jako dowolny tekst otoczony apostrofami. Przykłady:

 
'Calculating...' 
'1' 
'2' 

Formalnie, w notacji BNF, składnię tę można zapisać tak:

 
<literalDelimiter> ::= "'" 
<text> ::= <text> <char> | <char> 
 
<literal> ::= <literalDelimiter> <text> <literalDelimiter> 

Oczywiście wnętrze literału (token <text>), po wyłuskaniu z apostrofów, może być parsowane na potrzeby rozpoznania typu i wartości.

Escapowanie tekstu

Drugi problem to escapowanie (sorry, nie znalazłem lepszego słowa) tekstu. Co się stanie, jeśli użytkownik – w przypływie entuzjazmu – zamiast log('Calculating...') zechce zalogować: log('It's calculating!')? W najlepszym (a właściwie najgorszym) wypadku do loga trafi napis: It.

Moja składnia musi obsługiwać takie przypadki poprawnie. A że i tutaj zależy mi na prostocie, zastosuję standardowy sposób escapowania znaków specjalnych: poprzedzanie ich backslashem (\). Zauważmy, że tym samym sam backslash też stał się znakiem specjalnym. Przykłady:

 
log('It\'s calculating!') 
log('This is backslash: \\') 

Zatem finalna składnia literału przedstawia się następująco:

 
<escapingChar> ::= "\" 
<literalDelimiter> ::= "'" 
<specialChar> ::= <escapingChar> | <literalDelimiter> 
<regularChar> ::= [any char except special chars] 
 
<escapedTextChar> ::= <regularChar> |
                      <escapingChar> <specialChar> 
<escapedText> ::= <escapedTextChar> <escapedText> |
                  <escapedTextChar> 
 
<literal> ::= <literalDelimiter>
              <escapedText>
              <literalDelimiter> 

Wywołania funkcji

Ok, składnię pierwszego rodzaju konstrukcji mam gotową. Teraz wywołania funkcji.

Na początek rzecz prosta, czyli nazwa wywoływanej funkcji. Zezwólmy, aby w skład biblioteki standardowej tworzonego języka wchodziły funkcje, których nazwy zawierają jedynie litery i cyfry. Zatem:

 
<functionNameChar> ::= <letter> | <digit> 
<functionName> ::= <functionNameChar> <functionName> |
                   <functionNameChar> 

Następnie standard – nawiasy otaczające listę argumentów:

 
<functionArgs> ::= // TODO 
<functionCall> ::= <functionName> "(" <functionArgs> ")" 

Teraz sama lista argumentów, czyli… przystopujmy. Co właściwie może być argumentem funkcji? Na pewno literał. Ale też wywołanie innej funkcji. Znowu rekurencja! Trudno, zdążyłem się już z nią oswoić…

Ostatnią kwestią do wyjaśnienia jest separator argumentów funkcji – w językach C-podobnych jest to przecinek. Ale skoro i literały, i wywołania funkcji mam łatwo rozpoznawalne, to separator wydaje się zbędny – spróbuję się obyć bez niego. A więc:

 
<functionArg> ::= <literal> | <functionCall> 
<functionArgs> ::= <functionArg> <functionArgs> |
                   <functionArgs> 

Ostatecznie przykładowe wywołanie funkcji wygląda tak:

 
sub(add('1' '2') '3') 

Zestawy instrukcji

Na deser został ostatni rodzaj konstrukcji, czyli zestaw instrukcji. Jako że jedyną instrukcją w prezentowanym języku jest wywołanie funkcji, zestaw instrukcji to po prostu zestaw wywołań:

 
<batch> ::= <functionCall> <batch> | <functionCall> 

I gotowe! Operacja pokazana w przykładzie na początku posta, zapisana w opracowanej składni, wygląda tak:

 
log('Calculating...') 
sub(add('1' '2') '3') 

W tym momencie Czytelnik pewnie zadaje sobie pytanie: po co to wszystko? No właśnie, po co mi formalny zapis gramatyki? Ponieważ sformułowanie gramatyki to tylko wierzchołek góry lodowej. W następnych etapach pracy będę musiał zaimplementować:

1. Parsowanie tej gramatyki, rozkładające zapis instrukcji na pojedyncze tokeny.
2. Łączenie tokenów z odpowiadającymi im bytami z dziedziny DSLExecutora (np. wywołania funkcji z samymi funkcjami).
3. Generację bytów gotowych do wykonania, czyli wyrażeń (IExpression).

Brzmi znajomo? Dokładnie – czeka mnie implementacja kompilatora. A implementując kompilator, wolę zachować ostrożność i oprzeć się na sformalizowanych zapisach.

Hm, robi się ciekawie. Przedstawione wyżej kroki to mniej więcej tematy kolejnych wpisów – zapraszam!