Por que implementar um lexer como uma matriz 2D e um switch gigante?

Estou lentamente trabalhando para terminar minha graduação, e este semestre é o Compilers 101. Estamos usando o Dragon Book . Logo no início do curso, estamos falando sobre análise lexical e como ela pode ser implementada por meio de autômatos finitos determinísticos (doravante, DFA). Configure seus vários estados de lexer, defina transições entre eles, etc.

Mas tanto o professor quanto o livro propõem implementá-los por meio de tabelas de transição que equivalem a uma matriz 2d gigante (os vários estados não terminais como uma dimensão e os possíveis símbolos de entrada como a outra) e uma instrução switch para lidar com todos os terminais bem como despachar para as tabelas de transição se estiver em um estado não terminal.

A teoria está muito bem, mas como alguém que realmente escreveu código por décadas, a implementação é vil. Não é testável, não é sustentável, não é legível e é uma dor e meia para depurar. Pior ainda, não consigo ver como seria remotamente prático se o idioma fosse compatível com UTF. Ter um milhão ou mais de entradas na tabela de transição por estado não terminal fica improdutivo às pressas.

Então, qual é o problema? Por que o livro definitivo sobre o assunto está dizendo para fazê-lo dessa maneira?

A sobrecarga das chamadas de função é realmente assim? Isso é algo que funciona bem ou é necessário quando a gramática não é conhecida antecipadamente (expressões regulares?)? Ou talvez algo que lide com todos os casos, mesmo que soluções mais específicas funcionem melhor para gramáticas mais específicas?

( observação: possível duplicata " Por que usar uma abordagem OO em vez de uma declaração de switch gigante? " está próxima, mas eu não me importo com OO. Uma abordagem funcional ou mesmo uma abordagem mais sadia e imperativa com funções independentes seria adequada.)

E, por exemplo, considere uma linguagem que tenha apenas identificadores, e esses identificadores são [a-zA-Z]+. Na implementação do DFA, você obteria 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;
}

(embora algo que lide com o final do arquivo corretamente)

Comparado com o que eu esperaria:

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

Com o código NextTokenrefatorado para sua própria função, quando você tiver vários destinos desde o início do DFA.

Na prática, essas tabelas são geradas a partir de expressões regulares que definem os tokens do idioma:

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

Temos utilitários para gerar analisadores lexicais desde 1975, quando o lex foi escrito.

Você está basicamente sugerindo a substituição de expressões regulares por código processual. Isso expande alguns caracteres em uma expressão regular em várias linhas de código. O código processual manuscrito para análise lexical de qualquer linguagem moderadamente interessante tende a ser ineficiente e difícil de manter.

A motivação para o algoritmo específico é, em grande parte, o fato de ser um exercício de aprendizado; portanto, ele tenta se aproximar da ideia de um DFA e mantém estados e transições muito explícitos no código. Como regra, ninguém realmente escreveria manualmente esse código de qualquer maneira - você usaria uma ferramenta para gerar código a partir de uma gramática. E essa ferramenta não se importaria com a legibilidade do código, porque não é um código fonte, é uma saída baseada na definição de uma gramática.

Seu código é mais limpo para alguém que mantém um DFA escrito à mão, mas um pouco mais afastado dos conceitos que estão sendo ensinados.

O loop interno de:

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

tem muitas vantagens de desempenho. Não há ramificações nisso, porque você faz exatamente a mesma coisa para cada caractere de entrada. O desempenho do compilador pode ser controlado pelo lexer (que deve operar em uma escala de cada caractere de entrada). Isso foi ainda mais verdadeiro quando o Dragon Book foi escrito.

Na prática, além dos estudantes de CS que estudam lexers, ninguém precisa implementar (ou depurar) esse loop interno porque faz parte do clichê que acompanha a ferramenta que constrói a transitiontabela.

Da memória, - faz muito tempo desde que li o livro e tenho certeza de que não li a edição mais recente, com certeza não me lembro de algo parecido com Java - essa parte foi escrita com o código pretende ser um modelo, a tabela é preenchida com um lex como um gerador de lexer. Ainda na memória, havia uma seção sobre compactação de tabela (novamente a partir da memória, ela foi escrita de tal maneira que também se aplicava aos analisadores de tabela, talvez mais adiante no livro do que o que você já viu). Da mesma forma, o livro que eu lembro assumia um conjunto de caracteres de 8 bits; eu esperaria uma seção sobre como lidar com um conjunto maior de caracteres em edições posteriores, provavelmente como parte da compactação da tabela. Dei uma maneira alternativa de lidar com isso como resposta a uma pergunta SO.

Há uma certa vantagem de desempenho em ter dados de loop restrito conduzidos na arquitetura moderna: é bastante amigável ao cache (se você compactou as tabelas), e a previsão de salto é a mais perfeita possível (uma falha no final do lexem, talvez uma falta o envio do switch para o código que depende do símbolo; isso pressupõe que a descompressão da tabela possa ser feita com saltos previsíveis). Mover essa máquina de estado para código puro diminuiria o desempenho da previsão de salto e talvez aumentaria a pressão do cache.

Tendo trabalhado no Dragon Book anteriormente, a principal razão para ter alavancas e analisadores acionados por tabela é para que você possa usar expressões regulares para gerar o lexer e o BNF para gerar o analisador. O livro também aborda como ferramentas como lex e yacc funcionam e para que você saiba como essas ferramentas funcionam. Além disso, é importante que você trabalhe com alguns exemplos práticos.

Apesar de muitos comentários, não tem nada a ver com o estilo de código que foi escrito nas décadas de 40, 50, 60 ... ... tem a ver com a compreensão prática do que as ferramentas estão fazendo por você e do que você tem. fazer para fazê-los funcionar. Tem tudo a ver com o entendimento fundamental de como os compiladores funcionam, tanto do ponto de vista teórico quanto prático.

Felizmente, seu instrutor também permitirá que você use lex e yacc (a menos que seja uma classe de pós-graduação e você possa escrever lex e yacc).

Tarde para a festa :-) Os tokens são comparados com expressões regulares. Como existem muitos deles, você tem o mecanismo multi regex, que por sua vez é um DFA gigante.

"Pior ainda, não consigo ver como seria remotamente prático se o idioma fosse capaz de UTF."

É irrelevante (ou transparente). Além da UTF possuir propriedades agradáveis, suas entidades não se sobrepõem nem parcialmente. Por exemplo, o byte que representa o caractere "A" (da tabela ASCII-7) não é usado novamente para nenhum outro caractere UTF.

Portanto, você tem um DFA único (que é multi-regex) para todo o lexer. Qual a melhor forma de anotá-la do que a matriz 2D?