Nosso software irá receber primeiro uma lista de regras de reescrita, que define nosso sistema não determinístico, ocorrerá um processamento destas regras de reescrita e logo após será fornecida uma entrada para ser processada pelas regras.
Preferi partir então para a primeira etapa: a do processamento das regras de substituição. Como proposto no artigo, para cada regra de substituição pegamos sua expressão regular e a transformamos em uma gramática.
Na segunda parte, após o processamento das regras de reescrita, e já com a entrada para processamento, realizamos o parser de cada string com todas as gramáticas, que irá retornar diversas árvores de derivação. Percorremos as árvores de derivação que casaram criamos as novas strings de acordo com a cadeia de substituição da regra de reescrita específica.
Voltando à primeira etapa....
Para realizar a conversão da expressão regular em uma gramática através do método proposto no paper teremos interpretar a expressão regular de alguma forma. Lembrei quando o Rodrigo alertou na sala que teríamos que aceitar somente regras de reescrita válidas e resolvi matar dois coelhos com uma pancada só.
A descrição acima é de duas gramáticas que validam expressões regulares, se não casar, não é uma expressão regular válida, se casar percorremos sua árvore de derivação e aplicamos as regras de conversão propostas no paper.
Estas gramáticas estão no paper Enumerating Regular Expressions and Their Languages e podemos alterá-las para se adequarem a nossa gramática de expressão regular. Por exemplo, podemos não querer aceitar o símbolo vazio da variável C.
Porém antes de tudo, precisamos definir a versão final de nossa gramática de expressões regulares.
Abaixo segue minhas alterações das duas gramáticas acima para aceitar a gramática de expressões regulares proposta no paper, por favor verifiquem se está certo.
Nenhum comentário:
Postar um comentário