I have the following program that does the following, you insert the rules (V, T, P, S), through 1 file and then you enter the word (GLUD) to see if it is part or n of the language that is in the rule, and there the program returns a Yes or a No if the word does or does not part, only now I would like to know how to do step by step of the CheckWord () method; in the verifier.java file.
So when the word is not accepted, show where the error was.
PS: this is a work of formal languages and automata that is GLUD language
Running program:
Main.java
packageverificador;importjava.io.BufferedReader;importjava.io.FileReader;importjava.util.ArrayList;importjava.util.NoSuchElementException;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args)throwsException{Scannerin=newScanner(System.in);Verificadorverificador=newVerificador();Stringword;Stringg="";
BufferedReader bufferedReader;
if(args.length > 0){
bufferedReader = new BufferedReader(new FileReader(args[0]));
}else{
System.out.print("Não ha parametros, digite o nome do arquivo: ");
bufferedReader = new BufferedReader(new FileReader(in.nextLine()));
}
String line;
while((line = bufferedReader.readLine()) != null){
g += line;
}
verificador.readGrammar(g);
System.out.println("Gramatica: " + g.replaceAll("\s+"," "));
while (true) {
try {
System.out.print("Digite a palavra: ");
word = in.nextLine();
if(word.length() == 0){
return;
}
word = word.replaceAll("\s+|λ|#", "");
} catch (NoSuchElementException e) {
return;
}
if (verificador.checkWord(word)) {
System.out.println("Sim");
word.length();
} else {
System.out.println("Não");
}
//verificador.ShowRules(word);
}
}
}
Verifier.java
package verificador;
import java.util.ArrayList;
import java.util.Arrays;
public class Verificador {
private final ArrayList<State> states;
private final ArrayList<String> alphabet;
private final ArrayList<Rule> rules;
private State inicial;
public Verificador() {
states = new ArrayList<>();
alphabet = new ArrayList<>();
rules = new ArrayList<>();
}
public void setStates(String states) {
states = states.replaceAll("\{|\}", ""); // Tira {}
for (String e : states.split(",")) {
this.states.add(new State(e));
}
this.states.add(new State("DEFAULT", true));
}
public State getStateByName(String name) {
for (State e : states) {
if (e.getName().equals(name)) {
return e;
}
}
return null;
}
public void setAlphabet(String alphabet) {
alphabet = alphabet.replaceAll("\{|\}", ""); // Tira {}
this.alphabet.addAll(Arrays.asList(alphabet.split(",")));
this.alphabet.add("#");
this.alphabet.add("λ");
}
public boolean checkLetter(String letter) {
for (String l : alphabet) {
if (l.equals(letter)) {
return true;
}
}
return false;
}
public void setRules(String regras) throws Exception {
regras = regras.replaceAll("\{|\}", ""); // Tira {}
for (String regra : regras.split(",")) {
String[] r = regra.split("->");
if (r.length != 2) {
throw new Exception("Regra mal formatada");
}
State estadoAtual = getStateByName(r[0]);
if (estadoAtual == null) {
throw new Exception("Regra mal formatada - Estado invalido1:" + r[0]);
}
try {
for (String transicao : r[1].split("\|")) {
State estadoDestino;
String letter = transicao.substring(0,1);
if(!checkLetter(letter)){
throw new Exception("Regra mal formata - Caracter invalido: " + transicao.substring(0,1));
}
if (transicao.substring(1).equals("")) {
estadoDestino = getStateByName("DEFAULT");
} else {
estadoDestino = getStateByName(transicao.substring(1));
if (estadoDestino == null) {
throw new Exception("Regra mal formatada - Estado invalido:" + transicao.substring(1));
}
}
this.rules.add(new Rule(letter, estadoAtual, estadoDestino));
}
} catch (RuntimeException e) {
throw new Exception("Regra mal formatada");
}
}
}
public ArrayList<Rule> getPossibleRules(State estado, String elemento) {
ArrayList<Rule> regras = new ArrayList<>();
for (Rule r : this.rules) {
if (r.getState() == estado && r.getElement().equals(elemento)) {
regras.add(r);
}
}
return regras;
}
public void setInicial(String inicial) throws Exception {
State estado = getStateByName(inicial);
if (estado == null) {
throw new Exception("Estado inicial invalido");
}
this.inicial = estado;
}
// ({A,B,C}; {a,b,c}; A -> aB | bA | cA | λ, B -> aB | bC | cA | λ, C -> aB | bA | λ; A)
public void readGrammar(String gramatica) throws Exception {
gramatica = gramatica.replaceAll("\(|\)|\s+|\n", ""); // Tira parentesis e espaços
if(gramatica.contains("=")){ // Tira o nome da gramatica do inicio
gramatica = gramatica.split("=")[1];
}
gramatica = gramatica.replaceAll("\},", "\};"); // Substitui a , por ;
String[] g = gramatica.split(";"); // Quebra partes da gramatica
if (g.length != 4) {
throw new Exception("Gramatica mal formatada");
}
setStates(g[0]);
setAlphabet(g[1]);
setRules(g[2]);
setInicial(g[3]);
}
public void printRules() {
for (Rule r : rules) {
System.out.println(r.toString());
}
}
boolean checkWord(String palavra) {
return checkWord(palavra, inicial);
}
boolean checkWord(String palavra, State estadoAtual) {
if (palavra.isEmpty() && estadoAtual.getIsFinal()) { // terminou a palavra
return true;
} else if (palavra.isEmpty()) {
return false;
}
ArrayList<Rule> possiveisRegras = getPossibleRules(estadoAtual, String.valueOf(palavra.charAt(0)));
for (Rule r : possiveisRegras) {
if (checkWord(palavra.substring(1), r.getDestiny())) {
return true;
}
}
return false;
}
}
State.java
package verificador;
public class State {
private String name;
private boolean isFinal;
public State(String name){
this.name = name;
}
public State(String name, boolean isFinal){
this.name = name;
this.isFinal = isFinal;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public boolean getIsFinal() {
return isFinal;
}
public void setIsFinal(boolean isFinal) {
this.isFinal = isFinal;
}
@Override
public String toString(){
if(name.equals("DEFAULT")){
return "";
}
return name;
}
}
Rule.java
package verificador;
public class Rule {
private String element;
private State state;
private State destiny;
public Rule(String element, State state, State destiny){
this.element = element;
this.state = state;
this.destiny = destiny;
if(element.equals("#") || element.equals("λ")){
this.state.setIsFinal(true);
}
}
public String getElement() {
return element;
}
public void setElement(String element) {
this.element = element;
}
public State getState() {
return state;
}
public void setState(State state) {
this.state = state;
}
public State getDestiny() {
return destiny;
}
public void setDestiny(State destiny) {
this.destiny = destiny;
}
@Override
public String toString(){
return state + " -> " + element + destiny;
}
}