Avaliação • Capítulo 7

Árvores


Agora podemos ler a entrada, temos ela estruturada internamente, mas ainda não conseguimos avaliá-la (isto é, interpretá-la). Neste capítulo adicionamos o código que avalia esta estrutura e executa de verdade as computações codificadas nela.

Essa estrutura interna que vimos impressa pelo programa no capítulo anterior é chamada Árvore sintática abstrata (Abstract Syntax Tree), e representa a estrutura do programa baseada na entrada digitada pelo usuário. Nas folhas desta árvore estão números e operadores - os dados a serem realmente processados. Nos galhos estão as regras usadas para produzir esta parte da árvore - a informação em como atravessá-la (e.g. em que ordem visitar os galhos e folhas?) e avaliá-la.

tree

Árvore de Natal Abstrata • Uma variação sazonal

Antes de resolver exatamente como vamos fazer essa travessia, vamos ver exatamente como esta estrutura é definida internamente. Se olharmos dentro do mpc.h podemos dar uma olhada na definição de mpc_ast_t, que é a estrutura de dados que obtemos da análise sintática.

typedef struct mpc_ast_t {
  char* tag;
  char* contents;
  mpc_state_t state;
  int children_num;
  struct mpc_ast_t** children;
} mpc_ast_t;

Esta estrutura tem alguns campos que podemos acessar. Vamos dar uma olhada neles, um por um.

O primeiro campo é tag (etiqueta). Quando imprimimos a árvore, a tag era a informação que precedia o conteúdo do nó. Era uma string contendo uma lista de todas as regras usadas para analisar àquele item. Por exemplo, expr|number|regex.

Esse campo tag vai ser importante pois permite que vejamos quais regras de parsing foram usadas para criar o nó.

O segundo campo é contents. Este conterá o conteúdo de verdade do nó, como '*', '(' ou '5'. Você vai notar que para galhos ele é vazio, mas para folhas podemos usá-los para encontrar o operador ou número a usar.

O próximo campo é state. Este contém informação sobre o estado em que o parser estava quando encontrou esse nó, como o número da linha e coluna. Não faremos uso dele neste programa.

Finalmente, vemos dois campos que irão nos ajudar a atravessar a árvore. Eles são children_num e children. O primeiro campo nos diz quantos filhos um nó tem, e o segundo é um conjunto desses filhos.

O tipo do campo children é mpc_ast_t**, que é um apontador duple. Isso não é tão assustador quanto parece, e será explicado em maior detalhe em capítulos posteriores. Por enquanto, você pode pensar nele como uma lista dos nós desta árvore.

Nós podemos acessar um nó filho acessando este campo usando a notação de array. Fazemos isso escrevendo o nome do campo children e adicionando um sufixo com colchetes contendo o índice do filho a ser acessado. Por exemplo, para acessar o primeiro filho do nó, podemos usar children[0]. Note como C conta os índices do array a partir de 0.

Como o tipo mpc_ast_t* é um apontador para uma estrutura, há uma sintaxe um pouco diferente para acessar os seus campos. Precisamos usar uma seta -> em vez de um ponto .. Há um motivo fundamental para essa troca de operadores, então por enquanto simplesmente lembre-se que o acesso de campo de tipos apontadores usa uma flecha.

/* Carrega AST do output */
mpc_ast_t* a = r.output;
printf("Tag: %s\n", a->tag);
printf("Contents: %s\n", a->contents);
printf("Number of children: %i\n", a->children_num);

/* Pega primeiro filho */
mpc_ast_t* c0 = a->children[0];
printf("First Child Tag: %s\n", c0->tag);
printf("First Child Contents: %s\n", c0->contents);
printf("First Child Number of children: %i\n",
  c0->children_num);

Recursão


Há uma coisa estranha sobre esta estrutura de árvore. Ela se referencia à si mesma. Cada um dos seus filhos são eles próprios árvores novamente, e os filhos destes filhos também são árvores novamente. Da mesma forma que nossas linguagens e regras de reescrita, dados nesta estrutura contém subestruturas repetidas que lembram seus parentes.

recursion

Recursão • Perigosa em caso de fogo.

Esse padrão de subestruturas repetidas pode continuar infinitamente. Claramente se queremos uma função que funcione com todas as árvores possíveis nós não podemos apenas olhar alguns nós abaixo, nós temos que defini-la para funcionar com qualquer profundidade.

Felizmente podemos fazer isto, explorando a natureza de como essas subestruturas repetem e usando uma técnica chamada recursão.

De maneira simples, uma função recursiva é uma que chama a si mesma como parte do seu cálculo.

Soa estranho para uma função ser definida em termos dela mesma. Mas considere que funções podem ter diferentes saídas quando fornecidas entradas diferentes. Se provemos entradas mudadas ou substituídas para uma chamada recursiva da mesma função, e provemos uma maneira para esta função não chamar a si mesma em certas condições, podemos ter mais confiança de que essa função recursiva está fazendo algo útil.

Como um exemplo, vamos escrever uma função recursiva que irá contar o número de nós em nossa estrutura árvore.

Para começar, vamos definir como a função deve agir no caso mais simples - se a árvore não tem nenhum filho. Neste caso, sabemos que o resultado é simplesmente um. Agora podemos definir o caso mais complexo - se a árvore tem um ou mais filhos. Neste caso, o resultado será um (para o próprio nó), mais a soma do número de nós de todos os seus filhos.

Mas como descobrimos o número de nós em todos os seus filhos? Bem, podemos usar a função que estamos no processo de definir! Yeah, Recursão!

Em poderíamos escrever algo assim:

int number_of_nodes(mpc_ast_t* t) {
  if (t->children_num == 0) { return 1; }
  if (t->children_num >= 1) {
    int total = 1;
    for (int i = 0; i < t->children_num; i++) {
      total = total + number_of_nodes(t->children[i]);
    }
    return total;
  }
  return 0;
}

Funções recursivas são esquisitas porque requerem um certo salto de fé. Primeiro, temos que assumir que temos uma função que faz uma coisa corretamente, e então temos que prosseguir e usar essa função, para escrever a função inicial que assumimos que tínhamos!

Como a maioria das coisas, funções recursivas quase sempre acabam seguindo um padrão parecido. Primeiro um caso base é definido. Este é o caso que termina a recursão, como t->children_num == 0 no exemplo anterior. Em seguida, é definido o caso recursivo, que quebra a computação em partes menores e chama a si mesmo recursivamente para computar as outras partes, e por fim combiná-las.

Funções recursivas precisa de uma certa concentração, então faça uma pausa agora e entenda-as antes de continuar para outros capítulos porque faremos bastante uso delas no resto do livro. Se você está um pouco inseguro, pode tentar alguma das metas bônus para este capítulo.

Avaliação


Para avaliar a árvore sintática vamos escrever uma função recursiva. Mas antes de começar, vamos tentar ver quais observações podemos fazer sobre a estrutura da árvore que recebemos como entrada. Tente imprimir algumas expressões usando seu programa do capítulo anterior. O que você percebe?

lispy> * 10 (+ 1 51)
>
  regex
  operator|char:1:1 '*'
  expr|number|regex:1:3 '10'
  expr|>
    char:1:6 '('
    operator|char:1:7 '+'
    expr|number|regex:1:9 '1'
    expr|number|regex:1:11 '51'
    char:1:13 ')'
  regex

Uma observação é que se um nó tem uma tag/etiqueta number ele é sempre um número, não tem filhos, e podemos simplesmente convertê-lo para um inteiro. Isso funcionará como um caso base na nossa recursão.

Se um nó está etiquetado com expr, e não number, precisamos olhar para o segundo filho ( o primeiro filho é sempre '(') e ver qual é o operador. Então precisamos aplicar este operador para a avaliação dos filhos restantes, excluindo o último filho que é sempre ')'. Esse é nosso caso recursivo. Isto também precisa ser feito para o nó raiz.

Quando avaliamos nossa árvore, assim como quando contamos os nós, precisaremos acumular o resultado. Para representar este resultado usaremos o tipo C long, que significa um longo inteiro long integer.

Para detectar a etiqueta de um nó, ou para obter o número de um nó, vamos precisar usar os campos tag e contents. Estes são campos string, então teremos que aprender algumas funções de string antes.

atoiConverte um char* para um long.
strcmpRecebe duas strings (char*) como entrada e caso forem iguais, devolve 0.
strstrRecebe duas strings (char*) e devolve um apontador para a localização da segunda dentro da primeira, ou 0 caso o segundo não é uma sub-string do primeiro.

Podemos usar strcmp para checar qual operador usar, e strstr para checar se uma tag contém alguma sub-string. Juntas, nossa função de avaliação recursiva fica assim:

long eval(mpc_ast_t* t) {
  
  /* Caso etiquetado como numero, retorna diretamente. */ 
  if (strstr(t->tag, "number")) {
    return atoi(t->contents);
  }
  
  /* O operador eh sempre o segundo filho. */
  char* op = t->children[1]->contents;
  
  /* Armazenamos o terceiro filho em `x` */
  long x = eval(t->children[2]);
  
  /* Itera sobre os filhos restantes, e combina resultado. */
  int i = 3;
  while (strstr(t->children[i]->tag, "expr")) {
    x = eval_op(x, op, eval(t->children[i]));
    i++;
  }
  
  return x;  
}

Podemos definir a função eval_op como segue. Ela recebe um número, uma string operador, e um outro número. Ela testa qual operador é passado, e executa a operação correspondente para as entradas.

/* Usa string operador para ver qual operacao executar */
long eval_op(long x, char* op, long y) {
  if (strcmp(op, "+") == 0) { return x + y; }
  if (strcmp(op, "-") == 0) { return x - y; }
  if (strcmp(op, "*") == 0) { return x * y; }
  if (strcmp(op, "/") == 0) { return x / y; }
  return 0;
}

Impressão


Em lugar de imprimir a árvore, agora queremos imprimir o resultado da avaliação. Por isso precisamos passar a árvore para nossa função eval, e imprimir o resultado que obtemos usando printf e o especificador %li que é usado para o tipo long.

Também precisamos lembrar de deletar a árvore de saída quando terminamos de avaliá-la.

long result = eval(r.output);
printf("%li\n", result);
mpc_ast_delete(r.output);

Se tudo isso deu certo, devemos poder fazer alguma matemática básica na nossa nova linguagem de programação!

Lispy Version 0.0.0.0.3
Press Ctrl+c to Exit

lispy> + 5 6
11
lispy> - (* 10 10) (+ 1 1 1)
97

Referência


#include "mpc.h"

#ifdef _WIN32

static char buffer[2048];

char* readline(char* prompt) {
  fputs(prompt, stdout);
  fgets(buffer, 2048, stdin);
  char* cpy = malloc(strlen(buffer)+1);
  strcpy(cpy, buffer);
  cpy[strlen(cpy)-1] = '\0';
  return cpy;
}

void add_history(char* unused) {}

#else
#include <editline/readline.h>
#include <editline/history.h>
#endif

/* Use operator string to see which operation to perform */
long eval_op(long x, char* op, long y) {
  if (strcmp(op, "+") == 0) { return x + y; }
  if (strcmp(op, "-") == 0) { return x - y; }
  if (strcmp(op, "*") == 0) { return x * y; }
  if (strcmp(op, "/") == 0) { return x / y; }
  return 0;
}

long eval(mpc_ast_t* t) {
  
  /* If tagged as number return it directly. */ 
  if (strstr(t->tag, "number")) {
    return atoi(t->contents);
  }
  
  /* The operator is always second child. */
  char* op = t->children[1]->contents;
  
  /* We store the third child in `x` */
  long x = eval(t->children[2]);
  
  /* Iterate the remaining children and combining. */
  int i = 3;
  while (strstr(t->children[i]->tag, "expr")) {
    x = eval_op(x, op, eval(t->children[i]));
    i++;
  }
  
  return x;  
}

int main(int argc, char** argv) {
  
  mpc_parser_t* Number = mpc_new("number");
  mpc_parser_t* Operator = mpc_new("operator");
  mpc_parser_t* Expr = mpc_new("expr");
  mpc_parser_t* Lispy = mpc_new("lispy");
  
  mpca_lang(MPCA_LANG_DEFAULT,
    "                                                     \
      number   : /-?[0-9]+/ ;                             \
      operator : '+' | '-' | '*' | '/' ;                  \
      expr     : <number> | '(' <operator> <expr>+ ')' ;  \
      lispy    : /^/ <operator> <expr>+ /$/ ;             \
    ",
    Number, Operator, Expr, Lispy);
  
  puts("Lispy Version 0.0.0.0.3");
  puts("Press Ctrl+c to Exit\n");
  
  while (1) {
  
    char* input = readline("lispy> ");
    add_history(input);
    
    mpc_result_t r;
    if (mpc_parse("<stdin>", input, Lispy, &r)) {
      
      long result = eval(r.output);
      printf("%li\n", result);
      mpc_ast_delete(r.output);
      
    } else {    
      mpc_err_print(r.error);
      mpc_err_delete(r.error);
    }
    
    free(input);
    
  }
  
  mpc_cleanup(4, Number, Operator, Expr, Lispy);
  
  return 0;
}

Metas bônus


  • › Escreva uma função recursiva para calcular o número de folhas de uma árvore.
  • › Escreva uma função recursiva para calcular o número de galhos de uma árvore.
  • › Escreva uma função recursiva para calcular o maior número de filhos saindo dum galho duma árvore.
  • › Como usar strstr para ver se um nó foi etiquetado como expr?
  • › Como usar strcmp para ver se um nó possuía o conteúdo '(' ou ')'?
  • › Adicione o operador %, que devolve o resto da divisão. Por exemplo % 10 6 é 4.
  • › Adicione o operador ^, que eleva um número ao outro. Por exemplo ^ 4 2 é 16.
  • › Adicione a função min, que devolve o menor número. Por exemplo min 1 5 3 é 1.
  • › Adicione a função max, que devolve o maior número. Por exemplo max 1 5 3 é 5.
  • › Mude o operador menos - para que quando receba um argumento ele o transforme em negativo.

Navigation

‹ Análise Sintática

• Conteúdo •

Tratamento de Erros ›