Construção de Compiladores e Construção de Compiladores 1
Primeiro Semestre de 2008.
Prof. José de Oliveira Guimarães.

Segundo Trabalho.
Prazo de Entrega: 28 de Maio, quarta-feira, até às 12 h.

Entregue este trabalho com a folha de capa disponível na página da disciplina.

Siga as observações sobre correção de trabalhos disponíveis neste site.

Faça um compilador para a seguinte gramática:

Program ::= [ VarDec { VarDec } ] CompositeCommand

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

Command ::= PrintCommand | AssignmentCommand

| WhileCommand | ForCommand | IfCommand

| CompositeCommand

VarDec ::= Type Id { “,” Id } “;”

Type ::= “integer” | “boolean”

AssignmentCommand ::= Id “=” OrExpr “;”

PrintCommand ::= “print” OrExpr “;”

WhileCommand ::= “while” OrExpr “do” Command

ForCommand ::= “for” Id “=” OrExpr “to” OrExpr “do” Command

IfCommand ::= “if” OrExpr “then” Command

[ “else” Command ]

OrExpr ::= AndExpr [ "or" AndExpr ]

AndExpr ::= RelExpr [ "and" RelExpr ]

RelExpr ::= AddExpr [ RelOp AddExpr ]

AddExpr ::= MultExpr { AddOp MultExpr }

MultExpr ::= SimpleExpr { MultOp SimpleExpr }

SimpleExpr ::= Number | "true" | "false" |

| '(' OrExpr ')' | "not" SimpleExpr | AddOp SimpleExpr

| Id | getInteger

RelOp ::= '<' | '<=' | '>' | '>='| '==' | '<>'

AddOp ::= '+'| '-'

MultOp ::= '*' | '/' | '%'

Number ::= Digit { Digit }

Digit ::= '0'| '1' | ... | '9'

Algumas observações sobre a gramática:

1. { e } representam repetição de zero ou mais vezes;

2. qualquer item entre [ e ] é opcional;

3. Number representa constantes inteiras positivas entre 0 e 32767.

4. identificadores devem ser compostos por qualquer quantidade de letras, números e sublinhado (_), começando por letra ou sublinhado;

1. qualquer coisa depois de $$ até o final da linha é considerado comentário.

Você pode pegar o analisador sintático das expressões já pronto (e que necessita de correções). Todas as regras de expressões, começando com OrExpr, foram tomadas do compilador 10. Contudo, fizemos algumas modificações em relação a este compilador: não há chamada de função em SimpleExpr, não há caracteres literais nesta gramática e existe a função getInteger. Você pode copiar toda a análise sintática e a ASA para expressões deste compilador. Falta fazer a análise semântica.

Algumas observações sobre a linguagem:

1. variáveis booleanas podem conter true ou false;

2. variáveis minúsculas e maiúsculas são consideradas diferentes. Todas as palavras-chave são minúsculas;

3. o escopo de uma variável é do ponto de declaração ao final do programa;

4. a variável do comando “for i = expr1 to expr2 do ” inicia-se com expr1 e é incrementada de 1 a cada passo até expr2. A variável e as expressões devem ser inteiras;

5. função getInteger retorna um inteiro lido do teclado. Esta função, em C, é
int getInteger() {
char s[512];
int n;
gets(s);
sscanf(s, “%d”, &n);
return n;
}

O compilador deve construir a ASA e gerar código a partir dela, em C. A geração de código deve ser feita para um arquivo com o mesmo nome que a entrada, mas com extensão “.c”. Você pode (deve !) utilizar a classe Main do compilador 9. Ela já faz a entrada e saída para arquivos. A leitura da entrada deve ser feita de um arquivo.

Um programa na linguagem descrita acima poderia ser

integer n, i;

boolean ok;

begin

n = getInteger;

for i = 1 to n do

print i;

n = getInteger;

ok = true;

while i < n do

begin

if n/i == 0 or (n – 1)%i == 0 then

ok = false;

i = i + 1;

end

if ok then print 1; else print 0;

end

Naturalmente, o compilador deve fazer a análise semântica. Deve ser conferido:

- se uma variável está sendo redeclarada;

- se uma variável utilizada em algum lugar foi declarada;

- se, em uma atribuição, a variável da esquerda é do mesmo tipo da expressão da direita;

- se o operador (+, -, ou, etc) é compatível com os operandos: operadores aritméticos com inteiros e operadores booleanos (and, or, not) com valores booleanos. O menos e mais unário só se aplicam a inteiros;

- se os tipos da variáveis e expressões de um comando “for” são todos inteiros;

- se o tipo da expressão do “if” e “while” é bool;

- se leia e escreva escrevem e lêem inteiros.

Veja como são feitas estas conferências nos compiladores 9 e 10.

Observações:

• entregue a folha de capa disponível na página de trabalhos. É 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” e a linha em que ocorreu o erro;
• 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.

Você deve entregar, impressos:

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

Exemplo 1.

integer n, i;

boolean ok;

begin

n = getInteger;

for i = 1 to n do

print i;

n = getInteger;

ok = true;

i = 2;

while i < n do

begin

if n/i == 0 or (n – 1)%i == 0 then

ok = false;

i = i + 1;

end

if ok then print 1; else print 0;

end

Exemplo 2.

integer a, b, c, delta;

begin

a = getInteger;

b = getInteger;

c = getInteger;

$$ assume que delta seja um quadrado perfeito ou < 0

delta = b*b – 4*a*c;

if delta < 0 then print -1;

else

begin

if delta == 0 then print 0;

else

print 1;

$$ delta = n*n, logo, n = sqrt(delta)

ok = false;

n = 1;

while not ok do

begin

if n*n == delta then ok = true;

else n = n + 1;

end

print (-b + n)/(2*a);

print (-b - n)/(2*a);

end

end