No sistema de reescrita de expressões regulares as cadeias serão substituídas se somente se “casarem” com a expressão regular de uma dada regra Ri do sistema. O casamento de uma cadeia com uma expressão regular pode ser realizada de diversas formas, porém o método escolhido para o sistema de reescrita de expressões regulares é a utilização de um analisador sintático top-down (parser) que utilize análise LL com busca recursiva com retrocesso (backtracking) sobre uma gramática gerada através do método de conversão de expressões regulares para gramática proposto anteriormente.
Antes de efetuar a operação de casamento sobre uma determinada regra de reescrita, o parser deverá verificar se a gramática que será utilizada para realizar as a respectiva operação de casamento possui ou não infinitas produções recursivas à esquerda ou é ambígua, pois estes tipos de gramática podem levar analisador a um laço infinito, impedindo que as demais regras de reescrita sejam aplicadas a uma determinada cadeia.
Para solucionar o problema das infinitas produções recursivas à esquerda é necessário eliminar estas produções recursivas da gramática em questão, convertendo-a, adicionando um novo símbolo não terminal para torná-la uma recursão a direita, como segue o exemplo:
Dada a gramática:
A --> Aa
A --> b
Gramática convertida:
A’ --> bA’
A’ --> aA’
A’ --> e
Assinar:
Postar comentários (Atom)
Nenhum comentário:
Postar um comentário