Ok, mam już dobrze zdefiniowaną gramatykę wykonywalnego DSLa i jasno postawiony cel – stworzenie jego kompilatora. Teraz mogę sukcesywnie realizować kolejne kroki, które doprowadzą mnie do osiągnięcia tego celu. Dzisiaj zajmę się implementacją parsera sformułowanej ostatnio gramatyki. A pomoże mi w tym pewna genialna biblioteka.
Tokeny
Zanim zaczniemy przetwarzać tekst, powiedzmy sobie, co chcemy z niego wyłuskać. Jak pisałem ostatnio, w moim DSLu występują trzy rodzaje konstrukcji:
- literały,
- wywołania funkcji,
- zestawy instrukcji (wywołań funkcji).
Konstrukcje te to najmniejsze kawałki, na jakie chcę podzielić wejściowy DSL, czyli tokeny. Dla każdego tokena stworzyłem dedykowaną klasę. A jako że dwa rodzaje tokenów mogą być argumentami funkcji, dorzuciłem interfejs IFunctionArgumentToken:
interface IFunctionArgumentToken
{ }
Natomiast same tokeny wyglądają tak:
Literał
class Literal : IFunctionArgumentToken
{
string Value { get; set; }
}
Literał to na razie po prostu napis. Interpretacją tego napisu, czyli przetłumaczeniem go na wartość konkretnego typu, będę się martwił później.
Wywołanie funkcji
class FunctionCall : IFunctionArgumentToken
{
string FunctionName { get; set; }
IList<IFunctionArgumentToken> Arguments { get; set; }
}
Wywołanie funkcji zawiera nazwę funkcji i listę argumentów. Proste. Na podstawie nazwy (lub nazwy i listy argumentów, jeśli zdecyduję się wspierać przeciążanie funkcji) będę musiał określić, która konkretnie funkcja jest wołana – ale to też nie jest tematem dzisiejszego posta.
Zestaw instrukcji, czyli cały program, czyli całe drzewo tokenów
class TokenTree
{
IList<FunctionCall> FunctionCalls { get; set; }
}
No właśnie – jak nietrudno zauważyć, wynikiem parsowania będzie drzewo tokenów. O tym, że jest to drzewo i co można z nim zrobić, napiszę w kolejnym poście. A tymczasem skupmy się na uzyskaniu tego drzewa, czyli…
Parsowanie
Na jednym ze spotkań Warszawskiej Grupy .NET Marcin Malinowski (Orientman) wspomniał o pewnej bibliotece, która pozwala w przystępny sposób tworzyć parsery dowolnych (no, prawie) gramatyk. Od razu wiedziałem, że wykorzystam ją w projekcie konkursowym. Biblioteka mocno bazuje na pojęciu monad (po więcej informacji zapraszam do prezentacji Orientmana, kiedy już pojawi się na kanale grupy), dzięki czemu do definicji parserów używa się bardzo wygodnej składni. Mowa o Sprache.
Zamiast opisywać API Sprache, od razu pokażę przykłady.
Parser lierałów (LiteralParser)
Na początek rzeczy najprostsze, czyli pojedyncze znaki literałów. Ich parsery wyglądają tak:
EscapeMark = Parse.Char('\\');
LiteralDelimiter = Parse.Char('\'');
SpecialChar = EscapeMark.Or(LiteralDelimiter);
RegularChar = Parse.AnyChar.Except(SpecialChar);
Proste i czytelne, prawda? A co najważniejsze: idealnie odwzorowujące definicje zapisane w BNF (podane w poprzednim poście).
Pisząc wyżej o wygodnej składni, miałem na myśli Linq. Patrz, Czytelniku:
EscapedChar = from escapeMark in EscapeMark
from value in SpecialChar
select value;
Parser wyescapowanych znaków zjada znak escapujący (\) i znak wyescapowany, i zwraca sam znak wyescapowany. W ten prosty i wygodny sposób bez bólu zaimplementowałem wsparcie escapowania tekstu. (Ból natomiast sprawiłem językowi polskiemu…)
Reszta implementacji parsowania literałów jest nie mniej czytelna:
LiteralValue = RegularChar.Or(EscapedChar)
.Many()
.Text();
LiteralParser = (from start in LiteralDelimiter
from value in LiteralValue
from end in LiteralDelimiter
select new Literal
{
Value = value
}).Token();
Metoda Text istnieje dla wygody – zmienia parser kolekcji znaków w parser stringów. Metoda Token jest istotna – dopiero ona sprawia, że wyłuskany element jest traktowany jako token. Różnica jest taka:
- Białe znaki otaczające elementy wewnątrz tokenu nie są ignorowane.
- Białe znaki pomiędzy tokenami są ignorowane.
- Konsekwencja: gdybym LiteralDelimiter i RegularChar oznaczył jako tokeny, wynikiem parsowania ' abc ' byłoby "abc" (a powinno być " abc ").
Tym sposobem parsowanie literałów mamy za sobą. A dalej nie jest wcale trudniej – zobaczmy.
Parser wywołań funkcji (FunctionCallParser)
Jak zaznaczyłem w poprzednim poście, tutaj będziemy mieli do czynienia z rekurencją (argumentem funkcji może być wywołanie innej funkcji) – a to potrafi przysporzyć problemów podczas definicji gramatyki i implementacji jej parsera. W moim przypadku na szczęście poszło gładko – wystarczyło, że wzajemnie wywołujące się parsery dobierają się do siebie za pośrednictem metody Ref. Kompletny parser wywołań funkcji wygląda więc tak:
FunName = Parse.LetterOrDigit.AtLeastOnce().Text();
FunArgs = LiteralParser
.Or(Parse.Ref(() => FunctionCallParser))
.Many();
FunCallParser = (from name in FunName
from start in Parse.Char('(')
from args in Parse.Ref(() => FunArgs)
from end in Parse.Char(')')
select new FunctionCall
{
FunctionName = name,
Arguments = args.ToList()
}).Token();
Parser całego drzewa tokenów (TokenTreeParser)
Na koniec został najmniejszy z parserów – parsujący zestaw instrukcji, czyli zwracający całe drzewo tokenów:
TokenTreeParser = FunctionCallParser
.AtLeastOnce()
.Select(x => new TokenTree
{
FunctionCalls = x.ToList()
})
.Token();
Użycie parsera
I to wszystko. Przełożenie zapisanej w BNF definicji gramatyki na kod C# było czystą przyjemnością. Użycie TokenTreeParser wygląda tak:
TokenTree Parse(string input)
{
return TokenTreeParser.Parse(input);
}
, a kompletny kod dostępny jest tutaj.
Na dziś to wszystko; jestem o krok bliżej do implementacji własnego kompilatora. Kolejnym wyzwaniem będzie spacer po drzewie tokenów i sprawdzenie, co na nim wyrosło – zapraszam!