COMPILADORES (30)

Prévia do material em texto

Caderno de exercícios para a disciplina de: 
 
COMPILADORES 
 
Janeiro de 2005 
 
 
João M. P. Cardoso 
 
Departamento de Engenharia Electrónica e Informática (DEEI) 
Faculdade de Ciências e Tecnologia (FCT) 
Universidade do Algarve 
 
Campus de Gambelas 
8000-117 Faro 
 
Email: jmcardo@ualg.pt
URL: http://w3.ualg.pt/~jmcardo
 
 
 
Curso de Licenciatura em Engenharia de Sistemas e Informática 
Curso de Licenciatura em Ensino de Informática 
Curso de Licenciatura em Informática 
 
 
 
 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
Índice 
FICHA Nº 1 Optimizações de código.....................................................................5 
1.1 Verificar a diferença entre o tempo de execução utilizando o interpretador e 
utilizando o compilador JIT .......................................................................................5 
1.2 Optimizações..................................................................................................6 
1.3 Propagação de constantes (Constant Propagation) ........................................7 
1.4 Constant folding (Constant-Expression Evaluation) .....................................8 
1.5 Desenrolamento de ciclos (Loop Unrolling)..................................................9 
1.6 Simplificação algébrica (Algebraic simplification) .......................................9 
1.7 Desenrolamento de ciclos (Loop Unrolling)................................................10 
1.8 Simplificações algébricas + constant folding ..............................................11 
1.9 Scalar replacement .......................................................................................11 
1.10 Simplificação algébrica................................................................................12 
1.11 Eliminação de código ou de declarações não utilizadas ..............................13 
1.12 Strength reduction........................................................................................13 
1.13 Depois de simplificações algébricas e reassociação ....................................14 
1.14 Depois de CSE (eliminação de sub-expressões comuns): ...........................14 
1.15 Sumário ........................................................................................................15 
FICHA Nº 2 Introdução aos Algoritmos Iterativos...............................................16 
1.16 Algoritmo Iterativo para Determinar Funções Recursivas ..........................16 
1.17 Transitive Closure........................................................................................17 
1.18 Algoritmo Iterativo para Transitive Closure................................................17 
©João M. P. Cardoso 2 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
1.19 Exercício 1 ...................................................................................................18 
1.20 Código Java..................................................................................................18 
1.21 Classe Graph.java ........................................................................................19 
1.22 Classe TransitiveClosure.java......................................................................21 
1.23 Trabalho para Casa ......................................................................................21 
1.24 Créditos ........................................................................................................22 
FICHA Nº 3 Exercícios sobre Expressões Regulares e Autómatos Finitos..........23 
1.25 Exercícios com Expressões Regulares.........................................................23 
1.26 Exercícios com Autómatos Finitos ..............................................................23 
FICHA Nº 4 Exercícios sobre Gramáticas............................................................26 
FICHA Nº 5 Implementação de Analisadores Gramaticais Utilizando o JavaCC 
(1ª parte) 29 
1.27 Exemplo .......................................................................................................29 
1.28 Exercícios.....................................................................................................32 
1.29 Referências de Apoio...................................................................................32 
FICHA Nº 6 Implementação de Analisadores Gramaticais Utilizando o JavaCC 
(2ª parte) 33 
1.30 Exercício ......................................................................................................33 
FICHA Nº 7 Implementação de Analisadores Gramaticais Utilizando o JavaCC 
(3ª parte) 34 
1.31 Exemplo .......................................................................................................34 
1.32 Referências de Apoio...................................................................................45 
©João M. P. Cardoso 3 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 8 : Exercício sobre analisadores sintácticos........................................46 
FICHA Nº 9 : Exercícios de Revisão....................................................................50 
Anexo B: Enunciado de um Exame .............................................................................52 
©João M. P. Cardoso 4 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 
FICHA Nº 1 Optimizações de código 
Duração: 3 horas 
Esta aula tem como objectivo a utilização de algumas das optimizações de código 
realizadas pelos compiladores. Algumas dessas optimizações não dependem do 
processador alvo para garantirem sempre bons resultados. As optimizações do tipo 
anterior e cujo impacto será avaliado são: 
• Propagação de constantes (Constant propagation); 
• Avaliação de expressões com constantes (Constant folding ou Constant-
Expression evaluation); 
• Simplificações algébricas (Algebraic Simplifications) 
• Substituição por escalares (Scalar replacement) 
• Redução do custo (Strength reduction) 
• Eliminação de sub-expressões comuns (Common-Subexpression elimination - 
CSE) 
• Eliminação de código e de declarações não utilizadas 
• Desenrolamento de ciclos (Loop unrolling) 
Após leitura desta ficha e verificação das melhorias no tempo de execução, descreva 
cada uma das optimizações anteriores. 
1.1 Verificar a diferença entre o tempo de execução 
utilizando o interpretador e utilizando o 
compilador JIT 
O programa exemplo que vamos utilizar é formado pelas classes em bytecodes e por 
uma classe para a qual é dada o ficheiro Java original. Para executar o programa deve 
primeiro compilar o ficheiro Filter.java e depois executar um dos comandos seguintes: 
Utilizando o interpretador: 
Java –Xint DrawImage 
Utilizando o compilador JIT (por omissão): 
©João M. P. Cardoso 5 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
Java DrawImage 
Verifique os tempos de execução de cada um dos algoritmos apresentados. 
A Figura 1 apresenta o resultado da execução do referido programa. 
 
Figura 1. Appet Java utilizada para que os alunos possam verificar o impacto no 
desempenho da utilização de determinadas transformações (optimizações) ao 
nível do código da aplicação. 
1.2 Optimizações 
Vamos considerar a função doFIR apresentada em baixo e que é um método da classe 
Filter.java. Este método, como pôde constatar anteriormente implementa um 
algoritmo de processamento de imagem que reduz o ruído de uma imagem. De 
seguida vamos realizar manualmente um conjunto de optimizações, que integram ou 
constam como opções de alguns compiladores e que permitem melhorar o 
desempenho. 
final public static short[] doFIR(short[]IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
©João M. P. Cardoso 6 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 int DIM = 350; 
 short[] OUT = new short[DIM*DIM]; 
 
 for (int row=0; row < DIM-3+1; row++) { 
 for (int col = 0; col< DIM-3+1; col++) { 
 int sumval = 0; 
 for (int wrow=0; wrow < 3; wrow++) { 
 for (int wcol = 0; wcol<3; wcol++) { 
 sumval += IN[(row +wrow)*DIM+(col+wcol)]*K[wrow*3+wcol]; 
 } 
 } 
 sumval = sumval / 16; 
 OUT[row * DIM + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.3 Propagação de constantes (Constant Propagation) 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[350*350]; 
 
 for (int row=0; row < 350-3+1; row++) { 
 for (int col = 0; col< 350-3+1; col++) { 
 int sumval = 0; 
 for (int wrow=0; wrow < 3; wrow++) { 
 for (int wcol = 0; wcol<3; wcol++) { 
 sumval += IN[(row +wrow)*350+(col+wcol)]*K[wrow*3+wcol]; 
 } 
 } 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
©João M. P. Cardoso 7 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
1.4 Constant folding (Constant-Expression 
Evaluation) 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[350*350]; 122500 
 
 for (int row=0; row < 350-3+1; row++) { 348 
 for (int col = 0; col< 350-3+1; col++) { 
 int sumval = 0; 
 for (int wrow=0; wrow < 3; wrow++) { 
 for (int wcol = 0; wcol<3; wcol++) { 
 sumval+= IN[(row +wrow)*350+(col+wcol)]*K[wrow*3+wcol]; 
 } 
 } 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
 
Depois de aplicar constant folding: 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval = 0; 
 for (int wrow=0; wrow < 3; wrow++) { 
 for (int wcol = 0; wcol<3; wcol++) { 
 sumval+= IN[(row +wrow)*350+(col+wcol)]*K[wrow*3+wcol]; 
 } 
 } 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
©João M. P. Cardoso 8 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 } 
 } 
 return OUT; 
} 
1.5 Desenrolamento de ciclos (Loop Unrolling) 
 for (int wcol = 0; wcol<3; wcol++) { 
 sumval+= IN[(row +wrow)*350+(col+wcol)]*K[wrow*3+wcol]; 
 } 
Obtém-se: 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval = 0; 
 for (int wrow=0; wrow < 3; wrow++) { 
 sumval+= IN[(row +wrow)*350+(col+0)]*K[wrow*3+0]; 
 sumval+= IN[(row +wrow)*350+(col+1)]*K[wrow*3+1]; 
 sumval+= IN[(row +wrow)*350+(col+2)]*K[wrow*3+2]; 
 } 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.6 Simplificação algébrica (Algebraic simplification) 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
©João M. P. Cardoso 9 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 for (int col = 0; col< 348; col++) { 
 int sumval = 0; 
 for (int wrow=0; wrow < 3; wrow++) { 
 sumval+= IN[(row +wrow)*350+col])*K[wrow*3]; 
 sumval+= IN[(row +wrow)*350+(col+1)])*K[wrow*3+1]; 
 sumval+= IN[(row +wrow)*350+(col+2)])*K[wrow*3+2]; 
 } 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.7 Desenrolamento de ciclos (Loop Unrolling) 
for (int wrow=0; wrow < 3; wrow++) { 
 sumval+= IN[(row +wrow)*350+col]*K[wrow*3]; 
 sumval+= IN[(row +wrow)*350+(col+1)]*K[wrow*3+1]; 
 sumval+= IN[(row +wrow)*350+(col+2)]*K[wrow*3+2]; 
} 
 
Obtém-se: 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval = 0; 
 sumval+= IN[(row +0)*350+col]*K[0*3]; 
 sumval+= IN[(row +0)*350+(col+1)]*K[0*3+1]; 
 sumval+= IN[(row +0)*350+(col+2)]*K[0*3+2]; 
 sumval+= IN[(row +1)*350+col]*K[1*3]; 
 sumval+= IN[(row +1)*350+(col+1)]*K[1*3+1]; 
 sumval+= IN[(row +1)*350+(col+2)]*K[1*3+2]; 
 sumval+= IN[(row +2)*350+col]*K[2*3]; 
 sumval+= IN[(row +2)*350+(col+1)]*K[2*3+1]; 
 sumval+= IN[(row +2)*350+(col+2)]*K[2*3+2]; 
©João M. P. Cardoso 10 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.8 Simplificações algébricas + constant folding 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval= IN[row*350+col]*K[0]; 
 sumval+= IN[row*350+(col+1)]*K[1]; 
 sumval+= IN[row*350+(col+2)]*K[2]; 
 sumval+= IN[(row +1)*350+col]*K[3]; 
 sumval+= IN[(row +1)*350+(col+1)]*K[4]; 
 sumval+= IN[(row +1)*350+(col+2)]*K[5]; 
 sumval+= IN[(row +2)*350+col]*K[6]; 
 sumval+= IN[(row +2)*350+(col+1)]*K[7]; 
 sumval+= IN[(row +2)*350+(col+2)]*K[8]; 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.9 Scalar replacement 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
©João M. P. Cardoso 11 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 int sumval= IN[row*350+col]*1; 
 sumval+= IN[row*350+(col+1)]*2; 
 sumval+= IN[row*350+(col+2)]*1; 
 sumval+= IN[(row +1)*350+col]*2; 
 sumval+= IN[(row +1)*350+(col+1)]*4; 
 sumval+= IN[(row +1)*350+(col+2)]*2; 
 sumval+= IN[(row +2)*350+col]*1; 
 sumval+= IN[(row +2)*350+(col+1)]*2; 
 sumval+= IN[(row +2)*350+(col+2)]*1; 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.10 Simplificação algébrica 
final public static short[] doFIR(short[] IN) { 
 short[] K = {1, 2, 1, 
 2, 4, 2, 
 1, 2, 1}; 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval= IN[row*350+col]; 
 sumval+= IN[row*350+col+1]*2; 
 sumval+= IN[row*350+col+2]; 
 sumval+= IN[(row +1)*350+col]*2; 
 sumval+= IN[(row +1)*350+col+1]*4; 
 sumval+= IN[(row +1)*350+col+2]*2; 
 sumval+= IN[(row +2)*350+col]; 
 sumval+= IN[(row +2)*350+col+1]*2; 
 sumval+= IN[(row +2)*350+col+2]; 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short)sumval; 
 } 
 } 
 return OUT; 
} 
©João M. P. Cardoso 12 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
1.11 Eliminação de código ou de declarações não 
utilizadas 
final public static short[] doFIR(short[] IN) { 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval= IN[row*350+col]; 
 sumval+= IN[row*350+col+1]*2; 
 sumval+= IN[row*350+col+2]; 
 sumval+= IN[(row +1)*350+col]*2; 
 sumval+= IN[(row +1)*350+col+1]*4; 
 sumval+= IN[(row +1)*350+col+2]*2; 
 sumval+= IN[(row +2)*350+col]; 
 sumval+= IN[(row +2)*350+col+1]*2; 
 sumval+= IN[(row +2)*350+col+2]; 
 sumval = sumval / 16; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.12 Strength reduction 
final public static short[] doFIR(short[] IN) { 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval= IN[row*350+col]; 
 sumval+= IN[row*350+col+1]<<1; 
 sumval+= IN[row*350+col+2]; 
 sumval+= IN[(row +1)*350+col]<<1; 
 sumval+= IN[(row +1)*350+col+1]<<2; 
 sumval+= IN[(row +1)*350+col+2]<<1; 
 sumval+= IN[(row +2)*350+col]; 
 sumval+= IN[(row +2)*350+col+1]<<1; 
 sumval+= IN[(row +2)*350+col+2]; 
 sumval = sumval >> 4; 
 OUT[row * 350 + col] = (short) sumval; 
©João M. P. Cardoso 13 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 } 
 } 
 return OUT; 
} 
1.13 Depois de simplificações algébricas e 
reassociação 
final public static short[] doFIR(short[] IN) { 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int sumval=IN[row*350+col]; 
 sumval+=IN[row*350+col+1]<<1; 
 sumval+=IN[row*350+col+2]; 
 sumval+=IN[350*row +350+col]<<1; 
 sumval+=IN[350*row +351+col]<<2; 
 sumval+=IN[350*row +352+col]<<1; 
 sumval+=IN[350*row +700+col]; 
 sumval+=IN[350*row +701+col]<<1; 
 sumval+=IN[350*row +702+col]; 
 sumval = sumval >> 4; 
 OUT[row * 350 + col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.14 Depois de CSE (eliminação de sub-expressões 
comuns): 
final public static short[] doFIR(short[] IN) { 
 short[] OUT = new short[122500]; 
 
 for (int row=0; row < 348; row++) { 
 for (int col = 0; col< 348; col++) { 
 int row_350_col = row*350 + col; 
 
 int sumval= IN[row_350_col]; 
 sumval+= IN[row_350_col + 1]<<1; 
 sumval+= IN[row_350_col + 2]; 
©João M. P. Cardoso 14 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 sumval+= IN[row_350_col + 350]<<1; 
 sumval+= IN[row_350_col + 351]<<2; 
 sumval+= IN[row_350_col + 352]<<1; 
 sumval+= IN[row_350_col + 700]; 
 sumval+= IN[row_350_col + 701]<<1; 
 sumval+= IN[row_350_col + 702]; 
 sumval = sumval >> 4; 
 OUT[row_350_col] = (short) sumval; 
 } 
 } 
 return OUT; 
} 
1.15 Sumário 
As optimizações ilustradas nesta ficha permitem, sempre que haja potencial para a sua 
aplicação, melhorar o desempenho do código. No exemplo ilustrado foi necessário 
aplicar algumas das optimizações mais do que uma vez, em virtude da aplicação de 
certas optimizações potenciar a aplicação de outras (ver por exemplo a aplicação do 
desenrolamento de ciclos). 
 
©João M. P. Cardoso 15 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 2 Introdução aos Algoritmos 
Iterativos 
Duração: 3 horas 
1.16 Algoritmo Iterativo para Determinar Funções 
Recursivas 
Esta aula pretende representar uma classe de algoritmos muito utilizada em algumas 
fases de um compilador. Estes algoritmos designam-se por iterativos, pois vão 
alcançando a solução final por iterações. 
Pretende-se determinar se um conjunto de chamadas a funções existente num dado 
programa origina recursividade. Para tal é normalmente criado um grafo chamado de 
Call Graph1 (grafo de chamadas a funções) que representa a estrutura de chamadas a 
funções de um programa. Considere os pedaços de código seguintes (as reticências 
indicam enunciados no programa que não contêm chamadas a instruções): 
 Void P() {... Q(); … S(); …} 
 Void Q() {...R(); … T(); …} 
 Void R() {…P(); …} 
 Void S() {…} 
 Void T() {...} 
Cada nó do Call Graph representa a chamada a uma função ou procedimento, e cada 
laço entre dois nós representa que a função de onde sai a seta chama a função para 
onde a seta aponta. O Call Graph que representa o programa é (poderia ser construído 
com base na análise do código do programa): 
 
1 O Call Graph é utilizado na compilação em outros contextos que não apenas o de recursividade. 
©João M. P. Cardoso 16 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 
P
Q
R T
S
 
Vamos supor que um compilador pretendia determinar quais são as funções 
recursivas. 
1.17 Transitive Closure 
Uma das propriedades que se pode aplicar ao grafo é a propriedade transitiva: 
● Se existe uma seta do nó A para o nó B e do nó B para o nó C então vamos fazer 
com que exista também uma seta entre o nó A e o nó C. 
Como os enunciados ‘A chama A directa ou indirectamente e ‘A é recursiva’ são 
equivalentes a aplicação da regra anterior permite determinar automaticamente as 
funções recursivas num determinado programa. 
Após aplicação da propriedade transitiva teríamos o grafo seguinte: 
 
P
Q
R T
S
 
Que mostra claramente que as funções P, Q, e R são funções recursivas. 
1.18 Algoritmo Iterativo para Transitive Closure 
O seguinte algoritmo iterativo pode ser utilizado para aplicar a propriedade transitiva 
a um Call Graph: 
SET flag of Something changed TO TRUE; 
WHILE something changed { 
 SET flag of Something changed TO FALSE; 
©João M. P. Cardoso 17 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 FOR EACH node A IN Graph { 
 FOR EACH node B IN Descendants of Node A { 
 FOR EACH node C IN Descendants of Node B { 
 IF there is no arrow from Node A to Node C { 
 Add an arrow from Node A to Node C; 
 SET flag Something changed TO TRUE; 
 } 
 } 
 } 
 } 
} 
1.19 Exercício 1 
Com base no código Java (ver a secção seguinte) formado pelas classes Graph e 
TransitiveClosure, escreva o método da classe Graph, designado por 
transitiveClosure, que deve implementar o algoritmo apresentado anteriormente. De 
seguida realize os passos seguintes: 
a) Compile as classes java fazendo: javac *.java 
b) Execute o programa fazendo: java TransitiveClosure 
1.20 Código Java 
No código Java, o Call Graph original é representado por um array bidimensional, 
designado por Edges, de 5×5 elementos booleanos. O grafo original poderá ser 
representado pela seguinte matriz, em que os nós 0, 1, 2, 3, e 4 representam as funções 
P, Q, R, S, e T, respectivamente: 
J Edges[i][j] 
0 1 2 3 4 
0 False true false true false 
1 False False true False true 
2 true False False False False 
3 False False False False False 
I 
4 False False False False False 
 
©João M. P. Cardoso 18 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
Por exemplo, o valor true no elemento edges[0][1] indica que existe um laço entre o 
nó 0 e o nó 1 com sentido de 0 para 1.1.21 Classe Graph.java 
/** 
 This is the class of the calling graph structure. 
 It includes the transitive closure algorithm. 
 
the lines below tells the javadoc tool who is the author of this class and which is the 
version (try: javadoc graph.java and then view the generated html files) 
 @author João M. P. Cardoso 
 @version v0.1 
*/ 
 
// import from the API the class to use System.out.println 
import java.io.*; 
 
public class Graph { 
 
 // array which represents the edges between nodes 
 boolean[][] edges; 
 
 /** 
 add an edge between two nodes 
 @param source represents the source of the directed edge 
 @param sink represents the destination node of the directed edges 
 */ 
 public void addEdge(int source, int sink) { 
 edges[source][sink] = true; 
 } 
 
 /** 
 Print the edges between nodes. 
 */ 
 public void print() { 
 System.out.println("Graph edges: "); 
 int N = edges.length; 
 
 for(int i=0; i<N; i++) 
 for(int j=0; j<N; j++) 
 if(edges[i][j]) 
©João M. P. Cardoso 19 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 System.out.println(i+" -> "+j); 
 } 
 
 /** 
 Constructor of the graph. 
The line below defines the argument numNodes to be used by the javadoc tool 
 @param numNodes the number of nodes in the graph 
 */ 
 public Graph(int numNodes) { 
 // create the array with size = numNodes x numNodes 
 edges = new boolean[numNodes][numNodes]; 
 
 // initiate all the elements equal to false: none edges 
 for(int i=0; i<numNodes; i++) 
 for(int j=0; j<numNodes; j++) 
 edges[i][j] = false; 
 } 
 
 /** 
 Show the functions of the calling graph which are recursive. 
 */ 
 public void printRecursiveFunctions() { 
 int numNodes = this.edges.length; 
 
 System.out.print("Recursive Functions in nodes: {"); 
 for(int k=0; k<numNodes; k++) 
 // if there is an edge with source=sink then 
 // the node represents a recursive function 
 if(edges[k][k]) 
 System.out.print(" "+k); 
 
 System.out.println(" }"); 
 } 
 
 /** 
 Algorithm to perform the transitive closure on the original graph. 
 */ 
 public void transitiveClosure() { 
 // your code must be here!!! 
 } 
 
} 
©João M. P. Cardoso 20 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
1.22 Classe TransitiveClosure.java 
/** 
 Class where the calling graph is created and the transitive closure is applied. 
*/ 
public class TransitiveClosure { 
public static void main(String args[]) { 
 // create a calling graph with 5 nodes 
 Graph callGraph = new Graph(5); 
 
 // add the 5 edges 
 callGraph.addEdge(0, 1); 
 callGraph.addEdge(1, 2); 
 callGraph.addEdge(2, 0); 
 callGraph.addEdge(0, 3); 
 callGraph.addEdge(1, 4); 
 
 // print the original graph 
 callGraph.print(); 
 
 // call the transitive closure algorithm over the callGraph 
 callGraph.transitiveClosure(); 
 
 // print the graph after applying the transitive closure algorithm 
 callGraph.print(); 
 
 // show the nodes which represent recursive functions 
 callGraph.printRecursiveFunctions(); 
 } 
} 
1.23 Trabalho para Casa 
Modifique o método main da classe TransitiveClosure de modo a determinar as 
funções recursivas do seguinte Call Graph: 
©João M. P. Cardoso 21 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 
P
Q
R T
S
U 
1.24 Créditos 
A aula é baseada no exemplo apresentado no livro: 
Dick Grune, Henri E. Bal, Ceriel J. H. Jacobs, and Koen G. Langendoen, Modern 
Compiler Design, John Wiley & Sons, Ltd, 2000. 
©João M. P. Cardoso 22 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 3 Exercícios sobre Expressões 
Regulares e Autómatos Finitos 
Duração: 3 horas 
1.25 Exercícios com Expressões Regulares 
1.1 Escreva expressões regulares para os seguintes exemplos: 
(a) números binários representando números inteiros; 
(b) [TPC] URLs da forma: http://www.ualg.pt (em que o campo intermédio 
“ualg” é o único campo variável). 
(c) [TPC] IPs da forma: 140.192.33.37 (considere que todos os IPs têm o mesmo 
número de dígitos por cada campo). 
(d) Representação binária de números inteiros sem utilizarem zeros supérfluos; 
(e) Strings sobre o alfabeto {a, b, c} com número ímpar de a’s; 
(f) [TPC] Strings sobre o alfabeto {a, b, c} em que o primeiro “a” precede o 
primeiro “b”; 
(g) Números binários cuja divisão por 4 dá resto zero; 
(h) [TPC] Números binários maiores do que 101001; 
(i) [TPC] A linguagem das constantes em vírgula flutuante (notação utilizada em 
Java). 
1.2 Acha que é possível escrever expressões regulares para os seguintes exemplos? 
No caso de ser possível apresente uma solução: 
(j) números binários que começam e acabam com o mesmo digito; 
(k) [TPC] sequências de algarismos que formam capicuas; 
1.26 Exercícios com Autómatos Finitos 
2.1 Considere o autómato finito seguinte: 
©João M. P. Cardoso 23 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 
0 1 
0 
0 
2
0 
3
1 
1 
1 
 
(a) O autómato é determinista ou não determinista? 
(b) Qual é o seu estado de início? Quais são os estados de aceitação (finais)? 
(c) Este autómato aceita a sequência 110100? Qual a sequência de estados 
visitados no reconhecimento desta String? 
(d) Qual é a String mais pequena que o autómato aceita? 
(e) Pode indicar a String maior que o autómato aceita? 
(f) Por palavras, qual é a linguagem que o autómato aceita? 
2.2 Desenhe os NFAs para as expressões regulares seguintes. Depois converta cada 
um deles para DFA. 
(a) [01] 
(b) 1+ 
(c) (0 | 1) [0 | 1]+ 
2.3 Converta os NFAs seguintes para DFAs: 
(a) 
 0, 1
x y z
0 1
 
(b) 
 
(c) 
©João M. P. Cardoso 24 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 
2.4 Um analisador lexical baseado num interpretador de um DFA utiliza duas tabelas: 
● edges: indexada pelo número do estado e símbolo de entrada, retorna o número do 
estado, e 
● final: indexada pelo número do estado, retorna 0 ou um número representativo da 
acção a realizar. 
Considerando a seguinte especificação: 
(aba)+ ⇒ acção número 1 
(a(b*)a) ⇒ acção número 2 
(a | b) ⇒ acção número 3 
Apresente as tabelas edges e final para o analisador lexical. 
 
©João M. P. Cardoso 25 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 4 Exercícios sobre Gramáticas 
Duração: 3 horas 
1. Especificar utilizando a representação BNF gramáticas correspondentes às 
expressões regulares: 
(a) [0-9]+ 
(b) [0-9]* 
2. A gramática seguinte produz expressões constituídas de dígitos 0...9 separados 
pelos sinais + ou -: 
Expr → Expr “+” Expr | Expr “-“ Expr | Digit 
Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
(a) Considere as expressões 9-5+2 e 3+7-4-2. Desenhe árvores sintácticas 
concretas que derivem cada uma destas expressões; 
(b) Pode derivar -5+2 da gramática especificada? Se achar que sim desenhe a 
árvore sintáctica, caso contrário diga porque não. 
(c) É a gramática ambígua? No caso de ser, tente encontrar uma gramática que 
possa produzir a mesma linguagem (i.e., o mesmo conjunto de expressões) mas 
que não seja ambígua. 
(d) Diga se cada uma das gramáticas seguintes é equivalente (i.e., produz a mesma 
linguagem)à gramática anterior? 
(i) Expr → Expr “+” Expr 
 Expr → Expr “-“ Expr 
 Expr → Digit 
 Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
(ii) DIGIT = [0-9] 
 Expr → Expr “+” Expr 
 Expr → Expr “-“ Expr 
 Expr → DIGIT 
(iii) Expr → (Expr “+” Expr) | (Expr “-“ Expr) | Digit 
 Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
(iv) OP = “+“ | “-“ 
 Expr → (Expr OP Expr) | Digit 
 Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
3. Considere as gramáticas seguintes: 
©João M. P. Cardoso 26 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
DIGIT = [0-9] 
(i) Aexpr → “-“ | DIGIT | Aexpr DIGIT 
(ii) Bexpr → DIGIT Bexpr | Bexpr DIGIT | “.” 
(a) Descreva as linguagens produzidas por cada uma das gramáticas. 
(b) Ambas as gramáticas são recursivas. Apresente gramáticas equivalentes não-
recursivas utilizando a notação EBNF; 
4. Considere a gramática seguinte: 
NUMLIT = [0-9]+ 
IDENT = [a-zA-Z][a-zA-Z0-9]* 
BOOLLIT = “true” | “false” 
Seq → Comando { “;” Seq } 
Comando → “if” Expr “then” Comando [“else” Comando] 
 | IDENT “:=” Expr 
 | “{“ Seq “}” 
Expr → NUMLINT | BOOLLIT | IDENT 
(a) Desenhe a árvore sintáctica concreta para a sequência de código: 
y := 0; 
 if x then y := 1 
 else {y := 0} 
(b) Desenhe uma possível AST para a árvore sintáctica concreta anterior. 
5. Dada a gramática: 
 NUM = [0-9]+ 
ID = [A-Za-Z][0-9A-Za-z]* 
Expr → Expr “+” Term | Expr “–” Term | Term 
Term → Term “*” Factor | Term “/” Factor | Factor 
Factor → Primary “^” Factor | Primary 
Primary → “-” Primary | Element 
Element → “(“ Expr “)” | NUM | ID 
Quais as árvores sintácticas para: 
(a) 5-2*3 
(b) y^3 
6. Pretende-se especificar uma gramática que permita produzir expressões aritméticas 
com inteiros atendendo a que: 
©João M. P. Cardoso 27 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
(i) as operações aritméticas que podem ser utilizadas são (por ordem de 
precedência): 
• ^ 
• /, * 
• +, - 
(ii) a gramática deve ser não-ambígua e deve respeitar a prioridade das 
operações aritméticas; 
(iii) deve poder produzir expressões aritméticas com parêntesis; 
Especifique a gramática utilizando a notação EBNF. 
©João M. P. Cardoso 28 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 
FICHA Nº 5 Implementação de Analisadores 
Gramaticais Utilizando o JavaCC (1ª parte) 
Duração: 3 horas 
Utilização do JavaCC [1] para gerar parsers. Esta aula tem como objectivo o início da 
aprendizagem do gerador de analisadores sintácticos JavaCC. Esta tarefa requer a 
aplicação dos conhecimentos até agora adquiridos na disciplina, principalmente no 
que respeita aos conceitos sobre análise sintáctica e sobre analisadores sintácticos 
descendentes. 
O JavaCC utiliza um ficheiro com extensão .jj onde se encontra descrita a gramática 
para o parser e gera uma classe Java com o nome do parser e outras classes Java de 
suporte2. 
nome.jj Parser.java 
ParserTojenManager.java 
ParserConstants.java 
Token.java 
ParseError.java 
… 
JavaCC 
 
Figura 2. Entradas e saídas do JavaCC supondo que foi especificado “Parser” 
como nome do parser no ficheiro nome.jj. 
1.27 Exemplo 
Suponhamos que desejamos implementar um analisador sintáctico que reconheça 
expressões aritméticas com apenas um número inteiro positivo ou com uma adição ou 
uma subtracção de dois números inteiros positivos (por exemplo: 2+3, 1-4, 5, etc.). De 
seguida apresenta-se uma gramática em EBNF com a especificação do símbolo 
terminal utilizando uma expressão regular: 
 
2 À medida que forem percebendo o JavaCC vão também tomando conhecimento do significado das 
classes de suporte. 
©João M. P. Cardoso 29 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
INTEGER = [0-9]+ 
Aritm → Integer [(“+” | “-“) Integer] 
Para implementar um parser que implemente esta gramática utilizando o JavaCC 
temos de criar um ficheiro com extensão .jj (vamos chamar-lhe: Exemplo.jj). 
O ficheiro é constituído por: 
1. Lista de opções (opcional): é onde pode ser definido o nível de lookahead, por 
exemplo. 
2. Unidade de compilação Java (PARSER_BEGIN(nome) ... 
PARSER_END(nome)) 
3. Lista de produções da gramática (as produções aceitam os símbolos +, *, e ? 
com o mesmo significado, aquando da utilização em expressões regulares) 
Por exemplo para a gramática anterior, poderemos criar o ficheiro Exemplo.jj 
seguinte: 
PARSER_BEGIN(Exemplo) 
 // código Java que invoca o parser 
 public class Exemplo { 
 public static void main(String args[]) throws ParseException { 
 // criação do objecto utilizando o constructor com argumento para 
 // ler do standard input (teclado) 
 Exemplo parser = new Exemplo(System.in); 
 Exemplo.Aritm(); 
 } 
} 
PARSER_END(Exemplo) 
 
// símbolos que não devem ser considerados na análise 
SKIP : 
{ 
 “ “ | “\t” | “\r” 
} 
 
// definição dos tokens (símbolos terminais) 
TOKEN : 
{ 
 < INTEGER : ([“0” – “9”])+ > 
 | < EOL : “\n” > 
©João M. P. Cardoso 30 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
} 
 
// definição da produção 
void Aritm() : {} 
{ 
 <INTEGER> ( (“+” | “-“) <INTEGER> )? (<EOF> | <EOL>) 
} 
 
Em seguida deve fazer-se: 
Javacc Exemplo.jj 
Compilar o código Java gerado: 
Javac *.java 
Executar o analisador sintáctico: 
Java Exemplo 
Poderemos associar às funções referentes aos símbolos não-terminais pedaços de 
código Java. Por exemplo, as modificações apresentadas em seguida permitem 
escrever no ecrã mensagens a indicar os números que são lidos pelo parser: 
void Aritm : {Token t1, t2;} 
{ 
 t1=<INTEGER> { 
 System.out.println(“Integer = “+t1.image); 
 } 
 ( (“+” | “-“) t2=<INTEGER> { 
 System.out.println(“Integer = “+t2.image); 
 } 
 )? (<EOF> | <EOL>) 
} 
Por cada símbolo terminal INTEGER, foi inserida uma linha de código Java que 
imprime no ecrã o valor do token lido (o método image da classe Token retorna uma 
String representativa do valor do token3) 
Insira estas modificações no ficheiro Exemplo.jj e volte a repetir o processo até à 
execução do parser. Verifique o que acontece. 
 
3 Outros métodos serão apresentados posteriormente. 
©João M. P. Cardoso 31 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
Como poderíamos adicionar também a escrita do sinal (+ ou -) lido? 
1.28 Exercícios 
1. Considere a ficha Nº 5. No exercício pretendia-se implementar um programa para 
reconhecer números inteiros e números reais introduzidos via teclado. As expressões 
regulares que definem os números são: 
Inteiro → [0-9]+ 
Real → [0-9]*.[0-9]+ 
Agora, pretende-se implementar o programa utilizando o gerador de analisadores 
léxicos e sintácticos: JavaCC. 
Antes de iniciar as implementações referentes aos exercícios apresentados de seguida, 
deve ler com atenção o tutorial [1]. Tenha atenção aos símbolos que devem ser 
utilizados nas produções da gramática no JavaCC. Note que o JavaCC requer a 
definição de gramáticas não-ambíguas de modo a poder fornecer apenas uma árvore 
sintáctica concreta para uma dada frase. 
2. Implemente utilizando o JavaCC um analisador sintáctico que permita reconhecer 
expressões aritméticas com as operações *, +, e -. O analisador deve também aceitar a 
utilização de parêntesis; 
3. Com base no analisador anterior, adicione o código Java necessário para 
implementar uma calculadora de expressões aceites pela gramática. 
1.29 Referênciasde Apoio 
1. JavaCC: https://javacc.dev.java.net/ 
2. Oliver Enseling, “Build your own languages with JavaCC”, Copyright © 2003 
JavaWorld.com, an IDG company, http://www.javaworld.com/javaworld/jw-
12-2000/jw-1229-cooltools_p.html (cópia local em pdf: 
http://w3.ualg.pt/~jmcardo/ensino/PS2003/AulaTP7/jw-1229-cooltools.pdf) 
©João M. P. Cardoso 32 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 6 Implementação de Analisadores 
Gramaticais Utilizando o JavaCC (2ª parte) 
Duração: 3 horas 
Implementação de uma calculadora utilizando o JavaCC sem a criação da árvore 
sintáctica. 
1.30 Exercício 
Considere a gramática seguinte: 
EOL=”\n” 
INTEGER=[0-9]+ 
 
Start → Expr EOL 
Expr → Term {(“+” Expr) | (“-“ Expr)} 
Expr → “(“ Expr “)” 
Term → Unary {(“*” Term) | (“/” Term)} 
Term → “(“ Expr “)” 
Unary → “-“ INTEGER 
Unary → INTEGER 
a) É a gramática ambígua? 
b) A gramática respeita as precedências (prioridades) das operações aritméticas? 
c) Acha que a gramática tem recursividade à esquerda? 
d) Para que não seja necessário backtracking qual o nível mínimo de lookahead 
necessário? 
e) Implemente esta gramática utilizando o JavaCC. Utilize o nível de lookahead que 
achar necessário. 
f) Modifique o ficheiro do JavaCC da gramática de modo a calcular o valor das 
expressões (funcionamento como calculadora). 
©João M. P. Cardoso 33 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 7 Implementação de Analisadores 
Gramaticais Utilizando o JavaCC (3ª parte) 
Duração: 3 horas 
Esta ficha pretende que aprendam a utilizar o JJTree em conjunto com o JavaCC [1] 
para gerar parsers e árvores sintácticas. 
Após a utilização do JavaCC nas duas últimas aulas, é agora tempo de aprenderem 
como se pode gerar automaticamente a árvore sintáctica. Para tal utilizaremos o 
JJTree (é uma ferramenta integrada no pacote de software JavaCC). O JJTree é uma 
ferramenta de pré-processamento que permite gerar um ficheiro para o JavaCC que, 
para além da descrição da gramática, integra código Java para a geração da árvore 
sintáctica. O ficheiro de entrada do JJTree é um ficheiro que especifica a gramática do 
mesmo modo que para o JavaCC e que adicionalmente inclui directivas para a geração 
dos nós da árvore (é utilizado jjt como extensão do ficheiro origem). 
nome.jjt 
JJTree 
nome.jj 
Node.java 
… 
 
Figura 3. Entradas e saídas do JJTree. 
1.31 Exemplo 
Vamos considerar a gramática da FICHA 8 e vamos supor que pretendemos realizar 
um programa que calcule as mesmas expressões, desta vez gerando a árvore sintáctica 
e efectuando os cálculos sobre a árvore. 
Para gerar a árvore sintáctica vamos alterar a extensão do ficheiro da gramática 
original para jjt e vamos adicionar as directivas que indicam ao JJTree para criar a 
árvore. O ficheiro apresentado de seguida contém as modificações introduzidas (é 
utilizado o método dump() para imprimir no ecrã a árvore gerada por cada expressão 
introduzida). 
©João M. P. Cardoso 34 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
Ficheiro Calculator.jjt: 
options 
{ 
 LOOKAHEAD=2; 
} 
 
PARSER_BEGIN(Calculator) 
public class Calculator 
{ 
 public static void main(String args[]) throws ParseException { 
 Calculator parser = new Calculator(System.in); 
 int i=0; 
 while (true) { 
 // the function will return the root node of the Syntax Tree 
 SimpleNode rootNode = parser.parseOneLine(); 
 
 //print the Syntax Tree 
 rootNode.dump("Syntax Tree "+(i++)+": "); 
 } 
 } 
} 
PARSER_END(Calculator) 
 
SKIP : 
{ 
 " " 
 | "\r" 
 | "\t" 
} 
 
TOKEN: 
{ 
 < INTEGER: (["0"-"9"])+ > 
 | < EOL: "\n" > 
} 
 
SimpleNode parseOneLine() #Root : {} // diz ao JJTree para criar o nó Root 
{ 
 expr() <EOL> {return jjtThis;} // retorna o nó da árvore construído neste 
procedimento 
 | <EOL> 
©João M. P. Cardoso 35 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 | <EOF> { System.exit(-1); } 
} 
 
void expr(): 
{ 
} 
{ 
 term() 
 ( 
 "+" expr() #Add(2) // diz ao JJTree para criar um nó Add que tem dois filhos 
 | "-" expr() #Sub(2) // diz ao JJTree para criar um nó Sub que tem dois filhos 
 )* 
 | "(" expr() ")" 
} 
 
void term(): {} 
{ 
 unary() 
 ( 
 "*" term() #Mult(2) // diz ao JJTree para criar um nó Mult que tem dois filhos 
 | "/" term() #Div(2) // diz ao JJTree para criar um nó Div que tem dois filhos 
 )* 
 | "(" expr() ")" 
} 
 
void unary(): {} 
{ 
 "-" <INTEGER> 
 | <INTEGER> 
} 
 
Em seguida deve fazer-se: 
jjtree Calculator.jjt 
Gerar o código Java com o JavaCC: 
javacc Calculator.jj 
Compilar o código Java gerado: 
Javac *.java 
Executar o analisador sintáctico: 
Java Calculator 
©João M. P. Cardoso 36 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
Verifique de seguida as árvores geradas para um conjunto de expressões introduzidas. 
Contudo, a criação da árvore sintáctica não é suficiente para nós. Primeiro, a árvore 
gerada não armazena os valores dos números inteiros lidos. Segundo, é necessário 
programar o procedimento que atravessa a árvore e calcula o valor da expressão 
aritmética definida pela árvore. 
Para resolvermos o primeiro obstáculo teremos que fazer algumas alterações. O 
JJTree vai gerar uma classe Java para o SimpleNode (nome da classe definido como 
retorno do procedimento: parseOneLine()). Esta classe, é utilizada para representar os 
nós da árvore sintáctica, e pode ser personalizada para implementar as 
funcionalidades necessárias. A classe inclui os seguintes métodos: 
Alguns métodos da classe representativa 
dos nós da árvore sintáctica: 
Descrição: 
public Node jjtGetParent() Retorna o nó pai do nó actual 
public Node jjtGetChild(int i) Retorna o nó filho nº i 
public int jjtGetNumChildren() Retorna o número de filhos do nó 
Public void dump() Escreve no ecrã a árvore sintáctica 
a partir do nó 
 
Depois da classe SimpleNode ser gerada pela primeira vez pelo JJTree podemos 
adicionar-lhe métodos ou campos. Neste momento interessa-nos acrescentar à classe 
um campo que permita armazenar o valor do inteiro (no caso das folhas da árvore). 
Foram ainda adicionados dois métodos que permitem aceder ao campo (atribuir e 
retornar o seu valor). A classe é apresentada de seguida com as alterações efectuadas 
(a negrito). 
/* Generated By:JJTree: Do not edit this line. SimpleNode.java */ 
public class SimpleNode implements Node { 
 protected Node parent; 
 protected Node[] children; 
 protected int id; 
 protected Calculator parser; 
 
 int value; 
 public void setValue(int a) { 
 this.value = a; 
 } 
 
©João M. P. Cardoso 37 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 public int getValue() { 
 return this.value; 
 } 
 
 public SimpleNode(int i) { 
 id = i; 
 } 
 public SimpleNode(Calculator p, int i) { 
 this(i); 
 parser = p; 
 } 
 public void jjtOpen() { 
 } 
 public void jjtClose() { 
 } 
 public void jjtSetParent(Node n) { parent = n; } 
 public Node jjtGetParent() { return parent; } 
 public void jjtAddChild(Node n, int i) { 
 if (children == null) { 
 children = new Node[i + 1]; 
 } else if (i >= children.length) { 
 Node c[] = new Node[i + 1]; 
 System.arraycopy(children,0, c, 0, children.length); 
 children = c; 
 } 
 children[i] = n; 
 } 
 public Node jjtGetChild(int i) { 
 return children[i]; 
 } 
 public int jjtGetNumChildren() { 
 return (children == null) ? 0 : children.length; 
 } 
 
 /* You can override these two methods in subclasses of SimpleNode to 
 customize the way the node appears when the tree is dumped. If 
 your output uses more than one line you should override 
 toString(String), otherwise overriding toString() is probably all 
 you need to do. */ 
 public String toString() { return CalculatorTreeConstants.jjtNodeName[id]; } 
 public String toString(String prefix) { return prefix + toString(); } 
 
©João M. P. Cardoso 38 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 /* Override this method if you want to customize how the node dumps 
 out its children. */ 
 public void dump(String prefix) { 
 System.out.print(toString(prefix)); 
 if (children != null) { 
 for (int i = 0; i < children.length; ++i) { 
 SimpleNode n = (SimpleNode)children[i]; 
 if (n != null) { 
 System.out.println(); 
 n.dump(prefix + " "); 
 if(n.id == CalculatorTreeConstants.JJTUNARY) 
 System.out.println(" ["+n.getValue()+"]"); 
 } 
 } 
 } 
 } 
} 
O novo ficheiro que descreve a gramática, que indica ao JJTree para gerar a árvore 
sintáctica e que calcula o valor das expressões aritméticas introduzidas é apresentado 
de seguida. Durante o atravessamento da árvore é importante que se possa verificar de 
que tipo é um determinado nó. Tal pode ser feito utilizando o campo id de cada nó da 
árvore (ver nos exemplos node.id). Para cada tido de nó da árvore o JJTree gera um 
ficheiro em que são especificados os identificadores atribuídos (ver ficheiro 
CalculatorTreeConstants.java). O tipo de nós corresponde aos procedimentos da 
gramática e/ou aos nós especificados nas directivas para o JJTree. 
Novo ficheiro Calculator.jjt: 
options 
{ 
 LOOKAHEAD=2; 
} 
 
PARSER_BEGIN(Calculator) 
public class Calculator { 
 public static void main(String args[]) throws ParseException { 
 Calculator parser = new Calculator(System.in); 
 int i=0; 
 while (true) { 
 // the function will return the root node of the Syntax Tree 
©João M. P. Cardoso 39 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 SimpleNode rootNode = parser.parseOneLine(); 
 
 //print the Syntax Tree 
 rootNode.dump("Syntax Tree "+(i++)+": "); 
 
 // call the evaluation method with the ROOT node 
 System.out.println("Result: "+parser.eval(rootNode)); 
 } 
 } 
 
/* 
Método recursivo que realiza o cálculo da expressão percorrendo a árvore sintáctica. 
*/ 
int eval(SimpleNode node) { 
 // each node contains an id field identifying its type. 
 int id = node.id; 
 
 //System.out.println("VALUE "+node.getValue()+" "+id); 
 
 if(id == CalculatorTreeConstants.JJTUNARY) // node with integer value 
 return node.getValue(); 
 else if(node.jjtGetNumChildren() == 1) // only one child 
 return this.eval((SimpleNode) node.jjtGetChild(0)); 
 
 // nodes with two childs 
 SimpleNode lhs = (SimpleNode) node.jjtGetChild(0); //left child 
 SimpleNode rhs = (SimpleNode) node.jjtGetChild(1); // right child 
 
 switch(id) { 
 case CalculatorTreeConstants.JJTADD : return eval( lhs ) + eval( rhs ); 
 case CalculatorTreeConstants.JJTSUB : return eval( lhs ) - eval( rhs ); 
 case CalculatorTreeConstants.JJTMULT : return eval( lhs ) * eval( rhs ); 
 case CalculatorTreeConstants.JJTDIV : return eval( lhs ) / eval( rhs ); 
 default : // abort 
 System.out.println("Operador ilegal!"); 
 System.exit(1); 
 } 
 return 0; 
 } 
} 
PARSER_END(Calculator) 
 
©João M. P. Cardoso 40 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
SKIP : 
{ 
 " " 
 | "\r" 
 | "\t" 
} 
 
TOKEN: 
{ 
 < INTEGER: (["0"-"9"])+ > 
 | < EOL: "\n" > 
} 
 
SimpleNode parseOneLine() #Root : {} // diz ao JJTree para criar o nó Root 
{ 
 expr() <EOL> {return jjtThis;} // retorna o nó da árvore construído neste 
procedimento 
 | <EOL> 
 | <EOF> { System.exit(-1); } 
} 
 
void expr(): {} 
{ 
 term() 
 ( 
 "+" expr() #Add(2) // diz ao JJTree para criar um nó Add que tem dois filhos 
 | "-" expr() #Sub(2) // diz ao JJTree para criar um nó Sub que tem dois filhos 
 )* 
 | "(" expr() ")" 
} 
 
void term(): {} 
{ 
 unary() 
 ( 
 "*" term() #Mult(2) // diz ao JJTree para criar um nó Mult que tem dois filhos 
 | "/" term() #Div(2) // diz ao JJTree para criar um nó Div que tem dois filhos 
 )* 
 | "(" expr() ")" 
} 
 
void unary(): {Token t;} 
©João M. P. Cardoso 41 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
{ 
 "-" (t=<INTEGER> { 
 // diz ao JJTree para colocar o valor do inteiro num dos campos deste nó 
 // (para tal é necessário adicionar à classe Java SimpleNode o método setValue() e 
 // o campo que armazena o valor inteiro 
 jjtThis.setValue(-Integer.parseInt(t.image)4); }) 
 | (t=<INTEGER> { 
 // diz ao JJTree para colocar o valor do inteiro num dos campos deste nó 
 // (para tal é necessário adicionar à classe Java SimpleNode o método setValue() e 
 // o campo que armazena o valor inteiro 
 jjtThis.setValue(Integer.parseInt(t.image)); 
 }) 
} 
 
Acha que a árvore sintáctica gerada pelos ficheiros jjt apresentados é uma árvore 
sintáctica concreta ou uma AST (árvore sintáctica abstracta)? 
Para que não seja gerado um nó por cada procedimento na gramática utiliza-se a 
directiva #void a seguir ao nome do procedimento para o qual não se quer nó na 
árvore. Este método permite gerar as ASTs automaticamente sem por isso ser 
necessário transformar a árvore concreta numa AST. O ficheiro seguinte apresenta 
uma versão da calculadora em que são geradas ASTs. Verifique a colocação da 
directiva a indicar os símbolos não-terminais para os quais não será representado 
qualquer nó na árvore. 
Novo ficheiro Calculator.jjt: 
options 
{ 
 LOOKAHEAD=2; 
} 
 
PARSER_BEGIN(Calculator) 
public class Calculator 
 
4 Como o valor de um Token é guardado como String, é necessário converter a representação em String 
para inteiro. Tal pode ser conseguido utilizando métodos existentes nos API do Java. Por exemplo, 
Integer.parseInt(t.image) retorna o inteiro representado pela String t.image. 
©João M. P. Cardoso 42 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
{ 
 public static void main(String args[]) throws ParseException { 
 Calculator parser = new Calculator(System.in); 
 int i=0; 
 while (true) { 
 // the function will return the root node of the Syntax Tree 
 SimpleNode rootNode = parser.parseOneLine(); 
 
 //print the Syntax Tree 
 rootNode.dump("Syntax Tree "+(i++)+": "); 
 
 // call the evaluation method with the ROOT node 
 System.out.println("Result: "+parser.eval(rootNode)); 
 } 
 } 
 
int eval(SimpleNode node) { 
 // each node contains an id field identifying its type. 
 // we switch on these. 
 // enum values such as JJTUNARY come from the interface file 
 // SimpleParserTreeConstants, which SimpleParser implements. 
 // This interface file is one ofseveral auxilliary Java sources 
 // generated by JJTree. JavaCC contributes several others. 
 int id = node.id; 
 
 //System.out.println("VALUE "+node.getValue()+" "+id); 
 
 if(id == CalculatorTreeConstants.JJTUNARY) // node with integer value 
 return node.getValue(); 
 else if(node.jjtGetNumChildren() == 1) // only one child 
 return this.eval((SimpleNode) node.jjtGetChild(0)); 
 
 SimpleNode lhs = (SimpleNode) node.jjtGetChild(0); //left child 
 SimpleNode rhs = (SimpleNode) node.jjtGetChild(1); // right child 
 
 switch(id) { 
 case CalculatorTreeConstants.JJTADD : return eval( lhs ) + eval( rhs ); 
 case CalculatorTreeConstants.JJTSUB : return eval( lhs ) - eval( rhs ); 
 case CalculatorTreeConstants.JJTMULT : return eval( lhs ) * eval( rhs ); 
 case CalculatorTreeConstants.JJTDIV : return eval( lhs ) / eval( rhs ); 
 default : // abort 
 System.out.println("Operador ilegal!"); 
©João M. P. Cardoso 43 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 System.exit(1); 
 } 
 return 0; 
 } 
} 
PARSER_END(Calculator) 
 
SKIP : 
{ 
 " " 
 | "\r" 
 | "\t" 
} 
 
TOKEN: 
{ 
 < INTEGER: (["0"-"9"])+ > 
 | < EOL: "\n" > 
} 
 
SimpleNode parseOneLine() #Root : {} 
{ 
 expr() <EOL> {return jjtThis;} 
 | <EOL> 
 | <EOF> { System.exit(-1); } 
} 
 
void expr() #void : {} 
{ 
 term() 
 ( 
 "+" expr() #Add(2) 
 | "-" expr() #Sub(2) 
 )* 
 | "(" expr() ")" 
} 
 
void term() #void : {} 
{ 
 unary() 
 ( 
 "*" term() #Mult(2) 
©João M. P. Cardoso 44 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 | "/" term() #Div(2) 
 )* 
 | "(" expr() ")" 
} 
 
void unary() : {Token t;} 
{ 
 "-" (t=<INTEGER> { 
 jjtThis.setValue(-Integer.parseInt(t.image)); 
 }) 
 | (t=<INTEGER> { 
 jjtThis.setValue(Integer.parseInt(t.image)); 
 }) 
} 
1.32 Referências de Apoio 
3. JavaCC: http://www.experimentalstuff.com/Technologies/JavaCC/index.html 
• Documento de introdução ao JJTree incluído na distribuição da ferramenta: 
http://w3.ualg.pt/~jmcardo/ensino/PS2003/jjtree.intro 
©João M. P. Cardoso 45 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 8 : Exercício sobre analisadores 
sintácticos 
Tradução da notação EBNF para BNF: 
1. Para determinar os conjuntos First e Follow é necessário representar em BNF as 
seguintes gramáticas apresentadas na notação EBNF. Apresente as gramáticas em 
BNF. 
(a) 
A → “a” { “b” } (“a” | A) 
(b) 
A → { “(“ [B | D] “)” } 
D → { “[“ [B | D] “]” } 
(c) 
C → { ( “a” | [ “b” ] ) (“c” | “d” )} 
Conjuntos First e Follow: 
2. Considere a seguinte gramática representada em BNF: 
A → “a” A | “a” B “b” 
B → “b” B | C 
C → ε | B 
(a) Quais dos símbolos não-terminais podem derivar ε? 
(b) Determine os conjuntos First e Follow para os símbolos não-terminais A e B. 
Análise Sintáctica Descendente: 
3. Considere a gramática seguinte, em que PRINT, ID e NUM representam símbolos 
terminais: 
Start → S 
S → S “;“ S 
S → ID “:=” E 
S → PRINT “(“ L “)” 
©João M. P. Cardoso 46 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
E → ID 
E → NUM 
E → E “+” E 
E → “(“ S “,” E “)” 
L → E 
L → L “,” E 
(a) Acha que esta gramática é ambígua ou não-ambígua? Justifique a resposta. 
(b) Determine os conjuntos: First(S), First(E), First(L), Follow(S), Follow(E), e 
Follow(L). 
(c) Pretende-se implementar um analisador sintáctico descendente LL(1). Para tal 
deve-se, e apenas caso seja necessário, transformar a gramática de forma a eliminar 
ambiguidades e recursividades à esquerda. Caso seja necessário, deve-se também 
factorizar à esquerda. Tendo em atenção os pontos anteriores, verifique se é 
necessário modificar a gramática e caso seja necessário apresente a gramática 
modificada. 
Análise Sintáctica Ascendente: 
4. Considere a gramática seguinte em que B é o símbolo inicial (os números entre 
parêntesis identificam cada termo de uma produção): 
B → P “&” B | P (1, 2) 
P → “x” | “y” (3, 4) 
(c) Como pode a gramática produzir x&y&x? Pode a gramática produzir x&y&? 
(d) A partir das regras da gramática construa o DFA (autómato finito determinista) 
que implemente o controlo das acções num parser ascendente LR(0) ou SLR. 
(e) A partir do DFA obtido na alínea anterior construa as tabelas sintácticas supondo 
uma gramática LR(0) e uma gramática SLR. 
(f) Considerando a tabela sintáctica seguinte mostre como o parser aceita a entrada 
x&y&x completando a tabela apresentada a seguir à tabela sintáctica. 
Acção Goto Estado 
x y & $ B P 
S1 Shift s5 Shift s5 erro Erro Goto s2 Goto s3 
S2 erro erro erro Aceita 
S3 erro erro Shift s4 Reduce (2) 
©João M. P. Cardoso 47 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
S4 Shift s5 Shift s6 erro Erro Goto 7 Goto 3 
S5 Reduce (3) Reduce (3) Reduce (3) Reduce (3) 
S6 Reduce (4) Reduce (4) Reduce (4) Reduce (4) 
S7 erro erro erro Reduce (1) 
 
Pilha de 
Símbolos 
Pilha de Estados String na 
Entrada 
Acção 
 S1 x&y&x$ Shift s5 
x s1 s5 &y&x$ Reduce (3) 
P S1 &y&x$ Goto s3 
P s1 s3 &y&x$ Shift s4 
P & s1 s3 s4 y&x$ 
 
 
 
 
 
(g) Repita as acções efectuadas na tabela seguinte quando a String de entrada é 
x&y&: 
Pilha de 
Símbolos 
Pilha de Estados String na 
Entrada 
Acção 
 x&y&$ 
 
 
 
 
 
 
 
 
 
5. Considere cada uma das gramáticas seguintes. Diga se cada uma das gramáticas é 
uma gramática LR(0) e/ou SLR(1). Para tal, construa as tabelas sintácticas LR(0) 
e SLR(1). Nota: uma gramática designa-se, por exemplo, por gramática LR(0) se a 
tabela sintáctica LR(0) não apresenta conflitos (shift/reduce ou reduce/reduce). 
a) 
 S → X $ (1) 
©João M. P. Cardoso 48 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
 X → “(“ X “)” | “(“ “)” (2, 3) 
b) 
 S → X $ (1) 
 X → “(“ X “)” | ε (2, 3) 
c) 
 S → X $ (1) 
 X → “(“ | Y (2, 3) 
 Y → “(“ Y “)” | ε (4, 5) 
 
 
©João M. P. Cardoso 49 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
FICHA Nº 9 : Exercícios de Revisão 
1. Converta o NFA (autómato finito não-determinista) seguinte num DFA (autómato 
finito determinista) utilizando o algoritmo de conversão que aprendeu. 
 
0 1
x 
4 3
x 
y 
x 
y 
2 y 
x 
x 
5 a 
6
x 
x 
a 
a 
 
2. Um analisador lexical baseado num interpretador de um DFA utiliza duas tabelas: 
● edges: indexada pelo número do estado e símbolo de entrada, retorna o 
número do estado, e 
● final: indexada pelo número do estado, retorna 0 ou um número representativo 
da acção a realizar. 
Apresente as tabelas edge e final para o analisador lexical do exercício anterior. 
3. Considere a gramática seguinte (o número entre parêntesis identifica o número de 
cada produção): 
 
LIT = [0-9]+ 
OP = “+” | “-“ | “*” | “/” 
 
Start → Expr $ (1) 
Expr → Expr OP Term (2) 
Expr → LIT (3) 
Expr → “(“ Expr “)” (4) 
Term → LIT (5) 
(a) Desenhe as árvores sintácticas concretas que conseguir derivar para as 
entradas: (3/2)+4$ e 3/2+4$; 
(b) Acha que a gramática apresentada é ambígua ou não-ambígua? Justifique a 
resposta; 
©João M. P. Cardoso 50 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES(c) Caso pretendesse que a gramática aceitasse nomes de variáveis – começados 
com uma letra e seguidos de sequências com zero ou mais dígitos ou letras – e não 
apenas literais como símbolos terminais, quais as modificações que teria de introduzir 
na gramática? 
(d) Suponha que se pretende implementar um analisador sintáctico descendente 
sem retrocesso (backtracking). Diga se terá de modificar a gramática para a 
implementação ser possível. No caso de ter de ser modificada, apresente a nova 
gramática; 
(e) Determine os conjuntos First e Follow para cada um dos símbolos não 
terminais da gramática anterior; 
(f) Considerando a gramática original desenhe o DFA para o analisador sintáctico 
LR(0); 
(g) Desenhe a tabela sintáctica correspondente ao DFA da alínea anterior; 
(h) Diga se a gramática original é LR(0). Caso não seja indique se é SLR(1). 
Justifique as respostas; 
4. Na figura a seguir é apresentado um pedaço de código (os números entre 
parêntesis identificam cada linha de código). 
 
(1) int SumArray(int[] A, int N) { 
(2) int i, sum; 
(3) i = 0; 
(4) sum = 0; 
(5) while(i < N) { 
(6) sum = sum + A[i]; 
(7) i = i+1; 
(8) } 
(9) return sum; 
(10) } 
(i) Diga os elementos presentes no código que deverão ser armazenados na tabela 
de símbolos para as variáveis locais e na tabela de símbolos para os parâmetros da 
função; 
(j) Supondo que na geração de código assembly se pretendia utilizar a pilha de 
chamadas para armazenar todas as variáveis na função, quais os atributos que deverá 
ter o descritor associado a cada variável; 
(k) Qual a estrutura de dados que escolheria para implementar a(s) tabela(s) de 
símbolos? 
(l) Considerando as linhas de código (6) e (9), diga que verificações devem ser 
feitas pelo analisador semântico; 
(m) Desenhe a árvore de instruções e expressões de nível alto para a sequência de 
instruções de (3) a (8), considerando as instruções: lda, sta, ldl, stl, e ldp; 
 
©João M. P. Cardoso 51 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
Anexo B: Enunciado de um Exame 
Exame de época de recurso da disciplina de Programação de 
Sistemas 
Ano lectivo de 2002/2003 
2º Semestre 
Licenciatura em Engenharia de Sistemas e Computação 
Licenciatura em Ensino de Informática 
Licenciatura em Informática, ramo de Gestão 
Duração: 2 horas + meia hora de tolerância (total: 2H30) 
1. [2 valores] Converta o NFA (autómato finito não-determinista) seguinte num 
DFA (autómato finito determinista) utilizando o algoritmo de conversão que 
aprendeu. 
 
0 1
ε 
4 3
z 
y 
2 x 
z 
x 
5 a 
6
a 
a 
ε 
a 
y 
 
2. [1,5 valores] Escreva para cada estado de aceitação do autómato da figura anterior 
a expressão regular que represente as palavras da linguagem aceites pelo mesmo. 
3. [1,5 valores] Desenhe um autómato finito (determinista ou não-determinista) que 
permita reconhecer palavras representadas por cada uma das expressões regulares 
seguintes (o autómato deve diferenciar o reconhecimento por cada uma das 
expressões): 
©João M. P. Cardoso 52 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
d+e? 
[a-c]*[1-3]+
4. [10 valores] Considere a gramática seguinte (o número entre parêntesis identifica 
o número de cada produção): 
LIT = [0-9]+ 
OP = “+” | “-“ | “*” | “/” 
Start → Expr $ (1) 
Expr → Expr OP Expr (2) 
Expr → LIT (3) 
Expr → “(“ Expr “)” (4) 
(a) Desenhe as árvores sintácticas concretas que conseguir derivar para as 
entradas: (32*2)+1$ e 32*2+1$; 
(b) Acha que a gramática apresentada é ambígua ou não-ambígua? Justifique a 
resposta; 
(c) Supondo que os tokens definidos pelo símbolo terminal OP correspondem a 
operadores aritméticos, diga se a prioridade destes operadores é respeitada pela 
gramática. Justifique a resposta com um exemplo. Caso não seja, indique as 
modificações que teria de introduzir na gramática. 
(d) Suponha que se pretende implementar um analisador sintáctico descendente 
sem retrocesso (backtracking). Diga se terá de modificar a gramática para a 
implementação ser possível. Justifique a resposta. No caso de ter de ser modificada, 
apresente a nova gramática; 
[Nota: Apresente a resolução das duas alíneas seguintes na mesma página do 
teste] 
(e) Considerando a gramática original desenhe o DFA para o analisador sintáctico 
LR(0); 
(f) Desenhe a tabela sintáctica correspondente ao DFA da alínea anterior; 
(g) Determine os conjuntos First e Follow para cada um dos símbolos não 
terminais da gramática anterior; 
©João M. P. Cardoso 53 
CADERNO DE EXERCÍCIOS E TRABALHOS PRÁTICOS PARA A DISCIPLINA 
DE COMPILADORES 
(h) Diga se a gramática original é LR(0). Caso não seja indique se é SLR(1). 
Justifique; 
(i) Desenhe uma tabela (de acordo com a tabela exemplificativa indicada em 
baixo) com as etapas do analisador sintáctico shift/reduce para a entrada: 3*2+4$. 
Pilha de estados Pilha de símbolos Entrada Acção 
 3*2+4$ 
 
5. [5 valores] Na figura a seguir é apresentado um pedaço de código (os números 
entre parêntesis identificam cada linha de código). 
(1) void AddToArray(int[] A, int N, int C) { 
(2) int i; 
(3) i = 1; 
(4) while(i <= N) { 
(5) A[i] = C + A[i]; 
(6) i = i+1; 
(7) } 
(8) } 
 
(a) Considerando as linhas de código (5) e (6), diga que verificações devem ser 
feitas pelo analisador semântico; 
(b) No caso da variável i ter sido declarada como float que conversões teriam de 
ser introduzidas durante a análise semântica da linha (6); 
(c) Desenhe a árvore de instruções e expressões de nível alto para a sequência de 
instruções de (3) a (7), considerando as instruções: lda, sta, ldl, stl, ldp; 
(d) Desenhe a representação intermédia de nível baixo para a sequência de 
instruções de (3) a (7), considerando que todas as variáveis escalares locais são 
guardadas em posições da pilha. Considere para a representação as instruções: cbr, 
lda, sta, ld, st, ldp; 
[Nota: Considere uma memória de sistema endereçável ao byte.] 
©João M. P. Cardoso 54 
	Optimizações de código
	Verificar a diferença entre o tempo de execução utilizando o
	Optimizações
	Propagação de constantes (Constant Propagation)
	Constant folding (Constant-Expression Evaluation)
	Desenrolamento de ciclos (Loop Unrolling)
	Simplificação algébrica (Algebraic simplification)
	Desenrolamento de ciclos (Loop Unrolling)
	Simplificações algébricas + constant folding
	Scalar replacement
	Simplificação algébrica
	Eliminação de código ou de declarações não utilizadas
	Strength reduction
	Depois de simplificações algébricas e reassociação
	Depois de CSE (eliminação de sub-expressões comuns):
	Sumário
	Introdução aos Algoritmos Iterativos
	Algoritmo Iterativo para Determinar Funções Recursivas
	Transitive Closure
	Algoritmo Iterativo para Transitive Closure
	Exercício 1
	Código Java
	Classe Graph.java
	Classe TransitiveClosure.java
	Trabalho para Casa
	Créditos
	Exercícios sobre Expressões Regulares e Autómatos Finitos
	Exercícios com Expressões Regulares
	Exercícios com Autómatos Finitos
	Exercícios sobre Gramáticas
	Implementação de Analisadores Gramaticais Utilizando o JavaC
	Exemplo
	Exercícios
	Referências de Apoio
	Implementação de Analisadores Gramaticais Utilizando o JavaC
	Exercício
	Implementação de Analisadores Gramaticais Utilizando o JavaC
	Exemplo
	Referências de Apoio
	: Exercício sobre analisadores sintácticos
	: Exercícios de Revisão
	Anexo B: Enunciado de um Exame