terça-feira, fevereiro 27, 2007

Construindo um Compilador - Parte 1

Esta série de posts foi instigada por uma mensagem no grupo C++ Brasil.

Minha primeira experiência em construir um compilador foi na faculdade. Lembro vagamente que era um compilador que gerava um programa para uma calculadora Texas a partir de uma linguagem parecida com Basic.

Recem formado, tive a oportunidade de participar de uma série de cursos na Scopus, não relacionados diretamente a projetos. Um deles foi A Construção de Um Compilador, lecionado pelo professor Valdemar Setzer. O material para este curso foi uma versão preliminar de um livro do próprio Setzer (em conjunto com Inês S Homem de Melo), que posteriormente viria a ser publicado pela Editora Campus.

Vários anos depois, tive a oportunidade de utilizar na prática estes conhecimentos, ao participar da definição e desenvolvimento de uma linguagem de script para o programa de comunicação Zapt da Humana Informática.

A forma de implementar um compilador que vou apresentar nestes posts se baseia diretamente no livro do Setzer. Obviamente vou ser bastante superficial nestes posts (o livro tem mais de 300 páginas).



O Que é Um Compilador?

Podemos dizer que um compilador é um programa que traduz um programa escrito em uma linguagem (linguagem fonte) para uma outra linguagem (linguagem objeto). Tipicamente a linguagem fonte é uma linguagem de alto nível e a linguagem objeto é o código de máquina.

Um parente próximo do compilador é o interpretador, que ao invés de gerar o programa em linguagem objeto ele o executa.

Um compilador pode não converter diretamente a linguagem fonte na linguagem objeto, ele pode ser composto de vários passos utilizando linguagens intermediárias. Um exemplo típico são compiladores que usam linguagem Assembly como uma linguagem intermediária.

Definindo Uma Linguagem

Tipicamente a definição de uma linguagem começa com os itens básicos para a escrita de programas: palavras reservadas, símbolos especiais, constantes e identificadores. Estes itens são denominados itens léxicos.

A forma como estes itens léxicos são combinados para gerar declarações, expressões e comandos em geral de uma linguagem é definida pela gramática da linguagem. Existem várias formas de se definir uma linguagem, algumas mais formais (como a notação BNF) e outras menso. Nestes posts vou usar os grafos sintáticos para descrever a gramática.

A definição da linguagem pode facilitar ou complicar a sua compilação. O método que será abordado é mais adequado para lingugens "bem comportadas".

Estrutura de Um Compilador

Tradicionalmente se divide o compilador em três grandes partes:
  • Analisador Léxico: reconhece no fonte os itens léxicos
  • Analisador Sintático: verifica se a sequência de itens léxicos contida no fonte está de acordo com a gramática da linguagem e reconhece as várias construções.
  • Analisador Semântico: Gera o código objeto para as construções reconhecidas pala analisador sintático.
No próximo post veremos como fazer um analisador léxico.

2 comentários:

Bruno Belmont disse...

Ótimo post! To muito curioso para ver a sequencia, sempre tive muita curiosidade em relação a esse assunto.

Tiago "PacMan" Peczenyj disse...

Então, parou na quarta parte? Estava interessante :)

Alias ja adicionei este blog aos meus feeds!