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

143

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.

Don Wakefield
fonte

Respostas:

145

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.

Daniel Spiewak
fonte
2
Então a grande vantagem, possivelmente única, do Antlr em sua percepção é que ele gera menos erros como sr e rr durante a fase de construção? Espero que eu vou dar-lhe uma tentativa, mas provavelmente vai acabar furando com o que eu sei ...
Don Wakefield
1
Sim, é praticamente isso. :-) Eu também não concordo com a opinião popular de que o ANTLR é mais fácil que o Bison, então acho que concordo com a sua decisão.
Daniel Spiewak 18/10/08
2
A regra 'reais' precisa de uma segunda regra para indicar que um simples 'expr' é real? Caso contrário, boa explicação.
Jonathan Leffler
8
Outro comentário que encontrei recentemente, embora com uma década, faz uma observação razoável da saída : compilers.iecc.com/comparch/article/98-11-040 : "ANTLR / PCCTS são LL, o que dificulta a escrita da gramática, mas o o código gerado é legível. Você é o LALR (é claro que você sabe disso) facilita a escrita da gramática, mas o código gerado também pode ser hieróglifo. "
1111 Don
72
Acabei de concluir o suporte imediato à recursão à esquerda para o ANTLR na próxima versão v3.4. Lida com regras de expressão LR e coisas semelhantes, como regras do declarador C. :)
Terence Parr
117

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.

trijezdci
fonte
4
gosto dele porque ele explica a história por trás dos diferentes mecanismos, o que torna as pessoas entenderam imediately
zinking
35

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 $

Cristian Diaconescu
fonte
9

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.

John com waffle
fonte
9
  • 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.

apenas eu
fonte
7
Estou curioso. Você pode apontar para a documentação que descreve o consumo de 512 bytes de memória por token? Não me lembro de ter visto essa discussão. A minha escolha de palavras-chave do Google não está me dando satisfação ou ...
Don Wakefield
2
Você está falando sobre a pegada de memória do gerador do analisador enquanto gera um analisador ou está falando sobre a pegada de memória do analisador gerado enquanto analisa a entrada para o idioma de origem? Milhões de tokens em uma gramática seriam absolutamente insanos. Você deveria ser trancado em uma instituição mental se tentasse seriamente vender essa ideia. Quanto aos arquivos de entrada para o próprio analisador, pode haver casos em que estes possam ter um número extremamente grande de tokens, mas a maioria dos idiomas é modular, você não analisa toda a entrada em um único arquivo, os módulos individuais são menores.
trijezdci