Operadores de adição e subtração
Tags: compiler, antlr, go, braziliandevs
Published: 2024-03-23 18:06:02

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](https://dev.to/alexgarzao/compilando-o-hello-world-em-pascal-jan), que conseguia compilar e executar o "Hello world!" em [Pascal](https://en.wikipedia.org/wiki/Pascal_(programming_language)) 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](https://dev.to/alexgarzao/compilando-o-hello-world-em-pascal-jan), o POJ (Pascal on the JVM) lê um programa Pascal e gera o [JASM (_Java Assembly_)](https://www.eg.bucknell.edu/~cs360/java-assembler/examples.html) para posteriormente ser transformado em um arquivo [class](https://en.wikipedia.org/wiki/Java_class_file) 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)](https://github.com/roscopeco/jasm) 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](https://github.com/alexgarzao/poj/tree/889bd91606ad8ef00faaccdeec5044e4297b886c/tests). Com isso temos [testes End2End](https://microsoft.github.io/code-with-engineering-playbook/automated-testing/e2e-testing/) 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](https://www.javatpoint.com/compiler-phases).

## 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](https://github.com/antlr/antlr4/blob/master/doc/parser-rules.md#alternative-labels) 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](https://github.com/alexgarzao/poj/blob/889bd91606ad8ef00faaccdeec5044e4297b886c/parser/Pascal.g4) 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](https://github.com/antlr/grammars-v4/blob/master/pascal/pascal.g4). 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](https://www.antlr.org/) é 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](https://github.com/alexgarzao/poj).