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.

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.

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.)