Compiladores

Primeiro Semestre de 2010

Prof. José de Oliveira Guimarães

Primeiro Trabalho.

 

Prazo de Entrega:   9 de Abril, quarta-feira, até às 12h.

 

 

Trabalho em grupos de no máximo duas pessoas.

 

Faça o analisador léxico, sintático e a geração de código em C para uma pequena linguagem de programação chamada MSI2 (Mais Simples Impossível2). Nesta linguagem, todas as palavras-chave possuem apenas uma única letra, que é sempre maiúscula. Há comandos de atribuição, impressão, leitura do teclado, decisão e repetição, além do comando composto. As variáveis são todas as letras minúsculas, automaticamente declaradas como inteiros, que é o único tipo. Antes de mostrarmos os detalhes da linguagem, é interessante estudar um exemplo:

 

G n     

G p  

= i 0   

W i # n {     

  * a p i

  P a

  + i i 1

}

 

Este exemplo lê dois números do teclado, n e p, e imprime os n primeiros múltiplos de p, começando por 0. G é o comando “get”, uma leitura do teclado. = é a atribuição. W começa o comando While, que deve ser seguido de uma comparação. Há apenas três operadores, =, < e #, sendo que este último significa “diferente de”.  P é o comando de impressão na saída padrão. + é o comando soma. Para resumir, este código deverá ser traduzido para o seguinte código em C:

 

#include <stdio.h>

 

int main() {

  int a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, w, x, y, z;

  char str[512];  // auxiliar na leitura com G

  // G n

  { gets(str);

    sscanf(str, "%d", &n);

   }

  // G p

  { gets(str);

    sscanf(str, "%d", &p);

   }

  // = i 0

  i = 0;

  //W i # n {

  while ( i != n ) {

     // * a p i

     a = p * i;

     //  P a

     printf("%d\n", a);

     // + i i 1

     i = i + 1;

  }

  gets(str);

}

 

A gramática da linguagem é dada abaixo.

 

Program ::=  Command { Command }

Command ::= AssignCommand | GetCommand |

     AddCommand | SubCommand | MultCommand |

     DivCommand | ModCommand | PrintCommand |

     IfCommand | WhileCommand | CompositeCommand

 

AssignCommand ::= “=” Variable Value

GetCommand ::= “G”  Variable

AddCommand ::= “+” Variable Value Value

SubCommand ::= “-” Variable Value Value

MultCommand ::= “*” Variable Value Value

DivCommand ::= “/” Variable Value Value

ModCommand ::= “%” Variable Value Value

PrintCommand ::= “P”  Value

 

Comparison ::= Variable Operator Value

Operator ::= “=” | “<” | “#”

IfCommand ::= “I” Comparison Command

WhileCommand ::= “W”  Comparison  Command

CompositeCommand ::= “{” Command { Command } “}”

Value ::= Variable| Number

 

 

Variable é qualquer letra minúscula. Number é um número de um único dígito. Note que, em execução, as variáveis podem conter números de mais de um dígito. Um quadro mostrando os comandos em MSI2 e a tradução para C é mostrado abaixo.

 

Comando

código em C

= a b

a = b;

G a

{ gets(str); sscanf(str, "%d", &n);   }

+ c d 1

c = d + 1;

- x 2 4

x = 2 – 4;

* a b c

a = b*c;

/ d n p

d = n/p;

% r n p

r = n%p;

P 5

printf("%d\n", 5);

I  a < n  P n

if ( a < n ) { printf("%d\n", 5); }

W i < n {  P i + i i 1 }

while ( i < n ) { printf("%d\n", i); i = i + 1; }

 

 

 

O trabalho consiste em fazer um pequeno compilador para MSI2 dividido em duas partes:

 

a) O analisador sintático mais a geração de código em C. Coloque a geração de código como instruções misturadas às instruções do analisador sintático;

b) O analisador sintático mais a construção da ASA como feito na apostila da disciplina. Coloque a geração de código em C em métodos da ASA.

 

            Em ambos os casos, gere código para a saída padrão (com System.out.println).

 

 

Observações:

 

  • não faça nenhuma conferência semântica (se houver alguma);
  • entregue o código em papel. Indique no início de cada um dos dois programas a qual letra ele pertence, (a) ou (b). Entregue um exemplo em MSI2 e a saída em C produzida por cada um dos trabalhos a) e b);
  • entregue a folha de capa disponível na página de trabalhos. Entregue apenas uma folha de capa para todos os itens a) e b). É imprescindível a entrega da folha de capa, sem a qual nenhum trabalho será aceito;
  • as mensagem de erro devem indicar exatamente o erro, comoNúmero esperado” ouComando inexistente”;
  • siga as recomendações do “Guia de Correção de Trabalhosque está na página do curso;
  • todos os trabalhos deverão ser feitos em Java.

 

Você deve entregar, impressos:

  1. a folha de capa
  2. a listagem dos arquivos do compilador (para a)e b));
  3. a listagem do código gerado para os dois exemplos dados a seguir. O primeiro deles foi dado acima.

 

Primeiro exemplo

Segundo exemplo

G n      

G p  

= i 0   

W i # n {     

  * a p i

  P a

  + i i 1

}

 

G n     

= i 2

% a n i

W i < n {     

  I a = 0 = i n

  + i i 1

  % a n i

}

I a = 0 P 0

I a # 0 P 1

 

 

O que faz mesmo o segundo exemplo ?