quinta-feira, março 31, 2011

Pequenos Imãs e Micro Controladores - Parte 3

Uma opção mais sofisticada de detectar um imã é usando um sensor de Efeito Hall.

O Efeito Hall consiste na produção de uma diferença de voltagem em um condutor quando este é submetido a um campo elétrico. Hoje vamos ver um componente, o Allegro A1321, que possui internamente um elemento Hall e o circuito necessário para produzir uma tensão de saída proporcional ao campo magnético.

terça-feira, março 29, 2011

Corujando: Equipe Poli de Baja

Neste domingo passado (27/3) estive em Piracicaba (a terra da pamonha?) para acompanhar o final da competição Baja SAE Brasil 2011 e torcer pela Equipe Poli de Baja, da qual o meu filho é integrante.


O Baja SAE é uma competição estudantil promovida pela Sociedade de Engenheiros Automotivos, onde estudantes de engenharia projetam e constroem um pequeno veículo off-road. A competição envolve não somente provas práticas mas também apresentações do projeto.


No domingo foi a prova de enduro, onde os veículos correm por quatro horas em uma pista de terra cheia de lombadas e curvas complicadas. Na hora que os pilotos estão se acostumando com o gosto da poeira, entra um caminhão tanque na pista e transforma o pó em lama, principalmente nas curvas.


Foi uma prova de resistência não somente para os veículos e pilotos, mas também para os torcedores que precisaram suportar as quatro horas sob sol escaldante (das 10 às 14) e mais uma hora e meia até a divulgação do resultado.

No final os dois carros da FEI ficaram com os dois primeiros lugares (mantendo uma longa hegemonia na categoria), os dois da Poli com o terceiro e quarto e em quinto o carro Manguejaba 2 da Universidade Federal de Pernambuco. Festa para as três universidades, que com o resultado vão representar o Brasil na competição mundial que será nos EUA.


A prova teve até cobertura da imprensa; veja as matérias da Revista Auto Esporte:

Baja: Paulistas dominam pódio
Bajeiros tem torcida fiel
Competição de Bajas: FEI vence enduro
Terra neles!
Que Formula 1, nada!

Atualização 12:30 - Mais uma reportagem, com muitas fotos:

Equipes da FEI vencem a Baja SAE Brasil-Petrobras
Fotos

domingo, março 20, 2011

HQ do Mês: The Phantom 1937-1939

O segundo volume de "The Phantom - the complete newspaper dailies" prossegue com a definição do personagem. A arte de Ray Moore se encaixa perfeitamente; os bandidos parecem terríveis, as mulheres são lindas e o Fantasma oscila entre o misterioso, o ameaçador e, algumas vezes o divertido. Um bom subtítulo seria "Encontros e Desencontros" - o Fantasma e Diana passam grande parte das histórias um tentando encontrar o outro.

sexta-feira, março 18, 2011

Minhas Aventuras com "Parsing": LR Parser (parte 2)

Continuando a minha descrição do LR parser, vejamos a sua arquitetura e o algorítimo básico. Um LR Parser é normalmente implementado como um autômato descendente (ou autômato com pilha), que é (digamos) uma máquina de estados "turbinada" com uma pilha, movido por duas tabelas.

quinta-feira, março 17, 2011

Pequenos Imãs e Micro Controladores - Parte 2

Uma das opções mais simples de detectar um imã é através de um Reed Switch.

Um reed switch é uma chave montada na forma de dois (ou mais) contatos montados em uma ampola de vidro. Ao ser exposta a uma campo magnético suficientemente forte, um (ou ambos) os contatos se movem.

quarta-feira, março 16, 2011

Minhas Aventuras com "Parsing": LR Parser (parte 1)

Embora o Earley Parser seja capaz de analisar uma gama bastante grande de gramáticas, o seu desempenho pode deixar a desejar. Minha próxima opção é o LR Parser.

Este algorítimo é bastante usado em compiladores reais, com o auxílio de pequenos truques devido às excentricidades das linguagens de programação reais.

terça-feira, março 15, 2011

Pequenos Imãs e Micro Controladores - Parte 1

Imãs são uma daquelas coisas que nos encantam desde a infância, quando parecem nos conceder poderes mágicos de atuar à distância. Entre as suas infinitas aplicações, imãs podem ser usados para disparar sensores.

Já mostrei aqui um exemplo disso, o Spoke-o-dometer.


Infelizmente, não parece ser fácil encontrar imãs de qualidade à venda aqui nesta terra onde canta o sabiá. Felizmente, graças à loja do Laboratório de Garagem, consegui comprar alguns imãs muito pequenos na Sparkfun. Os imã tem o formato de cubo, com aresta de 0,125 polegada. Fica mais fácil entender este tamanho colocando o imã sobre uma moeda de 10 centavos:


O tamanho diminuto não significa que o imã é fraco. Trata-se de um imã de Neodymium, o tipo de imã permanente mais forte que se conhece atualmente. Os dez imãs que comprei vieram grudados na forma de uma barra; é tão difícil destacar um deles que a primeira impressão é que é uma barra contínua e não cubos isolados.


Nos próximos posts vamos ver que tipo de sensores podemos acionar com estes imãs e, mais adiante, como conectar estes sensores a microcontroladores.

segunda-feira, março 14, 2011

Minhas Aventuras com "Parsing": Implementando o Earley Parser

Passada a "Semana ZX81", é hora de retomar esta série de posts, apresentando uma implementação em C do algorítimo Earley Parser.

O programa apresentado supõe entrada e saída no formato do problema "ET Phone Home". O arquivo de teste original pode ser baixado de http://www.ime.usp.br/~cef/Xmaratona/problems/io/. Entretanto, o código apresentado aqui não é uma solução adequada, por ser muito lento.

domingo, março 13, 2011

EBook (Grátis) do Mês: Tarzan The Untamed

Continuando com a minha releitura dos livros de Tarzan, cheguei ao sétimo deles: Tarzan The Untamed (literalmente "Tarzan o Indomado", que eu traduziria para "Tarzan o Selvagem" mas que ganhou nestas terras a tradução "Tarzan o Destemido").

sexta-feira, março 11, 2011

ZX81/TK82C: Emuladores

Espero que vocês tenham se divertido com esta sequência de posts em comemoração aos 30 anos do ZX81. Embora não tenha como proporcionar para vocês a experiência que foi comprar um computador pessoal (em uma época em que isto era um artigo raro aqui no Brasil) e conectá-lo a uma TV e gravador K7, os mais aventureiros podem experimentar um pouco o gostinho de programar o ZX81, através de emuladores.

Você nem precisa instalar no seu micro, pode rodar dentro do browser o emulador em Java que está em http://www.vavasour.ca/jeff/ts1000/. Atenção que ele segue fielmente o layout do teclado do ZX81 (por exemplo, você precisa digitar Shift L para obter =).

Se você prefere baixar um emulador para rodar localmente, a página http://www.zx81.nl/ tem várias opções.

O TS1000 é um emulador bem simples e compacto, para executar sob DOS (roda em tela cheia no WIndows XP). Usa um mapeamento fiel.

O ZX81 é outro emulador DOS, mas não roda diretamente sob o XP (use o DosBox). Suporta algumas teclas do PC como backspace, igual e setas.

O Xtender é um emulador DOS mais sofisticado e roda em tela cheia sob o XP. Se você gostar do XTender, a página oficial (http://www.delhez.demon.nl/) permite você comprar (por US$20) a versão registrada que inclui 240 programas e um aplicativo para puxar as suas fitas K7 para o PC.

EightyOne é um emulador para Windows, cheio de recursos. Uma versão mais nova (e os fontes) pode ser baixada de http://www.aptanet.org/eightyone/.

quinta-feira, março 10, 2011

ZX81/TK82C: Literatura

O ZX81 foi um dos primeiros microcomputadores realmente acessíveis e teve inegável sucesso tanto na Inglaterra (seu país de origem) como nos EUA (onde foi licenciado com o nome de Timex 1000 e Timex 1500) e em vários outros países (na forma de clones não autorizados). Não é surpresa que esta popularidade tenha gerado um bom mercado para publicações.

O livro abaixo tinha por objetivo ajudar novatos na programação BASIC e não acrescentava muito ao manual, porém continha uma grande quantidade de exemplos bem comentados.


A revista americana Sync se dedicava exclusivamente ao ZX81 e era composta principalmente por anúncios, mas publicava programas suficientes para preencher um livro de quase 200 páginas.

Para quem queria programar algo um pouco mais sério (como jogos...) a pedida era o livro "Mastering Machine Code on Your ZX81". Impresso de forma semi-artesanal, partia da numeração hexadecimal e ia até um programa para jogar damas.

Aqui no Brasil tivemos várias revistas. A melhor delas era a Micro Sistemas (citada várias vezes nestes posts). Embora não fosse exclusiva para o TK82C (e demais clones nacionais do ZX81, pois eram vários), ela publicou artigos clássicos, notadamente os de Renato Degiovani. A Microdigital, fabricante do TK82C, publicou a revista Microhobby que se especializava em programas pequenos. A revista Microbits começou como uma fanzine e chegou a ter alguns números impressos de forma profissional e comercializados em bancas.



Quem Não Ama um Falso Positivo do Anti-Virus?

Pois é, quarta feira de cinzas, ligar o micro no começo da tarde... e o AVG reclama que o Acrobat Reader 10.1 é um Trojan (Generic21.ALDP)! Todo cheiro de um falso positivo - confirmado no final da tarde ao baixar uma atualização das definições do AVG e o aviso sumir.

Uma busca no Google mostra que não fui o único a ser brindado com isto. Será que a AVG não pensou em testar as definições com a versão atual do Acrobat Reader (em inglês)?

quarta-feira, março 09, 2011

ZX81/TK82C: Programando em Linguagem de Máquina

Embora o BASIC do ZX81 fosse suficiente para diversas aplicações, ele não tinha o desempenho necessário para jogos de ação. Para isto era necessário programar em linguagem de máquina; um pouco de código Z80 era suficiente para obter um bom desempenho, mesmo no modo SLOW.

O BASIC possui três instruções para interagir com código de máquina: PEEK, POKE e USR. A primeira possibilitava ler o conteúdo de qualquer posição de memória; a segunda permitia alterar este conteúdo; a terceira chamava uma rotina em linguagem de máquina.

Os princípios da programação em linguagem de máquina eram divulgados nas revistas e livros (mais detalhes na próxima parte). Uma vantagem que possuía era a experiência em programação com o 8080, tanto na escola como no trabalho. Conhecendo o processador Z80, alguns detalhes básicos da organização da memória do ZX81 e o endereço de algumas rotinas do seu firmware, você estava pronto para sair programando... no papel.

Escrito um programa em linguagem assembly, era preciso convertê-lo no código de máquina. Embora eu eventualmente tenha conseguido obter um Assembler que executava no próprio TK82C, no início eu me valia do MACRO-80 rodando em um dos micros CP/M-80 do trabalho.

Uma pergunta importante que não deve ter vindo a você é onde o código de máquina era colocado? Os comandos SAVE e LOAD salvavam e restauravam em fita K7 programas BASIC, portanto era preciso colocar o código dento de um programa BASIC. O lugar preferido era um comentário (REM), normalmente no início do código (cujo endereço era conhecido).

Surge daí uma convenção que os leitores das revistas especializadas devem lembrar até hoje. Num primeiro passo se digitava uma linha de comentário com um determinado tamanho e um programa simples (o LOADER ou MONITOR) para colocar o código no comentário. Em seguida se apagava o MONITOR (tá pensando que tem memória sobrando?) e se digitava a parte em BASIC do programa. Depois era salvar em fita e rodar, torcendo para não ter digitado algo errado (alguns Monitores mais sofisticados usavam um checksum para detectar erros de digitação).

O exemplo abaixo é um dos meus primeiros programas em assembler para o TK82C (clique para ampliar). Não foi nenhuma ideia muito original - alguém tinha publicado na revista Micro Sistemas um programa simples inspirado no Frogger e eu achei que conseguia fazer algo melhor. O resultado foi devidamente rejeitado pela Micro Sistema, por já ter publicado recentemente um programa semelhante. Avenida II acabou sendo acolhido pela MicroBits, uma revista de circulação mais modesta movida ao espírito hobbista.

"Engrish" sem Norte nem Sul

Engrish é uma forma depreciativa de se referir a textos malversados em inglês, tipicamente produzidos no oriente. Considerando-se a imensa penetração dos produtos chineses no mundo ocidental, é incrível a total falta de cuidado nos textos que os acompanham.

A imagem abaixo é do verso da embalagem de uma bussola comprada em uma loja da rede multicoisas e mais se assemelha a uma coleção aleatória de palavras; clique para se confundir:

terça-feira, março 08, 2011

ZX81/TK82C: Programando em BASIC

Para quem programa nos dias de hoje, a programação em BASIC no ZX81 deve parecer um pesadelo. O dialeto de BASIC utilizado (o Sinclair BASIC) possui várias esquisitices, a começar pela forma de digitação.

Como comentei antes, as palavras reservadas não devem ser digitadas letra a letra; existe uma combinação especial de teclas para cada uma delas. Algumas combinações são mnemônicas, como pressionar P para digitar o comando PRINT, mas outras são menos óbvias, como digitar Shift 3 para obter THEN.

As linhas do programa devem ser numeradas; não existe um processo automático de numeração ou re-numeração e os recursos de edição são grosseiros. Nas atribuições, o comando LET é obrigatório. O comando IF não dispõe da clausula ELSE.

Existem dois tipos de variáveis: numéricas (ponto flutuante) e alfanuméricas (strings). Não existe declaração de variáveis, exceto pelas matrizes. As variáveis numéricas podem ter nomes de qualquer comprimento, começando por uma letra, exceto as usados em FOR-NEXT (que devem ter nomes de apenas uma letra). As variáveis do tipo string devem ter o nome composto por uma única letra seguida de $. É possível ter matrizes de múltiplas dimensões tanto numéricas como de strings. Os tamanhos de uma matriz não precisam ser fixos, podem ser definidos por uma variável.

As imagens abaixo mostram o começo de uma aplicação de análise de circuitos elétricos que eu adaptei de um exercício da faculdade e que foi publicado na revista Micro Sistemas nos idos de 1984 (clique para ampliar).

segunda-feira, março 07, 2011

ZX81/TK82C: Características

O microcomputador ZX81 foi projetado especificamente para ser barato. Daí ter especificações baixas mesmo para a época:
  • Processador Z80 trotando a 3.25MHz
  • 1K bytes de Ram (2K no TK82C)
  • Teclado de membrana de 40 teclas
  • Modulador RF interno, para conexão a uma TV b&p pelos terminais de antena
  • Vídeo organizado em 24 linhas de 32 caracteres
  • Interface para gravador K7, com capacidade de ler e escrever a 300 bps
O ZX81 é a evolução de um modelo anterior, o ZX80. Os aperfeiçoamentos estão principalmente no firmware, com a inclusão do suporte a números de ponto flutuante e o modo "slow" (mais detalhes adiante). No lado do hardware, o ZX81 tem uma ROM maior (8K x 4K) para caber o novo firmware e utiliza um integrado custom no lugar de vários CIs padrões, reduzindo o número de CIs para 4 (o Z80, o chip custom, a Ram e a ROM). As primeiras unidades do TK82C utilizavam os CIs padrões, posteriormente a Microdigital conseguiu fabricar (ou obter) um chip custom equivalente.

A memória de 1K era insuficiente até mesmo para apresentar uma tela inteira, daí a expansão de 16K ser um acessório praticamente essencial (o que não impediu que um jogo de xadrez fosse feito para rodar nos 1K).

O teclado segue a disposição QWERTY, mas provavelmente isto é a única coisa boa a falar sobre ele. A sua construção não fornece nenhum feedback táctil - a sensação de apertar uma tecla é igual a apertar uma superfície dura. Cada tecla pode ter até cinco funções, dependendo do contexto e do uso do Shift e Function. Além de reduzir o número de teclas, isto elimina a necessidade do BASIC fazer análise léxica - ao invés de você escrever STOP digitando a letras S, T, O e P, você deve usar a tecla onde está a letra A, quando o BASIC está esperando um comando (o que é indicado por um cursor na forma de um K em reverso).


As teclas 5, 6, 7 e 8 correspondem às setas durante a edição do programa. Por este motivo, são usadas para movimentação na maioria dos jogos. O TK82C tinha um conector DIN na lateral que permitia ligar um joystick adaptado do Atari 2600 em paralelo com as teclas.


O vídeo é gerado diretamente pelo processador; o Z80 precisa comandar cada ponto a ser apresentado. Obviamente isto demanda processamento e os tempos são pouco flexíveis (o feixe de elétrons do tubo da TV não vai ficar parado esperando!). No ZX80 a imagem era gerada somente quando o computador estava esperando uma tecla, durante o processamento o vídeo apresentava ruído. No ZX81 foi acrescentado o modo SLOW, onde a interrupção NMI é usada para garantir que o vídeo será gerado durante o processamento. Entretanto, são tantas interrupções que sobra pouco tempo para processar (basicamente os retraços horizontais e verticais).

A rotina de vídeo decodifica cada um dos 256 valores possíveis em cada posição do vídeo em uma matriz de pontos fixa. Além dos caracteres comuns, são suportadas as 16 combinações produzidas dividindo cada caracter em quatro células; isto permite simular um modo gráfico de 48x64 posições. A decodificação dos caracteres usa uma tabela na ROM, Embora o firmware permita apontar para uma tabela em outro local, não existe memória neste endereço. Um hack de hardware interessante é colocar uma Ram adicional nesta faixa de endereço. Isto permite alterar por software os caracteres disponíveis.


Sobre a interface K7 podemos dizer que funcionava - a maior parte do tempo. Ocasionalmente eram necessárias algumas "mandingas"; circuitos que prometiam melhorar a gravação e leitura apareciam com frequência nas revistas especializadas. Existiam até gravadores especializados para o uso com o ZX81 e outros computadores. O mais chato é que os programas úteis costumavam demorar mais de 5 minutos para carregar - e você só descobria se teve sucesso no final.

domingo, março 06, 2011

Audio Book Grátis: Tarzan and the Jewels of Opar

O transito da volta às aulas combinada com chuva me levou de volta aos audio books grátis do AudioOwl e do LibriVox. O livro da vez foi Tarzan and the Jewels of Opar (Tarzan e as Joias de Opar).

sábado, março 05, 2011

Sinclair ZX81 - 30 anos

Foi surpreendido ontem por este artigo do The Register comemorando os 30 anos do lançamento do computador pessoal ZX81 da Sinclair. Para mim este computador tem um significado todo especial e merece alguns posts a respeito.


O primeiro computador que eu comprei foi o TK82C da Microdigital, uma cópia descarada do ZX81. Foi nos idos de 1983 que, aproveitando a minha segurança econômica de engenheiro formado há um ano e morando com os pais, desembolsei Cr$ 123.300,00 em um TK82C e uma expansão de memória de 16K bytes. Um mês depois bastei mais Cr$ 105.550,00 em uma TV 12" b&P e minha unidade de memória de massa - um gravador K7 mono.

O TK82C me levou a diversas atividades, entre as quais a contribuição de artigos para revistas e a autoria dos livros da série PC Assembler.

sexta-feira, março 04, 2011

Ruminações sobre o Malware "Android Dream"

Uma das diferenças entre o Android e o iOS é a política quanto à distribuição de aplicações. Enquanto a Apple é totalmente controladora, exigindo o uso da sua loja de aplicativos e impondo um processo de aprovação, a Google permite a carga de aplicações de diferentes fontes e possui requisitos mínimos para a publicação de aplicações na sua loja.

Eu certamente prefiro o modelo Android, prefiro eu decidir o que rodar no meu aparelho e quero poder fazer aplicações para mim e que possam ser compartilhadas com outros sem precisar da benção de terceiros. Mas é claro que com poder vem a responsabilidade.

Um dos motivos que a Apple aponta para o seu controle é evitar a propagação de malware. Não creio que o processo da App Store evite as pragas eletrônicas. Afinal, a Apple não recebe os fontes para examinar e já vimos casos da aprovação de aplicações serem revogadas quando determinadas funcionalidades foram descobertas após a aprovação.

É claro que no caso do Android é bem mais fácil distribuir malwares. No caso do "Android Dream", os criminosos pegaram aplicações já existentes, as empacotaram junto com os componentes maliciosos e colocaram de volta no Android Market.

O Android possui alguns níveis de defesa contra ameaças. A maioria da aplicações roda dentro de uma máquina virtual e operações perigosas exigem (em princípio) permissões expressas durante a instalação do aplicativo.

E não custa lembrar que o Android é um software aberto e baseado no Linux, o que algumas pessoas associam a invulnerabilidade. Estas pessoas vão se assustar ao saber que o Droid Dream usa uma conhecida vulnerabilidade do Linux (mais especificamente do udev) para fazer a "elevação de privilégio" que dá ao malware as permissões de super-usuário.

Esta vulnerabilidade foi inicialmente reportada em 2009 e afetava as principais distribuições de Linux (e continua afetando que não tiver atualizado o Linux ou aplicado os devidos patches). Do ponto de vista técnico a vulnerabilidade não está no kernel do Linux (ou do Android), mas sim em um componente externo. No Linux este componente é o udv, no Android o código em questão foi movido (com falha e tudo) para o init. A correção da falha, entretanto, envolve uma alteração no kernel (detalhes no link anterior).

O que nos leva a uma outra questão: a atualização do Android. Outra vantagem do iOS é que todos os equipamentos que o utilizam são do mesmo fabricante e a atualização de versão fica centralizada. Já no Android temos a conhecida fragmentação e a atualização de cada equipamento depende do respectivo fabricante (e a maioria deles não tem um histórico muito animador quanto à disponibilização de atualizações). A Microsoft está tentando evitar isto no Windows Phone 7, mas infelizmente a primeira experiência não foi totalmente positiva.

E ficamos com o conselho de "Mad-Eye" Moody: vigilância constante!

Fonte: Naked Security

O Mercado de Tablets Volta a Respirar: Anunciado o iPad2

O lançamento do iPad original não foi totalmente uma surpresa, mas o seu sucesso sim. O resultado foi uma corrida das empresas de computadores e celulares para lançar um aparelho concorrente. Isto levou à situação em que os lançamentos destes aparelhos praticamente coincidiu com o anúncio da segundo geração do iPad. E com isto ficou um suspense no ar; toda avaliação de tablet estava assombrada pelo espectro do iPad2.

Agora ele foi finalmente anunciado, permitindo uma avaliação melhor da situação atual do mercado. Na minha opinião, o iPad2 acabou saindo de bom tamanho.

Os fanboys podem comemorar que o líder inconteste do mercado está agora potencialmente duas vezes mais rápido no processamento (graças a um novo processador dual core), até nove vezes mais rápido no tratamento de gráficos, incrivelmente mais fino, notavelmente mais leve, com as duas inevitáveis câmeras e até mesmo disponível na cor branca, tudo isto pelo mesmo preço.

Já os concorrentes devem estar felizes em ver que a Apple não tirou nenhum coelho das cartolas e que as especificações técnicas (exceto a espessura) não são muito diferentes das suas.

É neste ponto que muitos se enganam: para esta classe de equipamento especificações técnicas com processadores e memória Ram não são fatores decisivos de compra (pelo menos diretamente) . O que importa é a experiência do uso. A Palm foi a primeira a perceber isto, há mais de dez anos: as fichas técnicas dos seus produtos dispensavam os megahertz e megabytes. Nas notícias que eu vi até agora existe um certo mistério sobre a quantidade de Ram no iPad2, será que isto importa? Eu digo que importa somente se alguém apontar um cenário claro e relevante em que a memória impacte no uso do iPad2 (algo do tipo "o iPad2 não pode receber email enquanto você assiste um filme porque falta memória", o que duvido que seja o caso).

Os concorrentes da Apple precisam se concentrar no software e não no hardware. Vários deles tem ainda que encontrar o caminho para conseguir pelo menos igualar os agressivos preços do iPad2. A seu favor eles continuam contando com a inflexibilidade da Apple em alguns pontos: por exemplo o iPad2 não tem conexão direta a SD, USB ou HDMI.

quinta-feira, março 03, 2011

Minhas Aventuras com "Parsing": Earley Parser

Earley Parser é um algorítimo capaz de analisar linguagens livres de contexto. Não é um algorítimo particularmente rápido no caso mais genérico: o tempo de execução é proporcional ao cubo do tamanho do texto a analisar. Em outras palavras, um texto com o dobro do tamanho demora oito vezes mais para ser analisado; um texto 10 vezes maior demora 1000 vezes mais. Este desempenho melhora em casos específicos como gramáticas não-ambíguas (onde um texto pode ser derivado de uma única forma) e as chamadas gramáticas LR(k) (falaremos mais sobre elas no futuro).

Obs: Recomendo a leitura do post anterior para entender a nomenclatura usada.

A Ideia Básica

O Earley Parser analisa o texto da esquerda para a direita, considerando um caracter adicional de cada vez. Na sua análise, vai montando uma relação das regras da gramática que potencialmente podem ser aplicadas no reconhecimento do texto. À medida que a análise prossegue, verifica-se que algumas regras não são compatíveis com o texto e devem ser abandonadas, enquanto que outras podem ser aplicadas para reconhecer outros trechos. Se, num certo instante, nenhuma regra puder ser aplicada, o texto é inválido; se o texto todo atender a uma regra do não terminal raiz, o texto é válido.

Se você experimentar fazer algo parecido no papel, verá que a ideia é boa mas a sua implementação não é trivial.

Linguagem Aumentada

Um primeiro truque para facilitar a análise é acrescentar uma regra adicional à gramática:

S' -> S

onde S é o não terminal raiz original. S' passa a ser a nova raiz da gramática, com a vantagem de ter uma única regra de produção. Desta forma o nosso objetivo é verificar esta única regra (ao invés de considerar explicitamente as potencialmente várias regras de produção da raiz original).

O Estado do Parsing

Para representar a situação do reconhecimento de uma regra X -> uv em um dado instante, Early usa a notação

X -> uv

o ponto na notação separa a parte que já foi reconhecida (u) do que é esperado (v).

Um estado no algorítimo é composto de três partes:
  • A regra sendo analisada (X -> uv)
  • A posição do ponto que indica quanto da regra já foi reconhecida
  • Um índice que indica a partir de qual posição no texto foi feito o reconhecimento
Este estado pode ser representado por

(X -> uv , i)

Conjuntos de Estados

Voltando à ideia básica, vamos analisar o texto caracter a caracter da esquerda para a direita. Em cada passo teremos um conjunto de estados que contém as regras que podem ser aplicadas até este momento. Para um texto com n caracteres teremos n+1 conjuntos de estado, correspondendo do momento em que não analisamos nenhum caracter até o momento em que analisamos todos. Representaremos estes conjuntos por S(0) a S(n).

Ao acrescentar um estado em um conjunto é preciso tomar o cuidado de não duplicá-lo se já estiver no conjunto.

Começamos colocando em S(0) o estado

(S' -> • S, 0)

Isto indica que a regra básica pode ser aplicada ao texto, nada foi reconhecido ainda e estamos partindo do primeiro caracter.

O Algorítmo

O nosso algorítimo vai percorrer o texto da esquerda para direita. Estaremos variando o índice k do caracter a examinar de 0 até n-1, onde n é o número de caracteres no texto.

Em cada passo vamos examinar os estados no conjunto atual S(k). Dependendo do que observarmos, vamos acrescentar novos estados ao conjunto atual ou ao conjunto seguinte S(k+1). Os estados acrescentados ao conjunto atual serão também examinados no passo atual; somente quando não tivermos mais estados a acrescentar e analisar no passo atual passaremos para o seguinte.

No nosso exame dos estados vamos procurar identificar uma das seguintes três situações (exclusivas entre si):
  • Completion: Um não terminal foi reconhecido. Isto é indicado pelo ponto estar no final da regra: (X -> u, j). O tratamento desta situação consiste em acrescentar ao conjunto atual S(k) estados do conjunto S(j) atualizados para indicar este reconhecimento. Sendo mais específico, para cada estado em S(j) que tenha o formato (Y -> u • X v, i) vamos incluir no conjunto atual S(k) um estado (Y -> u X • v, i).
  • Prediction: Acrescentar as regras referentes aos não terminal que são esperados. Isto é indicado pelo ponto estar na frente de um não terminal: (X -> u Y v, j). O tratamento desta situação consiste em incluir no conjunto atual S(k) o estado (Y -> •y, k) para cada regra Y -> y de produção de Y na gramática
  • Scanning: Reconhecer um não terminal. Isto ocorre quanto temos no conjunto atual S(k) um estado no formato (X -> u • a v, j) e o próximo caracter no texto é o não terminal a. O tratamento desta situação consiste em colocar no conjunto seguinte S(k+1) o estado (X -> u a • v, j) que indica o reconhecimento.
O estado (S' -> S •, 0) no passo n indica que o texto foi reconhecido (é válido).

Se, ao concluirmos um passo 0 a n-1, o conjunto de estados para o passo seguinte está vazio é sinal que o texto é inválido.

No próximo post veremos uma implementação direta deste algorítimo em C.

Referências

Wikipedia: http://en.wikipedia.org/wiki/Earley_parser
Uma apresentação (em formato pdf): http://www.sfs.uni-tuebingen.de/~fr/teaching/ws06-07/cl2/slides/EarleyParser.pdf
Uma apresentação bem mais clara (também em pdf): http://www.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/Earley-Parsing.pdf

quarta-feira, março 02, 2011

Segurança Através da Nudez

Esta é uma daquelas coisas que a gente fica se perguntando se é sério ou se estão tirando uma da cara da gente. Um bando de desenvolvedores resolver usar uma (minúscula) imagem de mulher para indicar quão segura é uma senha: quanto mais segura (segundo as fórmulas deles), menos roupa ela apresenta (clique para ampliar):


O site de exemplo está em http://www.nakedpassword.com/.

Além de politicamente incorreta, esta solução parece ser bastante simplória do ponto de vista de segurança: a senha 123456789 é considerada suficientemente segura para merecer um topless.

Fonte: Blog nakedsecurity (coincidência irônica?).

terça-feira, março 01, 2011

Minhas Aventuras com "Parsing" - Gramáticas

Estou retomando os problemas do SPOJ Brasil (em preparação para o Google Code Jam deste ano) e o primeiro que eu revi foi o "ET Phone Home". Eu já tinha tentado este problema antes, sem sucesso. Hora de estudar um pouco de teoria... Este problema envolve parsing - a análise de textos com base em uma gramática. Eu já falei um pouco sobre isto aqui no blog, mas dentro do contexto de compilar uma linguagem de programação adequadamente simples.

Os livros sobre o assunto são caros (versões "físicas" acima de US$100 e versões eletrônicas acima de US$50 na Amazon). Existe bastante material na web porém a maior parte é confusa e existe pouco código de exemplo. Daí a origem desta série de posts para organizar as minhas ideias e, se tudo der certo, ajudar a outros interessados.