segunda-feira, março 26, 2007

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.

5 comentários:

Tiago Kempin disse...

Bom Dia Daniel,

Gostaria de saber se você tem a próxima parte dos artigos sobre construção de compiladores. Estou fazendo um trabalho para a faculdade e preciso construir um compilador para parte da Linguagem C.

Ou ainda se você puder me indicar algum material que trate desse tema eu agradeço muito.

Daniel Quadros disse...

Tiago,

Ainda estou preparando a próxima parte, está indo bem devagar... As referências que conheço estão listadas na primeira parte e estão, infelizmente, indisponíveis.

Anônimo disse...

preciso urgente de um algoritmo (em turbo c de preferencia) de uma calculadora de expressoes, como essa q vc ta desenvolvendo....
por favor vc poderia me ajudar???
e-mail: vitorcmachado@hotmail.com
agradecço desde ja.

Daniel Quadros disse...

Vitor,

Acho que você está procurando no lugar errado. O objetivo desta série de artigos é explicar como um compilador é construído, não apresentar código pronto.

Ricardo Ferreira de disse...

Desenvolvi um compilador em Java e coloquei o código disponível no sourceforge.net

é só baixar os fontes:

http://verto.sf.net

abraços