Construção de Compiladores
Primeiro Semestre de 2005
Prof.
José de Oliveira Guimarães
Primeiro Trabalho.
Prazo de Entrega: 8 de Abril para ambas as turmas
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 30x30 elementos. 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
Caso o movimento faça a linha (coluna) maior do que 30, a linha (coluna) é iniciada em 0. Se o movimento fizer a linha (coluna) igual a -1, a linha (coluna) é inicada em 30. O comando P coloca o seu argumento na posição corrente
(cabeça). O argumento é um número inteiro entre 0 e 9. Este comando é usado como
P 0
U
P 7
Estes comandos fazem o seguinte: grava 0
na posição corrente, move a cabeça para cima e grava 7 na nova posição corrente.
O comando I testa se a cabeça é certo número, executando o comando que vem a seguir. Por exemplo, o comando
I 0
R
testa se a cabeça contém 0. Se sim, move a cabeça para a direita. O comando F repete o comando certo número de vezes. O comando
F 5
R
avança a cabeça para a direita cinco posições.
O comando W repete um comando enquanto a cabeça contiver certo número. Por exemplo,
W 1
R
move a cabeça para a direita enquanto o conteúdo da cabeça for 1.
Naturalmente, pode-se compor comandos. No exemplo abaixo, 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
P 1 // if c == 0 then c = 1
F 5
L // for i = 1 to 5 do “move para a esquerda”
D // move para baixo
P 7
// grava 7 na posição corrente
A gramática de Quad é dada abaixo. Nela, NUMBER é um terminal que representa números de um dígito. As letras entre aspas representam terminais.
Program
::= Command {
Command }
Command
::= LeftCommand | RightCommand | UpCommand |
DownCommand |
PrintCommand | IfCommand | WhileCommand |
ForCommand
LeftCommand ::= “L”
RightCommand ::= “R”
UpCommand ::= “U”
DownCommand ::= “D”
PrintCommand ::= “P”
NUMBER
IfCommand ::= “I”
NUMBER Command
WhileCommand ::=
“W” NUMBER Command
ForCommand ::= “F”
NUMBER Command
Terá um ponto extra na nota quem acrescentar à gramática um comando composto:
Command ::= ...
| CompositeCommand
CompositeCommand
::= “[” Command { Command } “]”
Assim podemos ter comandos tais como
W
0 [ R P 1]
Enquanto a cabeça contiver 0,
move para a direita e grava 1 na posição corrente.
A
geração de código para o exemplo dado acima deve ser:
#include
<stdio.h>
#include
<stdlib.h>
#define NumLines 30
#define NumColumns 30
#define MaxNumber 10
int main() {
int
m[NumLines][NumColumns];
int line, column, i;
for( line = 0; line
< NumLines; line++ )
for( column = 0;
column < NumColumns; column++ )
m[line][column]
= 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
P 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;
// P 7
m[line][column] = 7;
// 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.