Nesta fase será necessário dotar o analisador sintáctico da fase anterior duma tabela de símbolos. Após este aditamento será possível passar para a geração de código.
O código a ser gerado será escrito na linguagem MA-LEI (Máquina Abstracta da LEI). Esta linguagem descreve as instruções numa pilha duma máquina abstracta. Existem cinco registos:
A chamada de funções e o tratamento de classes são, devido à sua complexidade, tratadas numa secção à parte.
A linguagem LEI é uma linguagem Orientada a Objectos simples. Contém as principais instruções de fluxo de controlo, algumas funções pré-definidas de entrada/saída e estruturas de dados flexíveis.
Um programa em LEI pode ser dividido em 2 partes:
A definição duma classe pode ser definida de duas formas: usando as palavra chave classe e subclasse. Uma declaração duma classe que não é subclasse de nenhuma outra é feita da seguinte forma:
classe nome_classe { ... // elementos da classe }
ao passo que uma classe que seja subclasse doutra é declarada na forma:
subclasse nome_classe { ... uma ou mais classes } { ... // elementos da classe }
Neste segundo caso, as instâncias da subclasse vão poder usar todas as variáveis e funções que compõem as classes das quais esta é subclasse. Assim, a chamada a uma função de uma classe pode ser feita a partir duma instância duma classe ou duma sua subclasse, ou ainda duma subclasse desta, etc...
Como cada classe pode ser subclasse de várias classes pode haver alguns conflitos. No caso de haver mais do que uma função com o mesmo nome no conjunto das classes (na própria classe isso não pode acontecer), só uma será chamada e a ordem de preferência será: a própria classe, as classes da qual esta é subclasse pela respectiva ordem de declaração, subindo em cada caso às classes mais acima. Por exemplo, supondo que existem as classes principais c1 e c2, as subclasses c3 e c4 destas, e uma subclasse c5 das últimas a ordem de procura seria c5, c3, c1, c2, c4, c1, c2 (estas duas últimas pesquisas podem ser evitadas uma vez que são repetidas).
Outra questão tem a ver com a ordem de chamada dos construtores e destrutores das classes. No caso dos destrutores, todas as funções destrutoras de todas as classes envolvidas serão chamadas na mesma ordem de cima: c5, c3, c1, c2, c4, c1, c2. No caso dos construtores, as funções construtoras serão chamada da classe mais alta para a mais baixa: c1, c2, c3, c1, c2, c4, c5.
As variáveis podem ser simples ou vectores. No caso das variáveis simples elas podem ser do tipo "inteiro", "real" ou duma classe declarada. Na declaração podem-se declarar várias variáveis separadas por vírgula. Por exemplo, supondo que existe uma classe declarada chamada "cl", podemos ter declarações da forma:
inteiro x,y real z cl cx,cy
Os vectores podem ser dos mesmos tipos, sendo antecedidos da palavra "vector", e tendo a seguir ao nome da variável a sua dimensão entre parêntesis rectos. Por exemplo:
vector inteiro vx[5], vy[10] vector real vz[100] vector cl vcx[30], vcy[20]
As declarações de funções são antecedidas da palavra "funcao" seguida do tipo de retorno e nome da função, seguida dos tipos dos argumentos entre parêntesis separados por vírgulas (pode não haver argumentos). Por exemplo:
funcao inteiro f1(inteiro,vector real) funcao inteiro f2( )
De referir ainda que as variáveis e funções que compõem as classes são declaradas seguindo estas regras. A função construtora da classe é antecedida da palavra "construtor" enquanto a função destrutora é antecedida da palavra "destrutor", existindo na classe apenas uma de cada.
A segunda parte é a definição das funções que fazem parte das classes e das que foram declaradas. A função que é inicialmente chamada é a função "principal" que deverá existir obrigatoriamente.
As funções começam por ter o tipo de retorno seguido do nome da função, seguido dos argumentos entre parêntesis separados por vírgulas, seguido do corpo da função entre chavetas. Os argumento são compostos pelo tipo e nome da variável (seguem as regras das declarações das variáveis). No caso das funções que fazem parte das classes estas devem ser antecedidas do nome da classe e dum ponto. Por exemplo:
inteiro f1 (inteiro x, vector real v[10]) { ... // corpo da função } inteiro cl.g ( ) { ... // corpo da função }
O corpo da função é composto por duas partes:
A declaração de variáveis locais segue a regras das variáveis globais. As instruções podem ser:
As atribuições são da forma Variável <- Expressão. Por exemplo:
y <- x + 10 v[i] <- x - 10
Existe uma restrição importante relativamente à atribuição: se a variável do lado esquerdo da atribuição for inteiro então nenhum dos elementos do lado direito pode ser um número real; se a variável do lado esquerdo for um real então não haverá qualquer restrição, sendo todos os elementos da expressão que não sejam reais convertidos para real.
As chamadas a funções podem ser feitas sem ser no âmbito duma atribuição. Neste caso o valor de retorno é ignorado. Também aqui tem que ser tomado algum cuidado relativamente aos tipos dos argumentos. Se o tipo dum argumento for inteiro então a expressão passada nesse argumento também deverá ser um inteiro. Se o tipo for real então não haverá problemas, uma vez que o valor será convertido automaticamente. Alguns exemplos:
f(x-1,y+1) g()
As funções pré-definidas são funções elementares de entrada/saída. As funções "ler" e "escrever" servem, como o nome indica, para ler da entrada e escrever para a saída. Ambas funcionam de forma semelhante. Os argumentos podem ser nomes de variáveis ou então números inteiros desde que imediatamente seguidos do nome duma variável. Este último caso é usado para vectores, indicando o número de elementos do vector a ler ou escrever. As funções "ler_caracter" e "escrever_caracter" servem para ler ou escrever um carácter, respectivamente. A variável de onde é lida ou para onde é escrita vai conter o respectivo código ASCII. Exemplos:
ler(x,y,10,v) escrever(x,y,10,v) c <- ler_caracter() escrever_caracter(c)
A diferença entre as duas primeiras funções e as duas últimas tem a ver com a forma como são interpretados os valores inteiros. Por exemplo:
x <- 'A' escrever(x) escrever_caracter(x)
vai resultar na seguinte saída:
65A
Da mesma forma as instruções:
ler(x) x <- ler_caracter()
vão interpretar o que for introduzido de forma diferente. Se introduzirmos o número 1, no primeiro caso a variável x ficará com o valor 1, enquanto no segundo caso ficará com o código ASCII referente ao '1' que é o 49. No caso da função "ler", serão ignorados todos os caracteres até encontrar um padrão que corresponda a um número real ou inteiro.
Relativamente às instruções de fluxo de controlo existem algumas das mais habituais na maioria das linguagens. Estas instruções são da seguinte forma:
// instrução se-senao se(condição){ ... // instruções executadas se a condição for verdadeira } senao{ ... // instruções executadas se a condição for falsa } // instrução enquanto enquanto(condição){ ... // instruções executadas enquanto a condição for verdadeira } // instrução fazer-enquanto fazer{ ... // instruções executadas enquanto a condição for verdadeira ... // é sempre executada a primeira vez }enquanto(condição) // instrução para para(atribuição1 ate condição passo atribuição2){ ... // atribuição1 é realizada antes do ciclo ... // as instruções serão executadas se a condição for verdadeira ... // no fim do ciclo atribuição2 é realizada }
De notar que a instrução "para" é equivalente à sequência:
atribuição1 enquanto(condição){ ... // instruções iguais às do ciclo "para" atribuição2 }
A instrução "quebra" obriga à saída imediata do ciclo exterior àquele em que se encontra. A instrução "continua" obriga a testar novamente a condição relativa ao ciclo exterior àquele em que se encontra.
Uma instrução na linguagem MA-LEI é da seguinte forma:
label: INSTR arg %comentário
onde:
label: |
(opcional) corresponde a um local para onde poderá ser feito um salto |
INSTR |
é o nome duma instrução com o máximo de cinco caracteres |
arg |
(opcional) é o argumento da instrução |
%comentário |
(opcional) é uma parte de comentários que é ignorado até ao fim da linha |
GDEF n |
Reserva espaço de n bytes para variável global. |
GDEFI n? |
Reserva espaço para n variáveis globais inteiras; se o argumento n não existir será considerado n=1. |
GDEFR n? |
Reserva espaço para n variáveis globais reais; se o argumento n não existir será considerado n=1. |
LDEF n |
Reserva espaço de n bytes para variável local. |
LDEFI n? |
Reserva espaço para n variáveis locais inteiras; se o argumento n não existir será considerado n=1. |
LDEFR n? |
Reserva espaço para n variáveis locais reais; se o argumento n não existir será considerado n=1. |
Os inteiros e reais serão guardados com o mesmo número de bytes e serão indexados pela ordem de declaração. As variáveis globais serão visíveis durante todo o programa, enquanto as variáveis locais só serão visíveis durante a execução da função onde foram declaradas. Por exemplo, as declarações:
inteiro x,y real z vector inteiro v[10]
serão traduzidas para o seguinte código:
GDEFI 2 GDEFR GDEFI 10
Os índices das variáveis serão:
0 x 1 y 2 z 3 v[0] 4 v[1] ... 12 v[9]
PUSHI num_int |
Coloca no topo da pilha um número inteiro. |
PUSHR num_real |
Coloca no topo da pilha um número real. |
GPSHI end_rel |
Coloca no topo da pilha o valor de uma variável global inteira. |
GPSHR end_rel |
Coloca no topo da pilha o valor de uma variável global real. |
LPSHI end_rel |
Coloca no topo da pilha o valor de uma variável local inteira. |
LPSHR end_rel |
Coloca no topo da pilha o valor de uma variável local real. |
GSTRI end_rel |
Guarda o valor no topo da pilha numa variável global inteira. |
GSTRR end_rel |
Guarda o valor no topo da pilha numa variável global real. |
LSTRI end_rel |
Guarda o valor no topo da pilha numa variável local inteira. |
LSTRR end_rel |
Guarda o valor no topo da pilha numa variável local real. |
POP n? |
Retira n elementos a partir do topo da pilha; se o argumento n não existir será considerado n=1. |
Os valores das variáveis só podem ser usados se forem colocados na pilha. Para actualizar estes valores também se irá buscar o valor no topo da pilha. Os endereços das variáveis serão dados pelos respectivos índices. Assim a instrução:
x <- y
será traduzida para:
GPSHI 1 GSTRI 0
ADDI |
Adiciona os dois inteiros no topo da pilha. |
ADDR |
Adiciona os dois reais no topo da pilha. |
SUBI |
Subtrai ao segundo elemento inteiro a partir do topo da pilha o valor no topo da pilha. |
SUBR |
Subtrai ao segundo elemento real a partir do topo da pilha o valor no topo da pilha. |
MULTI |
Multiplica os dois inteiros no topo da pilha. |
MULTR |
Multiplica os dois reais no topo da pilha. |
DIVI |
Divide o segundo elemento inteiro a partir do topo da pilha pelo valor no topo da pilha. |
DIVR |
Divide o segundo elemento real a partir do topo da pilha pelo valor no topo da pilha. |
MOD |
Resto da divisão inteira. |
NEG |
Simétrico do valor no topo da pilha. |
Todas as operações são realizadas sobre a pilha. Sempre que se pretenda realizar uma operação binária terá que se colocar os dois elementos no topo da pilha e depois realizar a operação. A ordem das operações terá a ver com a precedência dos operadores. Por exemplo:
x <- x + 3 * y
será traduzida para:
GPSHI 0 PUSHI 3 GPSHI 1 MULTI ADDI GSTRI 0
Para realizar uma operação unária terá que se colocar o elemento no topo da pilha e realizar a operação. Por exemplo:
x <- -x + 2
será traduzida para:
GPSHI 0 NEG PUSHI 2 ADDI GSTRI 0
BAND |
e sobre bits dos dois inteiros no topo da pilha. |
BOR |
ou sobre bits dos dois inteiros no topo da pilha. |
BXOR |
ou exclusivo sobre bits dos dois inteiros no topo da pilha. |
BNOT |
não sobre bits do inteiro no topo da pilha. |
SHFTL |
Deslocamento à esquerda do inteiro no topo da pilha. |
SHFTR |
Deslocamento à direita do inteiro no topo da pilha. |
Estas operações são semelhantes às aritméticas. Por exemplo:
x<-x esq 2
é traduzida para:
GPSHI 0 PUSHI 2 SHFTL GSTRI 0
LAND |
e lógico dos dois inteiros no topo da pilha. |
LOR |
ou lógico dos dois inteiros no topo da pilha. |
LXOR |
ou exclusivo lógico dos dois inteiros no topo da pilha. |
LNOT |
não lógico do inteiro no topo da pilha. |
As operações lógicas actuam, como as restantes operações, sobre os valores no topo da pilha. O zero corresponde ao valor lógico "Falso" enquanto qualquer valor diferente de zero corresponde ao valor lógico "Verdadeiro".
GE |
Testa se o segundo elemento a partir do topo da pilha é maior ou igual do que o elemento no topo da pilha. |
GT |
Testa se o segundo elemento a partir do topo da pilha é maior do que o elemento no topo da pilha. |
LE |
Testa se o segundo elemento a partir do topo da pilha é menor ou igual do que o elemento no topo da pilha. |
LT |
Testa se o segundo elemento a partir do topo da pilha é menor do que o elemento no topo da pilha. |
EQ |
Testa se os dois elementos no topo da pilha são iguais. |
NE |
Testa se os dois elementos no topo da pilha são diferentes. |
As operações de comparação têm os mesmos valores lógicos associados que as operações lógicas.
JUMP label |
Salta para a posição associada a "label". |
JUMPC label |
Salta para a posição associada a "label" se o valor no topo da pilha for diferente de zero. |
CALL label |
Chama a função associada a "label". |
RET n |
Retorno de uma função com n argumentos. |
ITOR |
Converte o inteiro no topo da pilha para real. |
HALT |
Paragem da máquina. |
As instruções "JUMP" e "JUMPC" correpondem, respectivamente, a saltos incondicionais e condicionais. Enquanto a primeira salta para a posição associada ao argumento, a segunda salta apenas se o valor no topo da pilha for diferente de zero. Esta segunda é bastante útil para ciclos se-senao, fazer-enquanto, enquanto e para. Por exemplo:
se(x>=y){ y<-x } senao{ x<-y }
poderá ser traduzido para:
GPSHI 0 GPSHI 1 GE JUMPC l1 GPSHI 1 GSTRI 0 JUMP l2 l1: GPSHI 0 GSTRI 1 l2: ... % resto do programa
Outro exemplo:
fazer{ x<-x-1 }enquanto(x>0)
pode ser traduzido para:
l1: GPSHI 0 PUSHI 1 SUBI GSTRI 0 GPSHI 0 PUSHI 0 GT JUMPC l1 ... % resto do programa
Ainda outro exemplo:
enquanto(x!=y){ x<-x /r y }
e a respectiva tradução:
l1: GPSHI 0 GPSHI 1 NE NOT JUMPC l2 GPSHI 0 GPSHI 1 MOD GSTRI 0 JUMP l1 l2: ... % resto do programa
O último exemplo (supomos que i é um inteiro local com índice 0):
para(i<-0 ate i<10 passo i<-i+1){ x<-x+i }
e a última tradução:
PUSHI 0 LSTRI 0 l1: LPSHI 0 PUSHI 10 LT NOT JUMPC l2 GPSHI 0 LPSHI 0 ADDI GSTRI 0 LPSHI 0 PUSHI 1 ADDI LSTRI 0 JUMP l1 l2: ... % resto do programa
As instruções "CALL" e "RET" servem, respectivamente, para chamar uma função e retornar da mesma. Mais à frente descreve-se a forma como as funções serão chamadas.
GETC |
Lê um carácter da entrada para o topo da pilha. |
PUTC |
Escreve o carácter no topo da pilha na saída. |
GETI |
Lê um inteiro da entrada para o topo da pilha. |
PUTI |
Escreve o inteiro no topo da pilha na saída. |
GETR |
Lê um real da entrada para o topo da pilha. |
PUTR |
Escreve o real no topo da pilha na saída. |
Estas instruções servem para as funções básicas de entrada e saída. Estão directamente relacionadas com as funções pré-definidas. A função ler funciona da seguinte forma:
Assim, a instrução:
ler(x,y,z,10,v)
será traduzido para:
GETI GSTRI 0 GETI GSTRI 1 GETR GSTRR 2 GETI GSTRI 3 ... % v[1] a v[8] GETI GSTRI 12
A função escrever funciona de forma igual relativamente aos argumento, escrevendo no ecrã. Por exemplo:
escrever(x,y,z,10,v)
será traduzido para:
GPSHI 0 PUTI GPSHI 1 PUTI GPSHR 2 PUTR GPSHI 3 PUTI ... % v[1] a v[8] GPSHI 12 PUTI
A chamada de funções é feita usando o método de stack frames. Pode-se traduzir este nome para "enquadramentos" ou "ambientes" da pilha. O processo de execução das funções é feita em quatro fases:
Vamos ver como estas quatro fases são feitas, com o auxílio da seguinte função:
inteiro min(inteiro x, inteiro y) { se(x<y){ _ <- x } senao{ _ <- y } }
e da seguinte chamada:
x<-min(x+5,y-5)
1. A primeira coisa a fazer será guardar espaço para o valor de retorno. Como este espaço é temporário não serão usadas instruções de reserva de espaço. O valor de retorno será o que fica no topo da pilha aquando do retorno da função. Assim, faz-se a colocação dum valor qualquer no topo da pilha:
PUSHI 0
Os argumentos são calculados antes da chamada à função:
GPSHI 0 PUSHI 5 ADDI GPSHI 1 PUSHI 5 SUBI
Desta forma, ficarão no topo da pilha um espaço para o retorno da função e os valores calculados dos argumentos.
2. Na segunda fase é feita a chamada à função:
CALL _min
Com esta chamada as seguintes acções serão tomas automaticamente:
3. A função é executada normalmente. Inicialmente podem ser declaradas variáveis locais (o que não sucede neste exemplo), seguindo-se as restantes instruções. As variáveis locais são referenciadas normalmente começando por 0 até ao número total de variáveis declaradas. Os valores dos argumentos e o valor de retorno serão valores negativos referenciados localmente a partir de FP. Assim, no exemplo, teremos os seguintes índices:
-1 y -2 x -3 valor de retorno
A função "min" poderá ser traduzida da seguinte forma:
_min: LPSHI -2 LPSHI -1 LT JUMPC l1 LPSHI -1 LSTRI -3 JUMP l2 l1: LPSHI -2 LSTRI -3 l2: RET 2
4. A declaração "RET 2" faz automaticamente as seguintes acções:
Após estas acções fica no topo da pilha apenas o valor retornado pela função.
Sempre que uma classe é declarada a primeira coisa a ser feita é a declaração de variáveis seguida da chamada do construtor, tanto da classe como das classes das quais esta depende hierarquicamente. Na chamada do construtor e no caso de na hierarquia haver repetição do nome da variável, as regras são as que já foram referidas.
As variáveis da classe serão referenciadas global ou localmente, conforme a instanciação da variável seja global ou local, como qualquer variável. Quando é chamada uma função duma classe, associada a uma instanciação, as variáveis da classe são copiadas para o topo da pilha, sendo depois a chamada da função feita da mesma forma que as outras funções. A referência às variáveis da classe é feita usando números negativos abaixo da referência do valor de retorno. Após o retorno da função as variáveis da classe são copiadas para o local onde foram definidas.
Uma variável duma classe pode ser global ou local. Se for global, será visível todo o programa, sendo chamado o destrutor antes de terminar o programa. Se for local, será visível durante a execução da função na qual foi declarada, sendo chamado o destrutor imediatamente antes da saída da função.
Consideremos o seguinte exemplo:
classe c1 { inteiro x,y funcao inteiro f(inteiro) construtor funcao inteiro fc() destrutor funcao inteiro fd() } ... g() { c1 c inteiro i i<-5 _ <- c.f(i) }
As variáveis serão referenciadas localmente na função g com os seguintes índices:
0 c.x 1 c.y 2 i
A tradução será:
LDEFI 2 LPSHI 0 LPSHI 1 PUSHI 0 % valor de retorno CALL _c.fc POP % ignora valor de retorno LSTRI 1 LSTRI 0 LDEFI 1 PUSHI 5 LSTRI 2 LPSHI 0 LPSHI 1 PUSHI 0 % valor de retorno LPSHI 2 CALL _c.f LSTRI -1 LSTRI 1 LSTRI 0 LPSHI 0 LPSHI 1 PUSHI 0 % valor de retorno CALL _c.fd POP % ignora valor de retorno LSTRI 1 LSTRI 0 RET 0
Analisador Léxico e Sintáctico com geração de código em MA-LEI.
Ultima alteração: segunda-feira, 20 de Novembro de 2000 às 19:00