Análise Léxica e Sintática em Compiladores: Técnicas e Desafios

Análise Sintática: Função e Erros Comuns

A função da Análise Sintática (AS) é agrupar os tokens em frases gramaticais e analisar se a sintaxe do código-fonte está bem formada, ou seja, se faz parte da linguagem. Erros comuns incluem o balanceamento de parênteses (), chaves {}, colchetes [] e estruturas if-then-else.

Abordagens de Análise Sintática: Top-Down e Bottom-Up

Análise Top-Down

• Encontra a derivação mais à esquerda da cadeia de entrada.
• Constrói a árvore gramatical a partir da raiz, criando os nós em pré-ordem.
• Exemplos: Analisador Descendente Recursivo com Retrocesso e Preditivo LL(1).

Análise Bottom-Up

• Usa o conceito de empilhar e reduzir.
• Constrói uma árvore gramatical para uma cadeia de entrada começando pelas folhas.
• Reduz ao símbolo raiz da cadeia.
• Exemplos: Shift-Reduce com Backtracking, SLR(1), LALR(1) e LR(1).

Analisador Descendente Recursivo com Retrocesso

O Analisador Descendente Recursivo com Retrocesso expande a árvore sempre pelo Não-Terminal (ÑT) mais à esquerda. Quando existe mais de uma regra de produção para o ÑT, todas as alternativas são testadas até o sucesso ou a ocorrência de um erro.

Problemas:

• Uma Gramática Recursiva à Esquerda (G RaE) pode levar o analisador a um laço infinito, expandindo o ÑT pela segunda vez sem consumir símbolos de entrada.
• Necessidade de retroceder ações semânticas.
• Dificuldade em precisar onde ocorreu o erro.

Solução:

• Tratar a gramática para que identifique univocamente qual produção deve ser expandida.

Analisador Preditivo LL(1)

O Analisador Preditivo LL(1) tem como objetivo evitar o retrocesso, fazendo com que o token identifique exatamente qual produção deve ser aplicada na expansão de um Não-Terminal (ÑT). Ele elimina a recursão (pilha implícita) usando uma pilha explícita. Para seu funcionamento, é necessário que a gramática não seja recursiva à esquerda, esteja fatorada e a entrada da tabela de análise seja única.

Analisador Shift-Reduce

O Analisador Shift-Reduce opera substituindo o lado direito de uma produção pelo Não-Terminal (ÑT) correspondente. Suas ações principais são:

• Shift (Empilhar): Transfere o próximo símbolo da entrada para o topo da pilha.
• Reduce (Reduzir): O extremo direito da cadeia a ser reduzida deve estar no topo da pilha. Localiza o extremo esquerdo da cadeia no interior da pilha e decide por qual ÑT essa cadeia será substituída.
• Accept (Aceitar): Anuncia o término bem-sucedido da análise.
• Error (Erro): Chama uma rotina de tratamento de erro ou aborta a análise.

Problema:

• Conflitos ocorrem em casos de ambiguidade, onde não é possível definir entre as ações empilhar/reduzir ou reduzir/reduzir.

Família de Analisadores LR(k)

Vantagens:

• Reconhece praticamente todas as construções sintáticas definidas pelas Gramáticas Livres de Contexto (GLCs).
• Evita o retrocesso.
• A classe de gramáticas que podem ser reconhecidas pelos analisadores LR é um superconjunto próprio da classe de gramáticas.
• Possibilita a detecção de erros tão cedo quanto possível.

Desvantagens:

• Difícil de implementar manualmente.
• Uso de ferramentas especializadas (ex: Yacc).

Funcionamento:

O algoritmo é o mesmo para toda a família, o que varia é a construção da tabela de análise. O algoritmo lê caracteres de um buffer de entrada, e um Analisador Sintático LR transfere um estado para a pilha. Cada estado resume a informação contida na pilha abaixo dele.

Tipos de Analisadores LR

• SLR (Simple LR): Fáceis de implementar, porém aplicáveis a uma classe restrita de gramáticas.
• LR Canônicos: Poder e custo intermediário, funcionando para a maioria das gramáticas de linguagens de programação.
• LALR (Look-Ahead LR): Mais poderoso e mais caro, aplicados a um grande número de linguagens livres de contexto.

Reduções na Análise Sintática

Em cada passo da redução, uma subcadeia específica, que casa com o lado direito de uma produção, é substituída pelo Não-Terminal (ÑT) na cabeça da produção.

Dificuldades:

• Determinar quando reduzir.
• Determinar qual produção deve ser aplicada para que a análise prossiga.

Conceito de Handle (Poda)

Um Handle (Poda) de uma cadeia de símbolos é uma subcadeia que casa com o corpo de uma produção, e cuja redução para o Não-Terminal (ÑT) do lado esquerdo representa um passo da derivação mais à direita ao inverso.

Problemas em Gramáticas: Ambiguidade e Recursão à Esquerda

Gramáticas Ambíguas (GA):

• Uma mesma sentença apresenta duas ou mais árvores de derivações.
• Problema: Reconhecedores exigem derivações unívocas para obter bom desempenho ou concluir a Análise Sintática (AS).

Gramáticas Recursivas à Esquerda (G RaE):

• Uma gramática é recursiva à esquerda se possui um Não-Terminal (ÑT) A tal que exista uma derivação A → Aα para alguma cadeia α.
• Problema: Gramáticas Recursivas à Esquerda não podem ser processadas pelos métodos de Análise Sintática Top-Down. Consequentemente, uma transformação que elimine a recursão é necessária.

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

• Pilha Explícita: Existe uma estrutura de dados de pilha dentro do analisador que é usada durante o processo.
• Pilha Implícita: A estrutura de dados é gerenciada pelas chamadas recursivas dos métodos. A pilha é a call stack do compilador; o processo de empilhar é a chamada de um método e desempilhar é quando uma função retorna.

Tradução Dirigida pela Sintaxe (TDS)

A Tradução Dirigida pela Sintaxe (TDS) é uma técnica de compilação orientada por gramáticas que auxilia na organização das partes da vanguarda do compilador. Um esquema de tradução é uma Gramática Livre de Contexto (GLC) 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 ordem de avaliação das regras semânticas é explicitamente mostrada.

Compiladores: Um Passo e Múltiplos Passos

• Compilador de Um Passo: Percorre as partes de cada unidade do compilador somente uma vez, traduzindo cada parte diretamente para código de máquina.
• Compilador de Múltiplos Passos: Converte o código-fonte em código de máquina através de uma ou mais representações intermediárias, reprocessando toda a unidade de compilação em cada passo sequencial.

Análise Léxica: Tokens, Padrões e Lexemas

• Existe um conjunto de cadeias de entrada para as quais o mesmo token é produzido como saída. Esse conjunto de cadeias é descrito por uma regra chamada de padrão, associado ao token de entrada. O padrão é dito reconhecer cada cadeia do conjunto.
• Um lexema é um conjunto de caracteres no programa-fonte que é reconhecido pelo padrão de algum token.

Especificação de Tokens com Expressões Regulares

As Expressões Regulares (ER) são importantes para especificar os padrões dos lexemas.

Reconhecimento de Tokens com AFD

As Expressões Regulares (ER) podem ser convertidas em Autômatos Finitos Determinísticos (AFD), que são os mecanismos para reconhecimento de lexemas.

Tratamento de Erros Léxicos

• Erros Léxicos: Acontecem quando nenhum dos padrões para tokens casa com nenhum prefixo da entrada restante.
• Modo Pânico: Consiste em remover os caracteres seguintes da entrada restante até encontrar um token bem formado no início da entrada que resta.