¿Por qué implementar un lexer como una matriz 2D y un conmutador gigante?

Estoy trabajando lentamente para terminar mi carrera, y este semestre es Compiladores 101. Estamos usando el Libro del Dragón . Poco después del curso, estamos hablando del análisis léxico y de cómo se puede implementar a través de autómatas finitos deterministas (en adelante, DFA). Configure sus diversos estados lexer, defina transiciones entre ellos, etc.

Pero tanto el profesor como el libro proponen implementarlos a través de tablas de transición que equivalen a una matriz 2d gigante (los diversos estados no terminales como una dimensión y los posibles símbolos de entrada como la otra) y una declaración de interruptor para manejar todos los terminales así como el envío a las tablas de transición si se encuentra en un estado no terminal.

La teoría está muy bien, pero como alguien que realmente ha escrito código durante décadas, la implementación es vil. No es comprobable, no es mantenible, no es legible, y es un dolor y medio para depurarlo. Peor aún, no puedo ver cómo sería remotamente práctico si el lenguaje fuera UTF. Tener un millón de entradas en la tabla de transición por estado no terminal se vuelve muy rápido.

Entonces, ¿cuál es el trato? ¿Por qué el libro definitivo sobre el tema dice hacerlo de esta manera?

¿Es realmente tan elevada la sobrecarga de las llamadas a funciones? ¿Es esto algo que funciona bien o es necesario cuando la gramática no se conoce con anticipación (expresiones regulares)? ¿O tal vez algo que maneje todos los casos, incluso si las soluciones más específicas funcionarán mejor para gramáticas más específicas?

( nota: el posible duplicado " ¿Por qué usar un enfoque OO en lugar de una declaración de interruptor gigante? " está cerca, pero no me importa el OO. Un enfoque funcional o incluso un enfoque imperativo más sensato con funciones independientes estaría bien).

Y por ejemplo, considere un lenguaje que solo tiene identificadores, y esos identificadores son [a-zA-Z]+. En la implementación de DFA, obtendría algo como:

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

(aunque algo que manejaría correctamente el final del archivo)

En comparación con lo que esperaría:

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 el código NextTokenrefactorizado en su propia función una vez que tenga múltiples destinos desde el inicio de DFA.

En la práctica, estas tablas se generan a partir de expresiones regulares que definen los tokens del lenguaje:

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

Hemos tenido utilidades para generar analizadores léxicos desde 1975 cuando se escribió lex .

Básicamente, está sugiriendo reemplazar las expresiones regulares con código de procedimiento. Esto expande un par de caracteres en una expresión regular en varias líneas de código. El código de procedimiento escrito a mano para el análisis léxico de cualquier lenguaje moderadamente interesante tiende a ser ineficiente y difícil de mantener.

La motivación para el algoritmo particular es en gran medida que es un ejercicio de aprendizaje, por lo que trata de mantenerse cerca de la idea de un DFA y mantener estados y transiciones muy explícitos en el código. Como regla, nadie escribiría manualmente ninguno de estos códigos de todos modos; usaría una herramienta para generar código a partir de una gramática. Y a esa herramienta no le importaría la legibilidad del código porque no es código fuente, es un resultado basado en la definición de una gramática.

Su código es más limpio para alguien que mantiene un DFA escrito a mano, pero un poco más alejado de los conceptos que se enseñan.

El bucle interno de:

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

Tiene muchas ventajas de rendimiento. No hay ramas en eso en absoluto, porque haces exactamente lo mismo para cada carácter de entrada. El rendimiento del compilador puede ser controlado por el lexer (que debe operar en una escala de cada carácter de entrada). Esto fue aún más cierto cuando se escribió el Libro del Dragón.

En la práctica, además de los estudiantes de CS que estudian lexers, nadie tiene que implementar (o depurar) ese ciclo interno porque es parte de la repetitiva que viene con la herramienta que construye la transitiontabla.

De memoria, hace mucho tiempo que no leo el libro, y estoy bastante seguro de que no leí la última edición, seguro que no recuerdo algo parecido a Java, esa parte fue escrita con el código está destinado a ser una plantilla, la tabla se llena con un generador de lexer como lexer. Todavía desde la memoria, había una sección sobre compresión de tablas (nuevamente desde la memoria, fue escrita de tal manera que también era aplicable a los analizadores de tablas, por lo tanto, tal vez más en el libro de lo que has visto todavía). De manera similar, el libro que recuerdo asumió un conjunto de caracteres de 8 bits, esperaría una sección sobre el manejo de un conjunto de caracteres más grande en ediciones posteriores, probablemente como parte de la compresión de la tabla. He dado una forma alternativa de manejar eso como respuesta a una pregunta SO.

Hay una ventaja segura de rendimiento al tener datos de bucle cerrado controlados en la arquitectura moderna: es bastante amigable con la caché (si ha comprimido las tablas), y la predicción de salto es lo más perfecta posible (una falla al final del lexema, tal vez una omita el cambio de envío al código que depende del símbolo; eso supone que la descompresión de su tabla se puede hacer con saltos predecibles). Mover esa máquina de estado a código puro disminuiría el rendimiento de predicción de salto y tal vez aumentaría la presión de caché.

Después de haber trabajado antes en el Libro del Dragón, la razón principal para tener palancas y analizadores de tabla es que puede usar expresiones regulares para generar el lexer y BNF para generar el analizador. El libro también cubre cómo funcionan herramientas como lex y yacc, y para que sepa cómo funcionan estas herramientas. Además, es importante que trabaje con algunos ejemplos prácticos.

A pesar de muchos comentarios, no tiene nada que ver con el estilo de código que se escribió en los años 40, 50, 60 ..., tiene que ver con obtener una comprensión práctica de lo que las herramientas están haciendo por usted y lo que tiene hacer para que funcionen. Tiene todo que ver con la comprensión fundamental de cómo funcionan los compiladores, tanto desde un punto de vista teórico como práctico.

Con suerte, su instructor también le permitirá usar lex y yacc (a menos que sea una clase de posgrado y pueda escribir lex y yacc).

Tarde a la fiesta :-) Los tokens se comparan con expresiones regulares. Como hay muchos de ellos, tiene el motor multi regex, que a su vez es DFA gigante.

"Peor aún, no puedo ver cómo sería remotamente práctico si el lenguaje fuera capaz de UTF".

Es irrelevante (o transparente). Además, UTF tiene buenas propiedades, sus entidades no se superponen ni siquiera parcialmente. Por ejemplo, el byte que representa el carácter "A" (de la tabla ASCII-7) no se usa nuevamente para ningún otro carácter UTF.

Por lo tanto, tiene un solo DFA (que es multi-regex) para lexer completo. ¿Qué mejor para anotarlo que la matriz 2d?