Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

Desenvolva um tradutor para o reconhecimento de expressões aritméticas simples para a Simpletron Machine Language, considerando a gramática livre de contexto apresentada a seguir.

G = ({A, E, T, F, V, N, D}, {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, =, +, -, *, /, (, )}, P, A)
P = {AV=E
EE+T | E-T | T
TT*F | T/F | F
F → (E) | N | V
NND | D
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
V → a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z}

 

Autômato Finito Determinístico Tabela de Precedência de Operadores Implementação na Linguagem de Programação Java

Observações:

'#' - representa o espaço em branco

'$' - representa o fim de texto/fim de arquivo

M = ({a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, =, +, -, *, /, (, ), #, $}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10}, δ, q0, {q10})

Grafo com a função de transição de M
Grafo com a função de transição de M
Tabela com a função de transição de M
δabcdefghijklmnopqrstuvwxyz0123456789=+-*/()#$
q0q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q1q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q2q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q3q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q4q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q5q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q6q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q8q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q9q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q7q6q6q6q6q6q6q6q6q6q6q1q2q3q4q5q8q9q0q10
q10---------------------------------------------
Tabela de precedência de operadores da gramática G
 id+-*/()=$
iderro 3>>>>erro 3>erro 8>
+<>><<<>erro 8>
-<>><<<>erro 8>
*<>>>><>erro 8>
/<>>>><>erro 8>
(<<<<<<=erro 8erro 6
)erro 3>>>>erro 3>erro 8>
=erro 8erro 8erro 8erro 8erro 8erro 8erro 8erro 8erro 8
$<<<<<<erro 5erro 8aceita

Erros na consulta a matriz:

erro 1 - emite a mensagem: variável esperada.

erro 2 - emite a mensagem: atribuição esperada.

erro 3 - insere + na entrada e emite a mensagem: operador esperado.

erro 5 - descarta ) da entrada e emite a mensagem: abre parenteses esperado.

erro 6 - insere ) na entrada e emite a mensagem: fecha parenteses esperado.

erro 8 - substitui = por + na entrada e emite a mensagem: operador inválido.

erro 9 - emite a mensagem: erro desconhecido.

Erros na redução do handle:

erro 4 - se + ou - ou * ou / definem um handle, verificar se existem variáveis em ambos os lados do operador. Em caso negativo, executar a redução e emitir a mensagem: operando experado.

erro 7 - se o par ( ) deve ser reduzido, verificar se existe uma variável entre os parênteses. Em caso negativo, executar a redução e emitir a mensagem: expressão esperada.

Diagrama de Classes na Linguagem de Programação Java TokenType.java Token.java TokenList.java LexicalAnalysis.java SyntacticSymbol.java SyntacticInput.java SyntacticAnalysis.java Term.java ThreeAddressCode.java IntermediateCode.java MemoryCode.java SMLCode.java Compiler.java
Diagrama de Classes em Java
Diagrama de Classes na Linguagem de Programação Java

Arquivo Symbol.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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 interface Symbol
{
/**
* Delimitador de nova linha
*/
public int LF = 10;

/**
* Delimitador de fim de texto
*/
public int ETX = 3;

/**
* Operador de atribuicao (=)
*/
public int ASSIGNMENT = 11;

/**
* Operador aritmetico de adicao (+)
*/
public int ADD = 21;

/**
* Operador aritmetico de subtracao (-)
*/
public int SUBTRACT = 22;

/**
* Operador aritmetico de divisao inteira (/)
*/
public int DIVIDE = 23;

/**
* Operador aritmetico de multiplicacao (*)
*/
public int MULTIPLY = 24;

/**
* Operador relacional igual a (==)
*/
public int EQ = 31;

/**
* Operador relacional diferente de (!=)
*/
public int NE = 32;

/**
* Operador relacional maior que (>)
*/
public int GT = 33;

/**
* Operador relacional menor que (<)
*/
public int LT = 34;

/**
* Operador relacional maior ou igual a (>=)
*/
public int GE = 35;

/**
* Operador relacional menor ou igual a (<=)
*/
public int LE = 36;

/**
* Identificador
*/
public int VARIABLE = 41;

/**
* Constante numerica inteira
*/
public int INTEGER = 51;

/**
* Palavra reservada rem
*/
public int REM = 61;

/**
* Palavra reservada input
*/
public int INPUT = 62;

/**
* Palavra reservada let
*/
public int LET = 63;

/**
* Palavra reservada print
*/
public int PRINT = 64;

/**
* Palavra reservada goto
*/
public int GOTO = 65;

/**
* Palavra reservada if
*/
public int IF = 66;

/**
* Palavra reservada end
*/
public int END = 67;

/**
* Token nao reconhecido
*/
public int ERROR = 99;
}

Arquivo TokenType.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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;
}
}

Arquivo Token.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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();
}
}

Arquivo TokenList.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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();
}
}

Arquivo LexicalAnalysis.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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();
}
}
}

Arquivo SyntacticSymbol.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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;
}
}

Arquivo SyntacticInput.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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;
}
}

Arquivo SyntacticAnalysis.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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);
}
}

Arquivo Term.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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;
}
}

Arquivo ThreeAddressCode.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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();
}
}

Arquivo IntermediateCode.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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();
}
}

Arquivo MemoryCode.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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;
}
}

Arquivo SMLCode.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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;
}
}

Arquivo Compiler.java

/*************************************************************************
* Copyright (C) 2009/2018 - 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)));
}
}
}