Powoli pracuję nad ukończeniem studiów, a ten semestr to Kompilatory 101. Korzystamy ze Smoczej Księgi . Wkrótce w trakcie kursu mówimy o analizie leksykalnej i o tym, jak można ją wdrożyć za pomocą deterministycznych automatów skończonych (dalej DFA). Skonfiguruj różne stany leksykalne, zdefiniuj przejścia między nimi itp.
Ale zarówno profesor, jak i książka proponują wdrożenie ich za pomocą tabel przejściowych, które stanowią gigantyczną tablicę 2d (różne stany nieterminalne jako jeden wymiar i możliwe symbole wejściowe jako drugi) oraz instrukcję przełączania do obsługi wszystkich terminali a także wysyłanie do tabel przejściowych, jeśli nie są w stanie terminalnym.
Teoria jest dobra i dobra, ale jako ktoś, kto pisał kod od dziesięcioleci, implementacja jest nikczemna. Nie można go przetestować, nie można go konserwować, nie można go odczytać, a debugowanie to półtorej bólu. Co gorsza, nie widzę, jak byłoby to praktyczne, gdyby język był zdolny do UTF. Posiadanie około miliona wpisów w tabeli przejścia na stan nieterminalny staje się niespieszne w pośpiechu.
Więc o co chodzi? Dlaczego definitywna książka na ten temat mówi, żeby zrobić to w ten sposób?
Czy narzut wywołań funkcji jest tak duży? Czy jest to coś, co działa dobrze, czy jest konieczne, gdy gramatyka nie jest znana z góry (wyrażenia regularne?)? A może coś, co obsługuje wszystkie przypadki, nawet jeśli bardziej szczegółowe rozwiązania będą działać lepiej dla bardziej szczegółowych gramatyk?
( uwaga: możliwe duplikowanie „ Dlaczego warto stosować podejście OO zamiast instrukcji gigantycznego przełącznika? ” jest bliskie, ale nie dbam o OO. Funkcjonalne podejście, a nawet rozsądne imperatywne podejście z samodzielnymi funkcjami byłoby dobrze.)
Dla przykładu rozważmy język, który ma tylko identyfikatory, a są to identyfikatory [a-zA-Z]+. W implementacji DFA otrzymasz coś takiego:
private enum State
{
Error = -1,
Start = 0,
IdentifierInProgress = 1,
IdentifierDone = 2
}
private static State[][] transition = new State[][]{
///* Start */ new State[]{ State.Error, State.Error (repeat until 'A'), State.IdentifierInProgress, ...
///* IdentifierInProgress */ new State[]{ State.IdentifierDone, State.IdentifierDone (repeat until 'A'), State.IdentifierInProgress, ...
///* etc. */
};
public static string NextToken(string input, int startIndex)
{
State currentState = State.Start;
int currentIndex = startIndex;
while (currentIndex < input.Length)
{
switch (currentState)
{
case State.Error:
// Whatever, example
throw new NotImplementedException();
case State.IdentifierDone:
return input.Substring(startIndex, currentIndex - startIndex);
default:
currentState = transition[(int)currentState][input[currentIndex]];
currentIndex++;
break;
}
}
return String.Empty;
}
(chociaż coś, co poprawnie obsługiwałoby koniec pliku)
W porównaniu do tego, czego bym się spodziewał:
public static string NextToken(string input, int startIndex)
{
int currentIndex = startIndex;
while (currentIndex < startIndex && IsLetter(input[currentIndex]))
{
currentIndex++;
}
return input.Substring(startIndex, currentIndex - startIndex);
}
public static bool IsLetter(char c)
{
return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}
Po NextTokenponownym przekształceniu kodu w jego własną funkcję, gdy masz wiele miejsc docelowych od początku DFA.