Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /***************************************************************************
- * Definição da classe Automato. *
- * Última alteração: 12/11/2004 às 22:06 *
- * Autor: Raphael Araújo e Silva - khaotix_@hotmail.com *
- * *
- * ATENÇÃO: VOCÊ TEM A COMPLETA PERMISSÃO PARA ALTERAÇÃO E REDISTRIBUIÇÃO *
- * DO CÓDIGO NESTE E EM QUALQUER ARQUIVO ACOMPANHANTE DESDE QUE O *
- * AUTOR ORIGINAL SEJA CITADO. O USO DO CÓDIGO CONTIDO NESTE *
- * ARQUIVO É POR SUA CONTA E RISCO, O AUTOR NAO SE RESPONSABILIZA *
- * RÁ POR QUALQUER DANO QUE ESTE VENHA A CAUSAR A COMPUTADORES DE *
- * TERCEIROS. *
- ***************************************************************************/
- #include "automato.h"
- //***************************************************************************
- int extrairAlfabeto(string elems,vector<string> &alf)
- {
- //Função que extrai um alfabeto a partir de uma expressão regular
- //Na forma: [az:09:A:B:C:#]
- /* Descrição da máquina:
- Q.C = qualquer caractere da tabela ascii
- estado_final: 4
- { estado_atual: 0 char_entrada: '[' estado destino: 1 }
- { estado_atual: 1 char_entrada: Q.C estado destino: 2 }
- { estado_atual: 2 char_entrada: ':' estado destino: 1 }
- { estado_atual: 2 char_entrada: Q.C estado destino: 3 }
- { estado_atual: 2 char_entrada: ']' estado destino: 4 }
- { estado_atual: 3 char_entrada: ':' estado destino: 1 }
- { estado_atual: 3 char_entrada: ']' estado destino: 4 } */
- if(elems.length()<=2) //A expressão deve ter pelo menos 2 bytes de comp. para ser analisada
- return(ERRO_EXP_REG_INVAL);
- else
- {
- int idx=0,tam,st=1;
- char chr;
- string str_aux;
- bool fim=false;
- alf.clear(); //Limpa o vetor que guarda o alfabeto
- tam=elems.size();
- if(elems[0]=='[') //Ponto de partida de máquina
- {
- do
- {
- chr=elems[++idx]; //Obtém um caractere da string de entrada
- if((st==2 || st==3) && (chr==':' || chr==']')) //Indica o final de um intervalo
- {
- alf.push_back(str_aux); //Insere o que foi retirado até aqui no vetor que guarda o alfabeto
- st=1; //Volta para o estado 1
- str_aux="";
- if(chr==']') fim=true; //Finaliza a máquina
- }
- else if(st==1 || st==2)
- { str_aux+=chr; st++; }
- else break;
- }
- while(idx<tam && !fim);
- }
- if(!fim)
- {
- alf.clear(); //Limpa o vetor que guarda o alfabeto
- return(idx); //Retorna o índice do caractere inválido
- }
- else if(idx<tam-1)
- {
- alf.clear(); //Limpa o vetor que guarda o alfabeto
- return(ERRO_STR_NAO_TERM);
- }
- else return(EXP_VALIDA); //Retorna um valor q indica que o alfabeto foi extraido sem erros
- }
- }
- //***************************************************************************
- bool intervaloValido(string interv,vector<string> &alf)
- {
- int tam,tam_alf;
- tam=interv.length();
- tam_alf=alf.size();
- if(tam_alf>0 && tam>0)
- {
- bool valido=false;
- vector<string>::iterator itr,itr_end;
- string alfabeto;
- unsigned char ext1,ext2,_ext1,_ext2;
- itr=alf.begin();
- itr_end=alf.end();
- if(tam==2) //caso o intervalo contenha duas letras
- { ext1=interv[0]; ext2=interv[1]; } //Os extremos serão o primeiro e o segundo caractere do intervalo
- else
- { ext1=interv[0]; ext2=interv[0]; } //Os extremos será apenas o primeiro cractere do intervalo
- while(itr!=itr_end && !valido)
- {
- alfabeto=(*(itr++)); //Obtém um elemento do alfabeto
- tam_alf=alfabeto.length();
- if(tam_alf==2)
- { _ext1=alfabeto[0]; _ext2=alfabeto[1]; }
- else
- { _ext1=alfabeto[0]; _ext2=alfabeto[0]; }
- valido=(ext1>=_ext1 && ext2<=_ext2);
- }
- return(valido);
- }
- else return(false);
- }
- //***********************************************************************************
- ExpRegular::ExpRegular(void){ flag=FLAG_INDEF; }
- //-----------------------------------------------------------------------------------
- ExpRegular::~ExpRegular(void)
- {
- //Limpa as listas que constituem a expressão regular
- elems.clear();
- flag=FLAG_INDEF;
- }
- //-----------------------------------------------------------------------------------
- int ExpRegular::obterFlag(void){ return(flag); }
- //-----------------------------------------------------------------------------------
- vector<string> &ExpRegular::obterElementos(void){ return(elems); }
- //-----------------------------------------------------------------------------------
- ExpRegular &ExpRegular::operator = (ExpRegular &exp)
- {
- vector<string>::iterator itr,itr_end;
- elems.clear();
- itr=exp.elems.begin();
- itr_end=exp.elems.end();
- //Copia os elementos da expressão regular do parametro para
- //o objeto 'this'
- while(itr!=itr_end)
- elems.push_back(*(itr++));
- flag=exp.flag;
- return(*this);
- }
- //-----------------------------------------------------------------------------------
- int ExpRegular::extrairElementos(string exp,vector<string> &alf)
- {
- int tam;
- tam=exp.length();
- if(tam<3) //Expressão regular inválida (menos de dois caracteres)
- return(ERRO_EXP_REG_INVAL);
- else if(alf.size()==0) //Alfabeto vazio (indefinido)
- return(ERRO_ALF_INDEFINIDO);
- else
- {
- int idx=0,st=1;
- char chr;
- string str_aux;
- bool fim=false,erro=false,alf_definido;
- alf_definido=(alf.size()>0); //Vefifica se há um alfabeto definido, se naõ, o alfabeto padrão será a tabela ascii
- flag=FLAG_INDEF;
- elems.clear(); //Limpa a lista de elementos atual
- tam=exp.size();
- chr=exp[0];
- switch(chr)
- {
- //---------------------------
- case '%': //Retira as expressões %qc, %qo
- {
- idx++;
- if(exp[idx]=='q')
- {
- idx++;
- if(exp[idx]=='c') flag=FLAG_QC_ALF;
- else if(exp[idx]=='o') flag=FLAG_QO_ALF;
- else erro=true;
- }
- else erro=true;
- }
- break;
- //---------------------------
- case '[': //Retira as expressões []
- {
- flag=FLAG_ALF_DEF;
- do
- {
- chr=exp[++idx]; //Obtém um caractere da string de entrada
- if((st==2 || st==3) && (chr==':' || chr==']')) //Indica o final de um intervalo
- {
- if(alf_definido)
- erro=!intervaloValido(str_aux,alf); //Verifica se a string aux contém caracteres inválidos (fora do alfabeto)
- if(!erro)
- {
- elems.push_back(str_aux); //Insere o que foi retirado até aqui no vetor que guarda o alfabeto
- str_aux=""; st=1; //Volta para o estado 1
- if(chr==']') fim=true; //Finaliza a máquina
- }
- }
- else if(st==1 || st==2){ str_aux+=chr; st++; }
- else break;
- }
- while(idx<tam && !fim && !erro);
- if(!fim) erro=true;
- }
- break;
- //---------------------------
- default: erro=true; break;
- }
- if(erro){ flag=FLAG_INDEF; return(idx); }
- else if(idx<tam-1) return(ERRO_STR_NAO_TERM); //Retorna um erro indicando que a análise terminou, com sucesso, porém no meio da string
- else return(EXP_VALIDA); //Sem erro
- }
- }
- //***********************************************************************************
- Automato::Automato(void)
- {
- extrairAlfabeto("[ ÿ]",alfabeto); //O alfabeto padrão é toda tabela ascii (do caractere 32 ao 255)
- buf_entrada=buf_saida="";
- alfabeto_str="[ ÿ]";
- est_inicial=est_atual=-1;
- idx_atual=status=-1;
- }
- //------------------------------------------------------------------------------------
- Automato::~Automato(void){ limparConfig(); }
- //------------------------------------------------------------------------------------
- void Automato::reiniciarAutomato(void)
- {
- status=AFD_OCIOSO; //Somente com esse status que o automato é capaz de analisar a string
- idx_atual=0;
- est_atual=est_inicial; //Reinicia o estado atual do automato
- buf_saida="";
- }
- //------------------------------------------------------------------------------------
- void Automato::limparConfig(void)
- {
- Config *cfg;
- deque<Config *>::iterator itr,itr_end;
- est_inicial=est_atual=-1;
- idx_atual=status=-1;
- estados.clear();
- alfabeto.clear();
- itr=configs.begin();
- itr_end=configs.end();
- while(itr!=itr_end) //Destói cada configuração do automato separadamente
- {
- cfg=*(itr++); //Obtem uma configuração
- delete(cfg); //Destrói
- }
- configs.clear(); //Limpa a lista de configuraçoes
- buf_entrada=buf_saida=alfabeto_str="";
- }
- //------------------------------------------------------------------------------------
- int Automato::definirAlfabeto(string exp_reg)
- {
- int res;
- res=extrairAlfabeto(exp_reg,alfabeto); //Tenta extrair o alfabeto a partir da exp. regular passada
- if(res==EXP_VALIDA)
- {
- alfabeto_str=exp_reg;
- reiniciarAutomato();
- }
- return(res);
- }
- //------------------------------------------------------------------------------------
- const string &Automato::obterAlfabeto(void)
- { return(alfabeto_str); }
- //------------------------------------------------------------------------------------
- int Automato::inserirEstado(int tipo_est)
- {
- //Verifica se o tipo do estado é valido
- if(tipo_est>=EST_COMUM && tipo_est<=EST_FINAL_SAIDA)
- {
- estados.push_back(tipo_est);
- reiniciarAutomato();
- return(estados.size()-1);
- }
- else return(ERRO_EST_INVALIDO); //Erro!
- }
- //------------------------------------------------------------------------------------
- int Automato::inserirEstados(const int *vet_est,unsigned num_est)
- {
- unsigned idx;
- int res=0;
- for(idx=0;idx<num_est && res!=ERRO_EST_INVALIDO;idx++)
- {
- //Verifica se todos os estados no vetor são válidos
- res=(vet_est[idx]>=EST_COMUM && vet_est[idx]<=EST_FINAL_SAIDA ?
- SEM_ERRO : ERRO_EST_INVALIDO);
- }
- if(res==SEM_ERRO) //Caso sejam válidos
- {
- for(idx=0;idx<num_est;idx++) //Insere todos no vetor de estados
- estados.push_back(vet_est[idx]);
- reiniciarAutomato();
- }
- return(res);
- }
- //------------------------------------------------------------------------------------
- int Automato::definirEstadoInicial(int idx_est)
- {
- //Verfica se o estado passado existe na lista de estados
- if(idx_est>=0 && idx_est<static_cast<int>(estados.size()))
- {
- est_inicial=idx_est;
- reiniciarAutomato();
- return(est_inicial);
- }
- else return(ERRO_EST_INVALIDO); //Erro!
- }
- //------------------------------------------------------------------------------------
- void Automato::carregarBuffer(string buf)
- {
- buf_entrada=buf;
- reiniciarAutomato();
- }
- //------------------------------------------------------------------------------------
- int Automato::inserirConfig(string exp,int est_atual,int est_dest)
- {
- ExpRegular exp_reg;
- int res,num_est;
- //Extrai os elementos da expressão regular que define a condição da configuração
- res=exp_reg.extrairElementos(exp,alfabeto);
- num_est=estados.size();
- if(res!=EXP_VALIDA) //Caso a expressão seja inválida
- return(res); //Retorna o índice do caractere onde há o erro
- //Verifica se os estados de destino e atual a serem usados sao válidos
- else if(num_est==0 || num_est<est_atual || num_est<est_dest)
- return(ERRO_EST_INVALIDO);
- else
- {
- Config *cfg;
- int flag;
- cfg=new Config;
- cfg->exp_reg=exp_reg;
- cfg->est_atual=est_atual;
- cfg->est_dest=est_dest;
- //Logo abaixo é uma rotina para a organização das configurações de acordo com o flag da
- //expressao regular das mesmas.
- //Flags %qc são inseridos no inicio da lista, %qo no final e [az:09] no meio
- //Isso permite uma leitura sequencial e coerente caso as flags %qc e %qo estejam presentes na configuração
- flag=exp_reg.obterFlag();
- if(flag==FLAG_QC_ALF) //Flag %qc vai para o inicio da lista
- configs.push_front(cfg);
- else if(flag==FLAG_QO_ALF) //Flag %qo vai para o fim da lista
- configs.push_back(cfg);
- else
- {
- deque<Config *>::iterator itr,itr_end;
- itr=configs.begin();
- itr_end=configs.end();
- //Varre a lista enquanto o flag da exp. reg. do elemento atual é '%qc'
- while(itr!=itr_end && (*itr)->exp_reg.obterFlag()==FLAG_QC_ALF)
- itr++;
- //Insere a configuração
- if(itr!=itr_end)
- configs.insert(itr,cfg);
- else
- configs.push_back(cfg);
- }
- reiniciarAutomato();
- return(SEM_ERRO);
- }
- }
- //------------------------------------------------------------------------------------
- int Automato::inserirConfigs(unsigned num_cfgs,const string *vet_exp,const int *st_atual,const int *st_dest)
- {
- int res=SEM_ERRO,num_est;
- vector<ExpRegular> exp_reg;
- ExpRegular exp;
- num_est=estados.size();
- for(unsigned idx=0;idx<num_cfgs && (res==SEM_ERRO || res==EXP_VALIDA);idx++)
- {
- //Verifica se as expressões regulares sao válidas
- res=exp.extrairElementos(vet_exp[idx],alfabeto);
- if(res==EXP_VALIDA)
- {
- exp_reg.push_back(exp);
- //Verifica se os estados atuais e de destino são válidos
- if(st_atual[idx]>=num_est || st_dest[idx]>=num_est)
- res=ERRO_EST_INVALIDO;
- }
- }
- if(res==EXP_VALIDA)
- {
- Config *cfg;
- deque<Config *>::iterator itr,itr_end;
- int flag;
- //Logo abaixo é uma rotina para a organização das configurações de acordo com o flag da
- //expressao regular das mesmas.
- //Flags %qc são inseridos no inicio da lista, %qo no final e [az:09] no meio
- //Isso permite uma leitura sequencial e coerente caso as flags %qc e %qo estejam presentes na configuração
- for(unsigned idx=0;idx<num_cfgs;idx++)
- {
- cfg=new Config;
- cfg->exp_reg=exp_reg[idx];
- cfg->est_atual=st_atual[idx];
- cfg->est_dest=st_dest[idx];
- flag=exp_reg[idx].obterFlag();
- if(flag==FLAG_QC_ALF)//Flag %qc vai para o inicio da lista
- configs.push_front(cfg);
- else if(flag==FLAG_QO_ALF) //Flag %qo vai para o fim da lista
- configs.push_back(cfg);
- else
- {
- itr=configs.begin();
- itr_end=configs.end();
- //Varre a lista enquanto o flag da exp. reg. do elemento atual é '%qc'
- while(itr!=itr_end && (*itr)->exp_reg.obterFlag()==FLAG_QC_ALF)
- itr++;
- //Insere a configuração
- if(itr!=itr_end)
- configs.insert(itr,cfg);
- else
- configs.push_back(cfg);
- }
- }
- res=SEM_ERRO;
- reiniciarAutomato();
- }
- return(res);
- }
- //------------------------------------------------------------------------------------
- int Automato::obterEstado(int idx_est)
- {
- //Vefica se o índice não extrapola os limites do vetor de estados
- if(idx_est>=0 && idx_est<static_cast<int>(estados.size()))
- return(estados[idx_est]);
- else
- return(ERRO_EST_INVALIDO);
- }
- //------------------------------------------------------------------------------------
- int Automato::obterIndiceAtual(void){ return(idx_atual); }
- //------------------------------------------------------------------------------------
- char Automato::obterCaractereAtual(void)
- {
- if(idx_atual>=0)
- return(buf_entrada[idx_atual]);
- else
- return(0);
- }
- //------------------------------------------------------------------------------------
- int Automato::obterEstadoInicial(void){ return(est_inicial); }
- //------------------------------------------------------------------------------------
- int Automato::obterEstadoAtual(void){ return(est_atual); }
- //------------------------------------------------------------------------------------
- int Automato::obterStatus(void){ return(status); }
- //------------------------------------------------------------------------------------
- const string &Automato::obterBufEntrada(void){ return(buf_entrada); }
- //------------------------------------------------------------------------------------
- const string &Automato::obterBufSaida(void){ return(buf_saida); }
- //------------------------------------------------------------------------------------
- int Automato::analisarString(void)
- {
- int tipo_est;
- tipo_est=estados[est_atual];
- if(status==AFD_OCIOSO && (tipo_est==EST_COMUM || tipo_est==EST_COMUM_SAIDA))
- {
- deque<Config *>::iterator itr,itr_end;
- Config *cfg;
- bool chr_valido,chr_alf,est_mudado;
- int flag,tam;//,tam_alf;
- string str_aux;
- tam=buf_entrada.length();
- //tam_alf=alfabeto.size();
- str_aux="";
- for(idx_atual==0;idx_atual<tam && status==AFD_OCIOSO;idx_atual++)
- {
- str_aux="";
- str_aux+=buf_entrada[idx_atual];
- chr_alf=intervaloValido(str_aux,alfabeto); //Verifica se o caractere atual pertence ao alfabeto
- if(chr_alf)
- {
- est_mudado=false;
- itr=configs.begin();
- itr_end=configs.end();
- //Efetua uma varredura na lista de configurações
- while(itr!=itr_end && !est_mudado)
- {
- cfg=(*(itr++));
- if(cfg->est_atual==est_atual) //Caso o estado atual da configuração obtida seja o mesmo q o estado atual da máquina
- {
- flag=cfg->exp_reg.obterFlag();
- if(flag!=FLAG_QO_ALF) //CAso o flag da exp. reg. da configuração não seja '%qo'
- chr_valido=intervaloValido(str_aux,cfg->exp_reg.obterElementos()); //Verifica se o caractere é valido para aquela configuração
- //Condição 0: caractere pertence ao alfabeto
- //Condição 1: caractere válido
- //Condição 2: caractere inválido porém o estado possui a flag para qualquer outro caractere
- //Condição 3: flag da configuração é para qualquer caractere (o caractere atual é simplesmente desprezado)
- if(chr_alf && (chr_valido || (!chr_valido && flag==FLAG_QO_ALF) ||
- flag==FLAG_QC_ALF))
- {
- //Caso o estado seja de saída
- if(estados[est_atual]==EST_FINAL_SAIDA || estados[est_atual]==EST_COMUM_SAIDA)
- buf_saida+=str_aux; //coloca o caractere atual no buffer de saída
- est_atual=cfg->est_dest; //Muda o estado atual da máquina
- if(estados[est_atual]==EST_FINAL_ABS) status=AFD_PARADO; //Para imediatamente o automato
- est_mudado=true; //Indica q o estado foi mudado
- }
- }
- }
- if(!est_mudado) status=AFD_PARADO_ERRO;
- }
- //ERRO: A maq. nao consegue mudar de estado pois leu um caractere q nao está no alfabeto
- //ou não existe uma configuração válida para o caractere lido (apesar de ele pertencer ao alfabeto)
- else status=AFD_PARADO_ERRO;
- }
- }
- //else if(tipo==EST_FINAL || tipo_est==EST_FINAL_SAIDA || tipo_est=EST_FINAL_ABS)
- // status=AFD_PARADO;
- //Caso se chegue ao fim da string normalmente , pára o automato
- if(status==AFD_OCIOSO) status=AFD_PARADO;
- return(status);
- }
- //-----------------------------------------------------------------------------------
- bool Automato::stringValida(void)
- {
- int tipo=estados[est_atual];
- //Condição de validade de uma string: automato parado em um estado final
- return((status==AFD_PARADO &&
- (tipo==EST_FINAL || tipo==EST_FINAL_SAIDA || tipo==EST_FINAL_ABS)));
- }
- //***********************************************************************************
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement