Análise Sintática Bottom-Up e Analisadores LR

Análise Sintática Bottom-Up (Ascendente)

Constrói a árvore a partir dos tokens do texto até o símbolo inicial da gramática (redução).

A sentença é reduzida ao símbolo inicial da gramática, o que equivale a fazer uma derivação mais à direita invertida.

Redução na Análise Sintática

• Em cada passo da redução, uma subcadeia específica, que corresponde ao lado direito de uma produção, é substituída pelo não-terminal na cabeça da produção.
• As principais decisões relacionadas com a análise ascendente em cada passo do reconhecimento são:
  • Determinar quando reduzir;
  • Determinar a produção a ser aplicada para que a análise prossiga.

Handle (Alça)

É uma subcadeia que reconhece o lado direito de uma produção e cuja redução ao não-terminal do lado esquerdo representa um passo ao longo do percurso de uma derivação mais à direita.

Tipos de Analisadores Sintáticos Bottom-Up

Analisadores Shift-Reduce

Substituem o lado direito da produção (corpo) pelo não-terminal correspondente (cabeça).

• Implementação: Utilizam autômatos de pilha.
• Processo: Empilham a sentença de entrada até que se tenha na pilha o lado direito de alguma produção.

Família de Analisadores LR

• SLR (Simple LR): Fáceis de implementar, porém aplicáveis a uma classe restrita de gramáticas.
• LR Canônicos: Possuem poder e custo intermediários, funcionando para a maioria das gramáticas de linguagens de programação.
• LALR (Lookahead LR): Mais poderosos e mais caros, aplicáveis a um grande número de linguagens livres de contexto.

Vantagens dos Analisadores LR

• Reconhecem praticamente todas as construções sintáticas definidas pelas GLC (Gramáticas Livres de Contexto).
• Evitam retrocesso.
• A classe de gramáticas que podem ser reconhecidas pelos analisadores LR é um superconjunto da própria classe gramatical.

Desvantagens dos Analisadores LR

• Difíceis de implementar manualmente.
• Exigem o uso de ferramentas especializadas (ex: Yacc).

Funcionamento dos Analisadores LR

• Consistem em: uma entrada, uma saída, uma pilha, um algoritmo de análise sintática e uma tabela sintática que possui duas partes (ação e desvio).
• O algoritmo é o mesmo para todos os tipos de analisadores LR; o que varia é a tabela.
• O algoritmo de análise lê caracteres de um buffer de entrada, e um analisador LR transfere um estado.
• Cada estado resume a informação contida na pilha abaixo dele.
• A pilha contém uma sequência de estados s₀, s₁, ..., s_m.