Construção de Compiladores

Primeiro Semestre de 2007

Prof. José de Oliveira Guimarães

Primeiro Trabalho.

Prazo de Entrega: 16 de Abril, segunda-feira

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 MSI (Mais Simples Impossível). 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. Uma atribuição é feita como

a = 5

que atribui 5 à variável “a”. O comando de impressão é P e

P 1

imprime 1 no vídeo. O comando “R v” lê um número do teclado (que pode ter mais de um dígito) e o coloca na variável v. O comando “if” é feito com a letra I, toma um valor (variável ou número) e um comando como parâmetros e executa o comando se o valor é diferente de zero. Por exemplo,

I a P 1

imprime 1 se a variável “a” é diferente de zero. Um comando composto em MSI é delimitado por [ e ]. Por exemplo,

I a [ a = 1 P a ]

inicia “a” com 1 e imprime “a” se “a” é diferente de zero. O comando N incrementa o valor de uma variável de 1. Não se preocupe com conferências semânticas, como conferir se N é utilizado com um número. O comando D decrementa o valor de uma variável de 1:

N a

D b

O valor de “a” é incrementado e o de “b”, decrementado de 1.

O comando “W v C” executa o comando C enquanto o valor da variável “v” é diferente de zero.

Um exemplo de programa em MSI é

R a

i = 1

W a [ P a P i D a N i ]

R b

I b [ P 0 P 0 P 0 P b]

A gramática de MSI é dada abaixo.

Program ::=  Command { Command }

Command ::= AssignCommand | ReadCommand | IncCommand |

DecCommand |PrintCommand | IfCommand |

WhileCommand | CompositeCommand

AssignCommand ::= VARIABLE “=” Value

PrintCommand ::= “P” Value

ReadCommand ::= “R” VARIABLE

IncCommand ::= “N” VARIABLE

DecCommand ::= “D” VARIABLE

IfCommand ::= “I” Value Command

WhileCommand ::= “W” Value 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.

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

• não faça nenhuma conferência semântica. Assuma que o programa esteja correto semanticamente;
• 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, como “Número esperado” ou “Comando inexistente”;
• siga as recomendações do “Guia de Correção de Trabalhos” que está na página do curso;
• todos os trabalhos deverão ser feitos em Java.