Algorítmos de Ordenação - Parte V

QuickSort - Ordenação por troca de partições

Este algorítmo foi inventado por C. A. R. Hoare em 1962 e é provavelmente o mais popular algorítmo de ordenação. Ele é rápido, mas também um pouco manhoso.

A idéia básica do algorítmo é selecionarmos uma das chaves (o elemento de partição) e re-arranjamos os dados para que as chaves à esquerda do elemento de partição sejam anteriores a ela (mas não necessariamente em ordem) e as chaves à direita sejam posteriores. Repetimos o processo para as duas partições e assim por diante, até que as partições tenham um único elemento; neste ponto todos os dados estão ordenados.

Por exemplo, vamos supor que nossas chaves são [6909 6508 6407 6412 6512] e escolhemos o 6508 como elemento de partição. Um possível particionamente é [6407 6412] 6508 [6909 6512].

Uma maneira simples de particionar N chaves K₁, K₂ ... K_n é selecionar a primeira delas como elemento de partição e percorrer as chaves a partir das duas pontas, trocando de lado os elementos quando necessário. Para isto usamos dois índices, um partindo da segunda chave (i) e o outro partindo da última (j). Avançamos i até acharmos uma chave maior que K₁ (que portando deve ir para a direita) e recuamos j até acharmos uma chave menor que K₁ (que deve ir para a esquerda). Neste ponto, temos duas chaves que estão em lados errados; nós as trocamos de lugar. Quando i alcançar j, trocamos de lugar K_j com K₁, encerrando a partição.

A figura abaixo mostra uma ordenação pelo QuickSort.

O QuickSort em ação

O QuickSort tem uma natureza recursiva: após o particionamento nós usamos o mesmo algorítmo para ordenar as duas partições. Existem várias razões para não codificar o QuickSort como uma rotina recursiva:

• Chamadas a rotinas tem um overhead alto: os parâmetros precisam ser colocados na pilha do processador, um novo stack frame precisa ser criado para os parâmetros locais, etc.
• Chamadas a rotinas podem consumir uma quantidade razoável de espaço na pilha; esta quantidade não está totalmente sob o nosso controle.
• Se a pilha ficar cheia, provavelmente não conseguiremos encerrar o programa de uma forma limpa.

O que devemos fazer é codificar o QuickSort de uma forma iterativa ao invés de recursiva, gerenciando nós mesmos a pilha. A questão chave é: qual o tamanho desta pilha? Na prática, esta pilha é bem pequena, desde que coloquemos nela primeiro a partição maior e depois a menor. Desta forma, na iteração seguinte começamos com a partição menor, que por sua vez gerará um número menor de subpartições. No pior caso, a cada vez as partições serão quebradas em duas subpartições de igual tamanho, portanto o tamanho da partição é dividido continuamente por dois (mais precisamente, o tamanho diminui um pouco mais, pois o elemento de partição não entra em nenhuma das duas subpartições). Portanto, com uma pilha com k elementos podemos ordenar 2^k chaves. Ou, olhando pelo outro lado, para ordenar N chaves precisamos de uma pilha com log₂(N) elementos. Por exemplo, para ordenar um milhão de chaves basta uma pilha com 20 elementos! Cada elemento na pilha contém apenas dois inteiros (os índices do início e fim da partição a ordenar), portanto não ocupam muito espaço.

O tempo médio do QuickSort é proporciona a N log(N). Infelizmente, o pior caso é proporcional a N². Não apenas isto, escolhendo o elemento de partição da forma que descrevemos, o pior caso é quando as chaves já estão ordenadas! Neste caso, cada passo reduz o tamanho da partição de apenas uma chave (já que todas as outras serão maiores que ela). Muitas sugestões foram dadas sobre como tornar o pior caso mais improvável. Basicamente, devemos escolher melhor o nosso elemento de partição. Algumas maneiras típicas são:

• escolher aleatoreamente
• escolher a mediana dos elementos no inicio, fim e meio da partição
• escolher a mediana de uma amostra das chaves

Todos estes aperfeiçoamentos aumentam o processamento, portanto o tempo médio irá aumentar. O pior caso continua sendo proporcional a N², porém será mais difícil ele acontecer na prática.

Outro aperfeiçoamento que pode ser feito no QuickSort (e em outros) é usar um algorítimo mais simples (como a inserção direta) quando o número de elementos na partição for menor que um limite. Como já vimos, algorítimos mais simples costumam ser mais rápidos para N pequenos.

O QuickSort não é estável.

Na próxima parte vamos examinar o meu algorítmo preferido. Em seguida, nas duas partes finais, vamos finalmente ver código!

Algorítmos de Ordenação - Parte IV

Neste post vamos ver um algorítmo de ordenação um pouco esquisito e menos conhecido.

Ordenação por Incrementos Decrescentes - Shell Sort

Este algorítmo foi inventado por Donald L. Shell, e se baseia na idéia de que podemos ordenar mais rápido se começarmos movendo as chaves distâncias maiores, para que eles cheguem mais rapidamente nas posições finais.

Para usar o Shell Sort, você precisa ter ou gerar uma lista de incrementos decrescentes, onde o último é um. Iniciamos a ordenação ordenando os elementos espaçados pelo primeiro (e maior) incremento. Em seguida, ordenamos os elementos espaçados do segundo incremente e assim por diante. No último passo ordenamos os elementos espaçados de 1, ou seja, todos os elementos. Nos primeiros passos estamos ordenando conjuntos com poucas chaves mas bem diferentes, no final estamos ordenando conjuntos com muitas chaves mas quase totalmente ordenadas. Por este motivo podemos usar a inserção direta para a ordenação de cada conjunto.

Confuso? Vamos a um exemplo, ordenando 8 números usando os incrementos 4, 2 e 1. Vamos ter portanto 3 passos: no primeiro ordenamos 4 conjuntos de 2 chaves, no segundo 2 conjuntos de 4 chaves e no último um único conjunto com as 8 chaves. A figura abaixo mostra os dados originais e o resultado de cada passo.

Exemplo de ordenação por Incrementos Descrescentes

A análise do desempenho deste algorítmo é muito complexa. A escolha dos incrementos é um ponto chave, mas não é simples determinar qual seria uma boa escolha. Knuth sugere como razoável a série 1, 4, 14, 40, 121, etc, na qual cada número é igual a três vezes o anterior mais um. A série deve parar dois números antes de ultrapassar o número de itens a ordenar. Por exemplo, para ordenar 100 itens usaríamos 1, 4 e 13. Usando estes tempos, o tempo médio é proporcionala N^1.25 e pior caso proporcional a N^1.5. Memória adicional pode ser necessária para guardar os incrementos (se os calcularmos antecipadamente), a série sugerida possui log₃(N) incrementos. O Shell Sort não é estável.

Na próxima parte desta série vamos ver o algoritmo mais conhecido de ordenação (pelo menos no nome) - o Quicksort.

06/08/07: Acertados os subscripts e superscripts.

Divagações sobre Efetividade, Eficiência e Eficácia

Este texto surgiu da promoção do blog Efetividade.net, que está premiando artigos para comemorar o seu primeiro ano de vida. Ao contrário de outros textos que estão participando, este meu artigo não traz dicas ou soluções, apenas muito questionamento.

O que é Efetividade?

Há muito tempo atrás, se ouvia que eficiência era fazer bem alguma coisa e eficácia era fazer bem a coisa certa. E a onde entra a efetividade? Uma rápida consulta à wikipedia me faz crer que a efetividade é atualmente usada como equivalente ao que eu conhecia como eficácia. A eficácia foi rebaixada a fazer a coisa certa enquanto que a eficiência continua relacionada a fazer bem (com bom aproveitamento dos recursos).

Por trás de toda estas palavras e definições está uma grande questão: determinar o que é A Coisa Certa. A necessidade destas múltiplas palavras se deve principalmente a termos situações frequentes em que alguém (ou algo) fez tudo certo (por uma definição) e o resultado foi errado. Ou vice-versa (compare a seleção brasileira na copa de 82 com o time do Dunga na Copa América).

Métricas é uma Solução?

Métricas são sempre apresentadas como uma solução, muitas vezes até como algo essencial. Embora eu acredite na necessidade e na utilidade de métricas, cada vez questiono mais a crença da métrica como solução.

Estou lendo (bem devegar, há muito tempo) um livro chamado "Measuring and Managing Performance in Organizations", de Robert D. Austin (indicação do Joel On Software). Resumindo a teoria apresentada, usamos métricas para incentivar pessoas a fazerem A Coisa Certa. Entretanto, as pessoas vão procurar otimizar as métricas (até o ponto em que isto não compense frente aos incentivos) e acabar por se distanciar dA Coisa Certa (o que o autor chama de Dysfunction). Se você remunera o vendedor pelo volume do faturamento, ele concede descontos demais; se você o remunera por margem, ele atende mal clientes importantes por outros motivos (volume, boa referência para o mercado, etc); se você cria a "formula perfeita", provavelmente ela é tão complicada que o vendedor não vai se dar ao trabalho de entender e vai fazer o que quiser enquanto estiver obtendo uma remuneração satisfatória.

O Curto, o Médio e o Longo Prazo

No início do curso de Engenharia, um professor disse que a essência da Engenharia era achar o compromisso correto. Isto vale para a maioria das coisas. É frequente termos que optar entre uma solução rápida e barata que resolve o problema agora, mas vai trazer problemas mais para frente, e uma solução mais complexa e cara que achamos que vai ser mais tranquila no futuro. Qual destas soluções é mais efetiva?

Uma situação do meu dia a dia é quando me pego fazendo algo repetitivo. Será que é melhor fazer um programa (ou script) para automatizar isto? Em alguns casos continuo até hoje fazendo coisas manualmente. Em outros eu investi algum tempo e fiz uma solução automática que me traz um sorriso nos lábios toda vez que uso. Porém existem casos em que perdi muito tempo fazendo um destes programas auxiliares que está encostado sem uso em algum canto do meu HD.

As Interrupções

É inegável que o meu rendimento (e a qualidade do trabalho) aumenta quando me concentro em uma única coisa. Por outro lado, isto aumenta o tempo de resposta para as outras, o que irrita quem está esperando por elas. Aliás, o simples fato de achar que os outros vão ficar irritados acaba me irritando.

O mundo atual quer o instantâneo. Você pede para a pessoa enviar solicitações por e-mail e a pessoa liga dali a 5 minutos para perguntar se você recebeu o e-mail. Se você não atende o telefone, ligam no celular ou ligam para quem está no lado. No final, será que ser interrompido constantemente é mais efetivo que tentar bloquear o mundo por algumas horas?

Um dos artigos interessantes concorrendo na promoção do Efetividade.net é o Frango Tosco. Um ponto que me preocupou: a preparação demora cerca de 75 minutos, dividida em 6 passos sinalizados pelo apito do microondas. Para mim isto não funcionaria, estas seis interrupções me deixariam louco (sem contar que eu provavelmente ia xeretar entre elas, só para me certificar que está tudo correto).

Concluindo

Como avisei no início, este artigo não traz soluções. Não tenho a resposta para as perguntas que fiz e nunca estou plenamente satisfeito com as opções que fiz. A única coisa positiva que posso dizer é que me sinto mais satisfeito questionando as opções do que seguindo cegamente uma lista de regras.

Algorítmos de Ordenação - Parte III

Estes primeiros algorítmos são bastante óbvios, embora não apresentem bom desempenho.

Straight Insertion Sort (Ordenação por Inserção Direta)

Este é um dos mais simples algorítmos de ordenação e funciona como um jogador de cartas organizando a sua mão. Durante a execução deste algorítmo, as primeiras chaves estão ordenadas (no início esta parte esta vazia, no final todas as chaves foram ordenadas). Pegamos a primeira chave ainda não ordenada e achamos o seu lugar nas já ordenadas e a inserimos aí. Repetimos isto até que todas as chaves estejam ordenadas (ver a Figura 1) Este algorítmo pode levar a muitas movimentações de chaves, principalmente se elas estiverem em ordem inversa no início. Ele é bastante simplas de codificar, não requer memória adicional e é estável. É evidente que os tempos médio e máximo são proporcionais a N².

Figura 1 - Ordenando por Straight Insertion

Bubble Sort (Ordenação por Bolhas)

A idéia aqui é semelhante à inserção direta, mas, ao invés de fazermos várias comparações e depois inserir a chave atual no lugar correto, trocamos imediatamente de lugar a chave atual com a anterior se descobrimos que uma deve vir antes da outra. Desta forma os valores menores sobem para o topo da lista, como bolhas na água (ver a Figura 2). Como o Straight Insertion, é muito simples, não requer memória adicional, é estável e os tempos médio e máximo são proporcionais a N².

Figura 2 - Ordenando com o Bubble Sort (passo final)

Na próxima parte vamos ver um algorítmo menos comum, o Shell Sort.

Algorítmos de Ordenação - Parte II

Como Comparar Algorítmos de Ordenação

Alguns critérios normalmente usados para comparar algorítmos de ordenação são:

• Velocidade de execução
• Necessidade de Memória Adicional
• Estabilidade

Velocidade de Execução

Este é normalmente o critério mais importante. Não se pode, entretanto, esquecer que a velocidade vai depender de vários fatores.

É intuitivo que quanto mais itens temos para ordenar, mais tempo vai demorar. A forma como o tempo aumenta com o aumento dos itens varia conforme o algorítmo.

Considere o sequinte algorítmo simples: examinamos os N itens, um a um, e separamos o primeiro; repetimos o processo para os N-1 intens restantes e assim por diante. A ordenação levará N+(N-1)+(N-2)+...+1 passos. Esta soma resulta em N²/2 passos, daí dizermos que este algorítmo leva um tempo proporcional a N² para ordenar N itens. Veremos nos próximos artigos que um bom algorítmo reduz isto para N*log(N) passos. Na maioria dos casos, quanto melhor o algorítmo, mais complexos serão os passos e portanto eles serão mais demorados. Mesmo assim, para um N grande log(N) é muito menor que N.

Por exemplo, vamos supor que temos um programa que demora N² microsegundos para ordenar N itens e outro que leva 100*N*log(N) microsegundos (em outras palavras, cada passo do segundo programa demora 100 vezes mais que cada passo do primeiro).

Para ordenar 10 itens, o primeiro algorítmo demora 100 microsegundos e o segundo 1000 microsegundos. Ordenando 100 itens, os tempos sobem para 10000 e 20000 microsegundos. Para 1000 itens, o primeiro levará 1000000 de microsegundos (mais de 16 minutos), enquanto que o segundo levará apenas 300000 (5 minutos).

Não é o caso do algorítmos simples apresentado acima, mas o tempo para os algorítmos mais sofisticados vai depender dos dados serem ordenados. Isto nos obriga a falar em tempo médio e em tempo do pior caso. Por exemplo, veremos que o Quicksort possui um tempo médio proporcional a N*log(N) e um tempo do pior caso proporcional a N². Isto significa, que o Quicksort é normalmente muito rápido, porém às vezes é muito lento!

A velocidade depende também das características do computador. A ordenação envolve principalmente comparar e mover chaves. Computadores diferentes podem levar tempos relativos diferentes para estas duas operações. Por exemplo, suponha que as chaves sejam valores em ponto flutuante. Pode existir uma grande diferença nas velocidades de comparação entre um computador com unidade de ponto flutuante e um computador que necessite fazer uma chamada de biblioteca. Neste segundo computador pode fazer sentido minimizar as comparações, mesmo que isto signifique mais movimentações. O resumo da história é que um algorítmo que funcione bem num computador pode não se dar tão bem em outro.

Necessidade de Memória Adicional

Alguns algorítmos são capazes de ordenar os dados nas posições em que eles estão armazenados, usando memória adicional apenas para trocar de posição duas chaves. Outros necessitam de memória adicional proporcional ao tamanho dos dados sendo ordenados. Os algorítmos descritos nesta série necesitam de nenhuma ou muito pouca memória adicional.

Estabilidade

Dizemos que um algorítmo é estável se ele manter chaves iguais na mesma ordem em que elas estão na entrada. Dizendo de outra maneira, se nós aplicarmos o algorítmo a dados já ordenados, a saída será idêntica à entrada. É sempre possível converter um algorítmo instável em um estável usando a posição original da chave como o último critério de ordenação. Por exemplo, se estamos usando ponteiros para ordenar as chaves, comparamos os ponteiros se as chaves são iguais.

No próximo artigo da série vamos ver os primeiros algorítmos de ordenação.

Algorítmos de Ordenação - Parte I

Nesta série vamos ver alguns conceitos básicos de ordenação e ver como alguns algorítmos tradicionais funcionam.

Introdução

Comecei a escrever a primeira versão deste texto em inglês, em 2000, mas nunca cheguei a concluir. Para quem tiver curiosidade, aqui está a versão do texto que encostei em 2002.

Ordenar coisas é uma tarefa comum na programação. É também um daqueles tipos de tarefas onde o algorítmo utilizado faz uma grande diferença. Os exemplos que vão acompanhar esta série, além de conterem implementações dos algorítmos descritos, vai ajudar a ver como eles funcionam e comparar o desempenho deles.

Ordenação também é o tipo de tarefa que clama por uma boa análise matemática. Você não vai encontrar isto aqui! A "bíblia" da ordenação, na minha opinião, é o livro "The Art of Computer Programming, Vol 3 - Sorting and Searching" de Donald E. Knuth. Foi com este livro que aprendi o que apresento aqui. Alguns podem achar o estilo do Dr Knuth ultrapassado (implicando com os exemplos em linguagem assembler de um computador hipotético), mas dificilmente se acha um texto tão completo como o dele.

Por último, muitas linguagens possuem em sua biblioteca padrão funções genéricas de ordenação e muitos preferem simplesmente as usar sem conhecer como funcionam. Como veremos, existem vários pontos interessantes sobre a ordenação e nem sempre a escolha de um algorítmo é simples. Mesmo que você nunca precise escrever a sua própria função de ordenação, muito pode ser aprendido estudando estes algorítmos.

O Que é Ordenar?

Basicamente, estamos falando em colocar coisas em uma certa ordem. Nós temos itens (ou registros) a serem ordenados. Cada item está associado a uma uma chave. Nosso objetivo é re-arranjar os itens de forma que eles fiquem em ordem crescente (ou decrescente) de chave.

Nesta série vamos nos concentrar em ordenar um vetor de chaves numéricas (inteiras) que estão na memória. As idéias apresentadas podem ser facilmente expandidas:

• Podemos usar os mesmos algorítimos com qualquer tipo de chaves. Tudo que precisamos é uma forma de comparar as chaves e uma maneira de movê-las. Por exemplo, podemos ter chaves alfanuméricas e ordená-las sem considerando maiúsculas e minúsculas como equivalentes (de forma que 'aBc' seja igual a 'AbC' ou 'ABC')
• Podemos ter múltiplas chaves. Se as primeiras chaves são iguais, nós comparamos as segundas e assim por diante até acharmos uma diferença ou testarmos todas as chaves. Se as chaves forem alfanuméricas, podemos fazer isto simplesmente as concatenando. Se misturarmos chaves de tipo diferente, nossa comparação pode usar o operador && do C (ou construção equivalente de outra linguagem) para testar as chaves na ordem correta.
• Ao mesmo tempo em que ordenamos as chaves, ordenamos os registros. Se os registros forem pequenos, simplesmente os movemos junto com as chaves. Se os registros forem grandes, nós guardamos ponteiros para os registros junto com as chaves. Durante a ordenação, movemos junto as chaves e os ponteiros. Ao final seguimos os ponteiros para obter os registros na ordem certa (veja Figura 1).
• Se as chaves não cabem na memória, fazemos a ordenação por partes, gravando as partes em arquivos temporários. Ao final fazemos um merge das partes (ver Figura 2).

Figura 1 - Usando ponteiros para não mover os registros

Figura 2 - Dividindo o arquivo em partes, ordenando e fazendo o merge

Republicando artigos meus da Sharepedia

Estou colocando abaixo links para download dos artigos que eu tinha colocado na finada Sharepedia. A qualidade dos artigos é bem variável, peço desculpas antecipadamente pela pretenção da série "Guia dos Mestres"...

Animal

Um exemplo simples (bobo ?) de uso de árvore binária: um jogo de adivinhação de animais. A árvore consiste em vária perguntas do tipo Sim / Não, onde as folhas são animais. O programa vai percorrendo a árvore (fazendo as perguntas e obtendo as respostas). Ao chegar em uma folha, pergunta se este é o animal que o jogador pensou. Se não for, pergunta qual o animal e pede uma pergunta para distinguí-lo da resposta errada. A árvoré é então atualizada com a nova pergunta e o novo animal.

Arquivo

Avisa se esqueceu disco na unidade

CDAlert é um pequeno utilitário que testa se existe disco removível quando é feito shutdown. Ilustra como descobrir as unidades existentes e seus tipos, através da API Win32.

Arquivo

Aviso (Recado tipo Post-It)

Este é um programinha simples para colocar uma mensagem na tela. A mensagem pode ser colocada na linha de comando, chamando o programa sem parâmetro é apresentado um dialogo para digitacao da mensagem. A janela com a mensagem fica por cima das demais janelas e pode ser arrastada. Para fechá-la, basta dar um double click. Ilustra algumas técnicas menos comuns de programação Windows direto com a API.

Arquivo

Desenhando em Diálogo

O objetivo deste artigo é apresentar uma forma de desenhar gráficos em uma caixa de diálogo, utilizando diretamente a API do Windows. O artigo inclui um programa exemplo que mostra um relógio de ponteiros em um diálogo.

Arquivo

Como fazer um Editor Simples

Este exemplo ilustra três formas de criar um editor simples: usando um Edit Box, usando um Rich Edit controle e "na raça". O código está em C e usa apenas o Win32 SDK .

Arquivo

Launch - demo do uso de CreateProcess

Este programa mostra como usar a função CreateProcess da API do Windows para disparar uma aplicação.

Arquivo

Lista Ligada - O Guia dos Mestres

Este artigo explica a teoria e a prática das Listas Ligadas, com atenção particular à implementação em C e C++.

Arquivo

Exemplo de Uso de ListView

Exemplo de uso de ListView com imagens, usando C + API. Nova versão implementa ordenação pelo cabeçalho das colunas. Destaque para os infames dados usados no exemplo!

Arquivo

Screen Savers - "O Gua dos Mestres"

Uma descrição bem detalhada de como funciona e como fazer screen savers. Inclui dois exemplos, um usando a biblioteca Scrnsave.lib e o outro chamando direto as API do Windows.

Arquivo

Simulação de um Computador

Um exemplo (simples) de como simular um computador. O simulador apresenta na tela os registradores e a memória de um computador hipotético. Programas podem ser entrados em linguagem de máquina ou em assembler. Interessante para quem quer aprender um pouco sobre linguagem de máquina, sobre a simulação de computadores ou mesmo sobre programação Windows.

Arquivo

Threads & Sockets: exemplo de uso

Este código mostra como usar threads e sockets para fazer uma comunicação cliente/servidor.

Arquivo

Controlando um LED com um PIC - Parte III

Nesta parte final, vamos ver como testar o nosso projeto na prática.

Montagem do Circuito

Praticamente qualquer tipo de montagem pode ser feito, tomando-se o cuidado de usar um soquete para o PIC, já que ele terá que ser retirado do circuito para ser programado. Para uma montagem de teste, use uma breadboard como a abaixo:

Para uma montagem definitiva, você pode usar uma placa padrão. Existem algumas cujas trilhas seguem o mesmo padrão das breadboards.

Programação do PIC

O modelo de PIC selecionado armazena o programa em memória Flash, o que permite a gravação de forma relativamente simples (inclusive sem retirar o PIC do circuito, o que o nosso projeto não inclui).

De uma forma simplificada, a programação do PIC requer:

• alimentá-lo através dos pinos VDD e VSS, tipicamente 5 e 0 volts.
• colocar uma tensão de programação no pino GP3, tipicamente 13 volts.
• enviar comandos e receber respostas serialmente pelo pino GP0, usando o pino GP1 para sinalizar os bits (clock).

Para isto normalmente é usado um hardware adicional (o programador) que de um lado se conecta ao PIC e de outro a um PC (através de uma porta serial, paralela ou USB). Uma aplicação no PC controla a programação.

Existem vários modelos de programador para o PIC no mercado, com características diversas. Os mais aventureiros podem até projetar o seu próprio gravador a partir das especificações da Microchip.

No meu caso, usei o programador McFlash da Mosaico que permite a programação a partir do próprio MPLAB.

Referências

• PIC12F629/675 Datasheet - http://www.microchip.com/
• Desbravando o PIC - David José de Souza - Editora Érica

Controlando um LED com um PIC - Parte II

Nesta parte vamos ver o software do nosso projeto.

Uma vez que o software é bastante simples, vamos desenvolvê-lo em linguagem assembler e usar o ambiente de desenvolvimento MPLab, disponibilizado gratuitamente pela Microchip.

Definido o algorítmo é só pegar o manual de referência do PIC e enfrentar as esquisitices do conjunto de instruções. Alguns pontos a destacar:

• a execução começa sempre no endereço 0, a interrupção desvia sempre para o endereço 4. No endereço 0 foi colocado um GOTO para desviar para o corpo do programa, que fica após o tratamenteo da interrupção.


• é preciso tomar cuidado com o fato dos registradores de controle (SFR) estarem armazenados em dois bancos (BANK0 e BANK1). Antes de acessar um registrador de controle é preciso garantir que o banco correto está selecionado.


• no início da rotina de interrupção é preciso salvar os registradores W e STATUS. Ao final da interrupção estes registradores precisam ser restaurados.


• o PIC não possui instruções de desvio condicional convencionais. As instruções condicionais são sempre na forma de Skip If, na qual a instrução seguinte é pulada se uma determinada condição for verdadeira.

No inicio do programa deve-se definir a configuração do PIC, que será gravada em uma área especial da Flash:

; Configuração do PIC;
- habilita BrownOut Detect;
- desabilita pino MCLR;
- desabilita Watchdog;
- usa o oscilador interno
__CONFIG _BODEN_ON & _MCLRE_OFF & _WDT_OFF & _INTRC_OSC_NOCLKOUT

Uma variável (MODO_LED) é usada armazenar o modo atual de atuação do LED (APAGADO, ACESO ou PISCANDO). Quando for detectado o pressionamento do botão o modo será avançado para o modo seguinte (circularmente).

; Estados do LED
#define APAGADO  0
#define ACESO    1
#define PISCANDO 2

; Loop principal
PRINC
   BTFSS MODO_BOTAO, BOTAO_APERT
   GOTO  PRINC  ; aguarda apertar o botão
   BCF   MODO_BOTAO, BOTAO_APERT ; limpa indicação
   MOVF  MODO_LED,W
   XORLW APAGADO
   BTFSC STATUS,Z
   GOTO  ACENDER
   MOVF  MODO_LED,W
   XORLW ACESO
   BTFSC STATUS,Z
   GOTO  PISCAR

; Estava piscando, vamos apagar
   MOVLW APAGADO
   MOVWF MODO_LED
   BCF   LED
   GOTO  PRINC

; Estava apagado, vamos acender
ACENDER
   MOVLW ACESO
   MOVWF MODO_LED
   BSF   LED
   GOTO  PRINC

; Estava aceso, vamos piscar
PISCAR
   MOVLW PISCANDO
   MOVWF MODO_LED
   GOTO  PRINC

O tratamento do botão possui uma pequena dificuldade: quando o botão é apertado ou solto, por alguns instantes o contato abre e fecha rapidamente. Isto é chamado de 'bounce' (algo como 'quicar'). Para evitar que cada uma destas aberturas/fechamentos seja tratada como um aperta/solta do botão, é preciso aguardar que o sinal do botão fique estável por um certo tempo.

Para fazer o LED piscar e executar o 'debounce' do botão, vamos configurar o Timer 0 do PIC para gerar interrupções periodicamente. O valor que adotei foi aproximadamente 50 milisegundos, o que permite um piscar nítido e fazer o debounce simplesmente exigindo duas leituras iguais em interrupções consecutivas.

; Inicia o timer
   BANK0
   BCF   INTCON,T0IF ; limpa a interrupção do timer
   MOVLW .256-CNT_TIMER
   MOVWF TMR0  ; programa o timer
   BSF   INTCON,T0IE
   BSF   INTCON,GIE ; permite interrupções

O piscar do LED fica bastante simples: na interrupção testamos se o modo atual é piscar; se sim invertemos o sinal no pino do LED.

   MOVF  MODO_LED,W
   XORLW PISCANDO
   BTFSS STATUS,Z
   GOTO  TRATA_BOTAO
   MOVLW 0x01
   XORWF GPIO,F  ; pisca o LED
TRATA_BOTAO

A lógica do botão é um pouco mais complicada. São usados três valores lógicos, armazenados em três bits de uma variável (MODO_BOTAO):

• o estado do botão na interrupção anterior, que é atualizado ao final de toda interrupção


• o estado do botão após o debounce, que é atualizado somente quando o estado atual do botão é igual ao estado anterior


• uma indicação de que o botão foi apertado, que é ligado na interrupção quando o estado após o debounce passa de solto para apertado. Esta indicação é limpa no laço principal do programa, após tratar o acionamento da tecla.

; Controles do estado do botão
#define BOTAO_ANT   0x01 ; este bit indica o estado anterior
#define BOTAO_DEB   0x02 ; este bit tem o valor c/ "debounce"
#define BOTAO_APERT 0x04 ; este botão indica que foi detectado
                        ;  um pressionmento do botão

TRATA_BOTAO
   BTFSC BOTAO  ; testa o botão
   GOTO  SOLTO

; botao apertado
   BTFSC MODO_BOTAO,BOTAO_ANT ; testa leitura anterior
   GOTO  APERT_10
   BSF   MODO_BOTAO,BOTAO_ANT ; mudou
   GOTO  FIM_INT
APERT_10     ; igual a vez anterior
   BTFSC MODO_BOTAO,BOTAO_DEB
   GOTO  FIM_INT  ; ja estava apertado
   BSF   MODO_BOTAO,BOTAO_APERT ; apertou agora
   BSF   MODO_BOTAO,BOTAO_DEB
   GOTO  FIM_INT

SOLTO      ; botao solto
   BTFSS MODO_BOTAO,BOTAO_ANT
   GOTO  SOLTO_10
   BCF   MODO_BOTAO,BOTAO_ANT ; mudou
   GOTO  FIM_INT
SOLTO_10     ; igual a vez anterior
   BCF   MODO_BOTAO,BOTAO_DEB

O fonte completo está aqui

Na próxima parte vamos encerrar esta série, vendo como montar o circuito e as referências para maiores detalhes.

Controlando um LED com um PIC - Parte I

Este é mais um post sugerido pelas buscas que trouxeram alguem a este blog. Nesta série vamos ver como controlar um LED usando um microcontrolador PIC.

O Objetivo

O objetivo desta série é mostrar o projeto do hardware e software de um pequeno dispositivo que ilustra como controlar um LED usando um PIC. O dispositivo possui um LED e um botão que será usado para controlar o estado do LED (apagado, piscando ou aceso).

O Projeto de hardware

Para este projeto selecionei um modelo de PIC bastante simples, o 12F675. O modelo 12F629 pode ser usado sem nenhuma alteração e é simples alterar tanto o hardware como o software para outros modelos.

O PIC 12F675 tem as seguintes vantagens para este projeto:

• pode operar com alimentação de 2 a 5.5V, o que simplifica a operação com baterias e pilhas
• disponível em encapsulamento DIP de 8 pinos, o que simplifica a montagem
• possui um oscilador interno de 4MHz, dispensando a conexão de um cristal ou ressonador
• memória Flash para o programa, o que simplifica a gravação e regravação

O primeiro passo para o projeto de hardware é examinar o datasheet do microcontrolador, que pode ser baixado do site da Microchip.

No datasheet verificamos que podemos operar de 4 a 10 MHz com uma alimentação de 3 a 5.5 V (a operação com tensões entre 2 e 3 Volts requer clock inferior a 4MHz). Minha opção foi operar com o oscilador interno de 4MHz usando uma bateria de 3V (Duracell DL2032 ou equivalente). O positivo da bateria deve ser conectado ao pino 1 (VDD) do PIC e o negativo ao pino 8 (VSS).

O LED e o botão são conectados a pinos de entrada/saída de uso geral, que no 12F675 são qualquer um dos outros 6 pinos (para ser mais preciso, o botão não pode ser ligado ao pino 4 pois vou usar o pull-up interno que não está disponível no GP3). Escolhi o pino 7 para o LED e o pino 2 para o botão.

O LED, como diz a sigla, é um diodo emissor de luz. Quando submetido a uma tensão direta acima de sua tensão de queda ele emite uma luz com intensidade proporcional à corrente. Existem vários modelos de LEDs, que emitem as mais diversas cores. A tensão de queda é tipicamente de 2V e uma intensidade boa para um LED montado em painel pode ser obtida com uma corrente de 10 mA.

Voltando ao datasheet do PIC, verificamos que um pino de entrada/saída é capaz de gerar ou absorver uma corrente de até 125mA e tem uma tensão de 0,6V (nível zero) ou VDD-0.7V (nível um). A capacidade de corrente do PIC permite ligar um LED diretamente das duas maneiras abaixo:


Na primeira maneira, com o LED ligado entre o pino do PIC e VSS, o valor do resistor em série (conforme a lei de Ohm) deve ser

(VDD - 0.7 - 2,0)/0,01 = 30 ohms

Analogamente, com o LED ligando entre o pino do PIC e VDD, o valor do resistor deve ser

(VDD - 0.6 - 2,0)/0,01 = 40 ohms

No primeiro caso, o LED acende quando o pino do PIS está no nível um, no segundo quando está no nível zero. No meu circuito adotei a primeira maneira com um resistor de 33 ohms.

Para a ligação do botão poderia ser usado uma forma semelhante às vistas para o LED. Olhando mais uma vez o datasheet, o PIC considera nível zero um valor abaixo de 0.15*VDD (0.45V) e nível um um valor acima de 0.25*VDD+0,8 (1,55V). Poderíamos calcular a partir destes dados valores apropriados para o resistor em série com o botão que garantam os níveis apropriados com um valor reduzido de corrente.

Entretanto, a Microchip já fez estes cálculos e disponibiliza internamente ao PIC um resistor de weak pull-up, que faz com que um pino aberto seja lido como em nível um. Desta forma, o botão pode ser ligado diretamente ao VSS e erá lido como nível zero quando fechado e como nível um quando aberto.

A lista de componentes para o circuito fica sendo:

• 1 PIC 12F675 (ou 12F629)
• 1 LED
• 1 Botão de contato momentâneo
• 1 Resistor de 33 Ohms 1/8 W
• 1 Bateria de 3V
• 1 Suporte para a bateria

O circuito completo fica:



No próximo post da série vamos ver o software.

Construindo um Compilador - Parte 4

Recordando o que vimos na parte anterior, o algorítmo que estamos apresentando realiza uma análise descendente, na qual se procura identificar itens sintáticos cada ver mais simples. Em cada instante temos como objetivo reconhecer um determinado item sintático. A gramática indica quais os itens sintáticos que compõem o nosso objetivo, Alguns destes itens correspondem diretamente a item léxicos (são os chamados símbolos terminais), outros correspondem a itens sintáticos mais complexos (os não-terminais). No caso dos não-terminais, vamos salvar temporariamente o nosso objetivo atual numa pilha enquanto reconhecemos este novo objetivo.

A estrutura principal para realizar a análise sintática representa o grafo sintático e é um vetor de estruturas que armazenam os nós. Exemplificando em C:

typedef struct
{
int simb; // código do símbolo
int fTerm; // TRUE se simbolo terminal, FALSe se não-terminal
int alt; // índice do nó alternativo (-1 se não tiver)
int seg; // índice do nó seguinte (-1 se não tiver)
} NO;

Um segundo vetor armazena o índice do primeiro nó de cada não-terminal:

typedef struct
{
char *nome; // nome do não terminal (para debug)
int prim; // índice do primeiro nó
} NT;

Desta forma, quando queremos reconhecer um não-terminal, partimos do primeiro nó e vemos se ele corresponde ao item léxico atual. Se sim, obtemos o próximo item léxico e passamos ao nó seguinte. Se for diferente, vamos examinar o nó alternativo.

Estas tabelas podem ser constantes dentro do programa ou carregadas dinamicamente a partir de um arquivo. O trecho abaixo corresponde ao nosso exemplo da parte anterior:

// códigos dos terminais
#define T_VAZIO 0
#define T_NUM 1
#define T_MUL 2
#define T_DIV 3
#define T_SOMA 4
#define T_SUB 5
#define T_ABRE 6
#define T_FECHA 7

// códigos dos não-terminais
#define NT_FATOR 0
#define NT_TERMO 1
#define NT_EXPR 2

NT TabNaoTerm[] =
{
{ "Fator", 0 },
{ "Termo", 4 },
{ "Expr", 8 }
}

NO GrafoSint[] =
{
/* simb fTerm alt seg */
/* 0 */ { T_NUM, FALSE, 1, -1 },
/* 1 */ { T_ABRE, TRUE, -1, 2 },
/* 2 */ { NT_EXPR, FALSE, -1, 3 },
/* 3 */ { T_ABRE, TRUE, -1, -1 },

/* 4 */ { NT_FATOR, FALSE, -1, 5 },
/* 5 */ { T_MUL, TRUE, 5, 4 },
/* 6 */ { T_DIV, TRUE, 6, 4 },
/* 7 */ { T_VAZIO, TRUE, -1, -1 },

/* 8 */ { NT_TERMO, FALSE, -1, 9 },
/* 9 */ { T_SOMA, TRUE, 10, 8 },
/* 10 */ { T_SUB, TRUE, 11, 8 },
/* 11 */ { T_VAZIO, TRUE, -1, -1 },

}

O terminal T_VAZIO indica a situação em que o item léxico atual não precisa ser consumido para o reconhecimento.

O algorítmo do analisador sintático fica assim:

#define TAM_PILHA
int pilha[TAM_PILHA];
int topo = 0;

// retorna TRUE se sucesso, FALSE se encontrou erro
int AnalisadorSintatico ()
{
int item; // item léxico atual
int no; // no atual

// Nosso objetivo é uma expressão
no = TabNaoTerm [NT_EXPR].prim;

// le o primeiro item léxico
item = AnalisadorLexico ();

while (TRUE)
{
if (no != -1)
{
if (GrafoSint[no].fTerm)
{
if (GrafoSint[no].simb == T_VAZIO)
no = GrafoSint[no].seg; // reconheceu vazio
else if (GrafoSint[no].simb == item)
{
no = GrafoSint[no].seg; // reconheceu item léxico
item = AnalisadorLexico ();
}
else if (GrafoSint[no].alt != -1)
no = GrafoSint[no].alt; // não reconheceu mas tem alternativa
else
return FALSE; // sem alternativas: erro sintático
}
else
{
// temos um novo objetivo
if (topo >= TAM_PILHA)
return FALSE; // pilha cheia
pilha[topo++] = no;
no = TabNaoTerm [GrafoSint[no].simb].prim;
}
}
else
{
// reconheceu um não terminal
if (topo > 0)
{
// continua no seguinte
no = pilha[--topo];
no = GrafoSint[no].seg;
}
else
return TRUE; // chegamos ao final
}
}
}

Obviamente estamos fazendo grandes simplicações neste código.

Em primeiro lugar, estamos ignorando o tratamento de erros sintáticos. No mínimo o analisador deveria indicar em que ponto ocorreu o erro. Uma outra informação é a indicação do que era esperado. Por último existe a questão de recuperação do erro, permitindo prosseguir a análise. Embora tudo isto possa ser feito automaticamente a partir do grafo sintático, na prática é preferível programar um heurística específica para a linguagem, considerando quais os erros mais comuns e quais as recuperações que introduzem menos erros espúrios.

Neste algorítmo estamos apenas percorrendo o gráfico e verificando se a entrada obedece à gramática. Um compilador ou interpretador precisa executar ações à medida em que os itens são reconhecidos. Isto pode ser feito acrescentando ao nó uma indicação de qual rotina semântica deve ser executada (esta indicação pode ser um índice ou um ponteiro).

Na próxima parte vamos examinar um pouco mais o tratamento semântico.

De volta com o post #100 e um balanço

Após um mês de muito trabalho, estou retomando os posts no blog com um balanço deste um ano e meio de existência e uma idéia do que pretendo publicar no futuro.

Pois é, este é o centésimo post. Num levantamento rápido, os 99 posts passados envolveram principalmente Programação (27), Livros (22) e Microsoft (21). Como o gráfico abaixo (total de visitas por semana) mostra, tem algumas pessoas passando por aqui, mesmo quando não tem um post novo. As séries sobre gerenciamento de memória e construção de compiladores são as mais populares . Os posts sobre livros também tem os seus hits, principalmente por gente procurando eBooks para baixar.

O número de posts me parece satisfatório, considerando o tipo de posts que eu procuro fazer. De um modo geral, eu evito os posts curtos que tem apenas um link (principalmente para notícias efêmeras). A maioria dos meus posts exige um tempo razoável de pesquisa e escrita e certamente não dá para fazer um por dia.

Segue uma lista parcial de idéias para posts (ou série de posts) futuros; aceito sugestões nos comentários:

• Concluir a série "Construindo um Compilador" (urgente!)
• Projeto de Hw com PIC (controlando um LED, construindo um velocímetro para bicicleta)
• Gravação de CD usando a interface IMAPI do Windows
• A Reserva de Mercado de Informática
• Memórias (programando em Assembler 8bits e participando do projeto de um clone do IBM-PC na Scopus, desenvolvendo um software de comunicação de dados, etc)
• Meus primeiros computadores (TK-82C e o Apple II)

This may take a few minutes...

O Sql Server 2005 Express (veja também aqui) é uma adição interessante para muitas software houses e desenvolvedores. Não é "livre" nem o primeiro a ser "grátis", mas tem um bom conjunto de características, um nome conhecido no mercado e uma ótima integração com as ferramentas Microsoft. A Microsoft explicitamente permite que o instalador seja distribuído junto com outras aplicações (desde que elas não concorram com o Access).

Venho usando-o com bastante sucesso, até que fui instalar em um Grande Cliente. Tudo ia bem até que instalação deu uma parada no meio. Dando uma olhada no log (o que é fácil, basta clicar em um link na tela do instalador) deu para ver que parecia estar todando muito devagar. Após cerca de uma hora, cancelei a instalação. Tentei novamente mudando alguns parâmetros e aconteceu a mesma coisa. Após várias tentativas (inclusive baixando novamente o instalador), jogamos a toalha e pusemos a culpa no sistema operacional. Depois de um mês (Grande Cliente é assim mesmo) tentamos de novo e novamente "parou".

Felizmente, nesta altura a Microsoft já tinha publicado um fix. Veja os detalhes aqui:

http://support.microsoft.com/kb/910070/en-us

SYMPTOMS
The Microsoft SQL Server 2005 Setup program may take a very long time to be completed. Sometimes this time will be more than 24 hours.

Obviamente é algo raro (a explicação está no artigo). A Microsoft disponibiliza um hotfix (um remendo que você precisa pedir para eles para receber), um workaround editando o registry e uma quebra galho muito simples: desligue o cabo de rede antes de instalar (e ligue de novo ao final da instalação).

Pois é, foi só soltar o cabo de rede do micro (só complicado porque era um servidor de teste que estava em outro local).

Comprando OnLine com Cartão de Crédito

Há muito tempo compro coisas pela Internet pagando com cartão de crédito, e acho que hoje foi a primeira vez que tive uma experiência (de uso) ruim. Muita gente tem medo de comprar pela Internet, eu tenho mais medo de comprar em loja ou posta de gasolina onde o atendente some por alguns minutos com o seu cartão (e afinal basta xerocar, anotar ou memorizar uns poucos dados para "roubar" o cartão).

O problema que tive foi um problema de usabilidade, não de segurança. A coisa começou meio estranha quando a loja virtual criou um "pré-pedido" sem perguntar sobre a forma de pagamento. No e-mail de confirmação veio um "opção de pagamento disponível em nossa página 24h após o recebimento desta confirmação". Lendo nas entrelinhas, o pedido colocado na loja é conferido (particularmente preços e estoque) antes de permitir o pagamento. Talvez seja até mais seguro, mas é diferente do que se vê na maioria das lojas virtuais.

Algumas horas depois, veio o aviso que o "status do seu pedido mudou para aguardando pagamento". É um erro clássico (no qual também caio com frequência): falar com o usuário como se estivesse falando para o compilador. De qualquer forma, quer dizer que deu tudo certo com o pré-pedido e você pode voltar ao site para escolher a forma de pagamento.

Escolhi cartão de crédito Mastercard. O pagamento em si não é feito pela loja virtual, mas sim por um site padrão de pagamento; quando clico em prosseguir aparece o aviso de popup bloqueado. Volto atrás, habilito popups para o site. Aparece o formulário para entrar com os dados, devidamente desformatado no Firefox. Entre com os dados e ... tenta abrir um novo popup (que é bloqueado, pois agora é um outro domínio). Beco sem saída, será que o cartão foi debitado? Dica para os programadores Web: a maioria dos usuários usa bloqueador de popup, os browsers mais recentes saem com o bloqueador ligado. Se possível, não use popup. Se for usar, avise ao usuário para desbloquear e coloque um link para abrir a janela se o popup for bloqueado. Tem muita gente que faz isto direito.

Consulto o cartão de crédito e parece que não foi debitado. Resolvo arriscar novamente, usando o IE com o bloqueio de popup desligado. As janelas abrem, a formatação está correta. E no final um aviso de "erro no processamento". E novo beco sem saída.

Aguardo mais um pouco e decido tentar com um cartão Visa. O site para entrar com os dados é outro. As coisas vão melhor até que aparece dois botões em branco. Clico em um deles e aparece um message box de confirmação, também com o texto em branco. Sim ou Não. Sim... e acabo de desistir! Repito tudo e clico no outro botão. Aparece uma mensagem dizendo sucesso e um número de confirmação. Mais nada. Numa das primeiras telas aparecia um comprovante bonitinho com o impresso nos PDVs; será que custava muito apresentar de novo no final, para imprimir junto com o número de confirmação?

De qualquer forma, o pagamento parece ter sido feito correto e sem duplicidade. Mas a experiência foi terrível!

Obs.: Continuo na correria, ainda não consegui escrever a próxima parte da construção de compiladores, nem retomar uns outros textos maiores que eu comecei há muito tempo atrás. Só escrevi isto porque precisava desabafar!

A Dura Vida do Desenvolvedor para Windows CE

A história do Windows CE

Em 1994 a Microsoft iniciou o desenvolvimento de um novo sistema operacional de 32 bits, destinado a sistemas dedicados e/ou embarcados. Dadas as restrições de memória e capacidade de processamento destes sistemas, foi adotado um subconjunto da API Win32, reduzindo a funcionalidade e removendo funções redundantes. Embora tenham sido aproveitadas as APIs e idéias dos outros dois Windows de 32 bits da Microsoft (Windows 95 e NT), o código fonte do Windows CE é em grande parte novo. Como o NT, O Windows CE foi projetado para suportar diversos modelos de processadores.

Uma característica importante do Windows CE é a modularidade. Um fabricante de hardware pode selecionar os módulos que necessita (usando uma ferramenta gráfica, o Plataform Builder) e gerar uma versão do Windows CE contendo apenas os recursos que necessita. Neste processo o fabricante acrescenta os drivers e aplicações específicas ao seu equipamento. Uma das aplicações importantes a serem acrescentadas é o Shell que é o módulo responsável pela interface com o operador (por exemplo, apresentação do desktop para os dispositivos que o tiverem).

Ao contrário das demais versões de Windows, a Microsoft não comercializa o Windows CE diretamente para usuários. A Microsoft licencia o Windows CE para os fabricantes que o disponibilizam para os usuários.

Palm-Sized PC, Pocket PC e Windows Mobile

A própria Microsoft gera versões específicas do Windows CE. Basicamente, a Microsoft define os requisitos da plataforma de hardware (em alguns casos bastante específicos), desenvolve alguns drivers e aplicações (notamente o Shell) e licencia o resultado para os fabricantes de hardware. Os times que geram estas versões específicas são times separados dos que desenvolvem o sistema operacional.

Uma destas versões foi o Palm-sized PC, baseado no Windows CE 2.1. Esta foi a primeira experiência da Microsoft em projetar um PDA. O resultado não foi muito animador: a interface com o usuário era desconfortável e o desempenho irritante no hardware disponível na época.

A plataforma PDA seguinte veio em 2000 com um novo nome: PocketPC (talvez devido às pressões da Palm contra o nome anterior). Baseado no Windows CE 3.0 e com uma especificação de hardware mais recheada de MHz e Megabytes, permitiu à Microsoft fincar o pé definitivamente no mercado de PDAs.

A versão seguinte foi o Pocket PC 2002 (a versão original do Pocket PC foi retroativamente denominada de Pocket PC 2000), ainda baseada no Windows CE 3.0.

O nome foi alterado novamente na versão seguinte, que foi o Windows Mobile 2003, baseada no Windows CE .Net 4.0 (sim, o nome do sistema também mudou). A ele se seguiram o Windows Mobile 2003 Second Edition e o Windows Mobile 5.0.

Vários fabricantes fabricaram e fabricam para o "mercado de consumo" PDAs baseados nestes padrões. Estes fabricantes costumam lançar com frequência novos modelos. Uma pergunta comum dos compradores destes equipamentos é sobre a atualização do sistema operacional. Como vimos, os fabricantes é que tem a responsabilidade de gerar e disponibilizar estas novas versões, o que normalmente não preferem não fazer.

Um outro mercado que usa estes padrões é o de coletores de dados. Neste caso estamos falando de equipamentos mais robustos e caros (às vezes dez vezes mais caros que um PDA) e que são produzidos com volumes muito menores. Por estes motivo, não é incomum os fabricantes comercializarem a atualização do sistema operacional. Um outro ponto é que as exigências de hardware destes padrões são às vezes rigorosas demais para o mercado de coletores de dados (por exemplo, o Pocket PC exige um microfone e um botão para a função de gravação de voz). Em alguns modelos os fabricantes de coletores preferem fugir destes padrões e gerar a sua própria versão do Windows CE. Mesmo nos modelos compatíveis com os padrões às vezes é oferecida uma opção de menor custo baseada em uma versão customizada do Windows CE.

Desenvolvendo Para o Windows CE

A primeira dificuldade já deve estar óbvia: conviver com uma nomenclatura mutante e confusa.

O segundo ponto é que cada uma destas plataformas tem um SDK próprio. Particularmente no caso dos coletores de dados, existem diferenças de fabricante para fabricante e os modelos antigos (dada a sua robustez) se recusam a morrer. No caso dos coletores baseados em um padrão da Microsoft, normalmente é necessário instalar primeiro o SDK da Microsoft e depois o SDK do fabricante.

Algumas pessoas pensam que sendo o Windows CE um Windows, deve dar para executar os mesmos programas que no desktop. Como vimos, a API do Windows CE é diferente da Win32 do desktop. Na maioria dos casos, o processador é diferente. A memória disponível é muito menor e não existe disco. E, talvez o mais importante, a forma de operação é completamente diferente.

Inicialmente a Microsoft vendia Toolkits para o Visual C++ e Visual Basic (versões 5 e 6) para o desenvolvimento para o CE. No caso do VB, a linguagem era semelhante ao VBA e não ao VB propriamente dito.

Junto com o Pocket PC, a Microsoft lançou o eMbedded Visual Tools, composto pelo eMbedded Visual C++ (eVC) e do eMbedded Visual Basic (eVB). Estes produtos são gratuitos e sairam direto na versão 3. O eVC é bastante completo, incluindo os frameworks ATL e MFC. O eVB continuou sendo baseado no VBA.

Com o Pocket PC 2002 foi lançado o eVC 4 (o eVB morreu na versão 3 mesmo). Os SDKs anteriores continuavam exigindo o eVC3. É possível instalar na mesma máquina as duas versões do eVC, porém o ícone do programa é o mesmo e o Open With... se recusa a distinguir as duas.

Com o Windows CE .Net passou a estar disponível o Compact Framework para desenvolvimento usando C# e VB.Net. Entretanto, isto não ficou pronto a tempo para inclusão no Visual Studio .Net 2002 e acabou sendo disponilizado como um download gratuito. O Visual Studio .Net 2003 incluiu isto (da mesma forma que incluiu outras funcionalidades e correções de bugs que não ficaram prontas em 2002) e o download para o VS 2002 sumiu.

O Visual Studio 2005 absorveu a funcionalidade do eVC. E chegamos assim à data atual, quando resolvo fazer meu primeiro projeto em C para CE no VS 2005. Seleciono Smart Sevice Win32 Project, informo o nome do projeto e ... nada. Discretamente na linha de status aparece a mensagem "project creation failed". Vários minutos no Google e localizo a solução mágica, que reproduzo abaixo, em:
http://blogs.msdn.com/jeffabraham/archive/2007/02/13/are-you-having-issues-creating-native-projects.aspx

1) [opcional] Acenda uma vela vermelha de cada lado do micro. Sacrifique uma galinha preta sobre o teclado.

2) Feche o Visual Studio.

3) Chame o RegEdit e navege para

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Ext\PreApproved

4) Crie uma nova chave com o nome

{D245F352-3F45-4516-B1E6-04608DA126CC}

5) Feche o RegEdit e rode novamente o Visual Studio

É um problema conhecido que ocorre quando se faz upgrade para o Vista ou se instala o Internet Explorer 7. A solução está incorporada no Service Pack 1 do VS 2005.

É mole?

Bill Gates

Ocasionalmente alguém cai no meu blog procurando a "Biografia de Bill Gates". A biografia que eu conheço e lí é Gates de Stephen Mames e Paul Andrews. A história do surgimento da industria dos computadores pessoais (incluindo a Microsoft) pode ser lida em Fire in the Valley de Paul Freiberger e Michael Swaine.

Da leitura destes livros me veio uma imagem de Bill Gates diferente daquilo que a media normalmente apresenta. Sem dúvida ele tem grande conhecimento técnico e é um grande programador. Também é inegável o seu faro em reconhecer oportunidades. Entretanto, tudo isso me parece secundário frente ao que considero ter sido o principal motivador de Bill: fechar o negócio. Para mim é esta agressividade comercial a principal marca da Microsoft, pelo menos até o ano 2000. Agressividade esta que às vezes encrencou a Microsoft e que levou a práticas algumas vezes consideradas ilegais pela justiça americana.

Relato abaixo duas situações famosas, descritas em detalhes nos livros que citei, e que acredito reforçarem a minha opinião sobre Bill Gates.

O Surgimento da Microsoft

A maioria das pessoas já ouviu falar de como Paul Allen foi correndo mostrar para Bill Gates a edição de janeiro de 1975 da revista Popular Electronics que trazia na capa o Altair 8800 da MITS e neste momento os dois decidiram fazer um interpretador BASIC para ele. Muitos talvez saibam que Bill Gates ofereceu o produto para a Altair, apesar de não ter começado o desenvolvimento, e como a primeira versão foi construída rapidamente. O que poucos sabem é que este foi um mau negócio na ponta do lápis.

O Altair 8800 que aparecia na capa era um mockup de papelão (o protótipo, que não incluia ainda o famoso barramento S-100, foi perdido no transporte). Para aparecer na capa da revista, Ed Roberts (o dono da MITS) chutou um preço bem baixo e corria o risco de ter prejuizo. A solução era lucrar nos acessórios e o principal deles era a placa de memória. O kit original vinha com apenas 256 bytes de Ram, quem queria fazer algo sério precisava da placa de 4K e do BASIC da Microsoft. A placa de memória tinha uma margem imensa e um imenso problema: não funcionava. Não demorou muito para alguém se cansar da placa de memória da MITS, projetar uma e descobrir que dava para vender uma placa que funcionava por um preço bem inferior. Ed Roberts resolveu apelar para o seu trunfo: o BASIC. A MITS tinha um contrato de exclusividade do BASIC da Microsoft para processadores 8080 e compatíveis e Ed Roberts passou a vender o BASIC por $150 para quem comprasse a placa da MITS e $500 para os outros. A reação dos clientes foi a pirataria do BAISC, que resultou em uma famosa "Carta Aberta aos Hobistas" do Bill Gates.

A exclusividade da MITS estava prejudicando a Microsoft com mais que as baixas vendas do BASIC. Embora a Microsoft tivesse fechado acordo com outros fabricantes que usavam outros processadores, o primeiro grande negócio em vista era com a Tandy/Radio Shack cujo TRS-80 usava o Z80 que estava coberto pela exclusividade da MITS. Em meados de 1977 a Microsoft estava em dificuldades financeiras. A sorte da Microsoft foi que Ed Roberts tinha negligenciado itens básicos do acordo, inclusive não pagando os royalties combinados. Com base nisto a Microsoft conseguiu cancelar o acordo na justiça e fechar o negócio com a Tandy e equilibrar as contas.

O Sistema Operacional do PC-IBM

Quando a IBM resolveu desenvolver o seu computador pessoal, ela decidiu usar componentes de mercado, inclusive o BASIC da Microsoft e o sistema operacional CP/M da Digital Research. Como todos sabem o PC-IBM acabou sendo lançado com um sistema operacional da Microsoft, o MS-DOS.

Até o final de sua vida, Gary Kildall (dono da Digital Research) teve que agüentar a versão de que ele tinha ido passear em seu avião ao invés de atender a IBM. Na verdade, Kildall cuidava mais da parte técnica da Digital Research, quem cuidava dos contratos com os fabricantes de hardware era a sua esposa, Dorothy.

No dia da visita da IBM, Gary foi cumprir uma visita agendada anteriormente com outro cliente (pilotando realmente o seu avião) e Dorothy atendeu os representantes da IBM. Antes de dizer qualquer coisa, um advogado da IBM solicitou que ela assinasse um NDA (Non-Disclosure Agreement). Dorothy fez aquilo que todos nós sabemos ser o certo antes de assinar um documento: leu-o cuidadosamente. O documento era terrivelmente favorável à IBM. Dorothy fez aquilo que os advogados sempre recomendam: recusou-se a assinar e passou a negociar o texto do contrato. Embora este impasse tenha sido vencido, a relação entre a Digital Research e a IBM nunca foi boa. Também não ajudou nada o fato do CP/M-86 ter sido repetidamente adiado.

Como foi que Bill Gates se comportou quando a IBM entrou em contato com ele? A reação inicial dele foi: "a IBM é uma grande companhia". Ao contrário de Kildall, Gates se envolvia diretamente nas negociações. E não teve dúvidas em cancelar uma reunião com o chairman da Atari para atender a IBM, vestir um terno e gravata e convocar para a reunião um assistente - Steve Balmer. Ao ser apresentado o NDA, Bill Gates deu uma passada de olhos e assinou sem hesitar.

Enquanto que a diferença de cultura entre as empresas era um problema na relação entre a Digital Research e a IBM, Bill Gates se esforçava para agradar a IBM, apesar de tanto a Microsoft como a Digital Research terem um bando de hippies nos seus quadros. Quando, preocupada com os atrasos e os conflitos com a Digital Research, a IBM perguntou a Bill Gates se ele poderia fornecer também um sistema operacional, ele já tinha a resposta na ponta da língua (embora ainda não tivesse o produto).

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.

Três Livros Sobre C#

No ano passado incluí na minha coleção três livros sobre C# de características bem difererentes:

Pro C# 2005 and the .NET 2.0 Platform, Third Edition
Andrew Troelsen

Um livro bastante ambicioso, que tenta descrever a linguagem C#, a plataforma .Net e o framework .Net (e ainda encontra espaço para falar de conceitos gerais sobre programação orientada a objetos). É um livro imenso (ainda estou no primeiro terço), mas que gostaria de ter lido quando comecei a aprender C#. É claro que alguns assuntos como Windows Forms, ASP.Net, ADO.Net e Web Services ficam um pouco corridos (afinal existem livros inteiros sobre estes assuntos), mas é um dos poucos livros que explica bem o básico (no sentido de fundamento não de simples).

ASP.NET 2.0 Website Programming
Marco Bellinaso

A idéia do livro é ótima: descrever a construção de um site real do começo ao fim. Cada capítulo possui três partes: o problema, o projeto e a solução. Na primeira são descritos os requisitos, na segunda são discutidas as alternativas para atendê-los e na terceira é apresentado com detalhes a implementação adotada. O código todo está disponível para download (inclusive foi adotado como um dos exemplos pela Microsoft, veja aqui) e o site está on-line em http://www.dotnet2themax.com/thebeerhouse/.

O autor não foge de assuntos complexos nem economiza linhas de código e utiliza os recursos mais recentes do C# e do ASP.Net. O único porém é a diagramação do livro que deixa a leitura cansativa.

Altamente recomendado para quem desenvolver uma aplicação Web mais real que os Next/Next/Finish dos wizards do Visual Studio.

Visual C# 2005 - A Developer´s Notebook
Jesse Liberty

Este é um livro curto, que se concentra em algumas poucas (e importantes) novidades do C# 2.0 e Visual Studio 2005 e se destaca pela parte visual (imita um caderno com direito a um quadriculado de fundo e manchas de copo). O texto é muito bom, mas nem sempre muito profundo ou completo. Resumindo, é um livro extremamente agradável de ler, voltado para quem já conhece as versões anteriores do C# e quer se atualizar.

PS: Para quem está aguardando a terceira parte da série sobre Compiladores, peço um pouco de paciência, pois as coisas estão um pouco corridas.

Livro do Mês - Montenegro

Em torno da compra deste livro existe um história. No começo de dezembro, meu pai pediu de presente de Natal o livro "Casimiro Montenegro Filho A Trajetoria De Um Visionario" de Ozires Silva e Décio Fischetti. Procurando na internet, encontrei o livro nas Livrarias Cultura e Siciliano. Nos dois locais o livro estava com prazo de 6 dias úteis, porém a Siciliano tinha um preço um pouco menor e ofertas de parcelamento e frete grátis para compras acima de um certo valor.

Deste forma, resolvi comprar na Siciliano este livro junto com outros para dar de presente aos sobrinhos. Descobri também nas buscas a existência de um outro livro sobre o mesmo assunto: "Montenegro - As aventuras do marechal que fez uma revolução nos céus do Brasil" de Fernando Morais (autor de Olga e Chatô, que eu já tinha ouvido falar mas ainda não li). Resolvi surpreender meu pai e comprar os dois livros, o que me dava como vantagem adicional uma segurança extra no caso do livro não chegar a tempo para o Natal.

E realmente o livro não veio. Como desconfiei desde o começo, o prazo de 6 dias significava que o livro não estava em estoque e tinha que ser encomendado à editora. Por motivos que desconheço, a editora não entregou o livro à Siciliano (que me manteve informado sobre o atraso e desde o começo deu a opção de cancelar o pedido). A Livraria Cultura teve mais sucesso e o livro chegou até a ser objeto da "entrega foguete" (entrega no mesmo dia para São Paulo). Em meados de fevereiro resolvi entregar os pontos e cancelar o pedido na Siciliano e comprar da Cultura. Neste ponto a Cultura estava indicando prazo de 3 dias e poucas unidades em estoque (no momento está com prazo de 15 dias úteis). No lugar da entrega foguete as opções de frete eram expresso e normal. A entrega normal tinha um preço baixo (R$ 3) e um prazo razoável (3 dias) e foi minha opção. O livro chegou em dois dias via Sedex, de Porto Alegre (onde a Cultura tem uma loja).

Folheando o livro antes de entregar para o meu pai fiquei com a impressão de ser inferior ao do Fernando Morais, o que veio a ser confirmado pelo meu pai. Curioso sobre o assunto do livro, peguei emprestado o Montenegro do Fernando Marais para ler e é ele o "livro do mês" de fevereiro.

Montenegro - As aventuras do marechal que fez uma revolução nos céus do Brasil

O livro é a biografia de Casimiro Montenegro Filho, um cearense nascido em 1904 e foi o principal responsável pela criação do ITA (origem do interesse do meu pai).

O primeiro sentimento que me veio lendo o livro foi o meu grande desconhecimento da história do Brasil, talvez fruto de ter feito primário e ginásio numa época em que se ensinava que Tiradentes tinha a mesma aparência que Jesus. A história de Montenegro se entrelaça com a história do Brasil, dos acontecimentos que testemunhou na infância até a ditadura militar de 64 que o afastou do ITA, passando pelas revoluções de 30 e 32.

Na minha cabeça, o ITA era uma escola militar e uma fábrica de loucos. Nada sabia das idéias e motivos por trás da sua criação. Embora Montenegro fosse um militar, na sua concepção o ITA era um instituto primordialmente civil. Inspirado no MIT americano, o ITA foi uma tentativa de criação de um instituto de ensino de alto nível, com independência administrativa, para formar profissionais altamente qualificados e viabilizar o surgimento de uma industria aeronáutica nacional. A existência da Embraer é uma prova de que grande parte dos objetivos foram cumpridos (embora a independência nunca tenha vindo por completo e foi sufocada após o golpe de 64).

As dificuldades para a construção do ITA foram imensas. Burocracias, intrigas, invejas e paranoias se somaram à audácia de um idéia extremamente ambiciosa.

É bastante claro o esforço do autor em obter informações precisas sobre os fatos, não hesitando em apresentar múltiplas versões quando as pesquisas foram inconclusivas. O livro é bastante cativante, fazendo o leitor se apaixonar pela causa de Montenegro, passando a vibrar com as conquistas e sofrer com os reveses. Os inúmeros 'causos' relatados oferecem ao mesmo tempo um tom humorístico e uma idéia dos inúmeros contratempos enfrentados.

Na história de Montenegro estão elementos que continuam presentes: as intrigas políticas, a questão da educação, os sonhos de fazer no Brasil coisas no mesmo nível que o Primeiro Mundo.

Leitura altamente recomendada.

Fontes do DOS para Download

De vez enquando dou uma olhada no statcounter para ver por onde as pessoas chegaram a este blog, tipicamente por uma busca no google.

Uma busca curiosa foi pelos fontes do DOS. Embora até onde eu saiba a Microsoft não publicou os fontes do MS-DOS, quem estiver curioso sobre como fazer um sistema compatível tem pelo menos duas opções:

• FreeDOS: um projeto de software livre, é usado pelo excelente DosBox para simular um PC antigo e permitir rodar programas antigos (particularmente jogos).

• DR-DOS: tem uma história longa e curiosa. A Digital Research era a lider dos sistemas operacionais para os computadores profissionais de 8 bits com o CP/M-80. No lançamento do PC, a IBM deu preferência ao MS-DOS. Após anos tentando sem sucesso vender o CP/M-86, a Digital Research aproveitou um momento em que a Microsoft estava ocupada com os projetos do Windows e do OS/2 para lançar o DR-DOS. Altamente compatível com o MS-DOS, o DR-DOS 5 vinha com utilitários adicionais e utilizava os recursos de gerenciamento de memória do 386. A resposta da Microsoft foi o MS-DOS 5 e uma série de ações que posteriormente foram julgadas anti-competitivas (alguns documentos a respeitos podem ser vistos aqui). A Novell adquiriu a Digital Research e lançou um bundle do DR-DOS 6 com um pacote de rede local peer-to-peer (durante toda a vida do MS-DOS, a comunicação via rede local sempre foi um item a parte e que era explorado por empresas como a Novell e a Lantastic). Apesar de todo este esforço, o DR-DOS nunca conseguiu decolar e entre várias mudanças de dono acabou tendo os fontes liberados para o uso não comercial.

Construindo um Compilador - Parte 2

Nesta parte vamos ver como se constrói um analisador léxico. Como vimos na parte 1, ele é responsável por reconhecer os itens léxicos no fonte.

Itens léxicos típicos são identificadores de variáveis e rotinas, palavras reservadas, constantes e símbolos. Cada um destes itens se caracteriza por uma seqüência de caracteres que segue uma regra simples (por exemplo, "um identificador deve começar por uma letra e possuir somente letras e números"). Isto recomenda o uso de máquinas de estado para o reconhecer os itens léxicos. Toda vez que o analisador léxico é chamado para reconhecer o próximo item léxico, ele parte de um estado inicial e vai mudando de estado a cada caractere examinado, até reconhecer o item ou detectar uma seqüência inválida de caracteres (um "erro léxico").

Por exemplo, vamos considerar um caso simples, em que os itens léxicos são números inteiros decimais e as operações + e -. De uma forma livre, teríamos o seguinte analisador léxico na linguagem C:

estado = INICIAL;
while (estado != FINAL)
{
c = ProximoCaracter();
switch (estado)
{
case INICIAL:
  if (c == EOF)
  {
     item = EOF;
     estado = FINAL;
  }
  else if (isdigit(c))
     estado = NUMERO;
  else if (c == '+')
  {
     item = MAIS;
     estado = FINAL;
  }
  else if (c == '-')
  {
     item = MENOS;
     estado = FINAL;
  }
  else if (!isspace(c))
  {
     item = ERRO;
     estado = FINAL;
  }
  break;
case NUMERO:
  if (c == EOF)
  {
     item = NUMERO;
     estado = FINAL;
  }
  if (!isdigit(c))
  {
     DevolveCaracter(c);
     item = NUMERO;
     estado = FINAL;
  }
}
}

Para não estender mais o código, não estamos guardando o valor do número (o que fica como exercício para o leitor). Reparar que eventualmente o código acima examina um caractere além do final do item e precisa "devolvê-lo". Tipicamente um analisador léxico não precisa guardar estados entre uma chamada e outra nem voltar atrás nos seus passos.

Algumas linguagens possuem idiossincrasias que dificultam o analisador léxico. Por exemplo, algumas versões do FORTRAN permitem colocar espaços no meio de identificadores, criando seqüências de difícil análise como:

DO 10 I = 1, 10

Somente ao encontrar a vírgula o analisador léxico descobre que os itens léxicos são <DO> <10> <I> <=> (comando DO) ao invés de <DO10I> <=> (o que seria um comando de atribuição).

O analisador léxico é também responsável por desprezar os comentários nos fontes.

No caso de identificadores e palavras reservadas, a máquina de estado apenas isola a seqüência de caracteres. O analisador léxico precisa também identificar o item.

No caso das palavras reservadas, normalmente existe uma tabela ou lista onde a seqüência isolada deve ser procurada. Uma forma simples, mas ineficiente, é fazer uma busca seqüencial. Uma forma mais inteligente é ordenar previamente a lista e fazer uma busca binária.

Uma forma ainda melhor é usar hashing. No hashing, calcula-se um número (hash) a partir da seqüência de caracteres e usa-se este número como índice para a tabela.

O principal problema com o hashing é que várias seqüências podem gerar o mesmo hash (gerando uma colisão). Ao inserir um item numa tabela de hash, se a posição já estiver ocupada é preciso fazer uma lista ligada na posição para colocar o novo item. Ao fazer uma busca, é preciso fazer uma busca seqüencial nesta lista ligada.

Uma opção para diminuir as colisões é aumentar a faixa de valores para o hash, porém isto leva ao desperdício de memória. No caso das palavras reservadas, a lista é constante, o que permite escolher previamente uma função de hash que evite colisões. Por exemplo, pode-se criar uma função parametrizada e deixar um computador procurando exaustivamente os parâmetros que otimizem a função de hash.

Uma vez determinado que uma seqüência não é uma palavra reservada, o analisador léxico deve tentar descobrir o tipo de identificador. Isto é feito procurando a seqüência em tabelas de nomes de variáveis, funções, etc construída pelo analisador semântico. Estas tabelas podem usar o hashing para otimizar a busca. Um truque simples mas eficaz consiste ao encontrar um item na lista ligada da tabela de hash mover este item para o início da lista. Isto faz com que a lista automaticamente se ordene em função do uso dos itens.

Em algumas linguagens é permitido usar um identificador que ainda não foi declarado e portanto tem tipo ignorado. Isto não afeta o analisador léxico porém complica o analisador sintático e pode obrigar o analisador semântico a segurar a geração do código objeto até que o identificador seja declarado.

Na próxima parte vamos ver o coração do compilador, o analisador sintático.

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.