Sto lentamente lavorando per finire la mia laurea, e questo semestre è Compilatori 101. Stiamo usando il Libro del Drago . A breve nel corso e stiamo parlando di analisi lessicale e di come può essere implementato tramite automi finiti deterministici (di seguito, DFA). Imposta i tuoi vari stati lexer, definisci le transizioni tra loro, ecc.
Ma sia il professore che il libro propongono di implementarli tramite tabelle di transizione che equivalgono a un gigantesco array 2d (i vari stati non terminali come una dimensione, e i possibili simboli di input come l'altro) e una dichiarazione switch per gestire tutti dei terminali nonché invio alle tabelle di transizione se in uno stato non terminale.
La teoria è buona, ma come qualcuno che ha scritto codice per decenni, l'implementazione è vile. Non è testabile, non è manutenibile, non è leggibile ed è un dolore e mezzo per eseguire il debug. Peggio ancora, non riesco a vedere come sarebbe remoto se la lingua fosse UTF in grado. Avere un milione circa di voci della tabella di transizione per stato non terminale diventa spiacevole in fretta.
Quindi qual è il problema? Perché il libro definitivo sull'argomento dice di farlo in questo modo?
Il sovraccarico delle chiamate di funzione è davvero così tanto? È qualcosa che funziona bene o è necessario quando la grammatica non è conosciuta in anticipo (espressioni regolari?)? O forse qualcosa che gestisce tutti i casi, anche se soluzioni più specifiche funzioneranno meglio con grammatiche più specifiche?
( note: possibile duplicato " Perché usare un approccio OO invece di una gigantesca istruzione switch? " è vicino, ma non mi interessa OO. Un approccio funzionale o un approccio imperativo ancora più salutare con funzioni standalone sarebbe bene.)
E per esempio, considera un linguaggio che ha solo identificatori e quegli identificatori sono [a-zA-Z]+ . Nell'implementazione di DFA, otterrai qualcosa del tipo:
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;
}
(sebbene qualcosa che gestisca correttamente la fine del file)
Rispetto a quello che mi aspetterei:
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'));
}
Con il codice in NextToken rielaborato nella sua funzione una volta che hai più destinazioni dall'inizio del DFA.