Compiladores E Computabilidade Unidade II R

Análise Sintática II – Ascendente
As configurações também serão da forma (α, y), em que α é o conteúdo da pilha e y é o resto da entrada. Entretanto, a convenção sobre o topo da pilha é invertida: o topo fica à direita, ou seja, o último símbolo de α é o símbolo do topo. As mudanças de configuração são:
(1) redução pela regra A→ α: permite passar da configuração (βα, y) para a configuração (βA, y).
(2) empilhamento ou deslocamento de um terminal s: permite passar da configuração
(α, sy) para a configuração (αs, y).
Observe que este último tipo de transição é o que permite trazer os terminais para a pilha a fim de que possam participar das reduções.
A configuração inicial para a entrada x é (ε, x), com a pilha vazia, e ao final temos a configuração (S, ε), indicando que toda a entrada x foi lida e reduzida para S. Exemplo: Na tabela abaixo, é possível observar as configurações sucessivas de um analisador ascendente, para a cadeia x. A terceira coluna apresenta os passos correspondentes da derivação direita de x.
Pilha
(topo à esquerda) ε a
F
T
E
E+
E+a
E+F
E+T
E+T*
E+T*a
E+T*F
E+T
E

(restante da)
Entrada
a+a*a
+a*a
+a*a
+a*a
+a*a a*a *a
*a
*a a ε ε ε ε Derivação direita
(invertida)
a+a*a ⇐ F+a*a
⇐ T+a*a
⇐ E+a*a

⇐ E+F*a
⇐ E+T*a

⇐ E+T*F
⇐ E+T
⇐ E

Análise Sintática sLR(1)
Há um método de análise sintática ascendente que é chamado sLR(1). As letras que geram a sigla que lhe dá nome indicam:
•

S: a variante mais simples dos métodos LR(1).

•
•
•

L: a cadeia de entrada é lida da esquerda para a direita (left‐to‐right).
R: o método constrói uma derivação direita (rightmost) invertida.
1: apenas um símbolo do resto da entrada é examinado.

Como o símbolo inicial pode ocorrer em diferentes partes da árvore de derivação, devemos distinguir sua ocorrência relativa à raiz da árvore das demais. Assim, para simplificar a identificação do