Pourquoi implémenter un lexer comme un tableau 2D et un commutateur géant?

Je travaille lentement pour terminer mon diplôme, et ce semestre est Compilers 101. Nous utilisons le Dragon Book . Peu de temps dans le cours et nous parlons de l'analyse lexicale et de la façon dont elle peut être implémentée via des automates finis déterministes (ci-après, DFA). Configurez vos différents états de lexer, définissez les transitions entre eux, etc.

Mais le professeur et le livre proposent de les implémenter via des tables de transition qui équivalent à un tableau 2D géant (les différents états non terminaux comme une dimension, et les symboles d'entrée possibles comme l'autre) et une instruction switch pour gérer tous les terminaux ainsi que la répartition vers les tables de transition dans un état non terminal.

La théorie est très bien, mais en tant que personne qui a écrit du code pendant des décennies, l'implémentation est vile. Ce n'est pas testable, ce n'est pas maintenable, ce n'est pas lisible, et c'est une douleur et demie à déboguer. Pire encore, je ne vois pas comment ce serait à distance pratique si le langage était compatible UTF. Avoir un million d'entrées de table de transition par état non terminal devient vite imprudent.

Alors, quel est le problème? Pourquoi le livre définitif sur le sujet dit-il de procéder de cette façon?

Le surcoût des appels de fonction est-il vraiment si important? Est-ce quelque chose qui fonctionne bien ou est nécessaire lorsque la grammaire n'est pas connue à l'avance (expressions régulières?)? Ou peut-être quelque chose qui gère tous les cas, même si des solutions plus spécifiques fonctionneront mieux pour des grammaires plus spécifiques?

( Remarque: la duplication possible " Pourquoi utiliser une approche OO au lieu d'une déclaration de commutateur géant? " est proche, mais je ne me soucie pas de OO. Une approche fonctionnelle ou même une approche impérative plus saine avec des fonctions autonomes serait bien.)

Et à titre d'exemple, considérons un langage qui n'a que des identifiants, et ces identifiants le sont [a-zA-Z]+. Dans l'implémentation DFA, vous obtiendrez quelque chose comme:

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;
}

(bien que quelque chose qui gérerait correctement la fin du fichier)

Par rapport à ce que j'attendrais:

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'));
}

Le code étant NextTokenrefactorisé dans sa propre fonction une fois que vous disposez de plusieurs destinations depuis le début de DFA.

En pratique, ces tableaux sont générés à partir d'expressions régulières qui définissent les jetons du langage:

number := [digit][digit|underscore]+
reserved_word := 'if' | 'then' | 'else' | 'for' | 'while' | ...
identifier := [letter][letter|digit|underscore]*
assignment_operator := '=' | '+=' | '-=' | '*=' | '/=' 
addition_operator := '+' | '-' 
multiplication_operator := '*' | '/' | '%'
...

Nous avons des utilitaires pour générer des analyseurs lexicaux depuis 1975 lorsque lex a été écrit.

Vous proposez essentiellement de remplacer les expressions régulières par du code procédural. Cela développe quelques caractères dans une expression régulière en plusieurs lignes de code. Le code procédural manuscrit pour l'analyse lexicale de tout langage moyennement intéressant a tendance à être à la fois inefficace et difficile à maintenir.

La motivation de l'algorithme particulier est en grande partie qu'il s'agit d'un exercice d'apprentissage, il essaie donc de rester proche de l'idée d'un DFA et de garder les états et les transitions très explicites dans le code. En règle générale, personne n'écrirait de toute façon manuellement ce code de toute façon - vous utiliseriez un outil pour générer du code à partir d'une grammaire. Et cet outil ne se soucierait pas de la lisibilité du code car ce n'est pas du code source, c'est une sortie basée sur la définition d'une grammaire.

Votre code est plus propre pour quelqu'un qui gère un DFA manuscrit, mais un peu plus éloigné des concepts enseignés.

La boucle intérieure de:

                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;

présente de nombreux avantages en termes de performances. Il n'y a pas de branche du tout, car vous faites exactement la même chose pour chaque caractère saisi. Les performances du compilateur peuvent être gated par le lexer (qui doit fonctionner sur une échelle de chaque caractère d'entrée). C'était encore plus vrai lorsque le Dragon Book a été écrit.

En pratique, à part les étudiants CS qui étudient les lexers, personne n'a à implémenter (ou déboguer) cette boucle interne car elle fait partie du passe-partout fourni avec l'outil qui construit la transitiontable.

De mémoire, - cela fait longtemps que je n'ai pas lu le livre, et je suis presque sûr que je n'ai pas lu la dernière édition, je ne me souviens certainement pas de quelque chose ressemblant à Java - cette partie a été écrite avec le code étant destiné à être un modèle, la table étant remplie d'un générateur de lexer comme lexer. Toujours de mémoire, il y avait une section sur la compression de table (encore une fois de mémoire, elle a été écrite de telle manière qu'elle était également applicable aux analyseurs par table, donc peut-être plus loin dans le livre que ce que vous avez vu jusqu'à présent). De même, le livre dont je me souviens supposait un jeu de caractères 8 bits, je m'attendrais à une section sur la gestion d'un jeu de caractères plus important dans les éditions ultérieures, probablement dans le cadre de la compression du tableau. J'ai donné une autre façon de gérer cela comme une réponse à une question SO.

Il y a un avantage certain en termes de performances à avoir une boucle serrée pilotée dans une architecture moderne: elle est assez conviviale pour le cache (si vous avez compressé les tables), et la prédiction de saut est aussi parfaite que possible (une erreur à la fin du lexème, peut-être une manque pour le basculement de la répartition vers le code qui dépend du symbole; cela suppose que la décompression de votre table peut être effectuée avec des sauts prévisibles). Déplacer cette machine d'état vers du code pur diminuerait les performances de prédiction de saut et augmenterait peut-être la pression du cache.

Après avoir travaillé sur le Dragon Book auparavant, la principale raison d'avoir des leviers et des analyseurs pilotés par table est que vous pouvez utiliser des expressions régulières pour générer le lexer et BNF pour générer l'analyseur. Le livre couvre également le fonctionnement d'outils comme lex et yacc, et afin que vous sachiez comment ces outils fonctionnent. De plus, il est important pour vous de travailler à travers quelques exemples pratiques.

Malgré de nombreux commentaires, cela n'a rien à voir avec le style de code qui a été écrit dans les années 40, 50, 60 ..., cela a à voir avec l'acquisition d'une compréhension pratique de ce que les outils font pour vous et de ce que vous avez à faire pour les faire fonctionner. Cela a tout à voir avec la compréhension fondamentale du fonctionnement des compilateurs d'un point de vue théorique et pratique.

Si tout va bien, votre instructeur vous permettra également d'utiliser lex et yacc (à moins qu'il s'agisse d'un cours de niveau supérieur et que vous ne puissiez écrire lex et yacc).

Tard dans la soirée :-) Les jetons sont comparés aux expressions régulières. Comme il y en a beaucoup, vous avez le moteur multi regex, qui est à son tour un DFA géant.

"Pire encore, je ne vois pas comment ce serait à distance pratique si la langue était compatible UTF."

Elle n'est pas pertinente (ou transparente). Outre UTF a une belle propriété, ses entités ne se chevauchent même pas partiellement. Par exemple, l'octet représentant le caractère "A" (du tableau ASCII-7) n'est plus utilisé pour aucun autre caractère UTF.

Ainsi, vous avez un DFA unique (qui est multi-expression régulière) pour le lexeur entier. Comment mieux l'écrire que le tableau 2D?