prova8_cmentrudo

Prévia do material em texto

UFRGS - INSTITUTO DE INFORMÁTICA - Prof. Marcelo Johann 
INF01147 - COMPILADORES - Semestre 2021/2 - Prova P2 - 10/05/2022 
 
Instruções Gerais: 
• As questões aqui contidas são informação sigilosa, de uso exclusivo 
para fins de avaliação, não podem ser copiadas, exibidas, 
compartilhadas ou publicadas por nenhum meio, seja durante, seja após 
a sua realização; 
• A resolução da prova deve ser apresentada como um arquivo em 
formato PDF contendo tanto partes digitadas e também trechos escritos 
à mão em papel e digitalizados (escaneados ou fotografados); 
• Verifique o formato e tamanho das fotografias incluídas, para que 
sejam ao mesmo tempo legíveis e não muito grandes. O arquivo PDF 
final deve ter no máximo 16 MBytes; 
• Por favor, mantenha (ou copie) o enunciado completo de cada questão 
no arquivo de respostas a ser entregue; 
• Você deve incluir no final do arquivo de respostas referências para 
qualquer material que tiver sido consultado durante a resolução dos 
exercícios; 
• Embora a consulta a material bibliográfico e disponível online, em 
qualquer formato, seja permitida, a solução e a respostas das questões 
são individuais, e qualquer comunicação ou auxílio entre alunos, outros 
indivíduos ou grupos durante a prova é expressamente proibida; 
• Muita atenção: leia atentamente todas as instruções gerais e também 
descritas em cada enunciado das questões, para observar e responder de 
acordo com o que é solicitado; 
• A autoria das resoluções e respostas é de inteira responsabilidade 
do aluno, e você também deve incluir ao final do arquivo de 
respostas da sua prova o seguinte texto, assinado: 
"Declaro que as respostas aqui apresentadas para todas as questões são 
de minha autoria." 
 
 
 
 
 
 
Questão 1 (1,0 ponto): Considere a etapa 5 do desenvolvimento do trabalho. 
Escolha uma das construções não implementadas, ou que ainda ficou 
apresentando falha nos testes reportados pelo professor, e explique como 
deveria ter sido implementada ou corrigida. Se todas as TACs foram geradas e 
avaliadas integralmente, descreva como as TACs para um novo comando do 
tipo "for" com a mesma forma e comportamento das linguagens C/C++ 
poderia ser implementado; 
Resposta: 
Segue código de exemplo em linguagem C: 
 
TAC(TAC_LABEL, mYLabule0, 0, 0); 
TAC(TAC_L, mYweeirT_emp0, i, 10); 
TAC(TAC_IFZ, mYLabule1, mYweeirT_emp0, 0); 
TAC(TAC_PRINT, "loop for\n", 0, 0); 
TAC(TAC_ADD, mYweeirT_emp1, i, 1); 
TAC(TAC_COPY, i, mYweeirT_emp1, 0); 
TAC(TAC_JUMP, mYLabule0, 0, 0); 
TAC(TAC_LABEL, mYLabule1, 0, 0); 
Questão 2 (1,0 ponto): O que é a Árvore de Sintaxe Abstrata (AST)? 
Resposta: 
Árvore de sintaxe abstrata é uma estrutura de dados do tipo árvore, criada em memória e 
que representa a estrutura da árvore de derivações. Ela é abstrata porque não precisa ter 
exatamente todas as produções que foram usadas na árvore de derivação, ou seja, ela 
não representa cada detalhe que aparece na sintaxe real. 
Questão 3 (1,0 ponto): Elabore um exemplo de esquema de tradução que seja 
S-atribuído, e mostre a árvore anotada para uma sentença de entrada criada 
por você com exatamente 5 símbolos; 
Resposta: 
 
Produções Regras semânticas 
L → E print(E.val) 
E → E1 + T E.val = E1.val + T. val 
E → T E.val = T.val 
T → T1 * F T.val = T1.val * F.val 
T → F T.val = F.val 
F → (E) F.val = E.val 
F → digit F.val = digit.lexval 
 
Sentença de entrada: 3 * 5 + 7 
 
Questão 4 (1,0 ponto): Elabore um exemplo de expressão com 6 variáveis e 8 
operadores, mostre o código intermediário gerado assumindo associatividade 
à direita, e como o algoritmo de otimização de expressões pode reduzir o 
número de instruções em assembler em uma máquina de um acumulador, por 
maximizar o uso de um dado temporário imediatamente após sua geração, 
economizando instruções de STORE e LOAD; 
Resposta: 
 
Y = ((a + b) – (c + d) / ((e + (f – a)) * (c + d))) 
I1 = c + d LOAD c 
ADD d 
STORE I1 
I2 = f - a LOAD f 
SUB a 
STORE I2 
I3 = e + I2 LOAD e 
ADD I2 
STORE I3 
I4 = I3 * I1 LOAD I3 
MUL I1 
STORE I4 
I5 = c + d LOAD c 
ADD d 
STORE I5 
I6 = a + b LOAD a 
ADD b 
STORE I6 
I7 = I6 - I5 LOAD I6 
SUB I5 
STORE I7 
I8 = I7 / I4 LOAD I7 
DIV I4 
STORE I8 
Custo 24 instruções 
Aplicação da técnica exige que as expressões aritméticas satisfaçam as seguintes 
restrições: 
1. Não há operandos repetidos na expressão 
2. Todos os operandos são binários 
Observando que I1 e I5 são iguais, substituiremos I5 por I1. 
I1 = c + d LOAD c 
ADD d 
STORE I1 
I2 = f - a LOAD f 
SUB a 
STORE I2 
I3 = e + I2 LOAD e 
ADD I2 
STORE I3 
I4 = I3 * I1 LOAD I3 
MUL I1 
STORE I4 
I6 = a + b LOAD a 
ADD b 
STORE I6 
I7 = I6 - I5 LOAD I6 
SUB I5 
STORE I7 
I8 = I7 / I4 LOAD I7 
DIV I4 
STORE I8 
Custo 21 instruções 
 
 
 
 
 
 
 
 
 
 
 
 
 
Algoritmo para gerar uma sequência otimizada de código: A sequência ótima de 
instruções corresponde ao inverso da ordenação obtida. 
L = [I8, I7, I6, I4, I5/I1, I3, I2] 
I2 = f - a LOAD f 
SUB a 
STORE I2 
I3 = e + I2 ADD e 
 
STORE I3 
I1 = c + d LOAD c 
ADD d 
STORE I1 
I4 = I3 * I1 MUL I3 
 
STORE I4 
I6 = a + b LOAD a 
ADD b 
STORE I6 
I7 = I6 - I5 
SUB I5 
 
I8 = I7 / I4 
DIV I4 
STORE I8 
Custo 16 instruções 
 
f e d c b a 
+ + 
- 
- * 
/ 
+ 
I8 
I2 
I3 
I1, I5 
I4 
I6 
I7 
Questão 5 (1,0 ponto): Explique qual a limitação fundamental de usar o 
algoritmo Left-Edge para assinalamento de registradores, usando dois 
exemplos práticos, mostrando dados (lifetimes), registradores específicos da 
arquitetura, o que o algoritmo consegue e o que ele não consegue fazer nesses 
casos. A arquitetura deve ter mais de um acumulador ou registrador. 
Resposta: 
 
O algoritmo Left-Edge é eficiente e produz o menor número de registradores, porém ele 
não resolve a tarefa que temos. A tarefa não é otimizar o número de registradores e sim 
encaixar nos registradores presentes na arquitetura. Sendo assim, a limitação 
fundamental do algoritmo é que este problema de selecionar quais dados manter em 
registradores é bem mais difícil. 
Exemplo1: Sucesso – 3 registradores 
 
Exemplo2: Erro – 1 registrador 
 
Questão 6 (2,0 pontos): Para o algoritmo de análise sintática SLR1 com a 
gramática e tabela apresentadas abaixo, crie uma estratégia de recuperação de 
erros, preenchendo a tabela de acordo com as ações locais propostas nessa 
estratégia. Mostre então como o algoritmo se recupera em uma sentença 
elaborada por você mesmo contendo ao menos dois erros sintáticos, emitindo 
as mensagens correspondentes aos dois erros, e continuando a análise das 
partes corretas sem reportar outros falsos erros até o final do arquivo. 
G = {{ S L }, { a [ ] ; }, P, S}, 
com símbolo inicial S e as seguintes produções P: 
 
1) S → a 
2) S → [ L ] 
 
 
 
3) L → S 
4) L → L ; S 
 
 State a [ ] ; $ S L 
0 s2 s3 1 
1 End 
2 r1 r1 r1 
3 s2 s3 5 4 
4 s6 s7 
5 r3 r3 
6 r2 r2 r2 
7 s2 s3 8 
8 r4 r4 
 
Resposta: 
Segue conjunto de regras proposto para a recuperação de erros. 
Erro1: usados nos estados S0, S3 e S7. Em todos estes estados esperamos um “a” ou 
um “[“. Assumiremos aqui que para o algoritmo conseguir se ressincronizar, 
necessitamos de um “a”. Empilharemos “a” com o estado S2. Mensagem: “caractere a 
esperado.” 
Erro2: aqui assumimos que o “]” foi inserido de forma excedente. Descartamos o token 
da entrada e avançamos. Mensagem: “] excedente”. 
Erro3: aqui, no estado S4, podemos assumir duas possibilidades: fata um “]” ou um “;”. 
Em nossa estratégia assumiremos que está faltando o “;”. Empilharemos o “;” com o 
estado S7. Mensagem: “; esperado”. 
Erro4: assume que faltou o “]”. Empilharemos o “]” com o estado S6. Mensagem: “] 
esperado.” 
Erro5: no estado S1, o único símbolo esperado é a marcação de final dearquivo $. 
Neste caso o correto é descartar a entrada e avançar até encontrar a marcação $. 
Mensagem: “EOF esperado”. 
 State a [ ] ; $ S L 
0 s2 s3 Erro2 Erro1 Erro1 1 
1 Erro5 Erro5 Erro5 Erro5 End 
2 r1 r1 r1 r1 r1 
3 s2 s3 Erro2 Erro1 Erro1 5 4 
4 Erro3 Erro3 s6 s7 Erro4 
5 r3 r3 r3 r3 r3 
6 r2 r2 r2 r2 r2 
7 s2 s3 Erro2 Erro1 Erro1 8 
8 r4 r4 r4 r4 r4 
 
Demonstrando a recuperação com a entrada “]a;[$”: 
Pilha Entrada ação 
0 ]a;[$ Erro2: descarta “]” 
0 a;[$ S2 
0a2 ;[$ R1 
0S1 ;[$ Erro5: descarta a entrada e avança até o “$” 
0S1 [$ Erro5: descarta a entrada e avança até o “$” 
0S1 $ End (Aceita) 
 
 
 
Questão 7 (2,0 pontos): Explique a estratégia de otimização de laços citada 
abaixo, dando um exemplo de código antes e depois de otimizado 
(possivelmente em assembler) e dizendo como essa otimização economiza 
tamanho e/ou tempo de execução. 
Loop Software pipelining 
Resposta: 
A estratégia dessa otimização é prover paralelismo na execução de loops. Ela 
basicamente divide um loop em 3 partes (prólogo, kernel e epílogo) e agrupa operações 
que podem ser executadas em paralelo. 
Assume que um laço do tipo {ABC}n é semanticamente igual a A{BCA}n-1BC, fazendo 
com que {BCA} seja o novo corpo do loop (kernel). 
O principal objetivo é encontrar este novo corpo do loop. 
 
Considerando o programa abaixo: 
 
 
Antes da otimização: 
 
Depois da otimização 
 
Questão 8 (1,0 ponto): Dê uma nota ao seu desempenho e aprendizado 
na disciplina até o momento. A nota deve variar de 0 a 10 e representar a 
sua compreensão dos conceitos apresentados e habilidade de aplicar os 
recursos teóricos e práticos vistos. 
Resposta: 
Mantenho a mesma nota dada anteriormente por mim (9.5). Tenho conseguido 
acompanhar o andamento da disciplina e executar as etapas propostas para o trabalho 
prático do compilador. 
Referências: 
• Vídeos das aulas que estão no Microsoft Teams 
• Implementação de Linguagens de Programação: Compiladores - Ana Maria de 
Alencar Price e Simão Sirineo Toscani 
• https://www.ic.unicamp.br/~ducatte/mo401/1s2006/T2/895063-A.pdf 
• https://pages.cs.wisc.edu/~fischer/cs701.f05/lectures/Lecture15.pdf 
 
https://www.ic.unicamp.br/~ducatte/mo401/1s2006/T2/895063-A.pdf
https://pages.cs.wisc.edu/~fischer/cs701.f05/lectures/Lecture15.pdf
"Declaro que as respostas aqui apresentadas para todas as questões são 
de minha autoria."