Construção de Compiladores

Primeiro Semestre de 2006

Prof. José de Oliveira Guimarães

 

Primeiro Trabalho.

Prazo de Entrega:   13 de Abril

 

Trabalho em grupos de no máximo duas pessoas.

 

Antes de descrever o trabalho, definiremos a linguagem Quad. Um programa em Quad manipula uma matriz de 40x40 elementos. Cada posição contém uma letra em minúsculo ou um número de um dígito (0, 1, 2, ... 9). Há uma posição corrente que chamaremos de “cabeça” de gravação/leitura. Ao início do programa, a cabeça está sempre no canto inferior esquerdo da matriz, posição (0, 0). Os valores iniciais da matriz são os dados iniciais do programa Quad. Esta é a única forma de entrada de valores para o programa.

            Quad possui comandos para mover a cabeça para todas as direções:

L – move para a esquerda

R – move para a direita

U – move para cima

D – move para baixo

O –  move para cima e para a direita

N – move para baixo e para a esquerda

 

A cabeça sempre se move de uma posição na horizontal ou vertical (ou ambas). Não há comandos para mover a cabeça para cima e para a esquerda e para baixo e para a direita.

 

Caso o movimento faça a linha (coluna) maior do que 40, a linha (coluna) é iniciada em 0. Se o movimento fizer a linha (coluna) igual a -1, a linha (coluna) é iniciada em 40. O comando S coloca o seu argumento na posição corrente  (cabeça), sobre-escrevendo o valor que já está ali.. O argumento é uma letra minúscula (a, b, c, ...z) ou número. Este comando é usado como

             S a

             U

             S 2

Estes comandos fazem o seguinte: grava ‘a’ na posição corrente, move a cabeça para cima e grava ‘2’ na nova posição corrente.

            O comando I testa se a cabeça é certo caráter, executando o comando que vem a seguir. Por exemplo, o comando

            I  a  R

testa se a cabeça contém ‘a’. Se sim, move a cabeça para a direita. O comando F repete o comando certo número de vezes. A instrução

            F  5  R       

avança a cabeça para a direita cinco posições.

            O comando W repete um comando enquanto a cabeça for certo valor. Por exemplo,

            W  a  R

move a cabeça para a direita enquanto o conteúdo da cabeça for ‘a’.

            Um comando composto é delimitado por [ e ], que fazem o papel de “begin”-“end” de Pascal e “{“ e “}” de C/C++/Java.Um exemplo de comando composto é

            W 0 [ R S 1]

Enquanto a cabeça contiver 0, move para a direita e grava 1 na posição corrente.

 

            Naturalmente, pode-se compor comandos. Abaixo é mostrado um programa completo em Quad. Qualquer coisa entre // e o fim da linha é comentário (isto não faz parte da linguagem). A variável c é considerada a cabeça de leitura/gravação.

            F  9  R    // for i = 1 to 9 do “move para a direita

            W  1  U  // while c == 1 do “move para cima

            I  0  S  1  // if c == 0 then c = 1

            F  5  L   //  for i = 1 to 5 do “move para a esquerda

            D           // move para baixo

            S  f    // grava f na posição corrente             

 

A gramática de Quad é dada abaixo. Nela, NUMBER é um terminal que representa números de um dígito. LETTER representa uma única letra minúscula. As letras entre aspas representam terminais.

 

 

Program ::=  Command { Command }

Command ::= LeftCommand | RightCommand | UpCommand |

     DownCommand | UpRightCommand | DownLeftCommand |

     PrintCommand | IfCommand | WhileCommand |

     ForCommand | CompositeCommand

LeftCommand ::= “L”

RightCommand ::= “R”

UpCommand ::= “U”

DownCommand ::= “D”

UpRightCommand ::= “O”

DownLeftCommand ::= “N”

PrintCommand ::= “S” Value

IfCommand ::= “I” Value  Command

WhileCommand ::= “W”  Value  Command

ForCommand ::= “F” NUMBER Command

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

Value ::= LETTER | NUMBER

 

 

 

            A geração de código para o exemplo dado acima deve ser:

 

#include <stdio.h>

#include <stdlib.h>

 

#define NumLines 40

#define NumColumns 40

#define MaxNumber 10

 

int main() {

  char m[NumLines][NumColumns];

  int line, column, i;

 

  // para facilitar, preenchemos a matriz inicialmente

  // apenas com números

  for( line = 0; line < NumLines; line++ )

    for( column = 0; column < NumColumns; column++ )

      m[line][column] = ‘0’ + random(MaxNumber);

 

     // F  9  R

  for( i = 0; i < 9; i++ ) {

     column = (column + 1)%NumColumns;

  }

     // W  1  U

  while ( m[line][column] == 1 ) {

     line = (line + 1)%NumLines;

  }

     // I  0  S  1

  if ( m[line][column] == 0 ) {

    m[line][column] = 1;

  }

     // F  5  L

  for (i = 0; i < 5; i++ ) {

    column = (column - 1)%NumColumns;

  }

     // D

  line = (line - 1)%NumLines;

     // S  f

  m[line][column] = ‘f’;

 

 

  // imprime a matriz

  for( line = 0; line < NumLines; line++ ) {

    for( column = 0; column < NumColumns; column++ )

      printf("%d ", m[line][column]);

    puts("");

  }

  getchar();

  return 0;

}

           

 

Observe que não haveria necessidade de criar as constantes NumLines, NumColumns e MaxNumber, que este código não se destina à leitura humana. É altamente recomendável que você coloque as instruções em Quad como comentários no código gerado, embora isto não faça parte dos requerimentos do trabalho.

 

O trabalho consiste em fazer um pequeno compilador para Quad 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. 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:

  • 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 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.