MAB 471 - Compiladores I

Introdução

Gossip é uma linguagem orientada a objetos no estilo de Smalltalk (o nome é uma brincadeira com o nome dessa outra linguagem), mas com uma sintaxe parecida com a de Java/JavaScript. Apesar de ser poderosa o bastante para se programar nela, sua simplicidade a torna mais indicada para fins pedagógicos.

Léxico

Palavras reservadas

Operadores (precedência maior para menor)

Identificadores

Qualquer sequência de letras, dígitos e o caractere _ (underscore), começando por letra ou _ (underscore).

Numerais

Decimais sem sinal e parte científica opcional com ou sem sinal (Exs: 2, 3, 4.5, 2.29E-5, 2.32, 5E2, 10.2E+4). Isso implica que números como -5 e +3 são dois tokens!

Literais

Cadeias de caracteres literais são delimitadas através do uso de aspas duplas, não podem ter quebras de linha, e podem ter as seguintes seqüências de escape no estilo de C: '\n' (quebra de linha), '\r' (retorno de carro), '\t' (tabulação horizontal), '\\' (barra invertida) e '\"' (aspas duplas). Qualquer outro uso de uma barra invertida dentro de uma cadeia não é permitido.

Comentários

Comentários começam com /* e terminam com */ (não podem ser aninhados).

Outros itens

Sintaxe

Um parser recursivo pode ser construído facilmente para essa gramática ela, mas requer fatoração (ou uso de truques) nas regras lvalue e methodcall, além, é claro, da eliminação de recursão usual na regra exp (ou uso de um parser recursivo de precedência de operadores para essa parte da gramática).

gossip ::= {class-decl}
class-decl ::= CLASS ID '{' {member-decl} '}'
member-decl ::= var-decl | method-decl
var-decl ::= VAR ID ';'
method-decl ::= ID '(' [param-list] ')' '{' {cmd} '}'
param-list ::= ID {',' ID}
cmd ::= '{' {cmd} '}' | IF '(' exp ')' cmd [ELSE cmd]
        | WHILE '(' exp ')' cmd | BREAK ';'
        | RETURN exp ';' | lvalue '=' exp ';'
        | methodcall ';' | VAR ID ';'
        | VAR ID '=' exp ';' | ';'
lvalue ::= ID | simple '[' exp ']'
simple ::= atom {suffix}
atom ::= THIS | NULL | FALSE | TRUE | NUMBER | STRING | ID
         | '(' exp ')' 
suffix ::= '.' ID '(' [exp-list] ')' | '[' exp ']'
methodcall ::= simple '.' ID '(' [exp-list] ')'
exp ::=  simple | NEW ID '(' [exp-list] ')' | exp binop exp | unop exp
exp-list ::= exp {',' exp}
unop ::= '-' | '!'
binop ::= '+' | '-' | '*' | '/' | '&&' | '||' | '<' | '<='
          | '==' 

Semântica Estática

Gossip é uma linguagem com escopo léxico, ou escopo de bloco; o corpo da classe conta como um bloco para efeitos de escopo, mas as variáveis nesse caso são variáveis de instância do objeto em questão. Variáveis que não foram declaradas em nenhum escopo são assumidas como globais, e são visíveis em qualquer método. Como exemplo de aplicação dessas regras, veja o programa abaixo:

class Foo {
  var x;
  def bar(y) {
    var z = y;
    if(x > 0) {      /* campo x */
      var y = 2;
      out.print(y);  /* y local do if */
    } else {
      out.print(y);  /* parâmetro y */
    }
    /* out é uma global */
  }
}

O compilador Gossip deve fazer as seguintes checagens estáticas: não se pode ter duas variáveis com o mesmo nome no mesmo nível de escopo; não se pode declarar dois métodos com o mesmo nome em uma mesma classe; não se pode ter duas classes com o mesmo nome; não se pode usar o operador new em uma classe não existente (mas a classe pode ser declarada em qualquer ponto do programa); apenas uma classe no programa pode ter um método chamado main. O analisador deve poder receber uma lista de classes "pré-definidas".

O espaço de nomes de variáveis e de classes é diferente, ou seja, pode-se ter uma classe chamada Foo e uma variável chamada Foo que não há conflito (lembre que as classes só são usadas no operador new).

Gossip na Lua Virtual Machine

Cada método de cada classe de um programa Gossip deve ser compilado para uma função Lua com o nome NomeClasse_NomeMétodo. O registrador 0 do método é sempre this, e os argumentos recebidos pelo método ficam nos registradores seguintes (primeiro argumento no registrador 1, segundo no registrador 2, e assim por diante).

A função main do programa assembler deve registrar todas as classes e métodos, e rodar o programa indicando qual classe tem o método main. Existem funções auxiliares (acessadas via GETGLOBAL) para isso. A função __GOSSIP_CLASS recebe o nome de uma classe e a registra. A função __GOSSIP_METHOD recebe o nome de uma classe, o nome de um método, e o método em si (criado usando CLOSURE) e o registra. A função __GOSSIP_RUN recebe o nome de uma classe (que deve ter um método main), instancia um objeto dessa classe e executa seu método main.

Por exemplo, seja o programa a seguir:

class Foo {
  def foo() { return "foo"; }
}

class Bar {
  def main() {
    var foo = new Foo();
    out.print(foo.foo());
  }
}

Ele deve ser compilado para o seguinte programa assembler (corpos dos métodos foram omitidos):

function Foo_foo:
  ; corpo de foo da classe Foo
  RETURN R0 1

function Bar_main:
  ; corpo de main da classe Bar
  RETURN R0 1

function main:
  ; Registro da classe Foo
  GETGLOBAL R0 __GOSSIP_CLASS
  LOADK R1 Foo
  CALL R0 2 1
  ; Registro do método foo da classe Foo
  GETGLOBAL R0 __GOSSIP_METHOD
  LOADK R1 Foo
  LOADK R2 foo
  CLOSURE R3 Foo_foo 1
  CALL R0 4 1
  ; Registro da classe Bar
  GETGLOBAL R0 __GOSSIP_CLASS
  LOADK R1 Bar
  CALL R0 2 1
  ; Registro do método main da classe Bar
  GETGLOBAL R0 __GOSSIP_METHOD
  LOADK R1 Bar
  LOADK R2 main
  CLOSURE R3 Bar_main 1
  CALL R0 4 1
  ; Execução do programa
  GETGLOBAL R0 __GOSSIP_RUN
  LOADK R1 Bar
  CALL R0 2 1
  RETURN R0 1

Lembre-se de passar o número correto de parâmetros para CLOSURE, e que this conta como um parâmetro. Declarações de variáveis de classes não geram nenhum código. Declarações de variáveis locais var id; devem gerar um LOADNIL no registrador correspondente.

O corpo dos método sempre deve terminar com uma instrução RETURN R0 1, com o resto dos comandos compilados em sequência antes dele. A geração de código para a maior parte dos comandos é semelhante à de TINY.

methodcall : simple '.' ID '(' exp_list ')'

A geração de uma chamada de método usada como um comando, dada pela produção acima, segue o seguinte esquema (você deve reservar Rx, R(x+1), etc. antes de gerar o código das subexpressões):

  <código para simple em Rx>
  SELF Rx Rx <nome do método>
  <código para primeira exp de exp_list em R(x+2)>
  <código para segunda exp de exp_list em R(x+3)>
  ...
  CALL Rx <tamanho de exp_list + 2> 1

A geração de uma atribuição lvalue '=' exp quando lvalue é um ID é depende do tipo de escopo da variável. Se ela for global, o código gerado deve ser o seguinte (você deve reservar o temporário Rx):

  <código para exp em Rx>
  SETGLOBAL Rx <nome da var>

  <código para exp em Rx>
  SETTABLE R0 <nome da var> Rx

Finalmente, uma variável local é como em TINY:

  <código para exp no registrador da var>

Quando lvalue é uma indexação simple '[' exp ']' a atribuição segue o seguinte esquema (você deve reservar os temporários Rx, Ry e Rz antes de gerar o código das subexpressões):

  <código para simple em Rx>
  <código para exp da indexação em Ry>
  <código para exp da atribuição em Rz>
  SETTABLE Rx Ry Rz

A geração de um atom para um alvo Rx depende do átomo específico:

  ; NULL
  LOADNIL Rx Rx
  ; THIS
  MOVE Rx R0
  ; TRUE
  LOADBOOL Rx true
  ; FALSE
  LOADBOOL Rx false
  ; NUMBER
  LOADK Rx <número>
  ; STRING
  LOADK Rx <string>
  ; ID - variável global
  GETGLOBAL Rx <nome da var>
  ; ID - variável do objeto
  GETTABLE Rx R0 <nome da var> 
  ; ID - variável local
  MOVE Rx R<reg. da var>
  ; '(' exp ')'
  <código para gerar exp em Rx>

A geração de um simple composto por outro simple e um suffix depende do tipo do sufixo. Se for um sufixo de chamada de método e o alvo é Rx o código tem o seguinte esquema (você deve reservar Ry, R(y+1), etc. antes de gerar o código das subexpressões):

  <código para lado esquerdo em Ry>
  SELF Ry Ry <nome do método>
  <código para primeira exp de exp_list em R(y+2)>
  <código para segunda exp de exp_list em R(y+3)>
  ...
  CALL Ry <tamanho de exp_list + 2> 2
  MOVE Rx Ry

Se for um sufixo de indexação e o alvo for Rx o código tem o seguinte esquema (você deve reservar Ry e Rz antes de gerar o código das subexpressões):

  <código para lado esquerdo em Ry>
  <código para exp em Rz>
  GETTABLE Rx Ry Rz

A geração da maioria das expressões binárias e das expressões unárias é semelhante à de TINY (ao contrário de TINY, você pode usar a instrução DIV para divisão).

O código para o operador new usa o seguinte esquema, novamente assumindo que Rx é o alvo (você deve reservar Ry, R(y+1), etc. antes de gerar o código das subexpressões):

  GETGLOBAL Ry __GOSSIP_NEW
  LOADK R(y+1) <nome da classe>
  <código para primeira exp de exp_list em R(y+2)>
  <código para segunda exp de exp_list em R(y+3)>
  ...
  CALL Ry <tamanho de exp_list + 2> 2
  MOVE Rx Ry