BDBComp
Parceria:
SBC
Gramática Regular para Reconhecimento de Palíndromos

Adriel SeccoMariane Regina Sponchiado CassenoteLeonam Cordeiro de OliveiraLeo Natan PaschoalRodrigo Luiz Antoniazzi

Considerando-se a interface entre linguística e Ciência da Computação, faz-se necessária a discussão de seus objetos de estudo e da nomenclatura assumida por cada uma dessas áreas. Alguns dos conceitos fundamentais de disciplinas como Linguagens Formais e Compiladores englobam gramática, linguagem e sentença. Nesse contexto, a gramática delimita o subconjunto de um alfabeto que gera uma determinada linguagem, definindo-se uma estrutura sobre um alfabeto de forma a permitir que apenas determinadas combinações sejam válidas. Linguagens, no entanto, são conhecidas como conjuntos finitos de palavras, morfemas ou alguma sequência finita de caracteres, sendo todo o conjunto de elementos de uma língua. Sentenças são o produto final que fará parte da linguagem. Assim, caso se trate de uma gramática de formação de palavras, as sentenças serão palavras e os elementos formadores sons/letras/morfemas. Dentro do conceito de gramática existe um segmento que descreve as Gramáticas Livres de Contexto (GLC). Trata-se de um tipo mais complexo de geradores de linguagem, as quais disponibilizam um completo entendimento do processo de construção das palavras pertencentes à linguagem. Um exemplo muito conhecido de GLC é o palíndromo, uma cadeia que pode ser lida da mesma forma da direita para a esquerda e da esquerda para a direita. Este trabalho, o qual foi proposto na disciplina de Compiladores do Curso de Ciência da Computação, objetiva o desenvolvimento de um algoritmo reconhecedor de palíndromos por meio da linguagem de programação Object Pascal. Dada uma sentença sobre um alfabeto T = {a, b}, o sistema verifica se a mesma respeita a estrutura definida pela gramática G = (V, T, P, S). Define-se a gramática como: T = {a, b} trata os elementos terminais ou alfabeto formado pelos símbolos 'a' e 'b'; V = {S} refere-se ao conjunto de elementos não terminais; S = {S} é o elemento não terminal inicial e, por fim, P = {S -> aSa | bSb | a | b | &} representa o conjunto das regras sintáticas dessa gramática. Para testar as combinações informadas pelo usuário, utilizou-se operações de derivação a fim de, por meio de uma sequência de substituições, sair de um elemento não terminal inicial e chegar a um elemento terminal. A sequência de substituições seguiu o método chamado leftmost derivation (derivação mais à esquerda), no qual substituem-se os símbolos não terminais mais à esquerda da sentença pelos elementos correspondentes contidos nas regras gramaticais. Assim, ao ser executado, o algoritmo verifica se a entrada informada pelo usuário faz parte do alfabeto, condicionando-a em caso afirmativo. A seguir, executa-se quantas etapas de derivação mais à esquerda forem necessárias para que se chegue à formalização do palíndromo. A partir do desenvolvimento deste estudo espera-se demonstrar a eficiência da gramática determinada no reconhecimento de palíndromos. Apesar do pequeno número de regras gramaticais, de sua simplicidade e da utilização de uma linguagem de alto nível que dispõe de funções específicas de manipulação de sentenças como ferramenta de implementação, a lógica algorítmica empregada no programa mostrou-se um tanto complexa. Salienta-se, portanto, a importância do emprego de gramáticas de alta qualidade em compiladores a fim de garantir a integridade e confiabilidade do sistema implementado.

http://www.revistaeletronica.unicruz.edu.br/index.php/computacao/article/view/3899

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD