Simulador de Autômatos - Ler Arquivos TXT

Por exemplo, tenho que pular as 3 primeiras linhas, e verificar se a linha 4 está como “start ­> 0;” ou “start ­> 1” e armazenar numa váriavel estado inicial.

O seu problema parece que não é simplesmente ler um arquivo.

Se o formato do arquivo for bem definido e sempre for fixo, a análise dos dados pode até ser feita “na mão”. Caso essa DSL que você está criando possa ter muitas variações, acredito que você vai ter que usar um gerador de parsers. Se optar pela segunda alternativa, recomendo o ANTLR.

Enfim, existem diversas formas para ler um arquivo de texto.
Uma muito útil é usar a classe Scanner (http://download.oracle.com/javase/6/docs/api/java/util/Scanner.html).

Scanner scan = new Scanner( new File( "caminho do arquivo" ) );

[]´s

Ah, ano passado eu fiz um simulador de DFAs. Está bem tosquinho, fiz como passatempo. O código está horrível em algumas partes, mas o algoritmo de reconhecimento funciona perfeitamente, o que na verdade é muito fácil de implementar visto que esse não vai ser o seu principal problema

Dê uma olhada aqui: http://www.guj.com.br/posts/list/118828.java

[]´s

David, Exatamente o que você está falando.
O formato do arquivo sempre é fixo. A única coisa que aumenta para teste são as linhas 5 a 8 que podem ser aumentadas em algum outro arquivo.

A linha 4 define qual o estado inicial do autômato. Os estados dos autômatos sempre serão definidos por números inteiros. Neste caso, definiu-se que o estado inicial é o estado 0, mas poderia ser definido outro estado inicial. A linha abaixo define o estado inicial como sendo o estado 1:
start ­> 1; ou start ­> 0;
As linhas de 5 a 8 do exemplo definem as transições entre os estados. Cada transição requer um estado de partida, um estado de chegada e um símbolo para transição ocorrer, da seguinte forma:

partida ­> chegada [label=a];

Onde a é um símbolo do alfabeto do autômato, que é composto por todos caracteres ASCII. Qualquer caractere recebido para o qual o estado atual não contenha transições, deve levar ao estado de erro (não é reconhecido).

Problema: Depois de interpretado todo este arquivo e armazenado em váriaveis internas vou receber outro arquivo, com um conteudo de teste do Automato, por exemplo: 000111.

Se o seu arquivo for SEMPRE bem formado, fazer o parse não é difícil.
Parece que você está começando a estudar linguagens formais e autômatos agora, então você ainda não tem a bagagem necessária para construir um parser baseado em uma gramática livre de contexto e mesmo que conheça as CFL, você ainda não deve ter tido nenhum contato com a disciplina de compiladores.

Como falei, usei a classe Scanner e vá lendo o arquivo, quebrando linha a linha.
Leia as três primeiras, recorte os dados que precisar.
A partir da quarta, verifique se é um “}”. Se não for, faça o parse de linha. Se for, pare de ler o arquivo, pois o modelo do autômato já vai estar carregado, ai é só testar se cada linha do segundo arquivo contém strings válidas para a linguagem regular definida pelo DFA representado no primeiro arquivo.

Crie uma classe para representar o DFA, uma para representar os Estados e uma para representar as Transições.
Se os símbolos do seu alfabeto forem compostos de apenas um caractere, o algoritmo de reconhecimento é bem simples de ser implementado.
Caso os símbolos possam ser formados por mais de um caractere, então o algoritmo fica um pouquinho mais complicado, mas ainda assim, fácil de implementar.

[]´s

David, entendi o que você colocou.
Estou tentando fazer, mas não estou conseguindo fazer com que o codigo capture na linha 4 (start -> 0), o que está depois do “->” que pode ser 0 ou 1.

Olha o que fiz:
Observação: Ele está lendo o arquivo direitinho.
O arquivo está em anexo.

public class ReadWithScanner {

public static void main(String... aArgs) throws FileNotFoundException {
    ReadWithScanner parser = new ReadWithScanner("C:/dadosautomato/automato.txt");
    parser.processLineByLine();
    System.out.println("OK");
  }
  
  public ReadWithScanner(String aFileName){
    fFile = new File(aFileName);  
  }
  
  public final void processLineByLine() throws FileNotFoundException {
    Scanner scanner = new Scanner(new FileReader(fFile));
    try {
      while ( scanner.hasNextLine() ){
        processLine( scanner.nextLine() );
      }
    }
    finally {
      scanner.close();
    }
  }
  
  protected void processLine(String aLine){
    //use a second Scanner to parse the content of each line 
    Scanner scanner = new Scanner(aLine);
    scanner.useDelimiter("\n");
      String name = scanner.findInLine("start -> ");
    if ( scanner.hasNext() ){
      System.out.println("O Estado Inicial é: " + name);
    }
    else {
      System.out.println("Arquivo Invalido");
    }
    //no need to call scanner.close(), since the source is a String
  
  }
  
  // PRIVATE 
  private final File fFile;
}

Denis, vc precisa começar a formatar o seu código com a tag code…
Dê uma olhada aqui: http://www.guj.com.br/posts/list/50115.java

Obtenha a linha usando o método getLine() e atribua o retorno a uma variável. Ai sim, faça o recorte da String.

[]´s

Oi Denis,

E ai, deu certo?
Hoje tive umas horinhas de folga e aproveitei para modelar no ANTLR a linguagem que você apresentou.

Segue o código:
Estou preparando um projetinho no NetBeans para usá-la.

/**
 * Gramática para o reconhecimento da linguagem de representação
 * de um autômato finito determinístico.
 *
 * Exemplo:
 *
 * digraph D {
 * rankdir=LR;
 * start [shape=point];
 *      start ­> 0;
 *      0 ­> 0 [label=a];
 *      0 ­> 1 [label=b];
 *      1 ­> 0 [label=a];
 *      1 ­> 1 [label=b];
 *      0 [peripheries=2];
 * }
 */

grammar DFA;

@header {
    import java.util.Map;
    import java.util.HashMap;
    import parserdfa.dfa.*;
}

@members{
    private Estado estadoInicial;
    private Map<String, Estado> memoriaEstados = new HashMap<String, Estado>();
}

prog[boolean printMap] returns[parserdfa.dfa.DFA d]
                    :    DIGRAPH DIGRAPH_NAME {
                    
                             $d = new parserdfa.dfa.DFA( $DIGRAPH_NAME.text );
                             
                         } L_CURV header transitions R_CURV { 
                             
                             $d.setEstadoInicial( estadoInicial ); 
                             
                             if ( printMap ) {
	                             for ( Map.Entry<String, Estado> e : memoriaEstados.entrySet() ) {
	                                 System.out.println( e.getValue() + "\n" );
	                             }
                             }
                             
                         };

header              :    rankdirExp startExp;

rankdirExp          :    RANKDIR EQ RANKDIR_TYPES SEMICOLON;
startExp            :    START L_BRAC SHAPE EQ SHAPE_TYPES R_BRAC SEMICOLON;
transitions         :    startTransitionExp transitionExp+ aceptStateExp+;

startTransitionExp  :    START T_OPER STATE_NAME {

                             estadoInicial = new Estado( $STATE_NAME.text );
                             estadoInicial.setInicial( true );
                             memoriaEstados.put( $STATE_NAME.text, estadoInicial );
                             
                         } SEMICOLON;
                         
transitionExp       :    stateL {
                             
                             Estado eL = memoriaEstados.get( $stateL.text );
                             
                             if ( eL == null ) {
                                 eL = new Estado( $stateL.text );
                                 memoriaEstados.put( $stateL.text, eL );
                             }
                             
                         } T_OPER stateR {
                         
                             Estado eR = memoriaEstados.get( $stateR.text );
                             
                             if ( eR == null ) {
                                 eR = new Estado( $stateR.text );
                                 memoriaEstados.put( $stateR.text, eR );
                             }
                             
                         } L_BRAC LABEL EQ LABEL_VALUE {
                         
                             Transicao t = new Transicao( $LABEL_VALUE.text, eL, eR );
                             eL.addTransicao( t );
                             
                         } R_BRAC SEMICOLON;
                         
aceptStateExp       :    stateL {
                             
                             Estado eFinal = memoriaEstados.get( $stateL.text );
                             
                             if ( eFinal != null ) {
                                 eFinal.setFinal( true );
                             }
                             
                         } L_BRAC PERIPHERIES EQ stateR {
                         
                             // código para tratar as periferias
                             // não sei o que são as tais das periferias no seu código.
                             
                         } R_BRAC SEMICOLON;

stateL              :    STATE_NAME;
stateR              :    STATE_NAME;

RANKDIR             :    'rankdir';
DIGRAPH             :    'digraph';
START               :    'start';
SHAPE               :    'shape';
LABEL               :    'label';
PERIPHERIES         :    'peripheries';

RANKDIR_TYPES       :    'LR'|'LL';
DIGRAPH_NAME        :    'A'..'Z'+;
SHAPE_TYPES         :    'point'|'ellipse';
LABEL_VALUE         :    'a'..'z';
STATE_NAME          :    '0'..'9'+;

L_CURV              :    '{';
R_CURV              :    '}';
L_BRAC              :    '[';
R_BRAC              :    ']';
EQ                  :    '=';
SEMICOLON           :    ';';
T_OPER              :    '>';

WS                  :   (' '|'\t'|'\r'|'\n') { skip(); };

[]´s

Na facu, na matéria de automatos, utilizamos o JFlap. para simular uma Máquina de Turin. Serve pra automatos tb. Então da pra pegar umas idéias.

[]s

Oi Denis,

Acabei que não resisti e fiz tudo :oops:
Eu não entendi o que são algumas coisas na definição (rankdir, peripheries, etc.) então apesar de ser tratado, eu não faço nada com os valores.
Estou enviando em anexo o .jar, o antlr e os arquivos de teste.

Para aprender a usar, basta dar um "java -jar ParserDFA.jar" no prompt de comando.

digraph MAQUINA {
rankdir=LR;
start [shape=point];
     start > 0;
     0 > 0 [label=a];
     0 > 1 [label=b];
     1 > 0 [label=a];
     1 > 1 [label=b];
     0 [peripheries=2];
}

a
ab
aaa
aaabbb
ababab
aaabbba

Estado: 0*
Transições: 
    [>0*] > b [1]
    [>0*] > a [>0*]

Estado: 1
Transições: 
    [1] > b [1]
    [1] > a [>0*]

DFA "MAQUINA" construido com sucesso!
Iniciando testes...

Cadeia "a":
[>0*] > a [>0*]
Pertence!

Cadeia "ab":
[>0*] > a [>0*]
[>0*] > b [1]
Nao pertence...

Cadeia "aaa":
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > a [>0*]
Pertence!

Cadeia "aaabbb":
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > b [1]
[1] > b [1]
[1] > b [1]
Nao pertence...

Cadeia "ababab":
[>0*] > a [>0*]
[>0*] > b [1]
[1] > a [>0*]
[>0*] > b [1]
[1] > a [>0*]
[>0*] > b [1]
Nao pertence...

Cadeia "aaabbba":
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > b [1]
[1] > b [1]
[1] > b [1]
[1] > a [>0*]
Pertence!

Vou deixar você quebrar a cabeça um pouco.
Depois eu passo os fontes :D

Ah, e minha implementação do reconhecimento tem um errinho ;)
Veja se descobre o que é fazendo testes. Pode ser com essa definição mesmo.

O automato da definição é o da figura em anexo.
Não estou conseguindo fazer o upload do pacote compilado, vou subir o pacote no 4shared, já coloco o link.

[]´s

Segue o link do pacote compilado:

Ah, o parser vai aceitar indeterminismos no automôto, afinal, o parser verifica a linguagem, não o autômato, só que na hora de testar as cadeias no autômato, o algoritimo não vai funcionar. Ele vai pegar o primeiro caminho que encontrar.

[]´s

renzonuccitelli:

Na facu, na matéria de automatos, utilizamos o JFlap. para simular uma Máquina de Turin. Serve pra automatos tb. Então da pra pegar umas idéias.

[]s

O JFLAP é bem legal mesmo, usei ele bastante em 2008 para fazer uns experimentos com o lema do bombeamento para linguagens livres de contexto.
É um joguinho. http://www.cs.duke.edu/csed/jflap/tutorial/pumpinglemma/context_free/index.html

[]´s

davidbuzatto:

renzonuccitelli:

Na facu, na matéria de automatos, utilizamos o JFlap. para simular uma Máquina de Turin. Serve pra automatos tb. Então da pra pegar umas idéias.

[]s

O JFLAP é bem legal mesmo, usei ele bastante em 2008 para fazer uns experimentos com o lema do bombeamento para linguagens livres de contexto.
É um joguinho. http://www.cs.duke.edu/csed/jflap/tutorial/pumpinglemma/context_free/index.html

[]´s

O JFlap é muito bom mesmo! Eu fiz há um tempo um verificador de autômatos em Ruby e ele até exportava o autômato pro JFlap e lia os autômatos do JFlap também. Ele suportava autômatos finitos determinísticos, não-determinísticos e com movimento vazio.

Se for do interesse de alguém eu posso postar o código aqui.

Boa tarde David. Tudo bom?

Acabou que essa semana foi corrida e não deu para trabalhar tudo no projeto, está dando alguns erros. Depois me passa o seu e-mail para te passar as especificações do projeto.
Mas, você já está ajudando muito.
Parabéns pelo seu esforço e conhecimento em trabalho com a linguagem Java.

Agradeço a atenção.

Obrigado.

Boa Noite David.

Até tentei aqui. Tem como você disponibilizar o codigo.

Agradeço.

Att.

davidbuzatto:

Oi Denis,

Acabei que não resisti e fiz tudo :oops:
Eu não entendi o que são algumas coisas na definição (rankdir, peripheries, etc.) então apesar de ser tratado, eu não faço nada com os valores.
Estou enviando em anexo o .jar, o antlr e os arquivos de teste.

Para aprender a usar, basta dar um "java -jar ParserDFA.jar" no prompt de comando.

Para a definição (Teste.dfa):

digraph MAQUINA {
rankdir=LR;
start [shape=point];
     start > 0;
     0 > 0 [label=a];
     0 > 1 [label=b];
     1 > 0 [label=a];
     1 > 1 [label=b];
     0 [peripheries=2];
}

E os dados (DadosTeste.txt):

a
ab
aaa
aaabbb
ababab
aaabbba

A saída detalhada gerada é:

Estado: 0*
Transições: 
    [>0*] > b [1]
    [>0*] > a [>0*]

Estado: 1
Transições: 
    [1] > b [1]
    [1] > a [>0*]

DFA "MAQUINA" construido com sucesso!
Iniciando testes...

Cadeia "a":
[>0*] > a [>0*]
Pertence!

Cadeia "ab":
[>0*] > a [>0*]
[>0*] > b [1]
Nao pertence...

Cadeia "aaa":
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > a [>0*]
Pertence!

Cadeia "aaabbb":
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > b [1]
[1] > b [1]
[1] > b [1]
Nao pertence...

Cadeia "ababab":
[>0*] > a [>0*]
[>0*] > b [1]
[1] > a [>0*]
[>0*] > b [1]
[1] > a [>0*]
[>0*] > b [1]
Nao pertence...

Cadeia "aaabbba":
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > a [>0*]
[>0*] > b [1]
[1] > b [1]
[1] > b [1]
[1] > a [>0*]
Pertence!

Vou deixar você quebrar a cabeça um pouco.
Depois eu passo os fontes :D

Ah, e minha implementação do reconhecimento tem um errinho ;)
Veja se descobre o que é fazendo testes. Pode ser com essa definição mesmo.

O automato da definição é o da figura em anexo.
Não estou conseguindo fazer o upload do pacote compilado, vou subir o pacote no 4shared, já coloco o link.

[]´s

Boa Dia David.

Tem como você passar os fontes do programa.

Agradeço.

Att.

Nossa, tinha até esquecido desse tópico.
Ta ai o projeto no NetBeans. http://www.4shared.com/file/R8wimwnD/ParserDFA.html
Se precisar fazer alguma modificação na gramática, use o ANTLR Works

[]´s