Melhor gerador de analisador para analisar muitos textos pequenos em C ++?

Question

Estou, por motivos de desempenho, portando uma biblioteca C # para C ++. Durante a operação normal, esta biblioteca precisa, entre outras coisas, analisar cerca de 150.000 expressões matemáticas (pense em fórmulas do Excel) com um comprimento médio de menos de 150 caracteres.

Na versão C #, usei o analisador GOLD para gerar o código de análise. Ele pode analisar todas as 150.000 expressões em menos de um segundo.

Como estávamos pensando em estender nossa linguagem, imaginei que a mudança para C ++ poderia ser uma boa chance de mudar para ANTLR. Transferi a gramática (simples) para ANTLR e gerei o código C a partir dele. Analisar as 150.000 expressões leva mais de 12 segundos, porque para cada expressão, eu preciso criar um novo ANTL3_INPUT_STREAM, fluxo de token, lexer e analisador - não há, pelo menos na versão 3.4, nenhuma maneira de reutilizá-los.

Eu ficaria grato se alguém pudesse me dar uma recomendação sobre o que usar no lugar - GOLD é claro uma opção, embora gerar código C ++ ou C pareça muito mais complicado do que a variedade C #. Minha gramática é compatível com LALR e LL (1). A principal preocupação é analisar o desempenho em pequenas entradas.

Answer 1

Eu tentaria impulsionar :: espírito.Muitas vezes, é extremamente rápido (mesmo para analisar coisas simples como um número inteiro, pode ser mais rápido do que a função C atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html )

http://boost-spirit.com/home/

Tem coisas boas: apenas cabeçalho, portanto, inferno de dependências, licença liberal.

No entanto, esteja avisado que a curva de aprendizado é difícil.É C ++ moderno (sem ponteiro, mas com muitos modelos e erros de compilação muito frustrantes), portanto, vindo de C ou C #, você pode não se sentir muito confortável.

Answer 2

Se a gramática a ser analisada for simples, você pode escrever o analisador à mão.

A maioria dos geradores de analisador é projetada para facilitar a preparação de um analisador funcional, e o tempo de execução geralmente é prejudicado.

Answer 3

O melhor desempenho que vi em análise veio de Boost.Spirit.Qi, que expressa a gramática em C ++ usando programação de meta-template.Não é para quem tem coração fraco.

Isso precisará ser bem isolado e o tempo de compilação do arquivo que contém o analisador aumentará para vários segundos (então é melhor garantir que haja o mínimo possível).

Answer 4

Se a sintaxe da sua expressão for simples o suficiente, considere fazer um analisador descendente recursivo escrito à mão .Ele pode ser executado muito rápido e oferecer a capacidade (com cuidado suficiente) para relatar erros de sintaxe de maneira adequada e específica.

Você também pode usar bison , mas acredito que um analisador recursivo escrito à mão provavelmentevá mais rápido.

E você pode fazer lexing com um lexer gerado por flex e fazer a análise manualmente,de forma descendente recursiva.

Para sua informação, o compilador GCC tem seus próprios analisadores descendentes recursivos para C ++ e C, pelo menos.Ele não usa mais geradores de analisador (como bison ou ANTLR ).

Answer 5

Em vez de expr, faça com que a gramática reconheça sequence-of-expr.

Em vez de ter (sintaxe bison):

start: expr { process_expr ($1); }
     ;

tem:

start: expr_seq ;

expr_seq:   expr          { process_expr ($1); }
          | expr_seq expr { process_expr ($2); }
          ;

Answer 6

Escrevi muitos analisadores sintáticos, e a descida recursiva codificada manualmente é a minha maneira de fazer isso.Eles são fáceis de escrever e bastante ideais.

Dito isso, se você busca velocidade, não importa o que você escreva, haverá espaço de sobra para acelerá-lo. Serão de maneiras que podem surpreendê-lo, porque qualquer coisa em que pudesse pensar, você já teria feito.

Aqui está um conjunto de slides mostrandocomo fazer.