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

24

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.

Telastyn
fonte
5
uma herança dos antigos princípios de design de compiladores (1977) ? 40 anos atrás, estilo de codificação era muito diferente
mosquito
7
Como você implementaria as transições dos estados do DFA? E o que é isso sobre terminais e não terminais, "não terminais" geralmente se refere às regras de produção na gramática, que viriam após a análise lexical.
10
Essas tabelas não devem ser legíveis para humanos, devem ser utilizadas pelo compilador e executadas muito rapidamente. É fácil pular uma mesa ao olhar para a frente na entrada (por exemplo, para recuperar a recursão à esquerda, embora na prática a maioria dos idiomas seja criada para evitar isso).
5
Se uma parte de sua irritação é proveniente de saber como fazer um trabalho melhor e sem a capacidade de obter qualquer feedback ou apreciação por uma abordagem que você preferir - como décadas na indústria nos treina a esperar feedback e, às vezes, apreciação - talvez você deve escrever sua melhor implementação e publicá-la no CodeReview.SE para obter um pouco disso para sua própria paz de espírito.
Jimmy Hoffa
7
A resposta simples é porque o lexer geralmente é implementado como uma máquina de estados finitos e gerado automaticamente a partir da gramática - e uma tabela de estados é, sem surpresa, mais fácil e compactamente representada como uma tabela. Como no código de objeto, o fato de que não é fácil para os humanos trabalharem é irrelevante, porque os humanos não trabalham com ele; eles mudam a fonte e geram uma nova instância.
Kevlam #

Respostas:

16

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.

Kevin Cline
fonte
4
Não tenho certeza se estou sugerindo isso por atacado. Expressões regulares lidam com idiomas arbitrários (regulares). Não existem abordagens melhores ao trabalhar com idiomas específicos? O livro aborda abordagens preditivas, mas depois as ignora em exemplos. Além disso, tendo feito um analisador ingênuo para C # anos atrás, não achei terrivelmente difícil de manter. Ineficiente? claro, mas não muito, dada a minha habilidade na época.
Telastyn
11
@Telastyn: é quase impossível ir mais rápido do que um DFA orientado a tabelas: obter o próximo caractere, pesquisar o próximo estado na tabela de transição, alterar o estado. Se o novo estado for terminal, emita um token. Em C # ou Java, qualquer abordagem que envolva a criação de cadeias temporárias será mais lenta.
Kevin cline
@kevincline - claro, mas no meu exemplo não há seqüências temporárias. Mesmo em C, seria apenas um índice ou um ponteiro percorrendo a string.
Telastyn
6
@ JimmyHoffa: sim, o desempenho é definitivamente relevante nos compiladores. Os compiladores são rápidos porque foram otimizados para o inferno e para trás. Não são micro-otimizações, elas simplesmente não realizam trabalhos desnecessários como criar e descartar objetos temporários desnecessários. Na minha experiência, a maioria dos códigos comerciais de processamento de texto faz um décimo do trabalho de um compilador moderno e leva dez vezes mais tempo para fazê-lo. O desempenho é enorme quando você está processando um gigabyte de texto.
Kevin cline
11
@Telastyn, que "melhor abordagem" você tinha em mente e de que maneira você espera que seja "melhor"? Como já temos ferramentas de lexing que são bem testadas e produzem analisadores muito rápidos (como já foi dito, os DFAs orientados por tabelas são muito rápidos), faz sentido usá-los. Por que queremos inventar uma nova abordagem especial para um idioma específico, quando podemos escrever uma gramática lex? A gramática lex é mais sustentável e o analisador resultante tem mais probabilidade de estar correto (dado o quão bem testado lex e ferramentas semelhantes são).
DW
7

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.

psr
fonte
7

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.

Ben Jackson
fonte
5

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.

AProgrammer
fonte
2

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

Robert Baron
fonte
0

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?

greenoldman
fonte