Universidade Católica Dom Bosco Curso de Engenharia de Computação Disciplina: Compiladores II Professor: Ricardo Santos

Lista de Exercícios nō 1

1) Assinale a alternativa correta (V ou F)

( ) Um DAG G sempre gera o mesmo número de vértices que uma árvore sintática T para um mesmo trecho de código P.

( ) A geração de código de três endereços baseada em backpatching têm a vantagem de obter os endereços dos labels durante a geração do código.

( ) Um bloco de controle do tipo while(b > 100){b− = 1; } já está na forma de código de três endereços.

( ) Atributos herdados são sempre definidos antes (à esquerda) de um símbolo não-terminal que os utiliza, enquanto que atributos sintetizados são executados após a execução de todos os atributos não-terminais de uma regra e, antes de sua redução.

( ) Em uma tabela de símbolos organizada como uma árvore binária, é possível que elementos que estão em um mesmo nível no programa estejam em níveis diferentes na estrutura da árvore.

( ) Na construção de um registro de ativação, o ponteiro topsp (ponteiro para o registro de ativação atual) é atualizado pelo procedimento chamado.

( ) Exemplos de ações dinâmicas executadas sobre o código de um programa são: redução da fragmentação de um heap, verificação de unicidade de tipos, criação e atualização de registros de ativação e execução de algoritmos para garbage collection.

( ) Na geração de código que utiliza backpatching, os marcadores M são os responsáveis por “marcar” um ponto onde, possivelmente, o endereço de um label será necessário.

( ) A complexidade de adoção de uma otimização de código independe de qual representação intermediária está sendo usada.

( ) Uma maneira mais eficiente de traduzir uma construção do tipo switch(E){case V_{j} : S_{j} …} em código de três endereços seria: 1) Avaliar a expressão E e desviar para um label L; 2) A partir de L, encontrar o valor V_{j}, em uma lista de casos de comparação que possui o mesmo valor da expressão avaliada; 3) Executar a declaração S_{j} associada com o valor encontrado.

2) Traduza o código a seguir para uma representação na forma de DAGs e em código de três endereços.

a=10;
b=20;
c=5;
x=(b-a)*c;
y=(x+c)-(b-a);

3) Mostre o resultado final e a árvore sintática anotada para a tradução do código a seguir com a técnica de backpatching (considere que nextinstr = 100)?

  if (A==1)
    S=t;
  else if(A>5)
    S=A;

4) Mostre a árvore de ativação junto com a pilha de registros de ativação (considere apenas o valor do parâmetro, o valor de retorno e as variáveis locais s e t) para o programa a seguir. Considere que na primeira chamada f(4). Qual é o número máximo de procedimentos que utilizam a pilha para essa entrada?

int f(int n){
  int t, s;
  if (n < 2) return 1;
  s = f(n-1);
  t = f(n-2);
  return s+t;
}

5) Quais objetos serão excluídos se executarmos o algoritmo de contagem de referências e o algoritmo de marcar e varrer sobre a estrutura de objetos a seguir, considerando que a aresta A ) D é deletada?