Analisador_Redutivo

Prévia do material em texto

Análise Sintática Redutiva
A análise sintática redutiva são analisadores de precedência de operadores que se descrevem como podendo manipular analisadores léxicos sem uma necessidade de uma gramática subjacente e também tende a ser mais simples e eficiente.
Os tipos desses analisadores são: Simple LR (SLR), LR Canônico, Look Ahead LR (LALR).
SLR ou Simple LR: É um método mais simples com tabelas de análise relativamente pequenas mas geralmente eficiente pois encontra a única correta análise do tipo bottom-up percorrendo da esquerda para a direita.
LR Canônico: Consiste em usar símbolos de lookahead para tomar decisões em um analisador de redução de turno (o qual reduz a string ao primeiro símbolo da gramática) chamado de shift-reduce.
O LALR: Baseado no analisador Cânonico porém ultiliza técnicas de compactação dos estados
Quanto ao Analisador redutivo a sua gramática tende a ser de procedência de operadores, ou seja:
1. Não há símbolos não-terminais adjacentes.
2. Não há produções que derivam a cadeia nula.
Então terá que transformar a gramática de não precedẽncia para uma de precedência de operadores, por exemplo:
A = <A><B><A>
B = + | -
Ficando assim:
A = <A> + <A> | <A> - <A>
Para identificar essas substituições (handles) utilizá-se símbolos de menor, maior e igual para respectivamente identificar se o terminal tem precedência menor, maior ou a mesma precedência.
Usando esses símbolos é capaz de se construir uma tabela sintática porém seguindo as seguintes regras:
1. Se a<b ou a=b, então empilha b. Se a>b, então procura o lado direito do handle na pilha e o substitui pelo seu lado esquerdo
	
	id
	(
	+
	$
	id
	
	>
	>
	>
	(
	<
	>
	<
	>
	+
	<
	>
	>
	>
	$
	<
	<
	<
	
A primeira linha são os elementos da Cadeia, e os da primeiro coluna são os que estão no topo da pilha.
Dentro da tabela fica os símbolo idicando as substituições.
Fontes: http://www2.fct.unesp.br/docentes/dmec/olivete/compiladores/arquivos/Aula8.pdf