Recursiva Descida vs. analisadores gerados - Eficiência

Question

Como fazer analisador sintático descendente recursivo escritas à mão (que são inevitavelmente LL (k)) comparar com analisadores LALR gerados em termos de desempenho?

Eu sei que analisadores LALR são capazes de lidar com muito mais do que gramáticas LL (k); no entanto, é minha intenção de escrever o meu analisador à mão, e descida recursiva parece ser a escolha mais adequada. É possível escrever qualquer outro tipo à mão (razoavelmente legível) por interesse?

Nota Eu estou usando uma linguagem funcional, com otimização de chamada (F #), então [bem costurado] recursão não vai ser tanto de uma questão como em outros idiomas.

Answer 1

Eu acho que muito depende do idioma que você está tentando analisar. Outra parte do desempenho que às vezes fica esquecido é a análise lexical (digitalização) parte - é significativa para o desempenho como ele lida com personagens em vez de símbolos. descendente recursivo é uma boa primeira iteração em escrever um parser, e faz seguinte lógica da linguagem analisado bastante natural. Eu acho que se os ajustes da língua processadas que são (sem deixou recursão) você deve começar com descida recursiva. Escolhendo LALR para o desempenho nesta fase parece ser otimização prematura. Você pode escrever um gráfico analisador à mão, mas eu duvido que isso é o que você quer dizer. Escrever um analisador LALR à mão é possível, mas tedioso.

Answer 2

Decidir entre LALR e LL para desempenho razões neste sons pontuais como a otimização prematura. tempo de análise raramente é o gargalo em um compilador. Se eu fosse você, eu iria escolher com base em se você está mais confortável definir a sua gramática de baixo para cima ou de cima para baixo.

Pessoalmente, acho LALR gramáticas fácil trabalhar com, e integração de F # fsyacc (que é como eu aprendi a análise) faz com que seja muito fácil de integrar yacc em seu projeto.