\documentclass[a4paper,12pt,fleqn]{report}
\usepackage[portuges,brazil]{babel}
\usepackage{amssymb,amsmath,amsfonts}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{euler}
\usepackage[top=20mm,bottom=20mm,left=20mm,right=20mm]{geometry}
%\topmargin -2cm \oddsidemargin -0.5cm \textwidth 16,5cm
\textheight 28cm
\parindent=1cm
\newcommand{\portanto}{\ensuremath{. {}^. .\;}}
\newcommand{\talque}{ \, \mid \,}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\inteiros}{\mathbb{Z}}
\newcommand{\rac}{\mathbb{Q}}
\newcommand{\reais}{\mathbb{R}}
\newcommand{\complexos}{\mathbb{C}}
\pagestyle{empty}
\newcommand{\dmat}{\displaystyle}
\newcommand{\hsa}{\hspace{0.1cm}}
\newcommand{\hsb}{\hspace{0.25cm}}
\newcommand{\hsc}{\hspace{0.5cm}}
\newcommand{\hsd}{\hspace{0.75cm}}
\newcommand{\hse}{\hspace{1.0cm}}
\begin{document}
\noindent {\bf Universidade Católica Dom Bosco \\
              Curso de Engenharia de Computação \\
              Disciplina: Compiladores II\\
Professor: Ricardo Santos}\\

\centerline{\bf Lista de Exerc\'{\i}cios n$^{\textrm{\scriptsize
\b{o}}}$ 1 }

\small
\noindent
\begin{itemize}
\item[1)] Assinale a alternativa correta (V ou F)
\item[( )] 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$.
\item[( )] 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.
\item[( )] Um bloco de controle do tipo $while (b>100)\{ b-=1; \}$ já está na forma de código de três endereços.
\item[( )] 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.
\item[( )] 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. 
\item[( )] Na construção de um registro de ativação, o ponteiro $top\underline{ }sp$ (ponteiro para o registro de ativação atual) é atualizado pelo procedimento chamado.
\item[( )] 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 \textit{garbage collection}.
\item[( )] 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 \textit{label} será necessário.
\item[( )] A complexidade de adoção de uma otimização de código independe de qual representação intermediária está sendo usada.
\item[( )] Uma maneira mais eficiente de traduzir uma construção do tipo $switch(E)\{case~ V_j:~S_j~\ldots\}$ 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. 

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

\begin{verbatim}
a=10;
b=20;
c=5;
x=(b-a)*c;
y=(x+c)-(b-a);
\end{verbatim}
\newpage
\item[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
\textit{backpatching} (considere que $nextinstr=100$)?

\begin{verbatim}
  if (A==1)
    S=t;
  else if(A>5)
    S=A;
\end{verbatim}

\item[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?
\begin{verbatim}
int f(int n){
  int t, s;
  if (n < 2) return 1;
  s = f(n-1);
  t = f(n-2);
  return s+t;
}
\end{verbatim}

\item[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\rightarrow D$ é deletada?

\begin{figure}[!h]
\begin{center}
\includegraphics[scale=0.5]{objects_net.eps}
\end{center}
\end{figure}
\end{itemize}
\end{document}

-----------------------------------------------------------

\documentclass[12pt,fleqn]{report}
\usepackage[brazil]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{amsfonts}
\topmargin -2cm \oddsidemargin .1cm \textwidth 15cm \textheight
26cm
\parindent=1cm
\newcommand{\portanto}{\ensuremath{. {}^. .\;}}
\newcommand{\talque}{ \, \mid \,}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\inteiros}{\mathbb{Z}}
\newcommand{\rac}{\mathbb{Q}}
\newcommand{\reais}{\mathbb{R}}
\newcommand{\complexos}{\mathbb{C}}
\newcommand{\dmat}{\displaystyle}
\pagestyle{empty}
