O Analizador LR

Analisadores LR

Esta família de analisadores também se baseia nas operações shift e reduce (é, na verdade, uma evolução natural do algoritmo geral shift-reduce). A diferença fundamental é que estas operações (shift e reduce) são realizados sempre deterministicamente, com base no estado corrente da análise e nas propriedades estruturais da gramática em questão.

Composição dos Analisadores LR

Um analisador LR compõe-se se:

• Algoritmo de Análise Sintática -> padrão para todas as técnicas da família.
• Tabela de Análise Sintática (ou tabela de parsing) -> específica para cada técnica e para cada gramática.
• Pilha de Estados (ou pilha sintática) -> conterá um histórico da análise efetuada; é inicializada com o estado inicial da análise sintática.
• Entrada -> conterá a sentença a ser analisada, seguida por $ (a marca de final de sentença).
• Uma G.L.C. -> com as produções numeradas de 1 a p.

Significado e Procedimentos Associados às Ações 

• Halt (ou Accept): -> Fim de análise;

• Procedimento – A análise sintática deve ser encerrada.

• Erro: -> Indica a ocorrência de um erro sintático.

• Procedimento – As rotinas de recuperação, se existirem, deverão ser ativadas para que a situação de erro seja contornada e a análise possa continuar; senão, a análise deve ser encerrada.

• Shift S -> Significa o reconhecimento sintático do símbolo da entrada.

• Procedimento – O símbolo da entrada deve ser retirado e o estado S, indicado na tabela de Parsing, deverá ser empilhado.

• Reduce R -> Significa que uma redução pela produção número R deve ser efetuada.

• Procedimento – Deverão ser retirados da pilha sintática tantos estados quantos forem os símbolos do lado direito da produção R, e o símbolo do lado esquerdo dessa produção deverá ser tratado como um símbolo de entrada na próxima ação do analisador.

Observações: O processo de determinar e efetuar as ações sintáticas deverá ser repetido até que a ação Halt seja encontrada ou, para as implementações sem recuperação de erros, um erro seja detectado.

Tabela de Parsing LR

A tabela de parsing dos analisadores LR é dividida em duas partes:

Tabela Action -> contém as transições (Shift, Reduce, Erro e Halt) com os símbolos terminais.

• Tabela Goto -> contém as transições (Goto e Erro) com os símbolos não-terminais (Um Goto é um Shift especial sobre um símbolo não-terminal).

Exemplo SHIFT[pic 1]

1. A linha da tabela corresponde ao topo da pilha e a coluna corresponde ao símbolo inicial da entrada.
2. Após identificar a ação correta, ela é adicionada na tabela na coluna ação.
3. O número que acompanha a ação é adicionado ao topo da pilha.

Exemplo REDUCE[pic 2]

1. O número que acompanha a operação de redução corresponde ao número da produção.
2. Deve ser removido da pilha o número de produções.
3. A linha corresponde ao topo da pilha com os símbolos já removidos e a coluna o símbolo gerador da gramatica.
4. O número encontrado é adicionado no topo da pilha.

...