Vantagens do Antlr (versus digamos, lex / yacc / bison) [fechado]

Eu usei lex e yacc (mais geralmente bison) no passado para vários projetos, geralmente tradutores (como um subconjunto de EDIF transmitido para um aplicativo EDA). Além disso, tive que oferecer suporte a códigos baseados em gramáticas lex / yacc que datam de décadas atrás. Então, eu conheço as ferramentas, embora não seja especialista.

Já vi comentários positivos sobre o Antlr em vários fóruns no passado e estou curioso para saber o que posso estar perdendo. Portanto, se você já usou os dois, diga-me o que é melhor ou mais avançado no Antlr. Minhas restrições atuais são que eu trabalho em uma loja C ++ e qualquer produto que enviamos não inclui Java, portanto os analisadores resultantes teriam que seguir essa regra.

Atualização / aviso: Esta resposta pode estar desatualizada!

Uma grande diferença é que o ANTLR gera um analisador LL (*), enquanto que o YACC e o Bison geram analisadores que são LALR. Essa é uma distinção importante para várias aplicações, sendo as mais óbvias as operadoras:

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

O ANTLR é totalmente incapaz de lidar com essa gramática como está. Para usar o ANTLR (ou qualquer outro gerador de analisador de LL), você precisará converter essa gramática em algo que não seja recursivo à esquerda. No entanto, Bison não tem problemas com gramáticas deste formulário. Você precisaria declarar '+' e '-' como operadores associativos à esquerda, mas isso não é estritamente necessário para a recursão à esquerda. Um exemplo melhor pode ser o envio:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

Observe que expras actualsregras e as são recursivas à esquerda. Isso produz um AST muito mais eficiente quando chega a hora da geração do código, pois evita a necessidade de vários registros e derramamentos desnecessários (uma árvore inclinada para a esquerda pode ser recolhida, enquanto uma árvore inclinada para a direita não).

Em termos de gosto pessoal, acho que as gramáticas LALR são muito mais fáceis de construir e depurar. A desvantagem é que você precisa lidar com erros um tanto enigmáticos, como reduzir o turno e (o temido) reduzir-reduzir. Esses são os erros que o Bison detecta ao gerar o analisador, por isso não afeta a experiência do usuário final, mas pode tornar o processo de desenvolvimento um pouco mais interessante. O ANTLR é geralmente considerado mais fácil de usar que o YACC / Bison exatamente por esse motivo.

A diferença mais significativa entre YACC / Bison e ANTLR é o tipo de gramática que essas ferramentas podem processar. YACC / Bison lida com gramáticas LALR, ANTLR lida com gramáticas LL.

Freqüentemente, as pessoas que trabalham com gramáticas LALR há muito tempo acham mais difícil trabalhar com gramáticas LL e vice-versa. Isso não significa que as gramáticas ou ferramentas sejam inerentemente mais difíceis de trabalhar. Qual ferramenta você acha mais fácil de usar se resume principalmente ao tipo de gramática.

Quanto às vantagens, há aspectos em que as gramáticas LALR têm vantagens sobre as gramáticas LL e há outros aspectos em que as gramáticas LL têm vantagens sobre as gramáticas LALR.

O YACC / Bison gera analisadores acionados por tabela, o que significa que a "lógica de processamento" está contida nos dados do programa analisador, não tanto no código do analisador. A recompensa é que mesmo um analisador para uma linguagem muito complexa possui uma pegada de código relativamente pequena. Isso foi mais importante nas décadas de 1960 e 1970, quando o hardware era muito limitado. Os geradores de analisadores acionados por tabela remontam a essa época e a presença de código pequeno era um requisito principal na época.

O ANTLR gera analisadores de descida recursiva, o que significa que a "lógica de processamento" está contida no código do analisador, pois cada regra de produção da gramática é representada por uma função no código do analisador. A recompensa é que é mais fácil entender o que o analisador está fazendo lendo seu código. Além disso, os analisadores de descida recursiva geralmente são mais rápidos que os analisados ​​em tabelas. No entanto, para linguagens muito complexas, a pegada de código será maior. Este foi um problema nas décadas de 1960 e 1970. Naquela época, apenas linguagens relativamente pequenas como o Pascal, por exemplo, eram implementadas dessa maneira devido a limitações de hardware.

Os analisadores gerados pelo ANTLR estão tipicamente nas proximidades de 10.000 linhas de código e muito mais. Analisadores de descida recursiva manuscritos geralmente estão no mesmo estádio. O compilador Oberon da Wirth é talvez o mais compacto, com cerca de 4000 linhas de código, incluindo geração de código, mas o Oberon é uma linguagem muito compacta, com apenas cerca de 40 regras de produção.

Como alguém já apontou, uma grande vantagem do ANTLR é a ferramenta gráfica IDE, chamada ANTLRworks. É um laboratório completo de gramática e design de idiomas. Ele visualiza suas regras gramaticais à medida que você as digita e, se encontrar algum conflito, mostrará graficamente qual é o conflito e o que o causa. Pode até refatorar e resolver automaticamente conflitos como recursão à esquerda. Depois de ter uma gramática livre de conflitos, você pode permitir que o ANTLRworks analise um arquivo de entrada do seu idioma e crie uma árvore de análise e AST para você e mostre a árvore graficamente no IDE. Essa é uma grande vantagem, pois pode economizar muitas horas de trabalho: você encontrará erros conceituais no design do seu idioma antes de começar a codificar! Eu não encontrei nenhuma ferramenta para gramáticas LALR, parece que não existe.

Mesmo para pessoas que não desejam gerar seus analisadores, mas codificá-los manualmente, o ANTLRworks é uma ótima ferramenta para criação / prototipagem de linguagem. Muito possivelmente, a melhor ferramenta disponível. Infelizmente, isso não ajuda se você deseja criar analisadores LALR. Mudar de LALR para LL simplesmente para aproveitar o ANTLRworks pode valer a pena, mas para algumas pessoas, alternar tipos de gramática pode ser uma experiência muito dolorosa. Em outras palavras: YMMV.

Algumas vantagens para a ANTLR:

• pode gerar analisadores em várias linguagens - Java não é necessário para executar o analisador gerado.
• A GUI impressionante facilita a depuração gramatical (por exemplo, você pode ver o AST gerado diretamente na GUI, sem necessidade de ferramentas extras)
• O código gerado é realmente legível por humanos (é um dos objetivos do ANTLR) e o fato de gerar geradores de analisadores LL certamente ajuda nesse sentido.
• a definição de terminais também é livre de contexto (ao contrário de regex em (f) lex) - permitindo, por exemplo, a definição de terminais contendo parênteses adequadamente fechados

My .02 $

Outra vantagem do ANTRL é que você pode usar o ANTLRWORKS , embora não possa dizer que essa seja uma vantagem estrita, pois pode haver ferramentas semelhantes para outros geradores também.

• Bison e Flex resultam em um menor espaço de memória, mas você não possui um IDE gráfico.
• O antlr usa mais memória, mas você tem o antlrworks, um IDE gráfico.

O uso da memória Bison / Flex é tipicamente um mbyte. Compare isso com o antlr - supondo que ele use 512 bytes de memória para cada token no arquivo que você deseja analisar. 4 milhões de tokens e você está sem memória virtual em um sistema de 32 bits.

Se o arquivo que você deseja analisar for grande, o antlr poderá ficar sem memória; portanto, se você quiser apenas analisar um arquivo de configuração, seria uma solução viável. Caso contrário, se você deseja analisar um arquivo com muitos dados, tente o Bison.