Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

Apresente a implementação da Análise Recursiva Preditiva sobre a gramática a seguir.

G = ({S, L}, {a, ;, (, )}, P, S)
P = {S → (L) | a
LL;S | S}

 

1. Eliminação da recursividade à esquerda:

1.1. Simplificação da gramática livre de contexto:

G = ({S, L}, {a, ;, (, )}, P, S)
P = {S → (L) | a
LL;S | (L) | a}

1.2. Renomeação das variáveis em uma ordem crescente qualquer:

G = ({A, B}, {a, ;, (, )}, P, A)
P = {A → (B) | a
BB;A | (B) | a}

1.3. Transformação das produções da forma ArAsα, onde rs:

G = ({A, B}, {a, ;, (, )}, P, A)
P = {A → (B) | a
BB;A | (B) | a}

1.4. Exclusão das recursões da forma ArArα:

G = ({A, B, C}, {a, ;, (, )}, P, A)
P = {A → (B) | a
B → (B)C | aC | (B) | a
C → ;AC | ;A}

2. Fatoração a esquerda da gramática livre de contexto:

G = ({A, B, C, D}, {a, ;, (, )}, P, A)
P = {A → (B) | a
B → (B)D | aD
C → ;AD
DC | ε}

Conjuntos FIRST(α) e FOLLOW(A):

FIRST(A) = {a, (}
FIRST(B) = {a, (}
FIRST(C) = {;}
FIRST(D) = {;, ε}
FOLLOW(A) = {;, ), $}
FOLLOW(B) = {)}
FOLLOW(C) = {)}
FOLLOW(D) = {)}
Compiler.java

Arquivo Compiler.java

/*************************************************************************
* 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.tutorial03.exercicio69;

/**
* Classe responsavel pela analise recursiva preditiva
*/
public class Compiler
{
/**
* Token atual
*/
private int index;

/**
* Lista dos tokens
*/
private String tokens;

/**
* Apresentar a mensagem de erro
*
* @param estado estado onde o erro ocorreu
* @param validos tokens validos
*/
private void error(final char estado, final char ... validos)
{
System.out.print("q" + estado + " ");

boolean first = true;

for (char valido: validos)
{
if (first)
{
first = false;
}
else
{
System.out.print(" ou ");
}

System.out.print("'" + valido + "'");
}

System.out.print(" - '");

for (int i = index; i < tokens.length(); i++)
{
System.out.print(tokens.charAt(i));
}

System.out.print("'\n");
}

/**
* Retornar o token em analise
*
* @return token em analise
*/
private char getToken()
{
if (index < tokens.length())
{
return tokens.charAt(index);
}

return '$';
}

/**
* Pular para o proximo token
*/
private void nextToken(final char estado)
{
System.out.print("q" + estado + " '" + tokens.charAt(index) + "' - '");

index = index + 1;

for (int i = index; i < tokens.length(); i++)
{
System.out.print(tokens.charAt(i));
}

System.out.print("'\n");
}

/**
* Funcao responsavel pela validacao da regra A → (B) | a
*
* @return true caso a regra esteja correta, false caso contrario
*/
private boolean qA()
{
if ('a' == getToken())
{
nextToken('A');

return true;
}

if ('(' == getToken())
{
nextToken('A');

if (qB())
{
if (')' == getToken())
{
nextToken('A');

return true;
}
else
{
error('A', ')');

return false;
}
}
else
{
return false;
}
}

error('A', 'a', '(');

return false;
}

/**
* Funcao responsavel pela validacao da regra B → (B)D | aD
*
* @return true caso a regra esteja correta, false caso contrario
*/
private boolean qB()
{
if ('a' == getToken())
{
nextToken('B');

return qD();
}

if ('(' == getToken())
{
nextToken('B');

if (qB())
{
if (')' == getToken())
{
nextToken('B');

return qD();
}
else
{
error('B', ')');

return false;
}
}
else
{
return false;
}
}

error('B', 'a', '(');

return false;
}

/**
* Funcao responsavel pela validacao da regra C → ;AD
*
* @return true caso a regra esteja correta, false caso contrario
*/
private boolean qC()
{
if (';' == getToken())
{
nextToken('C');

return qA() && qD();
}

error('C', ';');

return false;
}

/**
* Funcao responsavel pela validacao da regra D → C | ε}
*
* @return true caso a regra esteja correta, false caso contrario
*/
private boolean qD()
{
if (';' == getToken())
{
return qC();
}

if (')' == getToken())
{
return true;
}

error('D', ';', ')');

return false;
}

/**
* Realizar a analise recursiva preditiva
*
* @param source codigo-fonte
* @return true caso o codigo-fonte esteja correto, false caso contrario
*/
public boolean parse(final String source)
{
tokens = source + '$';

index = 0;

return qA() && '$' == getToken();
}

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

if (compiler.parse("(a;(a;a);a)"))
{
System.out.println("Análise concluída com sucesso!");
}
else
{
System.out.println("Análise concluída com erro!");
}
}
}