Análise Sintática: Técnicas e Algoritmos

Análise Sintática: Técnicas e Algoritmos

Função da Análise Sintática (AS)

A função da AS é agrupar tokens em frases gramaticais e analisar a sintaxe do código fonte, ou seja, verificar se a estrutura do código está de acordo com as regras da linguagem. Erros como desbalanceamento de parênteses (), chaves {}, e colchetes [] são identificados nessa fase.

Abordagens de Análise Sintática

Top-Down

Encontra a derivação mais à esquerda da cadeia de entrada. Constrói a árvore sintática da raiz para as folhas, gerando a árvore em pré-ordem (ex: Analisador Recursivo com Retrocesso e Preditivo LL1).

Bottom-Up

Utiliza o conceito de empilhar e reduzir. Constrói a árvore sintática para uma cadeia de entrada partindo das folhas e reduzindo até o símbolo da raiz (ex: Shift-Reduce com Backtracking, SLR1, LALR1 e LR1).

Analisador Recursivo com Retrocesso

Expande a árvore sempre pelo não-terminal mais à esquerda. Quando há mais de uma regra de produção para um não-terminal, todas as alternativas são testadas até encontrar um sucessor ou um erro. Problema: Uma gramática recursiva à esquerda pode levar o analisador a um laço infinito, expandindo um não-terminal repetidamente sem consumir símbolos de entrada. É necessário retirar ações semânticas e há dificuldade para especificar onde ocorreu o erro. Solução: Tratar a gramática para identificar univocamente qual produção deve ser expandida.

Analisador Preditivo LL1

O objetivo do LL1 é evitar o retrocesso, fazendo com que o token identifique exatamente qual produção deve ser aplicada na expansão de um não-terminal. Elimina a recursão (pilha implícita) usando uma pilha explícita. É necessário que a gramática não seja recursiva à esquerda para que a entrada da tabela seja única.

Analisador Shift-Reduce

Substitui o lado direito de uma produção pelo não-terminal correspondente.

• Shift: transfere o próximo símbolo da entrada para o topo da pilha.
• Reduce: reduz a cadeia de caracteres a ser reduzida que está no topo da pilha. Localiza o extremo esquerdo da cadeia no interior da pilha e decide para qual não-terminal esta cadeia será substituída.
• Aceitar: anuncia que a análise terminou com sucesso.
• Erro: chama uma rotina de tratamento de erro ou aborta a análise.

Problema: Conflito em caso de ambiguidade. Não é possível definir entre empilhar (shift) e reduzir (reduce).

Família de Analisadores LR(k)

Vantagens:

• Reconhecem praticamente todas as construções sintáticas definidas por gramáticas livres de contexto.
• Evitam o retrocesso.
• A classe de gramáticas que podem ser analisadas por LR é um superconjunto das gramáticas LL.
• Possibilidade de detecção de erros assim que possível.

Desvantagem: Difícil de implementar e requer o uso de ferramentas especializadas como Yacc.

Funcionamento: O algoritmo é o mesmo para todos, o que varia é a tabela de análise. O algoritmo lê um buffer de entrada e um analisador LR transfere um estado para uma pilha. Cada estado resume a informação contida na pilha abaixo dele.

• SLR: Implementação simples, porém, analisa uma classe restrita de gramáticas.
• LR Canônico: Poder de análise intermediário, porém, funciona para a maioria das gramáticas de linguagens de programação.
• LALR: Mais poderoso e mais eficiente, aplicado a um grande número de linguagens livres de contexto.

Reduções

Em um passo de redução, uma subcadeia específica, que casa com o lado direito de uma produção, é substituída pelo não-terminal da cabeça da produção. Dificuldades: determinar quando reduzir e qual produção deve ser aplicada para que a análise prossiga.

Poda "Handle"

"Handle" é uma cadeia de símbolos e uma produção cuja subcadeia casa com o corpo da produção e cuja redução deve ser feita em seguida. Representa um passo da derivação mais à direita inversa.

Gramáticas Ambíguas e Gramáticas Recursivas à Esquerda

Gramática Ambígua: Uma mesma sentença apresenta duas ou mais árvores de derivações. Problema: Os compiladores exigem derivações únicas para obter bom desempenho ou concluir a análise sintática.

Gramática Recursiva à Esquerda: É possível que exista uma derivação A -> A(alfa) para alguma cadeia alfa. Problema: Gramáticas recursivas à esquerda não podem ser processadas por analisadores Top-Down, consequentemente, uma transformação que elimine a recursão à esquerda é necessária.

Análise Sintática Explícita e Implícita

Explícita: Existe uma estrutura de dados de pilha dentro do analisador que é usada durante o processo. Essa pilha não é implícita e é gerenciada por chamadas recursivas de dois métodos. A pilha pode ser uma pilha do compilador ou o processo de empilhar pode ser uma chamada de um método e o desempilhar ocorre quando a função retorna.

Implícita: A pilha é gerenciada implicitamente pelo mecanismo de chamadas de função da linguagem de programação.

Tradução Dirigida por Sintaxe

É uma técnica de compilação orientada por gramática e auxilia na organização das partes do compilador. O esquema de tradução é uma gramática livre de contexto na qual fragmentos de programas, chamados de ações semânticas, são inseridos nos lados direitos das produções. O esquema de tradução é como uma definição dirigida pela sintaxe, exceto que a semântica das regras de avaliação é mostrada explicitamente.

Compilação em um Passo e em Passos Separados

Compilação em um passo: Percorre as partes de cada unidade do compilador uma única vez, traduzindo cada parte em código de máquina.

Compilação em vários passos: Converte o código fonte em código de máquina em uma ou mais representações intermediárias, reprocessando todo o código em cada passo sequencial.