Tutoriais - Compiladores
Tutoriais
Compiladores

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial11.exercicio01;

/**
 * Interface responsavel pelas constantes utilizadas na fase de analise
 */
public enum Symbol
{
  /**
   * Delimitador de nova linha
   */
  LF (10),

  /**
   * Delimitador de fim de texto
   */
  ETX (3),

  /**
   * Operador de atribuicao (=)
   */
  ASSIGNMENT (11),

  /**
   * Operador aritmetico de adicao (+)
   */
  ADD (21),

  /**
   * Operador aritmetico de subtracao (-)
   */
  SUBTRACT (22),

  /**
   * Operador aritmetico de multiplicacao (*)
   */
  MULTIPLY (23),

  /**
   * Operador aritmetico de divisao inteira (/)
   */
  DIVIDE (24),

  /**
   * Operador aritmetico de resto da divisao inteira (%)
   */
  MODULO (25),

  /**
   * Operador relacional igual a (==)
   */
  EQ (31),

  /**
   * Operador relacional diferente de (!=)
   */
  NE (32),

  /**
   * Operador relacional maior que (>)
   */
  GT (33),

  /**
   * Operador relacional menor que (<)
   */
  LT (34),

  /**
   * Operador relacional maior ou igual a (>=)
   */
  GE (35),

  /**
   * Operador relacional menor ou igual a (<=)
   */
  LE (36),

  /**
   * Identificador
   */
  VARIABLE (41),

  /**
   * Constante numerica inteira
   */
  INTEGER (51),

  /**
   * Palavra reservada rem
   */
  REM (61),

  /**
   * Palavra reservada input
   */
  INPUT (62),

  /**
   * Palavra reservada let
   */
  LET (63),

  /**
   * Palavra reservada print
   */
  PRINT (64),

  /**
   * Palavra reservada goto
   */
  GOTO (65),

  /**
   * Palavra reservada if
   */
  IF (66),

  /**
   * Palavra reservada end
   */
  END (67),

  /**
   * Token nao reconhecido
   */
  ERROR (99);

  /**
   * Identificador do simbolo
   */
  private final int uid;

  /**
   * Inicializar o simbolo
   *
   * @param uid identificador do simbolo
   */
  private Symbol(final int uid)
  {
    this.uid = uid;
  }

  /**
   * Retornar o identificador do simbolo
   *
   * @return identificador do simbolo
   */
  public int getUid()
  {
    return uid;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

/**
 * Definicao dos tipos/classes do token
 */
public enum TokenType
{
  ATR("ATR"), // Operador de atribuicao '='
  ADD("ADD"), // Operador aritmetico de adicao '+'
  SUB("SUB"), // Operador aritmetico de subtracao '-'
  MUL("MUL"), // Operador aritmetico de multiplicacao '*'
  DIV("DIV"), // Operador aritmetico de divisao inteira '/'
  INT("INT"), // Operando numerico inteiro
  VAR("VAR"), // Operando variavel
  LPT("LPT"), // Delimitador abre parentese '('
  RPT("RPT"), // Delimitador fecha parentese ')'
  ETX("ETX"), // Delimitador fim de texto
  ERR("ERR"); // Token nao reconhecido

  /**
   * Nome do tipo/classe do token
   */
  private String name;

  /**
   * Inicializar o tipo/classe do token
   *
   * @param name nome do tipo/classe do token
   */
  private TokenType(String name)
  {
    this.name = name;
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    return name;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

import java.io.Serializable;
import java.text.DecimalFormat;

/**
 * Representacao de um token
 */
public class Token implements Serializable
{
  /**
   * Identificador de serializacao da classe
   */
  private static final long serialVersionUID = 1L;

  /**
   * Tipo/classe do token
   */
  private TokenType type;

  /**
   * Lexema do token no codigo-fonte
   */
  private StringBuilder lexeme;

  /**
   * Posicao do token no codigo-fonte
   */
  private int position;

  /**
   * Construtor para inicializar o token
   *
   * @param character caractere lido no codigo-fonte
   * @param type tipo/classe do token
   * @param position posicao do token no codigo-fonte
   */
  public Token(char character, TokenType type, int position)
  {
    lexeme = new StringBuilder().append(character);

    this.type = type;

    this.position = position;
  }

  /**
   * Adicionar um caractere ao lexema do token
   *
   * @param character caractere lido no codigo-fonte
   * @param type tipo/classe do token
   */
  public void append(char character, TokenType type)
  {
    lexeme.append(character);

    this.type = type;
  }

  /**
   * Retornar o tipo/classe do token
   *
   * @return tipo/classe do token
   */
  public TokenType getType()
  {
    return type;
  }

  /**
   * Retornar o lexema do token no codigo-fonte
   *
   * @return lexema do token no codigo-fonte
   */
  public String getLexeme()
  {
    return lexeme.toString();
  }

  /**
   * Retornar a posicao do token no codigo-fonte
   *
   * @return posicao do token no codigo-fonte
   */
  public int getPosition()
  {
    return position;
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    StringBuilder out = new StringBuilder();

    out.append("[");
    out.append(new DecimalFormat("000").format(position));
    out.append(", ");
    out.append(type);
    out.append(", ");

    if(type == TokenType.VAR)
    {
      out.append(lexeme.toString().toUpperCase());
      out.append("    ");
    }
    else if(type == TokenType.INT)
    {
      out.append(new DecimalFormat("+0000;-0000")
        .format(Integer.parseInt(lexeme.toString())));
    }
    else
    {
      out.append("     ");
    }

    out.append(")] // ");
    out.append(lexeme.toString());

    return out.toString();
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

import java.util.LinkedList;
import java.util.List;

/**
 * Tokens identificados na analise lexica
 */
public class TokenList
{
  /**
   * Tokens identificados na analise lexica
   */
  private List<Token> tokens;

  /**
   * Construtor para inicializar os tokens identificados na analise lexica
   */
  public TokenList()
  {
    tokens = new LinkedList<Token>();
  }

  /**
   * Adicionar o token identificado na analise lexica
   *
   * @param token token identificado na analise lexica
   */
  public void add(Token token)
  {
    tokens.add(token);
  }

  /**
   * Retornar o arranjo contendo os tokens identificados na analise lexica
   *
   * @return arranjo contendo os tokens identificados na analise lexica
   */
  public Token[] toArray()
  {
    return tokens.toArray(new Token[0]);
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    StringBuilder out = new StringBuilder();

    for(Token token : tokens)
    {
      out.append(token).append("\n");
    }

    return out.toString();
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

import java.text.DecimalFormat;

/**
 * Analisador lexico baseado num automato finito deterministico
 */
public class LexicalAnalysis
{
  /**
   * Codigo-fonte
   */
  private String source;

  /**
   * Tokens identificados na analise lexica
   */
  private TokenList tokens;

  /**
   * Posicao no codigo-fonte
   */
  private int position;

  /**
   * Token em reconhecimento
   */
  private Token token;

  /**
   * Codigo-fonte correto
   */
  private boolean correct;

  /**
   * Inicializar o analisador lexico
   *
   * @param tokens tokens identificados na analise lexica
   */
  public LexicalAnalysis(TokenList tokens)
  {
    position = 0;

    this.tokens = tokens;

    correct = true;
  }

  /**
   * Realizar a analise lexica do codigo-fonte
   *
   * @param source codigo-fonte de entrada
   */
  public void parser(String source)
  {
    this.source = source.toLowerCase().trim();

    while(this.source != null)
    {
      q0();
    }
  }

  /**
   * Retornar se o codigo-fonte esta correto
   *
   * @return codigo-fonte correto ou nao
   */
  public boolean isCorrect()
  {
    return correct;
  }

  /**
   * Retornar o proximo caracter do codigo-fonte para analise
   *
   * @return proximo caracter do codigo-fonte para analise
   */
  private char next()
  {
    if(position < source.length())
    {
      return source.charAt(position++);
    }

    return 0;
  }

  /**
   * Identificador o token
   */
  private void identifyToken()
  {
    if(TokenType.ERR != token.getType())
    {
      tokens.add(token);
    }
    else
    {
      correct = false;

      System.out.print(new DecimalFormat("000")
        .format(token.getPosition()));

      System.out.print(" Lexical analysis error: not recognized symbol '");

      if(TokenType.ETX != token.getType())
      {
        System.out.print(token.getLexeme());
      }
      else
      {
        System.out.print(" ");
      }

      System.out.println("'");
    }
  }

  /**
   * Estado inicial do automato finito deterministico
   */
  private void q0()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : break;
      case '=' : token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : q10();
                 break;
      default  : token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * operador de atribuicao '='
   */
  private void q1()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * operador aritmetico de adicao '+'
   */
  private void q2()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * operador aritmetico de subtracao '-'
   */
  private void q3()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * operador aritmetico de multiplicacao '*'
   */
  private void q4()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * operador aritmetico de divisao inteira '/'
   */
  private void q5()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * operando numerico inteiro
   */
  private void q6()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : token.append(caracter, TokenType.INT);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * operando variavel
   */
  private void q7()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * delimitador abre parentese '('
   */
  private void q8()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * delimitador fecha parentese ')'
   */
  private void q9()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q10();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q11();
    }
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * delimitador fim de texto
   */
  private void q10()
  {
    token = new Token('\0', TokenType.ETX, position + 1);

    identifyToken();

    source = null;
  }

  /**
   * Estado responsavel pelo reconhecimento do
   * token nao reconhecido
   */
  private void q11()
  {
    char caracter = next();

    switch(caracter)
    {
      case ' ' : identifyToken();
                 break;
      case '=' : identifyToken();
                 token = new Token(caracter, TokenType.ATR, position);
                 q1();
                 break;
      case '+' : identifyToken();
                 token = new Token(caracter, TokenType.ADD, position);
                 q2();
                 break;
      case '-' : identifyToken();
                 token = new Token(caracter, TokenType.SUB, position);
                 q3();
                 break;
      case '*' : identifyToken();
                 token = new Token(caracter, TokenType.MUL, position);
                 q4();
                 break;
      case '/' : identifyToken();
                 token = new Token(caracter, TokenType.DIV, position);
                 q5();
                 break;
      case '0' :
      case '1' :
      case '2' :
      case '3' :
      case '4' :
      case '5' :
      case '6' :
      case '7' :
      case '8' :
      case '9' : identifyToken();
                 token = new Token(caracter, TokenType.INT, position);
                 q6();
                 break;
      case 'a' :
      case 'b' :
      case 'c' :
      case 'd' :
      case 'e' :
      case 'f' :
      case 'g' :
      case 'h' :
      case 'i' :
      case 'j' :
      case 'k' :
      case 'l' :
      case 'm' :
      case 'n' :
      case 'o' :
      case 'p' :
      case 'q' :
      case 'r' :
      case 's' :
      case 't' :
      case 'u' :
      case 'v' :
      case 'w' :
      case 'x' :
      case 'y' :
      case 'z' : identifyToken();
                 token = new Token(caracter, TokenType.VAR, position);
                 q7();
                 break;
      case '(' : identifyToken();
                 token = new Token(caracter, TokenType.LPT, position);
                 q8();
                 break;
      case ')' : identifyToken();
                 token = new Token(caracter, TokenType.RPT, position);
                 q9();
                 break;
      case 0   : identifyToken();
                 q8();
                 break;
      default  : identifyToken();
                 token = new Token(caracter, TokenType.ERR, position);
                 q9();
    }
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

/**
 * Definicao dos simbolos da gramatica livre do contexto
 */
public enum SyntacticSymbol
{
  ATR("ATR"), // terminal - operador de atribuicao '='
  ADD("ADD"), // terminal - operador aritmetico de adicao '+'
  SUB("SUB"), // terminal - operador aritmetico de subtracao '-'
  MUL("MUL"), // terminal - operador aritmetico de multiplicacao '*'
  DIV("DIV"), // terminal - operador aritmetico de divisao inteira '/'
  IDF("IDF"), // terminal - operando numerico inteiro/operando variavel
  LPT("LPT"), // terminal - delimitador abre parentese '('
  RPT("RPT"), // terminal - delimitador fecha parentese ')'
  ETX("ETX"), // terminal - delimitador fim de texto
  VAR("VAR"); // variavel - S

  /**
   * Nome do simbolo da gramatica livre do contexto
   */
  private String name;

  /**
   * Inicializar o simbolo da gramatica livre do contexto
   *
   * @param name name do simbolo da gramatica livre do contexto
   */
  private SyntacticSymbol(String name)
  {
    this.name = name;
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    return name;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

/**
 * Entrada do analisador de precedencia de operadores
 */
public class SyntacticInput
{
  /**
   * Token da entrada
   */
  private Token token;

  /**
   * Inicializar a entrada do analisador de precedencia de operadores
   *
   * @param token token da entrada
   */
  public SyntacticInput(Token token)
  {
    this.token = token;
  }

  /**
   * Inicializar a entrada do analisador de precedencia de operadores
   *
   * @param character caractere lido no codigo-fonte
   * @param type tipo/classe do token
   * @param position posicao do token no codigo-fonte
   */
  public SyntacticInput(char character, TokenType type, int position)
  {
    token = new Token(character, type, position);
  }

  /**
   * Retornar o simbolo da entrada
   *
   * @return simbolo da entrada
   */
  public SyntacticSymbol getSymbol()
  {
    TokenType tokenType = token.getType();

    if(TokenType.ATR == tokenType)
    {
      return SyntacticSymbol.ATR;
    }

    if(TokenType.ADD == tokenType)
    {
      return SyntacticSymbol.ADD;
    }

    if(TokenType.SUB == tokenType)
    {
      return SyntacticSymbol.SUB;
    }

    if(TokenType.MUL == tokenType)
    {
      return SyntacticSymbol.MUL;
    }

    if(TokenType.DIV == tokenType)
    {
      return SyntacticSymbol.DIV;
    }

    if(TokenType.INT == tokenType)
    {
      return SyntacticSymbol.IDF;
    }

    if(TokenType.VAR == tokenType)
    {
      return SyntacticSymbol.IDF;
    }

    if(TokenType.LPT == tokenType)
    {
      return SyntacticSymbol.LPT;
    }

    if(TokenType.RPT == tokenType)
    {
      return SyntacticSymbol.RPT;
    }

    if(TokenType.ETX == tokenType)
    {
      return SyntacticSymbol.ETX;
    }

    return null;
  }

  /**
   * Retornar o token da entrada do analisador de precedencia de operadores
   *
   * @return token da entrada do analisador de precedencia de operadores
   */
  public Token getToken()
  {
    return token;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.List;

/**
 * Analisador sintatico baseado num analisador de precedencia de operadores
 */
public class SyntacticAnalysis
{
  /**
   * Erro 1: variavel esperada
   */
  private final String error1 = "expect variable";

  /**
   * Erro 2: atribuicao esperada
   */
  private final String error2 = "expect attribution";

  /**
   * Erro 3: operador esperado
   */
  private final String error3 = "expected operator";

  /**
   * Erro 4: operando esperado
   */
  private final String error4 = "expected operating";

  /**
   * Erro 5: abre parenteses esperado
   */
  private final String error5 = "expected left parenthesis";

  /**
   * Erro 6: fecha parenteses esperado
   */
  private final String error6 = "expected right parenthesis";

  /**
   * Erro7: expressao esperada
   */
  private final String error7 = "expected expression";

  /**
   * Erro8: operador invalido
   */
  private final String error8 = "invalid operator";

  /**
   * Erro 9: erro desconhecido
   */
  private final String error9 = "unknown error";

  /**
   * Entrada do analisador de precedencia de operadores
   */
  private List<SyntacticInput> input;

  /**
   * Pilha do analisador de precedencia de operadores
   */
  private List<SyntacticSymbol> stack;

  /**
   * Codigo-fonte correto
   */
  private boolean correct;

  /**
   * Inicializar a analise sintatica
   *
   * @param tokens tokens identificados na analise lexica
   */
  public SyntacticAnalysis(TokenList tokens)
  {
    stack = new LinkedList<SyntacticSymbol>();

    input = new LinkedList<SyntacticInput>();

    for(Token token: tokens.toArray())
    {
      input.add(new SyntacticInput(token));
    }

    correct = true;
  }

  /**
   * Realizar a analise sintatica do codigo-fonte
   */
  public void parser()
  {
    if(TokenType.VAR != input.get(0).getToken().getType())
    {
      printError(error1);
    }
    else
    {
      input.remove(0);
    }

    if(TokenType.ATR != input.get(0).getToken().getType())
    {
      printError(error2);
    }
    else
    {
      input.remove(0);
    }

    stack.add(SyntacticSymbol.ETX);

    boolean process = true;

    while(process)
    {
      SyntacticSymbol top = stack.get(0);

      int i = 1;

      while(SyntacticSymbol.VAR == top)
      {
        top = stack.get(i++);
      }

      SyntacticSymbol front = input.get(0).getSymbol();

      switch(top)
      {
        case IDF: lineIDF(front);
                  break;
        case ADD: lineADD(front);
                  break;
        case SUB: lineSUB(front);
                  break;
        case MUL: lineMUL(front);
                  break;
        case DIV: lineDIV(front);
                  break;
        case LPT: lineLPT(front);
                  break;
        case RPT: lineRPT(front);
                  break;
        case ETX: process = lineETX(front);
                  break;
        case ATR: printError(error8);
                  input.remove(0);
                  input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                  break;
        default : printError(error9);
                  break;
      }
    }
  }

  /**
   * Retornar se o codigo-fonte esta sintaticamente correto
   *
   * @return codigo-fonte sintaticamente correto ou nao
   */
  public boolean isCorrect()
  {
    return correct;
  }

  /**
   * Imprimir as mensagens de erro do analisador sintatico
   *
   * @param message mensagem de erro do analisador sintatico
   */
  private void printError(String message)
  {
    correct = false;

    Token token = input.get(0).getToken();

    System.out.print(new DecimalFormat("000").format(token.getPosition()));
    System.out.print(" Syntactic analysis error: ");
    System.out.print(message);
    System.out.print(" '");

    if(TokenType.ETX != token.getType())
    {
      System.out.print(token.getLexeme());
    }
    else
    {
      System.out.print(" ");
    }

    System.out.println("'");
  }

  /**
   * Avaliar o simbolo IDF no topo da pilha
   *
   * @param front simbolo lido da entrada
   */
  private void lineIDF(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case MUL:
      case DIV:
      case RPT:
      case ETX: reduce(SyntacticSymbol.IDF);
                break;
      case LPT:
      case IDF: printError(error3);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }
  }

  /**
   * Avaliar o simbolo ADD no topo da pilha
   *
   * @param front simbolo lido da entrada
   */
  private void lineADD(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case RPT:
      case ETX: reduce(SyntacticSymbol.VAR, SyntacticSymbol.ADD,
                       SyntacticSymbol.VAR);
                break;
      case MUL:
      case DIV:
      case LPT:
      case IDF: shift();
                break;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }
  }

  /**
   * Avaliar o simbolo SUB no topo da pilha
   *
   * @param front simbolo lido da entrada
   */
  private void lineSUB(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case RPT:
      case ETX: reduce(SyntacticSymbol.VAR, SyntacticSymbol.SUB,
                       SyntacticSymbol.VAR);
                break;
      case MUL:
      case DIV:
      case LPT:
      case IDF: shift();
                break;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }
  }

  /**
   * Avaliar o simbolo MUL no topo da pilha
   *
   * @param front simbolo lido da entrada
   */
  private void lineMUL(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case MUL:
      case DIV:
      case RPT:
      case ETX: reduce(SyntacticSymbol.VAR, SyntacticSymbol.MUL,
                       SyntacticSymbol.VAR);
                break;
      case LPT:
      case IDF: shift();
                break;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }
  }

  /**
   * Avaliar o simbolo DIV no topo da pilha
   *
   * @param front simbolo lido da entrada
   */
  private void lineDIV(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case MUL:
      case DIV:
      case RPT:
      case ETX: reduce(SyntacticSymbol.VAR, SyntacticSymbol.DIV,
                       SyntacticSymbol.VAR);
                break;
      case LPT:
      case IDF: shift();
                break;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }
  }

  /**
   * Avaliar o simbolo LPT no topo da pilha
   *
   * @param front simbolo lido da entrada
   */
  private void lineLPT(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case MUL:
      case DIV:
      case LPT:
      case RPT:
      case IDF: shift();
                break;
      case ETX: printError(error6);
                input.add(0, new SyntacticInput(')', TokenType.RPT, 0));
                break;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }
  }

  /**
   * Avaliar o simbolo RPT no topo da pilha
   *
   * @param front simbolo lido da entrada
   */
  private void lineRPT(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case MUL:
      case DIV:
      case RPT:
      case ETX: reduce(SyntacticSymbol.LPT, SyntacticSymbol.VAR,
                       SyntacticSymbol.RPT);
                break;
      case LPT:
      case IDF: printError(error3);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }
  }

  /**
   * Avaliar o simbolo ETX no topo da pilha
   *
   * @param front simbolo lido da entrada
   * @return true caso a analise sintatica seja concluida
   */
  private boolean lineETX(SyntacticSymbol front)
  {
    switch(front)
    {
      case ADD:
      case SUB:
      case MUL:
      case DIV:
      case LPT:
      case IDF: shift();
                break;
      case RPT: printError(error5);
                input.remove(0);
                break;
      case ETX: return false;
      case ATR: printError(error8);
                input.remove(0);
                input.add(0, new SyntacticInput('+', TokenType.ADD, 0));
                break;
      default : printError(error9);
                break;
    }

    return true;
  }

  /**
   * Realizar a reducao da expressao
   *
   * @param production producao a ser reduzida
   */
  private void reduce(SyntacticSymbol ... production)
  {
    if(SyntacticSymbol.IDF == production[0])
    {
      stack.remove(0);
      stack.add(0, SyntacticSymbol.VAR);
    }
    else if(SyntacticSymbol.VAR == production[0])
    {
      if(stack.get(0) != SyntacticSymbol.VAR)
      {
        printError(error4);
        input.add(0, new SyntacticInput('x', TokenType.INT, 0));
      }
      else if((stack.size() > 2) && (stack.get(2) != SyntacticSymbol.VAR))
      {
        printError(error4);
        stack.add(2, SyntacticSymbol.VAR);
      }
      else
      {
        stack.remove(0);
        stack.remove(0);
        stack.remove(0);
        stack.add(0, SyntacticSymbol.VAR);
      }
    }
    else if(SyntacticSymbol.LPT == production[0])
    {
      if(stack.get(1) != SyntacticSymbol.VAR)
      {
        printError(error7);
      }
      else
      {
        stack.remove(0);
      }

      stack.remove(0);
      stack.remove(0);
      stack.add(0, SyntacticSymbol.VAR);
    }
  }

  /**
   * Empilhar o simbolo lido na pilha
   */
  private void shift()
  {
    stack.add(0, input.get(0).getSymbol());

    input.remove(0);
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

import java.io.Serializable;

/**
 * Termo do codigo de tres enderecos
 */
public class Term implements Serializable
{
  /**
   * Identificador de serializacao da classe
   */
  private static final long serialVersionUID = 1L;

  /**
   * Lexema do token no codigo-fonte
   */
  private String lexeme;

  /**
   * Tipo/classe do token
   */
  private TokenType type;

  /**
   * Construtor para inicializar o termo
   *
   * @param lexeme lexema do token no codigo-fonte
   * @param type tipo/classe do token
   */
  public Term(String lexeme, TokenType type)
  {
    this.lexeme = lexeme;

    this.type = type;
  }

  /* (non-Javadoc)
   * @see java.lang.Object#equals(java.lang.Object)
   */
  @Override
  public boolean equals(Object obj)
  {
    if(this == obj)
    {
      return true;
    }

    if(obj == null)
    {
      return false;
    }

    if(getClass() != obj.getClass())
    {
      return false;
    }

    Term other = (Term) obj;

    if(lexeme == null)
    {
      if(other.lexeme != null)
      {
        return false;
      }
    }
    else if(!lexeme.equals(other.lexeme))
    {
      return false;
    }

    if(type != other.type)
    {
      return false;
    }

    return true;
  }

  /**
   * Retornar o lexema do token no codigo-fonte
   *
   * @return lexema do token no codigo-fonte
   */
  public String getLexeme()
  {
    return lexeme;
  }

  /**
   * Retornar o tipo/classe do token
   *
   * @return tipo/classe do token
   */
  public TokenType getType()
  {
    return type;
  }

  /* (non-Javadoc)
   * @see java.lang.Object#hashCode()
   */
  @Override
  public int hashCode()
  {
    final int prime = 31;

    int result = 1;

    result = prime * result + ((lexeme == null) ? 0 : lexeme.hashCode());
    result = prime * result + ((type == null) ? 0 : type.hashCode());

    return result;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

/**
 * Representacao de um codigo de tres enderecos
 */
public class ThreeAddressCode
{
  /**
   * Operacao
   */
  private Term oper;

  /**
   * Primeiro argumento
   */
  private Term arg1;

  /**
   * Segundo argumento
   */
  private Term arg2;

  /**
   * Resultado
   */
  private Term result;

  /**
   * Inicializar o codigo de tres enderecos
   *
   * @param oper operador
   * @param arg1 primeiro operando
   * @param arg2 segundo operando
   * @param result resultado
   */
  public ThreeAddressCode(Term oper, Term arg1, Term arg2, Term result)
  {
    this.oper = oper;
    this.arg1 = arg1;
    this.arg2 = arg2;
    this.result = result;
  }

  /**
   * Retornar o operador
   *
   * @return operador
   */
  public Term getOper()
  {
    return oper;
  }

  /**
   * Retornar o primeiro operando
   *
   * @return primeiro operando
   */
  public Term getArg1()
  {
    return arg1;
  }

  /**
   * Retornar o segundo operando
   *
   * @return segundo operando
   */
  public Term getArg2()
  {
    return arg2;
  }

  /**
   * Retornar o resultado
   *
   * @return resultado
   */
  public Term getResult()
  {
    return result;
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    StringBuilder out = new StringBuilder();

    out.append(oper.getLexeme());
    out.append(" ");

    if(TokenType.ATR != oper.getType())
    {
      out.append(arg1.getLexeme());
      out.append(" ");
      out.append(arg2.getLexeme());
      out.append(" ");
      out.append(result.getLexeme());
    }
    else
    {
      out.append(arg2.getLexeme());
      out.append(" ");
      out.append(" ");
      out.append(" ");
      out.append(arg1.getLexeme());
    }

    return out.toString();
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Geracao do codigo intermediario
 */
public class IntermediateCode
{
  /**
   * Expressao na notacao posfix
   */
  private List<Term> posfix;

  /**
   * Codigo em tres enderecos
   */
  private List<ThreeAddressCode> code;

  /**
   * Construtor para inicializar a geracao do codigo intermediario
   */
  public IntermediateCode()
  {

  }

  /**
   * Converter os tokens para codigo de tres enderecos
   *
   * @param tokens tokens identificados na analise lexica
   * @return codigo de tres enderecos
   */
  public List<ThreeAddressCode> convert(TokenList tokens)
  {
    infixToPosfix(tokens);

    code = new LinkedList<ThreeAddressCode>();

    int j = 1;

    while(posfix.size() > 1)
    {
      int i = 0;

      while((posfix.get(i).getType() == TokenType.VAR) ||
            (posfix.get(i).getType() == TokenType.INT))
      {
        i++;
      }

      ThreeAddressCode threeAddressCode =
        new ThreeAddressCode(posfix.get(i), posfix.get(i - 2),
                             posfix.get(i - 1),
                             new Term("T" + j, TokenType.VAR));
      code.add(threeAddressCode);

      i = i - 2;

      posfix.remove(i);
      posfix.remove(i);
      posfix.remove(i);

      posfix.add(i, threeAddressCode.getResult());

      j++;
    }
    
    return code;
  }

  /**
   * Converter a expressao infix para posfix
   *
   * @param tokens tokens identificados na analise lexica
   */
  private void infixToPosfix(TokenList tokens)
  {
    Stack<Token> stack = new Stack<Token>();

    posfix = new LinkedList<Term>();

    for(Token token : tokens.toArray())
    {
      if(TokenType.ATR == token.getType())
      {
        stack.push(token);
      }
      else if((TokenType.ADD == token.getType()) ||
              (TokenType.SUB == token.getType()))
      {
        if(stack.isEmpty())
        {
          stack.push(token);
        }
        else
        {
          while((stack.peek().getType() != TokenType.ATR) &&
                (stack.peek().getType() != TokenType.LPT))
          {
            Token aux = stack.pop();

            posfix.add(new Term(aux.getLexeme(), aux.getType()));
          }

          stack.push(token);
        }
      }
      else if((TokenType.MUL == token.getType()) ||
              (TokenType.DIV == token.getType()))
      {
        if(stack.isEmpty())
        {
          stack.push(token);
        }
        else
        {
          while((stack.peek().getType() == TokenType.MUL) ||
                (stack.peek().getType() == TokenType.DIV))
          {
            Token aux = stack.pop();

            posfix.add(new Term(aux.getLexeme(), aux.getType()));
          }

          stack.push(token);
        }
      }
      else if(TokenType.LPT == token.getType())
      {
        stack.push(token);
      }
      else if(TokenType.RPT == token.getType())
      {
        while(stack.peek().getType() != TokenType.LPT)
        {
          Token aux = stack.pop();

          posfix.add(new Term(aux.getLexeme(), aux.getType()));
        }

        stack.pop();
      }
      else if(TokenType.ETX == token.getType())
      {
        while(!stack.isEmpty())
        {
          Token aux = stack.pop();

          posfix.add(new Term(aux.getLexeme(), aux.getType()));
        }
      }
      else
      {
        posfix.add(new Term(token.getLexeme(), token.getType()));
      }
    }
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    StringBuilder out = new StringBuilder();

    for(ThreeAddressCode threeAddressCode: code)
    {
      out.append(threeAddressCode).append("\n");
    }

    return out.toString();
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

/**
 * Valores armazenados na memoria do computador
 */
public class MemoryCode
{
  /**
   * Operacao
   */
  private int operation;

  /**
   * Argumento da operacao
   */
  private Term argument;

  /**
   * Inicializar o codigo da memoria
   *
   * @param operation operacao
   * @param argument argumento
   */
  public MemoryCode(int operation, Term argument)
  {
    this.operation = operation;

    this.argument = argument;
  }

  /**
   * Retornar a operacao
   *
   * @return operacao
   */
  public int getOperation()
  {
    return operation;
  }

  /**
   * Retornar o argumento
   *
   * @return argumento
   */
  public Term getArgument()
  {
    return argument;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

import java.text.DecimalFormat;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Geracao do codigo para a Simpletron Machine Language
 */
public class SMLCode
{
  /**
   * Instrucoes
   */
  List<MemoryCode> memoryCode;

  /**
   * Dados
   */
  private Map<Term, Integer> memoryData;

  /**
   * Entradas
   */
  private Set<Term> memoryInput;

  /**
   * Formato numerico dos dados da memoria
   */
  private final DecimalFormat memoryFormatter;

  /**
   * Construtor para inicializar a geracao do codigo para a
   * Simpletron Machine Language
   */
  public SMLCode()
  {
    memoryFormatter = new DecimalFormat("+0000;-0000");
  }

  /**
   * Realizar a conversao do codigo intermediario para o codigo objeto para
   * a Simpletron Machine Language
   *
   * @param intermediateCode codigo intermediario em tres enderecos
   * @return codigo objeto para a Simpletron Machine Language
   */
  public String convert(List<ThreeAddressCode> intermediateCode)
  {
    memoryCode = new LinkedList<MemoryCode>();

    memoryData = new LinkedHashMap<Term, Integer>();

    memoryInput = new LinkedHashSet<Term>();

    for(ThreeAddressCode threeAddressCode : intermediateCode)
    {
      if(TokenType.ATR == threeAddressCode.getOper().getType())
      {
        memoryCode.add(new MemoryCode(2000, threeAddressCode.getArg2()));
        memoryCode.add(new MemoryCode(2100, threeAddressCode.getArg1()));
        memoryCode.add(new MemoryCode(1100, threeAddressCode.getArg1()));
        memoryCode.add(new MemoryCode(4300, null));

        storeData(threeAddressCode.getArg1());
        storeData(threeAddressCode.getArg2());

        storeInput(threeAddressCode.getArg2());
      }
      else
      {
        memoryCode.add(new MemoryCode(2000, threeAddressCode.getArg1()));

        if(TokenType.ADD == threeAddressCode.getOper().getType())
        {
          memoryCode.add(new MemoryCode(3000, threeAddressCode.getArg2()));
        }
        else if(TokenType.SUB == threeAddressCode.getOper().getType())
        {
          memoryCode.add(new MemoryCode(3100, threeAddressCode.getArg2()));
        }
        else if(TokenType.DIV == threeAddressCode.getOper().getType())
        {
          memoryCode.add(new MemoryCode(3200, threeAddressCode.getArg2()));
        }
        else if(TokenType.MUL == threeAddressCode.getOper().getType())
        {
          memoryCode.add(new MemoryCode(3300, threeAddressCode.getArg2()));
        }

        memoryCode.add(new MemoryCode(2100, threeAddressCode.getResult()));

        storeData(threeAddressCode.getArg1());
        storeData(threeAddressCode.getArg2());
        storeData(threeAddressCode.getResult());

        storeInput(threeAddressCode.getArg1());
        storeInput(threeAddressCode.getArg2());
      }
    }

    /*
     * Adicionar as leituras das variaveis utilizadas na expressao
     */

    int index = 0;

    for(Term input : memoryInput)
    {
      if(TokenType.VAR == input.getType())
      {
        memoryCode.add(index++, new MemoryCode(1000, input));
      }
    }

    StringBuilder objectCode = new StringBuilder();

    /*
     * Escrever o codigo das operacoes
     */

    for(MemoryCode code : memoryCode)
    {
      objectCode.append(memoryFormatter.format(code.getOperation() +
                        address(code.getArgument()))).append("\n");
    }

    /*
     * Escrever o codigo dos dados
     */

    for(Term data : memoryData.keySet())
    {
      if(TokenType.VAR == data.getType())
      {
        objectCode.append("+0000").append("\n");
      }
      else
      {
        objectCode.append(memoryFormatter.
          format(Integer.parseInt(data.getLexeme()))).append("\n");
      }
    }

    return objectCode.toString();
  }

  /**
   * Armazenar os dados utilizados pelo programa
   *
   * @param data dados utilizados pelo programa
   */
  private void storeData(Term data)
  {
    if(!memoryData.containsKey(data))
    {
      memoryData.put(data, memoryData.size());
    }
  }

  /**
   * Armazenar a entrada utilizada pelo programa
   *
   * @param input entrada utilizada pelo programa
   */
  private void storeInput(Term input)
  {
    if((TokenType.VAR == input.getType()) &&
       (input.getLexeme().length() == 1))
    {
      memoryInput.add(input);
    }
  }

  /**
   * Retornar a posicao do dado na memoria
   *
   * @param data dado armazenado na memoria
   * @return posicao do dado na memoria
   */
  private Integer address(Term data)
  {
    if(data != null)
    {
      return memoryData.get(data) + memoryCode.size();
    }

    return 0;
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial12;

/**
 * Compilador de expressoes aritmeticas para a Simpletron Machine Language
 */
public class Compiler
{
  /**
   * Construtor para inicializar a execucao do compilador
   */
  private Compiler()
  {

  }

  /**
   * Metodo principal da linguagem de programacao Java
   *
   * @param args argumentos da linha de comando (nao utilizado)
   */
  public static void main(String[] args)
  {
    TokenList tokens = new TokenList();

    LexicalAnalysis lexical = new LexicalAnalysis(tokens);

    lexical.parser("x = A + 5 * B");

    SyntacticAnalysis syntactic = new SyntacticAnalysis(tokens);

    syntactic.parser();

    if((lexical.isCorrect()) && (syntactic.isCorrect()))
    {
      IntermediateCode intermediateCode = new IntermediateCode();

      SMLCode smlCode = new SMLCode();

      System.out.println(smlCode.convert(intermediateCode.convert(tokens)));
    }
  }
}