O que é um analisador IELR (1)?

14

Eu tento me ensinar o uso do bisonte. A página de manual bison (1) diz sobre o bison:

Gere um analisador determinístico de LR ou LR generalizado (GLR) empregando tabelas de analisador LALR (1), IELR (1) ou LR (1) canônico.

O que é um analisador IELR? Todos os artigos relevantes que encontrei na rede mundial de computadores são pagos.

FUZxxl
fonte
@reinierpost Eu me sinto tão estúpido agora. Por que não encontrei isso?
FUZxxl
Eu não sei - Google faz resultados personalizamento ...
reinierpost
@reinierpost, você gostaria de responder a esta pergunta citando o seu link, para limpar essa pergunta ?
Merbs
Hmmm ... se é tudo o que é preciso, ok.
Reinierpost

Respostas:

3

O algoritmo de análise IELR (1)

O algoritmo de análise IELR (1) foi desenvolvido em 2008 por Joel E. Denny como parte de seu Ph.D. pesquisa sob a supervisão de Brian A. Malloy na Universidade Clemson. O algoritmo IELR (1) é uma variação do chamado algoritmo LR "mínimo" desenvolvido por David Pager em 1977 , que por si só é uma variação do algoritmo de análise LR (k) inventado por Donald Knuth em 1965 . O IE no IELR (1) significa eliminação de inadequação (consulte a última seção).

Algoritmos LR (1)

A LR (1) parte de IELR (1) meios G eft para a direita, R ightmost derivação com uma antecipação token. Os analisadores LR (1) também são chamados de analisadores canônicos. Essa classe de algoritmos de análise emprega uma estratégia de análise de baixo para cima e com turnos reduzidos, com uma tabela de transição de pilha e estado que determina a próxima ação a ser executada durante a análise.

Historicamente, os algoritmos LR (1) têm sido prejudicados por grandes requisitos de memória para suas tabelas de transição. A melhoria de Pager foi desenvolver um método de combinar os estados de transição quando a tabela de transição é gerada, reduzindo significativamente o tamanho da tabela. Assim, o algoritmo de Pager torna os analisadores LR (1) competitivos com outras estratégias de análise com relação à eficiência de espaço e tempo. A frase "analisador mínimo de LR (1)" refere-se ao tamanho mínimo da tabela de transição introduzida pelo algoritmo de Pager.

Limitações do algoritmo de Pager

Os algoritmos LR mínimos (1) produzem a tabela de transição com base em uma gramática de entrada específica para o idioma a ser analisado. Gramáticas diferentes podem produzir o mesmo idioma. De fato, é possível que uma gramática não LR (1) produza uma linguagem analisável LR (1). Na prática, os geradores de analisadores LR (1) aceitam gramáticas não LR (1) com uma especificação para resolver conflitos entre duas transições de estado possíveis ("conflitos de redução de turno") para acomodar esse fato. Denny e Malloy descobriram que o algoritmo de Pager falha ao gerar analisadores poderosos o suficiente para analisar linguagens LR (1) quando fornecidas determinadas gramáticas não LR (1), embora a gramática não LR (1) gere uma linguagem LR (1).

Denny e Malloy mostram que essa limitação não é meramente acadêmica, demonstrando que Gawk e Gpic, software maduro e amplamente utilizado, executam ações incorretas do analisador.

Melhorias no IELR (1)

Denny e Malloy estudaram a fonte das deficiências do algoritmo de Pager comparando a tabela de transição gerada pelo algoritmo de Pager com a tabela de transição de uma gramática equivalente LR (1) e identificaram duas fontes do que denominam inadequações que aparecem na tabela de transição de Pager algoritmo, mas não na tabela de transição LR (1). O algoritmo IELR (1) de Denny and Malloy ( eliminação de inadequação LR (1)) é um algoritmo projetado para eliminar essas inadequações ao gerar a tabela de transição com tamanho praticamente idêntico ao do algoritmo de Pager.

Robert Jacobson
fonte
6

Um artigo que pretende apresentá-lo: IELR (1): Tabelas Analisadoras Práticas de LR (1) para Gramáticas Não-LR (1) com Resolução de Conflitos (via archive.org) por Joel E. Denny e Brian A. Malloy, Clemson University , está disponível gratuitamente no site da Malloy.

O que eles valem é algo que não posso responder. (Pessoalmente, não entendo a necessidade de uma análise CFG tão aleijada - por que limitar seu poder expressivo quando você pode apenas usar o GLR ? O que faz sentido para mim é algo como TAG ou PEG (eles parecem naturais e acrescentam poder expressivo) ou árvore gramáticas (para linguagens como XML, nas quais o reconhecimento de árvores de análise é sem problemas por design.)

reinierpost
fonte
Embora eu concorde com o princípio em relação à tecnologia, o problema geralmente é que a análise determinística tradicional tem implementações melhores e mais completas. Outra questão é que a análise de CF geral é mais poderosa, mas o GLR pode não ser a melhor versão.
babou
4
A principal razão pela qual as pessoas desenvolveram analisadores CFG prejudicados é que um analisador GLR não é necessariamente executado em tempo linear - esse é um grande problema para muitos aplicativos. Um analisador IELR pode garantir tempo de execução linear e muito mais.
FUZxxl
Não entendo por que isso seria um problema.
Reinierpost
2
O(n4)O(n3)euEumxO(nx)
3
Gostaria de observar que "Pessoalmente, não entendo a necessidade de uma análise CFG tão prejudicada - por que limitar seu poder expressivo quando você pode apenas usar a GLR?" é bastante equivocado neste contexto. O IELR (1) é usado para gerar tabelas do analisador LR (1) mais eficientes , o que permite analisadores GLR mais eficientes .
orlp