Como fazer recursiva analisadores subida trabalho?

Question

Como fazer recursiva analisadores subida trabalho? Eu escrevi uma recursiva descida analisador mim, mas eu não entendo LR analisadores todos muito bem. O que eu encontrado na Wikipedia só fez aumentar minha confusão.

Outra questão é por analisadores de subida recursivas não são usados ??mais do que suas contrapartes com base em tabela. Parece que os analisadores de subida recursiva ter maior desempenho global.

Answer 1

O livro clasical dragão explica muito bem como analisadores LR trabalho. Há também análise técnicas. Um Guia Prático. onde você pode ler sobre eles, se me lembro bem. O artigo na wikipedia (pelo menos a introdução) não está certo. Eles foram criados por Donald Knuth, e ele explica-los em seu The Art of Computer Programming Volume 5. Se você compreender espanhol, há uma lista completa de livros aqui postado por mim. Nem tudo o que os livros são em espanhol, também.

Antes de entender como eles funcionam, você deve compreender alguns conceitos como primeiro, segue e lookahead. Além disso, eu realmente recomendo que você a entender os conceitos por trás LL (descendente) analisadores antes de tentar entender LR analisadores (Ascendente).

Há uma família de analisadores LR, especialmente LR (K), SLR (K) e LALR (K), onde K é quantas lookahead eles precisam de trabalho. Yacc suporta LALR (1) analisadores, mas você pode fazer ajustes, e não teoria baseada, para torná-lo trabalha com mais poderoso tipo de gramáticas.

Sobre o desempenho, isso depende da gramática está sendo analisado. Eles executam em tempo linear, mas quantos espaço que eles precisam depende de quantos estados você constrói para o analisador final.

Answer 2

Eu pessoalmente estou tendo dificuldade em entender como uma chamada de função pode ser mais rápido - muito menos "significativamente mais rápido" do que uma consulta à tabela. E eu suspeito que mesmo "significativamente mais rápido" é insignificante quando comparado a tudo o mais que um lexer / analisador tem a ver (principalmente leitura e tokenizing o arquivo). Olhei para a página da Wikipedia, mas não seguiu as referências; que o autor realmente o perfil de um lexer / parser completo?

Mais interessante para mim é o declínio de analisadores de mesa-driven em relação à descida recursiva. I de um fundo C, onde yacc (ou equivalente) foi o gerador de analisador de escolha. Quando me mudei para Java, eu encontrei uma implementação baseada em tabelas (JavaCup), e várias implementações de descida recursiva (JavaCC, ANTLR).

Eu suspeito que a resposta é semelhante à resposta de "por que Java em vez de C": velocidade de execução não é tão importante quanto a velocidade de desenvolvimento. Como observado no artigo Wikipedia, analisadores de mesa-driven são praticamente impossível entender a partir do código (de volta quando eu estava usando-los, eu poderia seguir suas ações, mas nunca teria sido capaz de reconstruir a gramática do analisador). descendente recursivo, em comparação, é muito intuitivo (que é sem dúvida por isso que antecede por cerca de 20 anos baseada em tabelas).

Answer 3

O artigo da Wikipedia sobre recursiva ascensão analisar as referências que parece ser o artigo original sobre o tema ( "Very Fast LR análise"). Skimming que o papel limpou algumas coisas para mim. Coisas que eu observei:

1. As negociações de papel sobre geração de código de montagem. Gostaria de saber se você pode fazer as mesmas coisas que eles fazem, se você está gerando código C ou Java em vez; ver secções 4 e 5, "Recuperação de erros" e "verificação de estouro de pilha". (Eu não estou tentando FUD sua técnica - que poderia funcionar muito bem -. Apenas dizendo que é algo que você pode querer olhar para antes de cometer)

2. Eles comparam sua ferramenta de ascensão recursiva para seu próprio parser baseado em tabela. A partir da descrição na seção de seus resultados, parece que o seu analisador baseado em tabela é "totalmente interpretado"; não requer qualquer código gerado personalizado. Gostaria de saber se há um meio termo onde a estrutura geral ainda é baseada em tabelas, mas você gerar o código personalizado para determinadas ações para acelerar as coisas.

O documento referenciado pela página da Wikipedia:

• "análise LR Muito rápido" (1986)
• http://portal.acm.org/citation.cfm?id=13310.13326

Outro artigo sobre o uso de geração de código, em vez de mesa-interpretação:

• "analisadores YACC compatível muito rápida (para muito pouco esforço)" (1999)
• http://www3.interscience.wiley.com/journal/1773/abstract

Além disso, nota que recursiva-descida de análise não é o caminho mais rápido para línguas de análise LL-baseada em gramática:

• entre um LL e recursiva Descida analisador?