16

Obviamente a pergunta não deve ser interpretada "ao pé da letra". Não quero que ninguém decida por mim, preciso saber as vantagens e desvantagens de usar um método ou o outro.

Quando devo usar um gerador de parser (em inglês) e quando devo desenvolver meu código do zero?

O que eu ganho ou perco escolhendo uma ou outra abordagem?

1

2 Respostas 2

16

Na verdade, há três opções, todas os três preferíveis em situações diferentes. A terceira pode ser observada na excelente resposta original no Software Engineering dada pelo Alex ten Brink.

Opção 1: geradores de parser, ou "você precisa para analisar alguma linguagem e você só quer fazê-lo funcionar, nada mais"

Você precisa construir um analisador para algum formato de dados antigo AGORA. Ou você precisa do seu analisador pronto rapidamente. Ou você precisa que seu analisador seja de fácil manutenção.

Nesses casos, provavelmente é melhor usar um gerador de parser. Você não tem que mexer com os detalhes, você não tem que ter um monte de código complicado para funcionar corretamente, você apenas escreve a gramática do texto de entrada que precisa aderir, escreve algum código de manipulação e pronto: parser instantâneo.

As vantagens são claras:

 - É (normalmente) muito fácil de escrever uma especificação, em especial se o formato de entrada não é muito estranho (opção 2 seria melhor se ele é).  - Você acaba com um produto muito fácil de manutenção do trabalho e de fácil compreensão: a definição da gramática geralmente flui muito mais natural do que o código.  - Os analisadores gerados por bons geradores de parsers são geralmente muito mais rápidos do que o código escrito à mão. Escrito à mão o código pode ser mais rápido, mas só se você entende seu material - é por isso que a maioria dos compiladores utilizam um analisador descendente recursivo escrito à mão.

Há uma coisa que você tem que ter cuidado com geradores de parser: eles podem, por vezes, rejeitar suas gramáticas. Para uma visão geral dos diferentes tipos de analisadores e como elas podem "te comer", você pode começar aqui(en). Aqui(en) você pode encontrar uma visão geral de uma série de implementações e os tipos de gramáticas que aceitam.

Opção 2: analisadores escritos à mão, ou "você quer construir seu próprio analisador, e você se importa em ser user-friendly"

Geradores de analisadores são bons, mas eles não são muito amigáveis ao usuário final do compilador (não o criador do compilador). Você normalmente não consegue dar boas mensagens de erro, nem pode fornecer recuperação de erros. Talvez a sua linguagem seja muito estranha e analisadores podem rejeitar a sua gramática ou você precisar de mais controle do que o gerador dá.

Nestes casos, utilizando um analisador descendente recursivo escrito à mão é provavelmente o melhor caminho. Embora acertar na sua confecção pode ser complicado, você tem total controle sobre seu analisador para fazer todos os tipos de coisas legais que você não pode fazer com geradores de analisador, como mensagens de erro e até mesmo a recuperação de erro (tente remover todos os pontos e vírgulas de um arquivo C#: o compilador C# vai reclamar, mas irá detectar a maioria dos outros erros de qualquer maneira, independentemente da presença de ponto e vírgula).

Analisadores manuais também, geralmente, são melhores do que os gerados na execução, assumindo que a qualidade do analisador é alta o suficiente. Por outro lado, se você não consegue escrever um bom parser - geralmente devido a (uma combinação de) falta de experiência, conhecimento ou design adequado -, então o desempenho é geralmente mais lento. Para lexers o oposto é verdadeiro: lexers gerados, geralmente, usam tabelas de lookup, tornando-os mais rápido do que (a maioria) dos escritos à mão.

Escrever seu próprio analisador vai te ensinar mais do que usar um gerador. Você tem que escrever código mais complicado, afinal de contas, mais, você terá que entender exatamente como analisar uma linguagem. Por outro lado, se você quer aprender como criar sua própria linguagem (obtendo experiência em design de linguagem), a opção 1 é preferível: se você está desenvolvendo uma linguagem, ela provavelmente vai mudar muita coisa, a opção 1 lhe dá uma experiência mais fácil.

Existe uma razão objetiva extra em fazer por conta própria. A criação de parser e lexer é uma fração do trabalho exigido na criação de uma linguagem realmente útil. Como outras vantagens existem na criação manual, a preocupação em ganhar tempo usando geradores é quase boba na maioria dos casos. Informação relevante pode ser obtida no artigo do Walter Bright, o criador da linguagem D, no Dr. Dobbs.

Por último, há um ponto subjetivo. Há diversos relatos, inclusive na resposta original no Software Engineering, de que fazer na mão é um divertimento sem fim, pelo menos para quem gosta do assunto.

Opção 3: geradores de analisador escritos á mão, ou "você está tentando aprender muito com este projeto e você não se importaria em acabar com uma monte de código bacana que você pode voltar a usar"

Apesar de útil, está um pouco fora da intenção da pergunta. Quem tiver interesse, pode olhar a resposta original.

Coloquei no GitHub para referência futura.

2
  • 1
    Apesar de ter colocado um resposta, outras podem ser bastante úteis. De fato, no post original no Programmers tem outras respostas bem interessantes que apresentam experiências boas. Qual é a sua?
    – Maniero
    Commented 17/01/2014 às 16:14
  • O luaparse é um ótimo exemplo de parser escrito às mãos, dá para aprender muito vendo seu código. Já consegui até modificar ele para suportar coisas não implementadas em Lua. O esprima também é ótimo exemplo e é fácil de manutenar. Concordo plenamente com a Opção 2
    – user37626
    Commented 12/01/2017 às 10:11
12

De um modo geral, uma ferramenta específica para um determinado domínio será mais fácil de usar, e potencialmente mais eficiente, que uma de propósito geral. Essa é a lógica por trás das "linguagens de domínio específico" (DSL), e também é a razão pela qual raramente alguém "programa um jogo" - preferindo em vez disso programar uma engine de jogos, e então desenvolver um jogo nessa engine. Da mesma forma, implementar um parser do zero em uma linguagem de programação de propósito geral muito provavelmente será mais difícil que fazê-lo usando um gerador de parsers.

Por outro lado, pode ser o caso dos geradores de parsers existentes - ou sua linguagem de representação de linguagens (gramáticas formais) - não ser a abstração mais adequada para aquilo que você quer fazer. Às vezes o problema é muito simples, e não se justifica fazer um parse completo, bastando algumas substituições simples (ex.: o Markdown - usado nesse próprio site - é implementado largamente por uma sequência de substituições regex). Outras vezes as características desejadas são pouco ortodoxas, e expressá-las em regras de produção simples se torna impraticável (ex.: em Prolog, a tabela de operadores não é fixa, de modo que durante a própria análise sintática pode-se encontrar instruções para alterá-los, já valendo no restante do código-fonte). Ainda pode ocorrer a situação da plataforma-alvo não ter muitas boas opções de geradores prontos (ex.: num projeto pessoal, precisei escrever um parser em JavaScript - as características desejadas do sistema excluíam o uso de qualquer código no lado servidor).

Se estiver em uma das situações acima - ou se o seu objetivo for mesmo aprender mais sobre como funciona um compilador (na minha opinião, é um exercício que amplia enormemente a compreensão de como funciona um computador por debaixo dos panos) - então pode valer a pena escrever o seu parser à mão. Só aconselho a torná-lo o mais modular e extensível possível - quase a ponto de escrever um "compilador de compiladores". Ou seja, evitar instruções hardcoded, preferindo parametrizar tudo o que for viável - lexer, tabela de operadores, etc. Dessa forma, ainda que o resultado não seja um parser "genérico" (i.e. capaz de interpretar um grande subconjunto das linguagens livres de contexto), ele ainda poderá ser extendido para interpretar linguagens mais ou menos parecidas com a sua, mas com diferenças sutis.

P.S. Há casos em que uma linguagem de programação de propósito geral possui funcionalidades próprias para facilitar a escrita de parsers e/ou a criação de DSLs que se encaixem em determinados padrões. Ver as macros de leitura do Lisp, a gramática de cláusulas definidas do Prolog (excelente para round-trip engineering), e para casos mais simples, a linguagem Groovy.

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .