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

Terceiro Trabalho.
Prazo de Entrega: 11 de Junho, 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 gramática dada a seguir, da linguagem NTSA (Não Tão Simples Assim). Esta linguagem suporta procedimentos e funções, declarados com a palavra-chave “proc”, e variáveis globais. O resto da linguagem é praticamente igual à linguagem do trabalho 2.

Variáveis globais e procedimentos/funções compartilham o nível léxico global. O outro nível léxico, local, contém variáveis locais e parâmetros. Dois identificadores do mesmo nível léxico não podem ser iguais. Mas um local pode ter o mesmo nome que o global, tendo precedência sobre este.

A gramática de NTSA é dada abaixo:

Program ::= GlobalVarList ProcList

GlobalVarList ::= [ VarDec { VarDec } ]

ProcList ::= ProcDec { ProcDec }

ProcDec ::= “proc” [ Type ] Id “(“ [ ParamList ] “)”

[ VarDec { VarDec } ] ProcBody

ParamList ::= Type Id {“,” Type Id }

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

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

Command ::= PrintCommand | AssignmentCommand

| WhileCommand | ForCommand | IfCommand

| CompositeCommand | ReturnCommand

| ProcCall

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 ]

ReturnCommand ::= “return” OrExpr “;”

ProcCall ::= Id “(“ [ OrExpr { “,” OrExpr } ] “)”

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 | ProcCall

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

AddOp ::= '+'| '-'

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

Number ::= Digit { Digit }

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

FuncCall ::= Id “(“ [ OrExpr { “,” OrExpr } ] “)”

Algumas observações sobre a gramática/linguagem:

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;

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

6. uma função só pode ser chamada onde se espera uma expressão. Um procedimento só pode ser chamado em uma instrução (fora de uma expressão, como usual);

7. o último procedimento/função do arquivo de entrada deve ser um procedimento sem parâmetros. Pode ter qualquer nome. É a partir deste procedimento que a execução começa;

8. o nome main não pode ser utilizado para nome de procedimentos/funções.

Agora a linguagem possui variáveis globais e procedimentos/funções. Um procedimento pode ser declarado como

proc imprime( integer n )

begin

$$ comandos. Isto é um comentário

end

Uma função deve ter tipo de retorno:

proc integer fatorial(integer n )

begin

if n == 0 then return 1;

else

return n*fatorial(n-1);

end

Usando variáveis locais, esta função poderia ter sido declarada como

proc integer fatorial(integer n )

integer i, p;

begin

p = 1;

for i = 2 to n do

p = p*i;

return p;

end

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.

Naturalmente, o compilador deve fazer a análise semântica, o que engloba todas as conferências feitas no segundo trabalho mais as abaixo.

- um procedimento/função está sendo redeclarado ?

- ao chamar um procedimento/função, o número e tipo dos parâmetros está correto ?

- um procedimento está sendo usado como função ou vice-versa (procedimento como expressão e função como instrução) ?

- alguma variável global está sendo redeclarada ?

- alguma variável global e procedimento/função tem o mesmo nome ?

- a última subrotina é um procedimento sem parâmetros ?

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.

Exemplo 1.

proc printInteger(integer k)

integer i;

begin

for i = 1 to k do

print i;

end

proc boolean test(integer n, integer i)

begin

return n/i == 0 or (n – 1)%i == 0;

end

proc principal()

integer n, i;

boolean ok;

begin

printInteger(getInteger);

n = getInteger;

ok = true;

while i < n do

begin

if test(n, i) then

ok = false;

i = i + 1;

end

if ok then print 1; else print 0;

end

Exemplo 2.

proc integer calcDelta(integer a, integer b, integer c)

begin

return b*b – 4*a*c;

end

proc integer calcSqrt(integer square)

boolean ok;

integer n;

begin

ok = false;

n = 1;

while not ok do

begin

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

else n = n + 1;

end

end

proc principal()

integer a, b, c, delta;

begin

a = getInteger;

b = getInteger;

c = getInteger;

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

delta = calcDelta(a, b, 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)

n = calcSqrt(delta);

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

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

end

end