LabCompl - A Análise Sintática

`Análise Sintática`

A análise léxica é uma fase menor dentro da implementação e execução de compiladores. Mesmo os erros léxicos que ocorrem em um programa são de dimensão reduzida; em geral, pouquíssimos. A maioria dos erros encontrados em programas, na fase de compilação, são erros de caráter sintático e semântico. O código circunf:=2 pi raio, lexicamente correto como visto anteriormente, produz a sequência de tokens

id₁ := num id₂ id₃

mas que não possui significado sintático nenhum para uma linguagem Pascal-like, independente do bloco em que é encontrado.

O trabalho do analisador sintático, e que possui um papel maior dentro do compilador, é comparar uma sequência de tokens na entrada com a gramática da linguagem é procurar qual é a melhor produção que se adapta à entrada e montar a árvore sintática correspondente.

Quando um código é compilado, é interessante que todos os erros no código, de natureza léxica, sintática ou semântica, sejam exibidos sem que o processo sejam interrompido no primeiro erro. Os compiladores devem saber tomar decisões quando encontram erros. No código , quando se encontra o token id₂ após o token num, algumas decisões podem ser tomadas pelo parser:

eliminar todos os tokens recebidos e continuar a leitura até encontrar sequências corretas.
o parser poderia acrescentar na posição errada um token que supostamente estaria esperando. No caso, poderia ser um operador, como +, -, * ou /.
o parser poderia eliminar o token reconhecido e avaliar o próximo. Neste caso o erro permaneceria, pois o token seguinte também é um identificador.

Estas alternativas constituem a estratégia de recuperação de erros do parser. O código permanecerá errado sintaticamente, pois o parser não corrige erros, apenas toma decisões quando um erro é encontrado para que ele possa continuar a análise da cadeia de tokens.

As variadas construções de uma linguagem são formalizadas em gramáticas livres de contexto ou usando a notação BNF (Backus-Naur Form). Uma gramática consiste num conjunto de símbolos terminais, símbolos não-terminais, regras de produção e não-terminais iniciais.

Símbolos terminais são símbolos que representam tokens. É o caso de símbolos de operadores, de pontuação, dígitos, cadeias de caracteres literais. Símbolos não-terminais são aqueles que são descritos pela regras de produção como combinação de símbolos não-terminais e terminais. Os símbolos não-terminais iniciais são aqueles com que todo o programa ou código deve ser casado. No caso da regra de produção que define o comando if,

comando -> if expressão then comando else comando

comando é o símbolo não-terminal definido pela regra, if, then e else são símbolos terminais correspondentes aos tokens if, then e else e expressão é outro símbolo não-terminal.

Considere agora a seguinte gramática para definir expressões aritméticas, onde o não-terminal E representa uma expressão.

E -> E + E | E * E | ( E ) | - E | id

O operador |tem a mesma funcionalidade de quando usado em expressões regulares, indicando aqui que E possui quatro representações ou produções alternativas. A regra informa que E pode ser uma soma de duas expressões (usando-se o terminal +) E + E, a multiplicação de duas expressões E * E, uma expressão entre parêntesis ( E ), uma expressão negada - E ou um identificador id. Com essas produções conseguimos gerar uma infinita árvore de sintática, como a da Figura 10. Árvore de Derivaçõea para a Gramática E

Uma expressão da forma (a+b)+c*d é casada com a produção da gramática de E na forma

E -> E + E
E -> ( E ) + E * E
E -> ( E + E ) + id * id
E -> ( id + id ) + id * id

gerando a árvore da Figura 11.

O diferencial na implementação de parsers é como funciona o algoritmo que efetua este casamento. De acordo com o algoritmo usado, o parser é capaz de identificar um conjunto diferente de gramáticas, assim como varia sua complexidade e eficiência em memória e velocidade.

Os métodos mais comumente utilizados para análise sintática são o bottom-up e o top-down. Parsers do tipo bottom-up constróem suas árvore a partir das folhas até chegarem à raiz, enquanto que os do tipo top-down constróem a árvore a partir da raiz até o fundo. Exemplos de algoritmos bottom-up são o shift-reduce (empilhar-reduzir), o LR e o LALR.

O tipo de gramática que reconhecem, o uso de memória e a eficiência são os três principais fatores que diferenciam cada um dos algoritmos de parser. O funcionamento de 3 dos algoritmos, devidamente demonstrados, está disponível.

Recursive-descent
LL(1)
Shift-reduce (empilhar-reduzir)

A geração do código ocorre a partir da avaliação dos ramos e folhas da árvore sintática. No exemplo da árvore da Figura 11, quando são encontradas suas folhas contendo um identificador cada uma, o parser avalia o conteúdo de cada uma pelo nó superior, como mostrado na Figura 12.

No exemplo, o valor dos identificadores são avaliados, o que significa procurar o conteúdo de id na tabela de símbolos, e seu valores somados e retornado para o nó superior. Em geral, não são apenas essas as ações realizadas. É preciso realizar verificações semânticas em cada nó, para avaliar se os identificadores existem, se existe consistência no tipo dos operandos, efetuar geração de código intermediário, etc.