Análise sintática top-down

Análise sintática top-down

1. Analisa se o código fonte está de acordo com as regras sintáticas e semânticas, e, assim, conclui-se a segunda etapa do processo de análise.

2. Como o analisador faz isso? Por meio da derivação da árvore sintática. Logo, construir um analisador sintático é desenvolver um algoritmo que nos permita construir uma árvore de derivação para qualquer sentença (estrutura de comando) que pertença à linguagem.

3. Processo de derivação

   • Consiste em substituir a sentença, ou parte dela, no lado direito da produção da gramática, repetidas vezes, até alcançar os símbolos terminais, e, segundo Aho (2007), podemos aplicar repetidamente as produções, em qualquer ordem, a fim de obtermos uma sequência de substituições.

4. Arvore de derivação

   • A derivação da árvore sintática, ou gramatical, pode ser vista como a representação gráfica da derivação. Como já visto, os nós têm sucessores, logo é um símbolo não-terminal e as folhas são os símbolos terminais.
   • Assim, ao construirmos a árvore de derivação de uma sentença de acordo com a gramática de uma linguagem, aplicarmos sucessivamente as regras e alcançarmos as folhas para todos logo a sentença será gerada pela gramática.

5. Ascendentes

   • que constroem a árvore gramatical das folhas para a raiz, chamados também de bottom-up, ou seja, de baixo para cima.

6. Descendentes

   • que analisam a árvore gramatical da raiz para as folhas, isto é, de cima para baixo, também chamados de top-down.
     • Esse é o método mais intuitivo e usual, e consiste em construir a árvore gramatical em pré-ordem (raiz-esquerda-direita)

7. Algoritmo preditivo recursivo

   • Os analisadores descendentes utilizam um modelo de algoritmo preditivo recursivo, que pode ser com retrocesso ou sem retrocesso. Um algoritmo preditivo é aquele que avança para ser capaz de tomar uma decisão agora, com base em uma informação que virá, mas se conhece previamente.
   • Algoritmo de análise sintática com retrocesso
     • Escolhe a 1ª opção e avança na construção da árvore gramatical, armazenando os dados em uma pilha até alcançar o final, mas se não reconhecer a sentença, retrocede, desempilhando os dados até o nó inicial, e reinicia o processo. Esse algoritmo é ineficiente do ponto de vista do tempo gasto na análise (o vai e volta), do tratamento da recuperação de erros e de análise semântica.
   • Algoritmo de análise sintática sem retrocesso
     • Não volta. Para que seja possível utilizar um algoritmo de análise sintática recursivo preditivo sem retrocesso, há uma condição: a gramática não pode ter recursão a esquerda. Assim, basta conhecer o primeiro token de entrada e a produção à frente, para expandir a árvore. Esse tipo de analisador é capaz de derivar a maioria das linguagens de programação, por serem do tipo livre de contexto.