Qual é a diferença entre analisadores LR, SLR e LALR?

Qual é a diferença real entre os analisadores LR, SLR e LALR? Eu sei que SLR e LALR são tipos de analisadores LR, mas qual é a diferença real no que diz respeito às tabelas de análise?

E como mostrar se uma gramática é LR, SLR ou LALR? Para uma gramática LL, só temos que mostrar que qualquer célula da tabela de análise não deve conter várias regras de produção. Alguma regra semelhante para LALR, SLR e LR?

Por exemplo, como podemos mostrar que a gramática

S --> Aa | bAc | dc | bda
A --> d

é LALR (1), mas não SLR (1)?

EDIT (ybungalobill) : Não obtive uma resposta satisfatória para qual é a diferença entre LALR e LR. Portanto, as tabelas do LALR são menores em tamanho, mas podem reconhecer apenas um subconjunto das gramáticas LR. Alguém pode elaborar mais sobre a diferença entre LALR e LR, por favor? LALR (1) e LR (1) serão suficientes para uma resposta. Ambos usam 1 token look-ahead e ambos são controlados por tabela! Como eles são diferentes?

Os analisadores SLR, LALR e LR podem ser implementados usando exatamente o mesmo maquinário baseado em tabelas.

Fundamentalmente, o algoritmo de análise coleta o próximo token de entrada T e consulta o estado atual S (e as tabelas de lookahead, GOTO e redução associadas) para decidir o que fazer:

• SHIFT: Se a tabela atual diz para SHIFT no token T, o par (S, T) é colocado na pilha de análise, o estado é alterado de acordo com o que a tabela GOTO diz para o token atual (por exemplo, GOTO (T) ), outro token de entrada T 'é buscado e o processo se repete
• REDUZIR: Cada estado tem 0, 1 ou muitas reduções possíveis que podem ocorrer no estado. Se o analisador for LR ou LALR, o token é verificado em relação aos conjuntos de antevisão para todas as reduções válidas para o estado. Se o token corresponde a um conjunto de antevisão para uma redução da regra gramatical G = R1 R2 .. Rn, ocorre uma redução e deslocamento da pilha: a ação semântica de G é chamada, a pilha é removida n (de Rn) vezes, o par ( S, G) é colocado na pilha, o novo estado S 'é definido como GOTO (G), e o ciclo se repete com o mesmo token T. Se o analisador for um analisador SLR, há no máximo uma regra de redução para o estado e, portanto, a ação de redução pode ser feita às cegas, sem pesquisar para ver qual redução se aplica. É útil para um analisador SLR de saber se existe éuma redução ou não; isso é fácil de dizer se cada estado registra explicitamente o número de reduções associadas a ele e essa contagem é necessária para as versões L (AL) R na prática de qualquer maneira.
• ERROR: Se nem SHIFT nem REDUCE for possível, um erro de sintaxe é declarado.

Então, se todos eles usam o mesmo maquinário, de que adianta?

O valor alegado em SLR é sua simplicidade na implementação; você não precisa examinar as reduções possíveis verificando os conjuntos de antevisão porque há no máximo um, e esta é a única ação viável se não houver SHIFT saídas do estado. A redução que se aplica pode ser anexada especificamente ao estado, para que a máquina de análise SLR não precise procurá-la. Na prática, os analisadores L (AL) R lidam com um conjunto útil de idiomas maior e é tão pouco trabalho extra para implementar que ninguém implementa SLR, exceto como um exercício acadêmico.

A diferença entre LALR e LR tem a ver com o gerador de tabela. Os geradores de analisador LR controlam todas as reduções possíveis de estados específicos e seu conjunto de lookahead preciso; você termina com estados nos quais cada redução está associada a seu conjunto de lookahead exato a partir de seu contexto esquerdo. Isso tende a construir conjuntos bastante grandes de estados. Os geradores do analisador LALR estão dispostos a combinar estados se as tabelas GOTO e conjuntos de lookhead para reduções forem compatíveis e não entrarem em conflito; isso produz um número consideravelmente menor de estados, ao preço de não ser capaz de distinguir certas sequências de símbolos que LR consegue distinguir. Portanto, os analisadores LR podem analisar um conjunto maior de linguagens do que os analisadores LALR, mas têm tabelas de analisador muito maiores. Na prática, pode-se encontrar gramáticas LALR que estão próximas o suficiente dos idiomas-alvo para que o tamanho da máquina de estado valha a pena otimizar;

Portanto: todos os três usam a mesma máquina. SLR é "fácil" no sentido de que você pode ignorar um pouquinho da máquina, mas simplesmente não vale a pena. LR analisa um conjunto mais amplo de idiomas, mas as tabelas de estado tendem a ser bem grandes. Isso deixa o LALR como a escolha prática.

Dito tudo isso, é importante saber que os analisadores GLR podem analisar qualquer linguagem livre de contexto, usando máquinas mais complicadas, mas exatamente as mesmas tabelas (incluindo a versão menor usada pelo LALR). Isso significa que o GLR é estritamente mais poderoso que o LR, LALR e SLR; basicamente, se você puder escrever uma gramática BNF padrão, o GLR irá analisar de acordo com ela. A diferença no mecanismo é que o GLR está disposto a tentar análises múltiplas quando há conflitos entre a tabela GOTO e / ou conjuntos de lookahead. (Como o GLR faz isso de forma eficiente é pura genialidade [não minha], mas não caberá neste post SO).

Isso para mim é um fato extremamente útil. Eu construo analisadores de programa e transformadores e analisadores de código são necessários, mas "desinteressantes"; o trabalho interessante é o que você faz com o resultado analisado e, portanto, o foco está em fazer o trabalho de pós-análise. Usar o GLR significa que posso construir gramáticas funcionais com relativa facilidade, em comparação com hackear uma gramática para entrar na forma utilizável do LALR. Isso é muito importante ao tentar lidar com idiomas não acadêmicos, como C ++ ou Fortran, onde você literalmente precisa de milhares de regras para lidar bem com a linguagem inteira, e não quer gastar sua vida tentando hackear as regras gramaticais para atender às limitações de LALR (ou mesmo LR).

Como um exemplo famoso, C ++ é considerado extremamente difícil de analisar ... por caras que fazem análise LALR. C ++ é simples de analisar usando o maquinário GLR usando praticamente as regras fornecidas no final do manual de referência do C ++. (Eu tenho precisamente esse analisador, e ele lida não apenas com o C ++ vanilla, mas também com uma variedade de dialetos de fornecedores. Isso só é possível na prática porque estamos usando um analisador GLR, IMHO).

[EDITAR novembro de 2011: estendemos nosso analisador para lidar com todo o C ++ 11. O GLR tornou isso muito mais fácil de fazer. EDITAR agosto de 2014: agora lidando com todo o C ++ 17. Nada quebrou ou piorou, GLR ainda é o miau do gato.]

Os analisadores LALR mesclam estados semelhantes dentro de uma gramática LR para produzir tabelas de estados do analisador que são exatamente do mesmo tamanho que a gramática SLR equivalente, que geralmente são uma ordem de magnitude menor do que as tabelas de análise LR puras. No entanto, para gramáticas LR que são muito complexas para serem LALR, esses estados mesclados resultam em conflitos do analisador ou produzem um analisador que não reconhece totalmente a gramática LR original.

BTW, menciono algumas coisas sobre isso em meu algoritmo de tabela de análise sintática MLR (k) aqui .

Termo aditivo

A resposta curta é que as tabelas de análise sintática LALR são menores, mas o mecanismo do analisador é o mesmo. Uma dada gramática LALR produzirá tabelas de análise muito maiores se todos os estados LR forem gerados, com muitos estados redundantes (quase idênticos).

As tabelas LALR são menores porque os estados semelhantes (redundantes) são mesclados, efetivamente descartando as informações de contexto / antecipação que os estados separados codificam. A vantagem é que você obtém tabelas de análise muito menores para a mesma gramática.

A desvantagem é que nem todas as gramáticas LR podem ser codificadas como tabelas LALR porque gramáticas mais complexas têm lookaheads mais complicados, resultando em dois ou mais estados em vez de um único estado mesclado.

A principal diferença é que o algoritmo para produzir tabelas LR carrega mais informações entre as transições de um estado para outro, enquanto o algoritmo LALR não. Portanto, o algoritmo LALR não pode dizer se um determinado estado mesclado deve realmente ser deixado como dois ou mais estados separados.

Mais uma resposta (YAA).

Os algoritmos de análise para SLR (1), LALR (1) e LR (1) são idênticos como Ira Baxter disse,
no entanto, as tabelas do analisador podem ser diferentes por causa do algoritmo de geração do analisador.

Um gerador de analisador SLR cria uma máquina de estado LR (0) e calcula as previsões da gramática (conjuntos FIRST e FOLLOW). Esta é uma abordagem simplificada e pode relatar conflitos que realmente não existem na máquina de estado LR (0).

Um gerador de analisador LALR cria uma máquina de estado LR (0) e calcula as previsões da máquina de estado LR (0) (por meio das transições de terminal). Esta é uma abordagem correta, mas ocasionalmente relata conflitos que não existiriam em uma máquina de estado LR (1).

Um gerador de analisador LR Canonical calcula uma máquina de estado LR (1) e os look-aheads já fazem parte da máquina de estado LR (1). Essas tabelas do analisador podem ser muito grandes.

Um gerador de analisador Minimal LR calcula uma máquina de estado LR (1), mas mescla estados compatíveis durante o processo e, a seguir, calcula as previsões da máquina de estado LR (1) mínima. Essas tabelas do analisador são do mesmo tamanho ou um pouco maiores do que as tabelas do analisador LALR, oferecendo a melhor solução.

LRSTAR 10.0 pode gerar analisadores LALR (1), LR (1), CLR (1) ou LR (*) em C ++, o que for necessário para sua gramática. Veja este diagrama que mostra a diferença entre os analisadores LR.

[Divulgação completa: LRSTAR é meu produto]

Suponha que um analisador sem um lookahead esteja analisando strings para sua gramática.

Usando seu exemplo dado, ele encontra uma string dc, o que faz? Isso se reduz a S, porque dcuma string válida é produzida por essa gramática? OU talvez estivéssemos tentando analisar bdcporque mesmo essa é uma string aceitável?

Como humanos, sabemos que a resposta é simples, só precisamos lembrar se acabamos de analisar bou não. Mas os computadores são estúpidos :)

Como um analisador SLR (1) tem poder adicional sobre LR (0) para executar uma verificação à frente, sabemos que nenhuma quantidade de verificação à frente não pode nos dizer o que fazer neste caso; em vez disso, precisamos olhar para trás em nosso passado. Assim, o analisador LR canônico vem para o resgate. Ele lembra o contexto passado.

A forma como se lembra desse contexto é que se disciplina, que sempre que encontrar um b, começará a trilhar um caminho de leitura bdc, como uma possibilidade. Portanto, quando ele vê um, dele sabe se já está percorrendo um caminho. Assim, um analisador CLR (1) pode fazer coisas que um analisador SLR (1) não pode!

Mas agora, como tivemos que definir tantos caminhos, os estados da máquina ficam muito grandes!

Assim, mesclamos os mesmos caminhos de aparência, mas, como esperado, isso pode gerar problemas de confusão. No entanto, estamos dispostos a correr o risco ao custo de reduzir o tamanho.

Este é o seu analisador LALR (1).

Agora, como fazer isso algoritmicamente.

Ao desenhar os conjuntos de configuração para o idioma acima, você verá um conflito de redução de deslocamento em dois estados. Para removê-los, você pode querer considerar um SLR (1), que toma decisões olhando para um seguimento, mas você observaria que ainda não será capaz. Assim, você desenharia os conjuntos de configuração novamente, mas desta vez com a restrição de que, sempre que calcular o fechamento, as produções adicionais adicionadas devem ter seguidor (es) estrito (s). Consulte qualquer livro sobre o que deve ser seguido.

A diferença básica entre as tabelas do analisador geradas com SLR vs LR, é que as ações de redução são baseadas no conjunto Follows para tabelas SLR. Isso pode ser excessivamente restritivo, causando, em última análise, um conflito de redução de mudança.

Um analisador LR, por outro lado, baseia as decisões de redução apenas no conjunto de terminais que podem realmente seguir o não terminal sendo reduzido. Este conjunto de terminais é frequentemente um subconjunto adequado do conjunto Follows de um não terminal e, portanto, tem menos chance de entrar em conflito com as ações de mudança.

Os analisadores LR são mais poderosos por esse motivo. No entanto, as tabelas de análise LR podem ser extremamente grandes.

Um analisador LALR começa com a ideia de construir uma tabela de análise LR, mas combina os estados gerados de uma forma que resulta em um tamanho de tabela significativamente menor. A desvantagem é que uma pequena chance de conflitos seria introduzida para algumas gramáticas que uma tabela LR teria evitado.

Os analisadores LALR são ligeiramente menos poderosos do que os analisadores LR, mas ainda mais poderosos do que os analisadores SLR. YACC e outros geradores de analisador semelhante tendem a usar LALR por esse motivo.

PS Para ser breve, SLR, LALR e LR acima realmente significam SLR (1), LALR (1) e LR (1), portanto, um token lookahead está implícito.

Os analisadores SLR reconhecem um subconjunto apropriado de gramáticas reconhecíveis pelos analisadores LALR (1), que por sua vez reconhecem um subconjunto adequado de gramáticas reconhecíveis pelos analisadores LR (1).

Cada um deles é construído como uma máquina de estado, com cada estado representando algum conjunto de regras de produção da gramática (e a posição em cada uma) enquanto analisa a entrada.

O exemplo do Dragon Book de uma gramática LALR (1) que não é SLR é este:

S → L = R | R
L → * R | id
R → L

Aqui está um dos estados para esta gramática:

S → L•= R
R → L•

O •indica a posição do parser em cada uma das produções possíveis. Não sabe em qual das produções está realmente até chegar ao fim e tentar reduzir.

Aqui, o analisador pode deslocar um =ou reduzir R → L.

Um analisador SLR (também conhecido como LR (0)) determinaria se poderia reduzir, verificando se o próximo símbolo de entrada está no seguinte conjunto de R(ou seja, o conjunto de todos os terminais na gramática que podem seguir R). Como =também está neste conjunto, o analisador SLR encontra um conflito de redução de deslocamento.

No entanto, um analisador LALR (1) usaria o conjunto de todos os terminais que podem seguir essa produção particular de R, que é apenas $(ou seja, fim da entrada). Portanto, nenhum conflito.

Como comentadores anteriores notaram, os analisadores LALR (1) têm o mesmo número de estados que os analisadores SLR. Um algoritmo de propagação antecipada é usado para direcionar antecipações para produções de estado SLR a partir de estados LR (1) correspondentes. O analisador LALR (1) resultante pode introduzir conflitos de redução-redução não presentes no analisador LR (1), mas não pode introduzir conflitos de redução de deslocamento.

Em seu exemplo , o seguinte estado LALR (1) causa um conflito de redução de deslocamento em uma implementação de SLR:

S → b d•a / $
A → d• / c

O símbolo a seguir /é o seguinte conjunto para cada produção no analisador LALR (1). Em SLR, follow ( A) inclui a, que também pode ser alterado.

Além das respostas acima, este diagrama demonstra como diferentes analisadores se relacionam:

Uma resposta simples é que todas as gramáticas LR (1) são gramáticas LALR (1). Comparado com LALR (1), LR (1) tem mais estados na máquina de estados finitos associada (mais do que o dobro dos estados). E essa é a principal razão pela qual as gramáticas LALR (1) requerem mais código para detectar erros de sintaxe do que as gramáticas LR (1). E mais uma coisa importante a saber sobre essas duas gramáticas é que nas gramáticas LR (1) podemos ter menos conflitos de redução / redução. Mas em LALR (1) há mais possibilidade de reduzir / reduzir conflitos.