Operadores de adição e subtração

Faz mais de um mês desde a última publicação sobre o projeto. Culpa da correria do dia-a-dia :-D

Após a primeira versão, que conseguia compilar e executar o "Hello world!" em Pascal na JVM, fiz alguns avanços neste último mês. Os mais relevantes foram:

• Concatenação de strings
• Soma e subtração de inteiros

Conforme citado em uma publicação anterior, o POJ (Pascal on the JVM) lê um programa Pascal e gera o JASM (Java Assembly) para posteriormente ser transformado em um arquivo class e executado na JVM.

Para exemplificar o que o POJ faz, abaixo temos um exemplo em Pascal que concatena três strings:

program ConcatStrings;
begin
  writeln ('Hello ' + 'world ' + 'again!');
end.

Abaixo temos o JASM gerado pelo POJ:

// Code generated by POJ 0.1
public class concat_three_strings {
  public static main([java/lang/String)V {
    getstatic java/lang/System.out java/io/PrintStream
    ldc "Hello "
    ldc "world "
    invokedynamic makeConcatWithConstants(java/lang/String, java/lang/String)java/lang/String {
      invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants(java/lang/invoke/MethodHandles$Lookup, java/lang/String, java/lang/invoke/MethodType, java/lang/String, [java/lang/Object)java/lang/invoke/CallSite 
      [""] 
    }
    ldc "again!"
    invokedynamic makeConcatWithConstants(java/lang/String, java/lang/String)java/lang/String {
      invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants(java/lang/invoke/MethodHandles$Lookup, java/lang/String, java/lang/invoke/MethodType, java/lang/String, [java/lang/Object)java/lang/invoke/CallSite 
      [""] 
    }
    invokevirtual java/io/PrintStream.println(java/lang/String)V
    return
  }
}

A partir deste assembly utilizamos o JASM (assemblador de Java Assembly) para criar o arquivo class final.

Testes End2End

Para auxiliar no desenvolvimento, além dos testes unitários agora temos uma pasta com exemplos em pascal e a saída esperada em JASM. Com isso temos testes End2End no POJ que validam a entrada (exemplos em Pascal) com a saída esperada (JASM).

Validação de tipos

Outra funcionalidade implementada foi a validação de tipos. Apesar da JVM validar a tipagem dos dados, é extremamente recomendado que o POJ valide o código Pascal para não gerar um arquivo JASM inválido.

Para exemplificar, o código abaixo está sintaticamente correto, mas semanticamente incorreto porque em Pascal não é possível somar strings com inteiros.

program Hello;
begin
  writeln ('Hello ' + 1);
end.

Para realizar esta tipagem o parser agora mantém uma pilha com os tipos de dados que estão sendo empilhados na JVM. Com isso, nas operações de soma e subtração o tipo dos dados são validados durante a análise semântica.

Concatenação de strings, soma e subtração de inteiros

Algumas modificações foram realizadas no parser para reconhecer a expressão "expression additiveoperator expression" (trecho da gramática abaixo).

expression
  : expression op = relationaloperator expression # RelOp
  | expression op = ('*' | '/') expression        # MulDivOp
  | expression op = additiveoperator expression   # AddOp
  | signedFactor                                  # ExpSignedFactor
  ;

Esta expressão é responsável pela derivação tanto da soma bem como da subtração de strings e inteiros.

O "# AddOp" na gramática acima é uma anotação do ANTLR que permite que cada regra da gramática possa ser facilmente identificada durante o parser. Com esta anotação o ANTLR gera um método (ExitAddOp abaixo) que será executado sempre que o parser terminar o reconhecimento da expressão.

func (t *TreeShapeListener) ExitAddOp(ctx *parsing.AddOpContext) {
  // Check pascal types.
  pt1 := t.pst.Pop()
  pt2 := t.pst.Pop()
  if pt1 != pt2 {
    t.jasm.AddOpcode("invalid types")
    return
  }

  // Get operator.
  op := ctx.GetOp().GetText()
  switch {
  case op == "+":
    switch pt1 {
    case String:
      t.GenAddStrings()
    case Integer:
      t.GenAddIntegers()
    default:
      t.jasm.AddOpcode("invalid type in add")
    }
  case op == "-":
    switch pt1 {
    case Integer:
      t.GenSubIntegers()
    default:
      t.jasm.AddOpcode("invalid type in sub")
    }
  }
}

Este método inicia retirando os últimos 2 tipos da pilha e verificando se possuem o mesmo tipo. Após isso é verificado qual o operador (+ ou -) e, baseado no operador e no tipo do dado, executado o método que irá gerar o JASM. Neste ponto o código também indica uma operação inválida (como no caso da subtração de strings, que é uma operação inválida em Pascal).

Como exemplo temos abaixo o método GenAddStrings, responsável por gerar o JASM para concatenar duas string, invocado no trecho acima:

func (t *TreeShapeListener) GenAddStrings() {
t.jasm.StartInvokeDynamic(`makeConcatWithConstants(java/lang/String, java/lang/String)java/lang/String`)
  t.jasm.AddOpcode(`invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants(java/lang/invoke/MethodHandles$Lookup, java/lang/String, java/lang/invoke/MethodType, java/lang/String, [java/lang/Object)java/lang/invoke/CallSite`)
  t.jasm.AddOpcode(`[""]`)
  t.jasm.FinishInvokeDynamic()
  t.pst.Push(String)
}

O jasm (em t.jasm) é um objeto que auxilia na geração do JASM, podendo emitir assinaturas de métodos, classes (do Java Assembly) bem como os opcodes.

Vale observar a última linha do trecho acima: t.pst.Push(String). "pst" (pascal stack type) é a pilha que guarda os tipos dos dados. Neste caso, como foi reconhecida uma concatenação de strings, e foi emitido código para concatená-las, estamos também inserindo o tipo String na pst.

Até este ponto reconhecemos o operador, o tipo do dado, realizamos uma validação de tipos e geramos código para executar a operação. Mas e as strings e os inteiros? Como eles são carregados para a pilha da JVM?

Na gramática os strings e os inteiros de um programa Pascal são considerados "símbolos terminais" e derivam a partir da regra signedFactor existente na regra expression (vide trecho da gramática acima). E o parser, baseado nas regras instrumentadas em Go, sempre que reconhece estes símbolos terminais automaticamente gera o JASM para carregá-los na pilha da JVM.

No trecho abaixo é possível ver que ao terminar o reconhecimento de uma string o método ExitString gera o opcode ldc (load constant) seguido da string a ser carregada na pilha da JVM. O ctx.GetText() é disponibilizado pelo runtime Go do ANTLR e permite obter o valor do símbolo terminal, que no nosso caso é a string.

func (t *TreeShapeListener) ExitString(ctx *parsing.StringContext) {
  str := ctx.GetText()
  t.jasm.AddOpcode("ldc", "\""+str+"\"")
  t.pst.Push(String)
}

A "pegadinha" da precedência de operadores

No site do ANTLR tem a gramática pronta de Pascal. Porém, apesar de reconhecer corretamente os programas em Pascal, esta gramática não lida corretamente com a precedência de operadores. A forma recomendada no próprio site do ANTLR é similar ao exemplo abaixo:

grammar Expr;
prog:   (expr NEWLINE)* ;
expr:   expr ('*'|'/') expr
    |   expr ('+'|'-') expr
    |   INT
    |   '(' expr ')'
    ;
NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

Com isso a derivação do parser não respeitava a precedência de operadores e o POJ gerava um JASM errado.

Por exemplo, para o trecho em Pascal abaixo:

writeln (8-4-2);

O correto seria o POJ gerar o seguinte assembly:

getstatic java/lang/System.out java/io/PrintStream
sipush 8
sipush 4
isub 
sipush 2
isub 
invokevirtual java/io/PrintStream.println(I)V

No exemplo acima atentem para a localização dos opcodes isub.

Basicamente o assembly acima é executado na JVM da seguinte forma:

Instrução	Descrição instrução	Estado pilha após instrução
sipush 8	Empilha o inteiro 8	[ 8 ]
sipush 4	Empilha o inteiro 4	[ 8, 4 ]
isub	Retira os 2 últimos elementos da pilha (8 e 4), subtrai e empilha o resultado (4)	[ 4 ]
sipush 2	Empilha o inteiro 2	[ 4, 2 ]
isub	Retira os 2 últimos elementos da pilha (4 e 2), subtrai e empilha o resultado (2)	[ 2 ]

No final da execução a pilha contém o resultado esperado de 8-4-2: 2.

Porém por não lidar corretamente com a precedência de operadores, a partir da gramática original era gerado o assembly abaixo. Reparem novamente na localização dos opcodes isub:

getstatic java/lang/System.out java/io/PrintStream
sipush 8
sipush 4
sipush 2
isub 
isub 
invokevirtual java/io/PrintStream.println(I)V

E o assembly acima é executado na JVM da seguinte forma:

Instrução	Descrição instrução	Estado pilha após instrução
sipush 8	Empilha o inteiro 8	[ 8 ]
sipush 4	Empilha o inteiro 4	[ 8, 4 ]
sipush 2	Empilha o inteiro 2	[ 8, 4, 2 ]
isub	Retira os 2 últimos elementos da pilha (4 e 2), subtrai e empilha o resultado (2)	[ 8, 2 ]
isub	Retira os 2 últimos elementos da pilha (8 e 2), subtrai e empilha o resultado (6)	[ 6 ]

Com isso o resultado do assembly acima era 6 :-)

O repositório com o código completo do projeto e instruções sobre como criar o executável bem como executar os testes está aqui.