Análise Sintática De Programas

1 INTRODUÇÃO

Cada linguagem de programação possui as regras que descrevem a estrutura sintática dos programas bem formados. Em Pascal por exemplo, um programa é constituído por blocos, um bloco por comandos, um comando por expressões , uma expressão por tokens e assim por diante. A sintaxe das construções de uma linguagem de programação pode ser descrita pelas gramáticas livres de contexto ou pela notação BNF (Forma de Bakcus – Naur). As gramáticas oferecem vantagens significativas tanto para os projetistas de linguagens quanto para os escritores de compiladores.

Uma gramática oferece, para uma linguagem de programação, uma especificação sintática precisa e fácil de entender.

Para certas classes de gramáticas, podemos construir automaticamente um analisador sintático que determine se um programa-fonte está sintaticamente bem-formado. Como benefício adicional, o processo de construção do analisador pode revelar ambigüidades sintáticas bem como outras construções difíceis de se analisar gramaticalmente, as quais poderiam, de outra forma, seguir indetectadas na fase de projeto inicial de uma linguagem e de seu compilador.

Uma gramática propriamente projetada implica uma estrutura de linguagem de programação útil à tradução correta de programas-fonte em códigos objeto e também à detecção de erros. Existem ferramentas disponíveis para a conversão de descrições de traduções, baseadas em gramáticas, em programas operativos.

As linguagens evoluíram ao longo de um certo período de tempo, adquirindo novas construções e realizando tarefas adicionais. Essas novas construções podem ser mais facilmente incluídas quando existe uma implementação baseada numa descrição gramatical da linguagem.

2 O PAPEL DO ANALISADOR SINTÁTICO

Existem três tipos gerais de analisadores sintáticos. Os métodos universais de análise sintática, tais como o algoritmo de Cocke-younger-Kasami e o de Earley, podem tratar qualquer gramática. Esses métodos, entretanto, saio muito ineficientes parta se usar num compilador de produção. Os métodos mais comumente usados nos compiladores são classificados como top-down ou bottom-up. Como indicado por seus nomes, os analisadores sintáticos top-down, constroem árvores do topo (raiz) para o fundo (folhas), enquanto que os bottom-up começam pelas folhas e trabalham árvore acima até a raiz. Em ambos os casos, a entrada é varrida da esquerda para a direita, um símbolo de cada vez.

Os métodos de análise sintática mais eficientes, tanto top-down quanto bottom-up, trabalham somente em determinadas subclasses de gramáticas, mas várias dessas subclasses, como as das gramáticas LL e LR, são suficientemente expressivas para descrever a maioria das construções sintáticas das linguagens de programação. Os analisadores implementados manualmente trabalham freqüentemente com gramáticas LL; por exemplo. Assumimos que a saída de um analisador sintático seja alguma representação da árvore gramatical para o fluxo de tokens produzido pelo analisador léxico. Na prática, existe um certo número de tarefas que poderiam ser conduzidas durante a análise sintática, tais como coletar informações sobre os vários tokens na tabela de símbolos, realizar a verificação de tipos e outras formas de análise semântica, assim como gerar o código intermediário.

3 TRATAMENTO DE ERROS DE SINTAXE

Se um compilador tivesse que processar somente programas corretos, seu projeto e sua implementação seriam grandemente simplificados. Mas os programadores freqüentemente escrevem programas incorretos, e um bom compilador deveria assistir o programador na identificação e localização de erros. É gritando que, apesar dos erros serem lugar-comum, poucas linguagens sejam projetadas tendo-se o tratamento de erros em mente. Nossa civilização seria radicalmente diferente se as linguagens faladas tivessem as mesmas exigências de correção sintática que as das linguagens de computadores. A maioria das especificações das linguagens de programação não descreve como um compilador deveria responder aos erros; tal tarefa é deixada para o projetista desde o início poderia ser tanto simplificar a estrutura de um compilador quanto melhorar sua resposta aos erros.

Sabemos que os programas podem conter erros em muitos níveis diferentes. Por exemplo, os erros podem ser:

léxicos, tais como errar a grafia de um identificador, palavra-chave ou operador

sintáticos, tais como uma expressão aritmética com parênteses não balanceados

semânticos, tais como um operador aplicado a um operando incompatível

lógicos, tais como uma chamada infinitamente recursiva

Freqüentemente, boa parte da detecção e recuperação de erros num compilador gira em torno da fase de análise sintática. Isto porque os erros ou são sintáticos por natureza ou são expostos quando o fluxo de tokens proveniente do analisador léxico desobedece às regras gramaticais que definem a linguagem de programação. Outra razão está na precisão dos modernos métodos de análise sintática; podem detectar muito eficientemente a presença de erros sintáticos num programa. Detectar precisamente a presença de erros semânticos ou lógicos em tempo de compilação é muito mais difícil.

Um tratador de erros num analisador sintático possui metas simples de serem estabelecidas:

- Deve relatar a presença de erros clara e acuradamente.

- Deve se recuperar de cada erro suficientemente rápido a fim de ser capaz de detectar erros subseqüentes.

- Não deve retardar significativamente o processamento de programas corretos.

A realização efetiva dessas metas apresenta desafios difíceis.

Felizmente, os erros comuns são simples e freqüentemente basta um mecanismo de tratamento de erros relativamente direto. Em alguns casos, entretanto, um erro pode ter ocorrido muito antes de sua presença ter sido detectada e sua natureza precisa pode ser muito difícil