Ensino sequencial, é tão difícil assim?

Quando estudei linguagens formais com o professor Marcelo Pelágio fiquei muito entusiasmado e ancioso pra colocar logo a mão na massa e utilizar ferramentas construídas com base nos problemas já conhecidos na contrução de compiladores (lex, yacc). A maior vontade era ver um autômato daquele virar código fonte de compilador. A maioria da turma aprendeu a matéria muito bem.

Existe algo chocante na troca de professor. Seria muito interessante se houvesse uma continuação. Pra que vai servir aquela matéria agora? Você se esforça, pergunta, tenta compreender, enfim, pra que? Você podia estar muito bem testando seu compilador, na linguagem que você inventou, ao invés de ficar lendo este artigo aqui agora ou pior ainda, estar aprendendo a programar na aula de compiladores.

Nada contra aprender programar, pelo contrário. Só acredito que a aula de compiladores não seja o lugar ideal. Na verdade penso que deviamos estar implementando um compilador de linguagem, usando autômatos, follow, first, e tudo mais. Porém, esta questão é polêmica e vou deixar de lado.

Bom, vou fazer uso daquele conteúdo neste artigo, mais precisamente da parte de recursão à esquerda, embora de uma forma pouco usual.

O último exercício pedido na disciplina de Compiladores foi o reconhecimento de uma expressão algébrica. Minha dúvida tentava fazer o professor perceber que aquela regra de produção está com recursão a esquerda, e por isso está tão difícil perceber como validar a sintaxe.

O “livro do dragão” explica muito bem isso. Bater o olho e perceber o que é reconhecido pela regra de produção fica bem mais fácil se eliminarmos a recursão. Lembra-se que o professor Pelágio dizia que não é possível implementar uma regra com recursão à esquerda?

Veja a regra com recursão:

  <soma>  -> <soma> <sinal> <termo> | <termo>
  <sinal> -> + | -
  <termo> -> 0|1|2|3|4|5|6|7|8|9

Agora sem recursão (alfa e beta, se lembra?):

  <soma>  -> <termo> <soma2>
  <soma2> -> <sinal> <termo> <soma2> | E
  <sinal> -> + | -
  <termo> -> 0|1|2|3|4|5|6|7|8|9

Ou mais simples ainda:

  <soma>  -> <termo> <soma> | + <termo> <soma> | - <termo> <soma> | E
  <termo> -> 0|1|2|3|4|5|6|7|8|9

Derivando isso, observamos que sempre teremos as seguintes combinações:

  <termo>
  <termo> + <termo>
  <termo> + <termo> - <termo> ...
  <termo> - <termo>
  <termo> - <termo> - <termo> + <termo> ...

Ou seja, “um só termo” ou “um termo e sequências de sinal seguido de termo”.

Desta forma fica mais fácil desenvolver o algorítimo.

Vamos desenvolver um protótipo. Para cada item da regra de produção defina uma função. Crie também uma função chamada “erro” que quando executada mostra a mensagem “erro de sintaxe” e sai do programa. Veja abaixo os exemplos. Observe os comentários antes de cada função.

  void erro() {
    printf("Erro de sintaxe!n");
    exit(1);
  }
	
  /* Sai do programa se a palavra recebida como argumento não for
   * o sinal de adição ou o sinal de subtração
   */
  void sinal(char *palavra) {
    if (*palavra != '+' && *palavra != '-')
      erro();
  }
  /* Sai do programa se a palavra recebida como argumento não for
   * um número
   */
  void termo(char *palavra) {
    se (!isdigit(*palavra))
      erro();
  }

  /* A regra de produção em si. "Um termo"
   * ou "um termo e sequencias de sinal e termo"
   *
   * A função proxPalavra retorna a próxima palavra do 
   * arquivo que foi lido no inicio do programa, está em anexo no final.
   *
   */
  void soma(char *textoDoArquivo) {
    char *palavra;
    palavra = (char*)malloc(sizeof(char)256);

    proxPalavra(palavra, &textoDoArquivo);
    termo(palavra);
      while(1) { /* infinitamente (a recursão da regra de produção é esta) */
      proxPalavra(palavra, &textoDoArquivo);
      sinal();
      proxPalavra(palavra, &textoDoArquivo);
      termo();
    }
  }

Depois que você abrir o arquivo e carregar seu conteúdo, chame a função soma passando a variável com o conteúdo do arquivo.

Em resumo, não mudou nada. Derivar a regra de produção é a forma mais fácil de saber por onde começar, como era em Linguagens Formais.

Baixe o arquivo com a função proxPalavra()

Tenho também a função que lê todo o arquivo e armazena em uma variável. Se estiver interessado é só me pedir por e-mail.

Anúncios