Você está projetando o “miolo” de um compilador para uma linguagem imperativa que precisa: (i) analisar estrutura gramatical com boa noção de precedência, (ii) eliminar subexpressões repetidas ainda no front/middle-end, e (iii) otimizar o uso de registradores e reordenar instruções respeitando dependências ao nível do bloco. Quais estruturas/IRs são mais adequadas para atender, respectivamente, a (i), (ii) e (iii)?

Alternativa E - AST, DAG, Grafo de Fluxo de Controle (CFG) com blocos básicos

Para responder corretamente, é necessário associar cada requisito de otimização ou análise à estrutura de dados intermediária adequada utilizada na fase de "miolo" (middle-end) de um compilador.

Análise Detalhada

A questão descreve três etapas distintas de processamento. Vamos analisar cada uma para encontrar a estrutura correspondente:

(i) Analisar estrutura gramatical com boa noção de precedência

• Objetivo: Representar a hierarquia das operações e a ordem em que elas devem ser executadas com base nas regras da linguagem.
• Estrutura Adequada: AST (Abstract Syntax Tree) ou Árvore Sintática Abstrata.
• Por quê? A AST remove detalhes irrelevantes (como parênteses excessivos ou chaves de delimitação) presentes na árvore de derivação, mantendo apenas a estrutura essencial das expressões. Ela preserva naturalmente a precedência dos operadores através da profundidade da árvore.

(ii) Eliminar subexpressões repetidas (Common Subexpression Elimination)

• Objetivo: Identificar cálculos duplicados e garantir que sejam realizados apenas uma vez, armazenando o resultado para reuso.
• Estrutura Adequada: DAG (Directed Acyclic Graph) ou Grafo Acíclico Direcionado.
• Por quê? Diferente de uma árvore (onde cada nó é único), um DAG permite que múltiplas referências apontem para o mesmo nó. Se duas partes do código calculam x + y, o DAG cria apenas um nó para essa operação, facilitando a identificação e eliminação de redundâncias.

(iii) Otimizar uso de registradores e reordenar instruções (nível de bloco)

• Objetivo: Gerenciar o fluxo de execução dentro de regiões de código contínuas (blocos básicos) para maximizar o uso de registradores e reordenar instruções seguras.
• Estrutura Adequada: CFG (Control Flow Graph) com blocos básicos.
• Por quê? O CFG representa as transições entre blocos básicos. Ao nível de bloco, ele permite a análise de fluxo de dados necessária para Register Allocation (alocação de registradores) e Instruction Scheduling (reordenamento de instruções), garantindo que dependências de dados não sejam violadas.

Conclusão

A combinação correta para atender aos requisitos (i), (ii) e (iii) segue a ordem:

1. AST (Estrutura Gramatical)
2. DAG (Eliminação de Redundância)
3. CFG (Otimização de Bloco/Registradores)

Portanto, a alternativa correta é a que apresenta esta sequência exata.