Quais são as principais vantagens e desvantagens da análise de LL e LR?

Ao construir um analisador para uma linguagem de programação, o que ganho e o que perdi ao escolher um ou outro?

Compararei a análise LL e LR para vários critérios:

Complexidade

LL vence aqui, mãos para baixo. Você pode escrever com facilidade um analisador LL à mão. De fato, isso geralmente é feito: o compilador C # da Microsoft é um analisador de descida recursivo escrito à mão (fonte aqui , procure um comentário feito por Patrick Kristiansen - o post do blog também é muito interessante).

A análise de LR usa um método bastante contra-intuitivo para analisar um texto. Funciona, mas levei algum tempo para entender exatamente como funciona. Escrever esse analisador manualmente é, portanto, difícil: você implementaria mais ou menos um gerador de analisador LR.

Generalidade

O LR vence aqui: todos os idiomas LL são idiomas LR, mas há mais idiomas LR do que idiomas LL (um idioma é um idioma LL, se pode ser analisado com um analisador LL, e um idioma é um idioma LR, se pode ser analisado com um analisador LR).

O LL possui muitos incômodos que o incomodarão na implementação de praticamente qualquer linguagem de programação. Veja aqui uma visão geral.

Existem idiomas inequívocos que não são idiomas LR, mas esses são bem raros. Você quase nunca encontra esses idiomas. No entanto, o LALR tem alguns problemas.

O LALR é mais ou menos um hack para os analisadores de LR tornarem as tabelas menores. As tabelas para um analisador de LR geralmente podem crescer enormes. Os analisadores LALR abrem mão da capacidade de analisar todos os idiomas LR em troca de tabelas menores. A maioria dos analisadores de LR realmente usa LALR (embora não secretamente, geralmente você pode encontrar exatamente o que implementa).

A LALR pode reclamar sobre conflitos de redução de turno e redução de redução. Isso é causado pelo hack da tabela: ele 'dobra' entradas semelhantes, o que funciona porque a maioria das entradas está vazia, mas quando não está vazia, gera um conflito. Esses tipos de erros não são naturais, difíceis de entender e as correções geralmente são bastante estranhas.

Erros do compilador e recuperação de erros

LL vence aqui. Em uma análise LL, geralmente é muito fácil emitir erros úteis do compilador, principalmente em analisadores escritos à mão. Você sabe o que está esperando a seguir; portanto, se não aparecer, geralmente você sabe o que deu errado e qual seria o erro mais sensato.

Além disso, na análise de LL, a recuperação de erros é muito mais fácil. Se uma entrada não analisar corretamente, você pode tentar avançar um pouco e descobrir se o restante da análise é analisado corretamente. Se, por exemplo, alguma instrução de programação estiver malformada, você poderá pular adiante e analisar a próxima instrução, para detectar mais de um erro.

Usando um analisador de LR, isso é muito mais difícil. Você pode tentar aumentar sua gramática para que ela aceite entradas erradas e imprima erros nas áreas onde as coisas deram errado, mas isso geralmente é bastante difícil de fazer. A chance de você acabar com uma gramática não LR (ou não LALR) também aumenta.

Rapidez

A velocidade não é realmente um problema com a maneira pela qual você analisa sua entrada (LL ou LR), mas a qualidade do código resultante e o uso de tabelas (você pode usar tabelas para LL e LR). LL e LR são, portanto, comparáveis ​​a este respeito.

Ligações

Aqui está um link para um site que também contrasta com LL e LR. Procure a seção perto da parte inferior.

Aqui você pode encontrar uma conversa sobre as diferenças. Não é uma má idéia olhar criticamente para as opiniões expressas lá, porém, há um pouco de uma guerra santa acontecendo lá.

Para mais informações, aqui e aqui estão duas das minhas próprias postagens sobre analisadores, embora não sejam estritamente sobre o contraste entre LL e LR.