| |
| Acadêmico(a): Cleison Vander Ambrosi |
| Título: Transformação de Gramáticas Livres do Contexto para Expressões Regulares Estendidas |
| |
| Introdução: |
| Este trabalho visa o estudo da representação sintática das linguagens, em especial as linguagens livres do contexto, que são usadas principalmente para o desenvolvimento de analisadores sintáticos de linguagens de programação. Uma linguagem de programação é definida por [JOS1987] como um conjunto de todos os textos que podem ser gerados a partir de uma gramática. Ela difere da linguagem natural por ser simples e direta, pois é através desta que uma máquina pode ser instruída. Por outro lado, linguagens de programação possuem propriedades em comum com as linguagens naturais. Toda linguagem possui uma sintaxe e semântica. A sintaxe é definida como a formação de frases em uma linguagem de programação. Cada linguagem possui um vocabulário de símbolos e regras que são agrupados para formar expressões, declarações, comandos, e em última instância formar programas. Cada linguagem tem suas próprias regras para compor as frases, podendo ter comandos equivalentes e diferir sintaticamente ([WAT1991]). Segundo [LEW2000], a sintaxe manipula esses símbolos sem considerar os seus significados correspondentes, portanto não existe uma noção de programa “certo” ou “errado”. Os símbolos de uma linguagem de programação são identificadores, literais, símbolos de operadores. Cada linguagem tem suas próprias regras por formar frases, portanto podem possuir comandos equivalentes que diferem sintaticamente ([JOS1987]). A semântica é definida como o significado das frases de uma linguagem. Uma interpretação semântica deve ser dada aos símbolos para resolver o problema na realidade propriamente dita. Ao contrário da sintaxe, que é facilmente formalizável, a semântica exige notações muito mais complexas, de aprendizagem mais difícil e, em geral, apresentando simbologias bastante carregadas e pouco legíveis ([JOS1987] [WAT1991]). As linguagens são classificadas em diversas classes, em uma ordem hierárquica, denominada hierarquia de Chomsky, resultando nas seguintes classes básicas de linguagens ([MEN1998]): a) linguagens regulares ou tipo 3; b) livres do contexto ou tipo 2; c) sensíveis ao contexto ou tipo 1; d) enumeráveis recursivamente ou tipo 0; Na especificação das linguagens livres de contexto, uma série de verificações e transformações necessitam ser feitas, para posterior implementação (em computação). Estas verificações e transformações consistem na retirada da recursividade, na retirada do indeterminismo (tratado no jargão de “compiladores” como fatoração). Métodos para tornar uma linguagem livre do contexto implementável podem ser vistos em [AHO1995]. Este trabalho aplica técnicas apresentadas em [WAT1991] e [SIL2000b] para transformação de definições em linguagens livres do contexto em expressões regulares estendidas. Para esta transformação, serão utilizadas algumas técnicas apresentadas em [WAT1991] para linguagens livres do contexto ‘Não Auto-Embutidas’ e [SIL2000b] para linguagens livres do contexto ‘Auto-Embutidas’. Será também aplicado o teorema de Kleene, definido para linguagens regulares nas expressões regulares estendidas. Conforme [MEN1998], uma linguagem é dita linguagem livre do contexto se for gerada por uma gramática livre do contexto, onde esta é uma gramática onde o lado esquerdo das produções contém exatamente uma variável. Segundo [AHO1995], uma gramática livre do contexto possui quatro componentes: a) um conjunto de tokens, conhecidos como símbolos terminais; b) um conjunto de não terminais; c) um conjunto de produções, onde uma produção consiste em um não-terminal, chamado de lado esquerdo da produção, uma seta e uma seqüência de tokens e/ou não-terminais, chamados de lado direito da produção; d) uma designação a um dos não-terminais como o símbolo de partida. Um exemplo de gramática pode ser vista no quadro 1.1. Ainda, este trabalho propõe-se a implementar um protótipo que automatize o processo de eliminação do indeterminismo em linguagens livres do contexto, usando o mesmo teorema de Kleene para eliminação do indeterminismo em linguagens regulares através da transformação de linguagens livres do contexto em expressões regulares estendidas. Esse teorema diz que toda linguagem regular com indeterminismo é possível transformar em uma linguagem determinística. |
| |
|
