Construindo um Compilador - Parte 3

Vamos começar a estudar nesta parte como fazer um analisador sintático. Na parte anterior, usamos uma máquina de estados (também chamada de autômato finito) para fazer a análise léxica. Na máquina de estados do analisador léxico os itens léxicos são reconhecidos analisando a entrada sequêncialmente da esquerda para a direita.

Na análise sintática esta forma de operação não é suficiente. O reconhecimento de uma construção sintática requer o reconhecimento de vários trechos, não necessáriamente da esquerda para a direita. Além disso, é comum um item ser definido de forma recursiva. Consideremos este exemplo de linguagem, onde os itens léxicos são num, '*', '/', '+', '-', '(' e ')':

e vamos analisar o seguinte "programa fonte":

10 + ( 70 - 4 * 5 )

o reconhecimento dos vários itens léxicos e sintáticos gera um árvore:
A figura acima sugere duas estatégias básicas para a análise sintática:

• análise ascendente, onde itens sintáticos mais complexos vão sendo reconhecidos a partir de itens sintáticos mais simples.
• análise descentente, onde se procura identificar itens sintáticos cada ver mais simples.

O algorítimo que apresentarei utiliza a análise descendente. Em cada passo teremos como objetivo reconhecer um item sintático. Para isto utilizamos uma tabela que representa os grafos que indicam as várias alternativas disponíveis naquele instante, junto com uma pilha que guarda os sucessivos objetivos à medida em que descemos na análise.

Considerando a expressão de exemplo, teríamos os seguintes passos iniciais:

• O nosso objetivo inicial é reconhecer uma expressão.
• O primeiro item de uma expressão tem que ser um termo, salvamos na pilha o ponto em que estamos no reconhecimento da expressão e passamos a tentar reconhecer um termo.
• O primeiro item de um termo tem que ser um fator, salvamos na pilha o ponto em que estamos no reconhecimento do termo e passamos a tentar reconhecer um fator.
• Um fator pode começar com um '(' ou com um número. No nosso caso encontramos o número '10' e com isto concluímos o reconhecimento de um fator.
• Retiramos da pilha o nosso objetivo. Estamos reconhecendo um termo, já reconhecemos um fator. As alteranativas seguintes são '*', '/' ou final do reconhecimento. Como o item seguinte é um '+', damos por encerrado o reconhecimento do termo.
• Voltamos assim ao reconhecimento da expressão. Já reconhecemos um termo, as alternativas seguintes são '+', '-' ou fim do reconhecimento.
• Como temos um '+', passamos a reconhecer um novo termo

Este algorítimo, que usa um autômato finito com pilha, permite analisar uma grande variedade de linguagens, mas não todas. A principal restrição é que cada item léxico reconhecido determina imediatamente o próximo "ramo" da sintaxe a ser examinado.

No próximo post vamos ver em detalhes como se implementa este algorítimo.