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, já 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, 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.