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

24

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.

Telastyn
fuente
55
¿Una herencia de principios antiguos (1977) de diseño de compiladores ? Hace 40 años, el estilo de codificación era muy diferente
mosquito
77
¿Cómo implementaría las transiciones de los estados de DFA? Y de qué se trata esto de terminales y no terminales, "no terminales" generalmente se refiere a las reglas de producción en la gramática, que vendrían después del análisis léxico.
10
Esas tablas no están destinadas a ser leídas por los humanos, sino que deben ser utilizadas por el compilador y funcionar muy rápidamente. Es fácil saltar alrededor de una mesa cuando se mira hacia adelante en la entrada (por ejemplo, para atrapar la recursión izquierda, aunque en la práctica la mayoría de los idiomas están diseñados para evitar eso).
55
Si una parte de su irritación proviene de saber cómo hacer un mejor trabajo y no tener la capacidad de obtener comentarios o apreciación por un enfoque que preferiría, ya que décadas en la industria nos capacitan para esperar comentarios y, a veces, apreciación, tal vez debe escribir su mejor implementación y publicarla en CodeReview.SE para obtener algo de eso para su propia tranquilidad.
Jimmy Hoffa
77
La respuesta simple es porque el lexer generalmente se implementa como una máquina de estados finitos y se genera automáticamente a partir de la gramática, y una tabla de estados es, no sorprendentemente, la más fácil y compacta como una tabla. Al igual que con el código objeto, el hecho de que no sea fácil para los humanos trabajar es irrelevante porque los humanos no trabajan con él; cambian la fuente y generan una nueva instancia.
keshlam

Respuestas:

16

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.

Kevin Cline
fuente
44
No estoy seguro de estar sugiriendo eso al por mayor. Las expresiones regulares tratarán con lenguajes arbitrarios (regulares). ¿No hay mejores enfoques cuando se trabaja con idiomas específicos? El libro toca enfoques predictivos pero luego los ignora en los ejemplos. Además, después de haber hecho un analizador ingenuo para C # hace años, no me resultó terriblemente difícil de mantener. ¿Ineficiente? claro, pero no terriblemente, dada mi habilidad en ese momento.
Telastyn
1
@Telastyn: es casi imposible ir más rápido que un DFA controlado por tabla: obtener el siguiente carácter, buscar el siguiente estado en la tabla de transición, cambiar el estado. Si el nuevo estado es terminal, emite un token. En C # o Java, cualquier enfoque que implique la creación de cadenas temporales será más lento.
Kevin Cline
@kevincline: claro, pero en mi ejemplo no hay cadenas temporales. Incluso en C, solo sería un índice o un puntero que recorre la cadena.
Telastyn
66
@JimmyHoffa: sí, el rendimiento es definitivamente relevante en los compiladores. Los compiladores son rápidos porque han sido optimizados para el infierno y viceversa. No son micro optimizaciones, simplemente no hacen trabajo innecesario como crear y descartar objetos temporales innecesarios. En mi experiencia, la mayoría del código de procesamiento de texto comercial hace una décima parte del trabajo de un compilador moderno y tarda diez veces más en hacerlo. El rendimiento es enorme cuando procesas un gigabyte de texto.
Kevin Cline
1
@Telastyn, ¿qué "mejor enfoque" tenía en mente y de qué manera esperaría que fuera "mejor"? Dado que ya tenemos herramientas de lexing que están bien probadas y producen analizadores muy rápidos (como han dicho otros, los DFA basados ​​en tablas son muy rápidos), tiene sentido usarlos. ¿Por qué querríamos inventar un nuevo enfoque especial para un idioma específico, cuando podríamos escribir una gramática lex? La gramática de lex es más fácil de mantener, y el analizador resultante es más probable que sea correcto (dada la eficacia de lex y herramientas similares).
DW
7

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.

psr
fuente
7

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.

Ben Jackson
fuente
5

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é.

Un programador
fuente
2

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).

Robert Baron
fuente
0

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?

Greenoldman
fuente