Construção de Compiladores.
Primeiro Semestre
de 2006.
Prof. José de Oliveira Guimarães.
Segundo Trabalho.
Prazo de Entrega:
29 de Maio, segunda-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 ::= “program” Id CompositeCommand
CompositeCommand ::= “begin” Command {
Command } “end”
Command ::= “read” Id
| “write” OrExpr { “,” OrExpr }
| WhileCommand | IfCommand | AssignmentCommand
| CompositeCommand | VarDec
VarDec ::= Type Id
Type ::= “int” | “bool”
AssignmentCommand ::= Id “=” OrExpr
WhileCommand ::= “while” “(“ OrExpr
“)” Command
IfCommand ::= “if” “(“ OrExpr “)” 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
RelOp ::= '<' | '<=' | '>' |
'>='| '==' | '<>'
AddOp ::= '+'| '-'
MultOp ::= '*' | '/' | '%'
Number ::= Digit { Digit }
Digit ::= '0'| '1' | ... | '9'
Qualquer
coisa depois
de // até o final
da linha é considerado comentário.
Você pode pegar o analisador léxico e parte do sintático (as expressões) já prontos(e que necessitam de correções
― não foram testados). 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 e não
há caracteres literais
nesta gramática. Você pode copiar
toda a análise
sintática e a ASA
para expressões
deste compilador. Falta fazer a análise semântica.
Assuma que o escopo de uma variável
é do ponto de declaração ao “}” que está no mesmo nível léxico da declaração.
Um novo nível léxico é criado nos comandos do if (parte do then), else, while e composto. Veja os exemplos a), b) e
c)
a)
program
t1
int
n
...
//
o escopo de n é todo o programa
end
b)
program
t2
int
n
if
( n > 0 )
int k
// o escopo de k é apenas esta linha
write
n
end
c)
program
t2
int
n
if
n > 0
begin
int k
read(k)
n = k + 1
end // o escopo de k é até aqui
end
Assuma que um programa nesta
linguagem pode ter no máximo 10 níveis léxicos
diferentes.
Um
programa na linguagem
descrita acima poderia
ser
program
Exemplo
int
n
read
n
int
i
i
= 1
write
i, i*i, i + i
i
= 2
ok
= true
while
( i < n )
begin
if ( n/i == 0 or (n – 1)%i == 0 )
ok = false
i = i + 1
end
if
( ok ) write 1 else write 0
end
Algumas observações:
1. {
e } representam repetição de zero ou mais vezes;
2. qualquer item entre [ e ] é opcional;
3. Number
representa constantes inteiras
positivas. Variáveis booleanas podem conter true ou false;
4. identificadores
devem ser compostos
por qualquer
quantidade de letras
e números, começando por letra;
5. números podem ter qualquer número
de dígitos, mas
devem estar entre
0 e 32767;
6. 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. Você
pode (deve !) utilizar a classe
Main do compilador 9. Ela
já faz a entrada
e saída para arquivos;
7. a
leitura da entrada
deve ser feita de um arquivo;
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 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. Note que o
identificador que se segue à palavra chave ``program” não tem nenhuma utilidade
no programa. Uma atribuição nesta linguagem é considerada uma instrução.
O trabalho pode ser em grupo de até duas pessoas.