Devo usar um gerador de analisador ou devo rolar meu próprio código lexer e analisador personalizado?

Quais vantagens e desvantagens específicas de cada maneira de trabalhar em uma gramática de linguagem de programação?

Por que / quando devo fazer o meu próprio? Por que / quando devo usar um gerador?

Na verdade, existem três opções, todas preferíveis em situações diferentes.

Opção 1: geradores de analisadores, ou 'você precisa analisar um idioma e deseja fazê-lo funcionar, droga'

Digamos que você seja solicitado a criar um analisador para algum formato de dados antigo AGORA. Ou você precisa que seu analisador seja rápido. Ou você precisa que seu analisador seja fácil de manter.

Nesses casos, provavelmente é melhor usar um gerador de analisador. Você não precisa se preocupar com os detalhes, não precisa ter muito código complicado para funcionar corretamente, basta escrever a gramática à qual a entrada irá aderir, escrever algum código de manipulação e pronto: analisador instantâneo.

As vantagens são claras:

• É (geralmente) bastante fácil escrever uma especificação, especialmente se o formato de entrada não for muito estranho (a opção 2 seria melhor se for).
• Você acaba com um trabalho de fácil manutenção que é facilmente entendido: uma definição gramatical geralmente flui muito mais natural que o código.
• Os analisadores gerados por bons geradores de analisadores geralmente são muito mais rápidos que o código escrito à mão. O código escrito à mão pode ser mais rápido, mas apenas se você conhece suas coisas - é por isso que os compiladores mais usados ​​usam um analisador de descida recursiva à mão.

Há uma coisa com a qual você deve ter cuidado com os geradores de analisadores: às vezes, a lata rejeita suas gramáticas. Para uma visão geral dos diferentes tipos de analisadores e como eles podem mordê-lo, você pode começar por aqui . Aqui você pode encontrar uma visão geral de muitas implementações e os tipos de gramática que eles aceitam.

Opção 2: analisadores escritos à mão ou 'você deseja criar seu próprio analisador e se preocupa em ser amigável'

Os geradores de analisador são bons, mas não são muito amigáveis ​​ao usuário (o usuário final, você não). Você normalmente não pode dar boas mensagens de erro, nem fornecer recuperação de erros. Talvez seu idioma seja muito estranho e os analisadores rejeitem sua gramática ou você precise de mais controle do que o gerador lhe fornece.

Nesses casos, o uso de um analisador de descida recursiva manuscrita provavelmente é o melhor. Embora a correção seja complicada, você tem controle total sobre o seu analisador para poder fazer todo tipo de coisa interessante que não pode ser feita com os geradores, como mensagens de erro e até recuperação de erros (tente remover todos os pontos e vírgulas de um arquivo C # : o compilador C # reclamará, mas detectará a maioria dos outros erros, independentemente da presença de ponto e vírgula).

Os analisadores escritos à mão também costumam ter um desempenho melhor que os gerados, assumindo que a qualidade do analisador seja alta o suficiente. Por outro lado, se você não conseguir escrever um bom analisador - geralmente devido a (uma combinação de) falta de experiência, conhecimento ou design -, o desempenho é geralmente mais lento. Para os lexers, o oposto é verdadeiro: os lexers geralmente gerados usam pesquisas de tabela, tornando-os mais rápidos do que os escritos à mão.

Em termos de educação, escrever seu próprio analisador lhe ensinará mais do que usar um gerador. Você precisa escrever um código cada vez mais complicado, além de entender exatamente como analisa um idioma. Por outro lado, se você quiser aprender a criar seu próprio idioma (obtenha experiência no design de idiomas), é preferível a opção 1 ou a opção 3: se você estiver desenvolvendo um idioma, provavelmente mudará muito, e as opções 1 e 3 facilitam o processo.

Opção 3: geradores de analisadores escritos à mão, ou 'você está tentando aprender muito com este projeto e não se importaria de terminar com um pedaço de código bacana que pode reutilizar muito'

Este é o caminho que estou percorrendo atualmente: você escreve seu próprio gerador de analisador. Embora não seja trivial, fazer isso provavelmente o ensinará mais.

Para ter uma idéia do que é fazer um projeto como esse, vou contar sobre o meu próprio progresso.

O gerador lexer

Criei meu próprio gerador de lexer primeiro. Normalmente, eu desenvolvo softwares começando com a forma como o código será usado, então pensei em como queria poder usar meu código e escrevi esse trecho de código (em C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

Os pares de entrada-símbolo de entrada são convertidos em uma estrutura recursiva correspondente, descrevendo as expressões regulares que eles representam usando as idéias de uma pilha aritmética. Este é então convertido em um NFA (autômato finito não determinístico), que por sua vez é convertido em um DFA (autômato finito determinístico). Em seguida, você pode combinar as strings com o DFA.

Dessa forma, você terá uma boa idéia de como exatamente os lexers funcionam. Além disso, se você fizer da maneira correta, os resultados do seu gerador de lexer poderão ser aproximadamente tão rápidos quanto as implementações profissionais. Você também não perde nenhuma expressividade em comparação com a opção 2 e não possui muita expressividade em comparação com a opção 1.

Eu implementei meu gerador lexer em pouco mais de 1600 linhas de código. Esse código faz o trabalho acima, mas ainda gera o lexer em tempo real toda vez que você inicia o programa: adicionarei código para gravá-lo no disco em algum momento.

Se você quer saber como escrever seu próprio lexer, este é um bom lugar para começar.

O gerador do analisador

Você então escreve seu gerador de analisador. Refiro-me aqui novamente para obter uma visão geral dos diferentes tipos de analisadores - como regra geral, quanto mais eles conseguem analisar, mais lentos são.

Como a velocidade não é um problema para mim, optei por implementar um analisador Earley. As implementações avançadas de um analisador Earley mostraram ser duas vezes mais lentas que outros tipos de analisador.

Em troca desse golpe de velocidade, você tem a capacidade de analisar qualquer tipo de gramática, mesmo as ambíguas. Isso significa que você nunca precisa se preocupar se o seu analisador tem alguma recursão à esquerda ou o que é um conflito de redução de turno. Você também pode definir gramáticas mais facilmente usando gramáticas ambíguas, se não importa qual árvore de análise é o resultado, como se não importasse se você analisava 1 + 2 + 3 como (1 + 2) +3 ou como 1 + (2 + 3).

É assim que um pedaço de código usando meu gerador de analisador pode ser:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Observe que o IntWrapper é simplesmente um Int32, exceto que o C # exige que seja uma classe, portanto tive que introduzir uma classe de wrapper)

Espero que você veja que o código acima é muito poderoso: qualquer gramática que você possa criar pode ser analisada. Você pode adicionar bits de código arbitrários na gramática, capazes de executar muitas tarefas. Se você conseguir fazer com que tudo funcione, poderá reutilizar o código resultante para realizar muitas tarefas com muita facilidade: imagine criar um interpretador de linha de comando usando esse trecho de código.

Se você nunca escreveu um analisador, eu o recomendaria. É divertido e você aprende como as coisas funcionam e aprende a apreciar o esforço que os geradores de analisador e lexer evitam que você faça da próxima vez que precisar de um analisador.

Eu também sugiro que você tente ler http://compilers.iecc.com/crenshaw/ , pois tem uma atitude muito realista em relação a como fazê-lo.

A vantagem de escrever seu próprio analisador de descida recursiva é que você pode gerar mensagens de erro de alta qualidade em erros de sintaxe. Usando geradores de analisador, você pode produzir produções de erro e adicionar mensagens de erro personalizadas em determinados pontos, mas os geradores de analisador simplesmente não correspondem ao poder de ter controle completo sobre a análise.

Outra vantagem de escrever o seu próprio é que é mais fácil analisar uma representação mais simples que não tem uma correspondência individual com a sua gramática.

Se sua gramática for corrigida e as mensagens de erro forem importantes, considere usar a sua própria ou, pelo menos, usar um gerador de analisador que forneça as mensagens de erro necessárias. Se sua gramática está constantemente mudando, considere o uso de geradores de analisador.

Bjarne Stroustrup fala sobre como ele usou o YACC para a primeira implementação do C ++ (consulte O design e a evolução do C ++ ). Nesse primeiro caso, ele desejou ter escrito seu próprio analisador de descida recursiva!

Opção 3: nenhum dos dois (role seu próprio gerador de analisador)

Só porque há uma razão para não usar ANTLR , bisonte , Coco / R , Grammatica , JavaCC , Lemon , Parboiled , SableCC , Quex , etc - isso não significa que você deve instantaneamente rolar seu próprio analisador + lexer.

Identifique por que todas essas ferramentas não são boas o suficiente - por que elas não permitem que você atinja seu objetivo?

A menos que você tenha certeza de que as esquisitices da gramática com que você está lidando são únicas, você não deve apenas criar um único analisador + lexer personalizado para ele. Em vez disso, crie uma ferramenta que criará o que você deseja, mas também pode ser usada para atender a necessidades futuras e, em seguida, libere-a como Software Livre para evitar que outras pessoas tenham o mesmo problema que você.

Rolar o seu próprio analisador obriga a pensar diretamente sobre a complexidade do seu idioma. Se o idioma é difícil de analisar, provavelmente será difícil de entender.

Havia muito interesse nos geradores de analisadores nos primeiros dias, motivados por uma sintaxe de linguagem altamente complicada (alguns diriam "torturada"). O JOVIAL foi um exemplo particularmente ruim: era necessário procurar dois símbolos, em um momento em que todo o resto exigia no máximo um símbolo. Isso tornou a geração do analisador para um compilador JOVIAL mais difícil do que o esperado (como a General Dynamics / Fort Worth Division aprendeu da maneira mais difícil ao adquirir os compiladores JOVIAL para o programa F-16).

Hoje, a descida recursiva é universalmente o método preferido, porque é mais fácil para os escritores de compiladores. Os compiladores de descida recursiva recompensam fortemente o design de linguagem simples e limpa, pois é muito mais fácil escrever um analisador de descida recursiva para uma linguagem simples e limpa do que para uma linguagem complicada e confusa.

Finalmente: você considerou incorporar seu idioma no LISP e deixar que um intérprete do LISP faça o trabalho pesado para você? O AutoCAD fez isso e descobriu que tornou a vida deles muito mais fácil. Existem muitos intérpretes LISP leves por aí, alguns incorporáveis.

Eu escrevi um analisador para aplicação comercial uma vez e usei o yacc . Havia um protótipo concorrente em que um desenvolvedor escrevia tudo manualmente em C ++ e funcionava cerca de cinco vezes mais devagar.

Quanto ao lexer deste analisador, escrevi-o inteiramente à mão. Levou - desculpe, foi há quase 10 anos, então eu não me lembro exatamente - cerca de 1000 linhas em C .

A razão pela qual escrevi o lexer manualmente foi a gramática de entrada do analisador. Era um requisito, algo que minha implementação do analisador tinha que cumprir, em oposição a algo que eu projetei. (É claro que eu o teria projetado de maneira diferente. E melhor!) A gramática era severamente dependente do contexto e até lexante dependia da semântica em alguns lugares. Por exemplo, um ponto-e-vírgula pode fazer parte de um token em um local, mas um separador em um local diferente - com base na interpretação semântica de algum elemento analisado anteriormente. Então, "enterrei" essas dependências semânticas no lexer escrito à mão e isso me deixou com um BNF bastante simples e fácil de implementar no yacc.

ADICIONADO em resposta ao Macneil : yacc fornece uma abstração muito poderosa que permite ao programador pensar em termos de terminais, não terminais, produções e coisas assim. Além disso, ao implementar a yylex()função, ele me ajudou a focar no retorno do token atual e não me preocupar com o que havia antes ou depois dele. O programador C ++ trabalhou no nível de caractere, sem o benefício dessa abstração e acabou criando um algoritmo mais complicado e menos eficiente. Concluímos que a velocidade mais lenta não tinha nada a ver com o próprio C ++ ou com qualquer biblioteca. Medimos a velocidade pura da análise com arquivos carregados na memória; se tivéssemos um problema de buffer de arquivo, o yacc não seria nossa ferramenta de escolha para resolvê-lo.

TAMBÉM QUER ADICIONAR : essa não é uma receita para escrever analisadores em geral, apenas um exemplo de como funcionou em uma situação específica.

Isso depende inteiramente do que você precisa analisar. Você pode fazer o seu próprio mais rápido do que poderia atingir a curva de aprendizado de um lexer? O material a ser analisado estático o suficiente para que você não se arrependa da decisão mais tarde? Você acha as implementações existentes excessivamente complexas? Nesse caso, divirta-se, mas apenas se você não estiver se esquivando de uma curva de aprendizado.

Ultimamente, gosto muito do analisador de limão , que é sem dúvida o mais simples e fácil que já usei. Para facilitar a manutenção das coisas, eu apenas uso isso para a maioria das necessidades. O SQLite o usa, assim como alguns outros projetos notáveis.

Mas eu não estou nem um pouco interessado em lexers, além deles não atrapalharem quando eu precisar usar um (daí o limão). Você pode ser, e se sim, por que não fazer um? Tenho a sensação de que você voltará a usar um que existe, mas coça a coceira se precisar :)

Depende de qual é seu objetivo.

Você está tentando aprender como os analisadores / compiladores funcionam? Em seguida, escreva o seu a partir do zero. Essa é a única maneira que você realmente aprenderia a apreciar todos os meandros do que eles estão fazendo. Eu escrevi um nos últimos dois meses, e tem sido uma experiência interessante e valiosa, especialmente os momentos 'ah, então é por isso que a linguagem X faz isso ...'.

Você precisa montar algo rapidamente para um aplicativo em um prazo? Então talvez use uma ferramenta de análise.

Você precisa de algo que queira expandir nos próximos 10, 20, talvez até 30 anos? Escreva o seu, e não se apresse. Vai valer a pena.

Você já considerou a abordagem do ambiente de trabalho de idiomas Martin Fowlers ? Citando o artigo

A mudança mais óbvia que um ambiente de trabalho de linguagem faz na equação é a facilidade de criar DSLs externos. Você não precisa mais escrever um analisador. Você precisa definir a sintaxe abstrata - mas essa é realmente uma etapa bastante direta da modelagem de dados. Além disso, sua DSL obtém um IDE poderoso - embora você precise gastar algum tempo definindo esse editor. O gerador ainda é algo que você precisa fazer, e eu sinto que não é muito mais fácil do que nunca. Porém, construir um gerador para uma DSL boa e simples é uma das partes mais fáceis do exercício.

Lendo isso, eu diria que os dias para escrever seu próprio analisador terminaram e é melhor usar uma das bibliotecas disponíveis. Depois de dominar a biblioteca, todas as DSLs que você criar no futuro se beneficiarão desse conhecimento. Além disso, outros não precisam aprender sua abordagem de análise.

Editar para cobrir o comentário (e a pergunta revisada)

Vantagens de rodar o seu próprio

1. Você será o proprietário do analisador e obterá toda a adorável experiência de pensar através de uma intrincada série de problemas
2. Você pode criar algo especial que ninguém mais pensou (improvável, mas você parece um sujeito inteligente)
3. Vai mantê-lo ocupado com um problema interessante

Então, resumindo, você deve se esforçar quando quiser realmente penetrar profundamente nas entranhas de um problema seriamente difícil que se sente fortemente motivado a dominar.

Vantagens de usar a biblioteca de outra pessoa

1. Você evitará reinventar a roda (um problema comum na programação, você concorda)
2. Você pode se concentrar no resultado final (seu novo idioma brilhante) e não se preocupar muito com a forma como ele é analisado etc.
3. Você verá seu idioma em ação muito mais rápido (mas sua recompensa será menor porque não foi tudo o que você)

Portanto, se você deseja um resultado final rápido, use a biblioteca de outra pessoa.

No geral, isso se resume a uma escolha de quanto você deseja possuir o problema e, portanto, a solução. Se você quiser tudo, então faça o seu próprio.

A grande vantagem de escrever o seu é que você saberá como escrever. A grande vantagem de usar uma ferramenta como o yacc é que você saberá como usá-la. Sou fã da copa das árvores para a exploração inicial.

Por que não bifurcar um gerador de analisador de código aberto e torná-lo seu? Se você não usar geradores de analisadores, seu código será muito difícil de manter, se você fizer grandes alterações na sintaxe do seu idioma.

Nos meus analisadores, usei expressões regulares (quero dizer, estilo Perl) para tokenizar e use algumas funções de conveniência para aumentar a legibilidade do código. No entanto, um código gerado pelo analisador pode ser mais rápido criando tabelas de estados e long switch- cases, o que pode aumentar o tamanho do código-fonte, a menos que você .gitignoreos faça.

Aqui estão dois exemplos de meus analisadores personalizados:

https://github.com/SHiNKiROU/DesignScript - um dialeto BASIC, porque eu estava com preguiça de escrever lookaheads em notação de matriz, sacrifiquei a qualidade da mensagem de erro https://github.com/SHiNKiROU/ExprParser - Uma calculadora de fórmula. Observe os truques estranhos de metaprogramação

"Devo usar essa 'roda' testada e testada ou reinventá-la?"