% vim:tw=74:
\section{Conceitos Teóricos}

Como foi explicado, este projecto consistiu em
desenvolver um módulo em Perl -- secção~\ref{perl} -- para tratamento de
Cronologias. Este módulo foi escrito utilizando técnicas de
\ac{POO} -- descritas na secção~\ref{poo} -- e foram aproveitados alguns
dos módulos existentes no \ac{CPAN} para a realização de várias tarefas,
especialmente na área do Processamento de Linguagens -- ver secção~\ref{pl}
-- e da Programação orientada à Web usando \ac{CGI} -- ver
secção~\ref{cgi}.

\subsection{Perl}\label{perl}

\ac{Perl} é uma linguagem de programação de uso genérico, desenvolvida
originalmente com maior ênfase na manipulação de texto mas usada
actualmente para um vasto número de tarefas incluindo administração de
sistemas, desenvolvimento orientado à Web, programação de redes e
programação de \ac{GUI}'s.

Esta linguagem permite programar, quer seguindo o paradigma
funcional, quer seguindo o paradigma orientado a objectos, e é geralmente
definida como sendo uma linguagem de \emph{scripting}\footnote{A definição
de linguagem de \emph{scripting} é algo subjectiva podendo tanto
abranger as características da linguagem em si como os objectivos dessa
linguagem. No primeiro grupo estão características tais como ser uma
linguagem interpretada ou ter uma definição dinâmica de tipos de dados
(\emph{dynamic typing}). O segundo grupo engloba as
definições como sendo uma linguagem que serve de ``cola'' entre os outros
programas ou entre funções do sistema.}.

O facto de ter sido originalmente desenvolvida para a manipulação de texto
dotou-a de grandes capacidades no tratamento de texto, particularmente
no uso de expressões regulares~(sendo as expressões regulares em \ac{Perl}
bem mais poderosas que aquelas definidas na norma \ac{POSIX}). Estas
capacidades permitem que o uso desta linguagem seja bastante difundido em
áreas onde seja necessário efectuar algum tipo de tratamento em
conteúdos textuais.

Desde que foram introduzidas propriedades de uma linguagem orientada, a
objectos a criação de módulos sofreu um grande impulso, existindo
actualmente uma vasta colecção que abrange a mais diversas áreas de
aplicação. De forma a facilitar a consulta e pesquisa desses mesmos
módulos foi criado o \ac{CPAN} onde é possível pesquisar, consultar e
descarregar quase todos os módulos existentes\footnote{Na altura em que
este texto foi escrito o \ac{CPAN} incluia perto de 6000 módulos
distribuídos por cerca de 25 áreas-chave.}.

A sintaxe da linguagem em si herda aspectos de outras linguagens e
ferramentas, tais como C\footnote{Uma das principais linguagens de
programação imperativas cujas origens remontam à década de 1970.},
\texttt{awk}\footnote{Uma linguagem interpretada para processamento de
informação textual.} ou \texttt{sed}\footnote{O editor de \emph{streams} do
Unix. Tem uma poderosa mas confusa linguagem de comandos baseada em
expressões regulares.}, pelo que será mais facilmente perceptível por quem
tenha conhecimento destas ferramentas. Existe boa documentação online
sobre esta linguagem~(um bom sítio para começar é o \ac{CPAN}) e grande
parte vem incorporada com a distribuição da linguagem. Para se poder
consultar usa-se uma ferramenta chamada \texttt{perldoc}:

\begin{comando}
\$ perldoc perl
\end{comando}

Desta forma tem-se acesso a um índice onde estão explicadas as várias
secções da documentação. A mesma ferramenta também pode ser usada para
consultar informações sobre cada módulo instalado.

\subsection{Programação Orientada aos Objectos}\label{poo}

A \ac{POO} é um dos paradigmas de programação mais referenciados hoje em
dia. O ponto fulcral deste paradigma é o conceito de \emph{objecto}.

Tal como é referido em \cite{mm}, um objecto é uma forma de nos
abstrairmos de um comportamento complexo num ``módulo computacional único
e básico'' que apresenta um conjunto de atributos internos~(o seu
\emph{estado}) e um conjunto de operações, algumas das quais invocáveis do
exterior do objecto~(a sua \emph{interface}), e que manipulam
essencialmente o seu estado interno~(estas operações definem o
\emph{comportamento} do objecto). Este paradigma facilita a reutilização
de código uma vez que o programador não necessita de conhecer a
complexidade e estado interno de um objecto, optando apenas por comunicar
com ele através de uma interface previamente conhecida e bem definida.

Uma das propriedades essenciais a uma boa reutilização de código~(e que se
demonstra essencial em \ac{POO}) é o \emph{encapsulamento} de dados. Para
este objectivo ser atingido um objecto deve possuir uma estrutura interna,
invisível para o exterior, e que, como tal, nunca deve ser manipulada
directamente. Se isto for conseguido atinge-se um nível de abstracção que
nos permita~(a nós criadores do objecto), modificá-lo internamente sem que
isso tenha impacto na forma como ele é utilizado~(desde que a interface
seja mantida). Para haver esta separação muitas linguagens incluem
primitivas de controlo de acesso que limitam quem pode aceder às varáveis
e aos métodos.

Outra propriedade associada aos objectos é a \emph{herança}. Graças a ela
um objecto pode identificar um~(herança simples) ou vários~(herança
múltipla) outro(s) objecto(s) como sendo seu(s) ``pai(s)''. Ao fazer isto
um objecto está a \emph{herdar} as características~(leia-se métodos e
variáveis) que os seus ascendentes possuem. Graças a este conceito é
possível criar uma hierarquia de forma a ser possível agrupar estruturas
que sejam comuns a várias entidades diferentes. Note-se que apesar de
haver diferenças no número de ascendentes possíveis, a regra geral é que o
número de descendentes seja ilimitado~(embora existam casos em que se pode
eliminar a existência de descendentes).

\subsubsection{POO em Perl}

Em \ac{Perl} há muito tempo que existe o conceito de \emph{módulo}. Esta
noção de uma entidade abstracta capaz de agrupar uma série de funções e/ou
variáveis tem sido desde sempre necessária em qualquer linguagem de
programação de forma a permitir construir aplicações com alguma
complexidade.

Nesta linguagem cada módulo inclui o seu próprio
\emph{namespace}\footnote{Espaço abstracto onde cada nome tem de ser
único. Em programação um \emph{namespace} refere-se, normalmente, ao
conjunto do nome das funções e/ou variáveis.} e é este conceito que surge
como base para a noção de objecto. A declaração de um módulo é feita com a
directiva \texttt{package}, o seu uso é feito com \texttt{use}:

\begin{lstlisting}
package Nome;
...
use Nome;
\end{lstlisting}

\medskip

A herança é obtida através da variável \texttt{@ISA}:

\begin{lstlisting}
package Pai;
...
package Filho;
use Pai;
our @ISA = qw(Pai); # herdar Pai
\end{lstlisting}

\medskip

É regra geral existir um método que sirva de \emph{construtor} -- cria o
objecto e efectua inicializações se necessário. Em \ac{Perl} não existe
uma imposição ao nome deste método, no entanto é prática corrente optar-se
pelo nome \texttt{new}:

\begin{lstlisting}
package Contador;

sub new {
   my $class = shift();
   my $valor = shift() || 0;
   my $self  = [ $valor ];
   bless($self, $class);
   return($self);
}
\end{lstlisting}

Neste método é passado como primeiro parâmetro o nome da classe. A
``magia'' é feita pela função \texttt{bless}. Esta função associa a uma
referência um nome que identifica que tipo de objecto ela contém. Desta
forma é possível invocar métodos que estejam definidos para o módulo nesse
objecto. A variável \texttt{\$self} agrupa dentro de si o estado interno
do objecto. É possível passar parâmetros ao construtor, apenas é
necessário ter atenção que eles são passados depois do nome.

Existem várias formas de invocar o construtor:

\begin{lstlisting}
$contador = new Contador(0);
$contador = Contador->new(0);
\end{lstlisting}

Para se definirem outros métodos é necessário ter a noção que esse método
deve receber como primeiro argumento o próprio objecto, permitindo desta
forma aceder a outros métodos ou ao seu estado interno:

\begin{lstlisting}
sub incrementa {
   my $self = shift();
   $self->[0] = $self->[0] + 1;
}

...

$contador->incrementa();
\end{lstlisting}

Esta introdução a \ac{POO} em \ac{Perl} foi bastante simples de forma a
não entrar em temas mais complexos de programação em \ac{Perl}. Para quem
desejar aprofundar este assunto existe boa documentação online nas secções
do manual \texttt{perlboot}, \texttt{perltoot} e \texttt{perltooc}. Todo o
módulo de cronologias foi implementando usando \ac{POO}.

\subsection{\emph{Parsing}}\label{pl}

\subsubsection{Gramáticas}                                                                                      
Uma gramática é um formalismo que permite especificar abstractamente a
sintaxe de uma certa linguagem. Existem ainda outras formas de efectuar
esta especificação, como é o caso das \emph{expressões regulares}. No
entanto estas, apesar da sua simplicidade de notação, apenas são úteis
para linguagens com um certo número de restrições. As gramáticas são uma
ferramenta com um poder expressivo bastante grande, dado que conseguem
descrever linguagens que seriam impossíveis de definir com, por exemplo,
\emph{expressões regulares}. Outro factor que torna as gramáticas uma
ferramenta importante na especificação de linguagens, é a sua
legibilidade, assim como a sua notação bastante compacta, que permite, de
uma forma bastante intuitiva, a apreensão da sintaxe da linguagem.

Uma gramática é um quadruplo constituído por: um conjunto de
\emph{símbolos terminais}, um conjunto de \emph{símbolos não
terminais}, um \emph{símbolo inicial} ou \emph{axioma}, e um conjunto
de \emph{produções}.

\begin{itemize}
\item
Os \emph{símbolos terminais} são os elementos base da linguagem. Eles
representam o alfabeto da linguagem, ou seja, os símbolos que a esta admite
como válidos. Por uma questão de facilidade, estes são normalmente
definidos, recorrendo a expressões regulares.
                                                       
\item
Os \emph{símbolos não terminais} representam subconjuntos da linguagem.
Um \emph{símbolo não terminal} pode ser reescrito, ou seja, pode
representar, uma sequenciação de \emph{símbolos terminais} e de outros
\emph{símbolos não terminais}, constituindo uma \emph{produção}.

\item
O \emph{símbolo inicial} ou \emph{axioma}, é um \emph{símbolo não
terminal}, que representa a linguagem definida pela gramática. A partir
deste, é possível derivar todas as frases válidas da linguagem. Por frase
entende-se qualquer sequência de símbolos, e por derivação, o processo de a
partir do \emph{axioma} fazer a reescrita do símbolo, através das suas
\emph{produções}, em sequências equivalentes, até obter apenas
\emph{símbolos terminais}.

\item
Uma \emph{produção} representa uma regra de sintaxe, em que um
\emph{símbolo não terminal} é definido recorrendo a \emph{símbolos
terminais} e a outros \emph{símbolos não terminais}.

\end{itemize}

A definição formal de gramática é:

\begin{defin}
Uma gramática G é um quadruplo G = (T, N, S, P), em que:

\begin{itemize}
\item
T é o conjunto finito não vazio de símbolos \emph{terminais};

\item
N é o conjunto finito não vazio de símbolos \emph{não terminais};

\item
S $\in$ N é o símbolo inicial, também designado por \emph{axioma} da
gramática;

\item
$P \subseteq (N \cup T)^{+} \times (N \cup T)^{*}$ é o conjunto finito não
vazio de \emph{produções} ou regras de derivação. Cada produção é um
par~($\alpha$, $\beta$) em que $\alpha$ designa o lado esquerdo da produção
e $\beta$ o lado direito da produção; sendo $\alpha \in (N \cup T)^{+}$ e
$\beta \in (N \cup T)^{*}$. Geralmente, uma produção representa-se por
$\alpha \rightarrow \beta$ e lê-se ``$\alpha$ deriva~(imediatamente) em
$\beta$''.
\end{itemize}
\end{defin}

Consoante o nível de linguagem que especificam, as gramáticas podem
dividir-se em várias categorias. Estes níveis foram propostos pelo
linguista \texttt{Chomsky}, e dividem as linguagens de acordo com as suas
características. No entanto, para aplicações informáticas, as gramáticas que
se revestem de maior importância são as \ac{GIC}, e as \emph{Gramáticas
Regulares}. Isto porque é relativamente fácil conceber programas para
trabalhar com estes tipos de gramáticas, assim como é relativamente fácil
gerar reconhecedores automáticos para estes tipos de gramáticas.

Uma \ac{GIC} é uma gramática, cuja restrição consiste em que um
\emph{símbolo não terminal} deriva da mesma forma, independentemente do
contexto onde está inserido, isto é, o seu significado não é sensível à
adjacência com outros símbolos. Assim, os lados esquerdos das produções têm
apenas um \emph{símbolo não terminal}. A sua definição formal é:

\begin{defin}
$ $\\
$\phantom{20}A \rightarrow \alpha$ tal que $A \in N$ e $\alpha \in (N \cup T)^{*}$
\end{defin}

Uma \ac{GIC} pode ser considerada uma \emph{Gramática Regular} se obedecer
a um certo número de restrições. Para uma \emph{Gramática Regular} existe
sempre associada uma \emph{expressão regular} equivalente, que define a
mesma linguagem.

O reconhecimento de \emph{Gramáticas Regulares} pode ser feito
computacionalmente de uma forma muito eficiente. Devido à sua equivalência
com uma expressão regular, e dado que esta pode ser convertida num
reconhecedor baseado num \emph{autómato finito determinista}, que é um
programa com um estado interno, que pode executar o reconhecimento de uma
frase muito rapidamente, também o reconhecimento de \emph{Gramáticas
Regulares} pode ser efectuado pelos referidos autómatos.

O reconhecimento de \ac{GIC}s que não possam ser representadas por
expressões regulares é mais complexa, e exige algoritmos mais poderosos para
ser efectuado. O programa gerado é normalmente designado por
\emph{parser}.

\subsubsection{\emph{Parsers}}

Como já foi referido, um parser é um programa que é utilizado para
reconhecer se uma determinada frase de entrada, verifica as regras
definidas por determinada gramática.

Um parser recebe como input uma frase de entrada, que é uma sequência de
símbolos, e devolve como output, uma informação de sucesso ou insucesso, na
tentativa de derivar a frase de entrada, a partir do \emph{axioma} da
gramática. A primeira fase deste processo deverá ser a verificação de que
todos os símbolos da frase de entrada pertencem ao alfabeto da gramática,
ou seja, ao seu conjunto de \emph{símbolos terminais}. A esta fase chama-se
a \emph{análise léxica}, e ao reconhecedor que a efectua, \emph{analisador
léxico}.

Como já foi referido anteriormente, os \emph{símbolos terminais} são
normalmente definidos recorrendo a expressões regulares, logo o
\emph{analisador léxico} poderá fazer o reconhecimento de símbolos,
baseando-se no reconhecimento através de autómatos.  A segunda fase do
processo é verificar se a sequência de símbolos reconhecida pelo
\emph{analisador léxico}, obedece às regras definidas pela gramática, e
designa-se por \emph{análise sintáctica}, sendo o respectivo analisador, o
\emph{analisador sintáctico}. Geralmente, o \emph{analisador léxico}
fornece ao \emph{analisador sintáctico}, não o símbolo lido, mas um código
de símbolo, que se costuma designar por \emph{lexema}. Assim, o
\emph{analisador sintáctico} vai tentar, a partir do \emph{axioma} da
gramática derivar a sequência de lexemas recebida. A forma como esta
derivação é feita, vai distinguir os parsers em dois grandes grupos: os
parsers \emph{top-down} e os parsers \emph{bottom-up}:

\begin{itemize}
\item
Um parser \emph{top-down} vai tentar, partindo do axioma, e reescrevendo
cada sucessivamente todos os \emph{símbolos não terminais} pelas suas
produções, alcançar no final apenas \emph{símbolo terminais} que coincidam
com a sequência de lexemas recebida.

Estes são os parsers mais simples de implementar, contudo, são também os mais
limitados.

\item
Um parser \emph{bottom-up} vai tentar, partindo dos lexemas recebidos, e
analisando as produções da gramática, agrupá-los de forma a constituírem
sequências correspondentes a produções de \emph{símbolos não terminais}.
Continuando o agrupamento de sequências de lexemas e de \emph{símbolos não
terminais}, vai tentar chegar a uma situação onde a sequência pode ser
substituída pelo \emph{axioma} da gramática, verificando-se que a frase de
entrada é válida.  Em caso de não se conseguir alcançar o \emph{axioma} a
partir da frase de entrada, esta é considerada inválida.

Estes parser são os mais poderosos, no entanto, sofrem de uma complexidade
adicional nos algoritmos de reconhecimento.
\end{itemize}


No entanto, um parser que só indique se um texto de entrada é, ou não,
válido, tem uma utilidade limitada. A maioria das vezes, queremos, depois
de verificada a correcção, efectuar acções úteis sobre a informação
recebida, como por exemplo, gerar código executável, ou imprimir uma página
HTML. Para tal, podemos associar acções semânticas ao \emph{analisador
sintáctico}, ou seja, executar uma determinada acção sobre a informação
reconhecida. Em alternativa, podemos pôr o \emph{analisador sintáctico} a
gerar uma representação abstracta do texto recebido, e enviá-la a um
\emph{analisador semântico} para o seu tratamento posterior. Nestes casos,
o \emph{analisador léxico} transmite ao \emph{analisador sintáctico}, não
só o lexema, como também o símbolo reconhecido.

A representação abstracta construída pelo \emph{analisador sintáctico}
é geralmente designada por \emph{árvore de sintaxe abstracta}, e é uma
representação equivalente á frase de entrada, ou seja, possui a mesma
informação. O \emph{analisador semântico} recebe esta árvore, e procede à
execução de acções, que dependem do objectivo do programa, sobre esta
representação. Pode mesmo incluir, em alguns casos, a optimização da
informação presente naquela. Outra utilização do \emph{analisador
semântico} é, muitas vezes, a análise da correcção semântica do texto de
entrada, ou seja, do seu significado. O \emph{analisador sintáctico}
apenas avalia a correcção da forma do texto de entrada; não faz nenhuma
validação sobre a validade do seu conteúdo, ou significado. Esta análise é,
normalmente, mais complexa do que as fases anteriores, e justifica a
utilização de \emph{analisadores semânticos} como componentes separados.

\subsubsection{\emph{Parsing} com Perl}

Fazer \emph{parsing} ao nível das expressões regulares é bastante fácil em
\ac{Perl} uma vez que elas estão embutidas na própria linguagem. Para
construir \emph{parsers} existem vários módulos seguindo a maior parte deles
uma abordagem semelhante ao programa \texttt{yacc}. Na descrição da
implementação os detalhes da implementação de um \emph{parser} em
\ac{Perl} são discutidos com maior detalhe.

\subsection{CGI}\label{cgi}

A Internet, quando foi inicialmente desenhada, há mais de de 30 anos
atrás, foi pensada como sendo uma forma de disponibilizar conteúdos
estáticos. Com a massificação da utilização, os fabricantes começaram-se a
aperceber da necessidade de desenvolver um protocolo que permitisse
adicionar conteúdos dinâmicos à Web. Foi com este objectivo que se definiu
a tecnologia \ac{CGI}.

\subsubsection{Funcionamento}

A ideia por detrás desta tecnologia é permitir criar um interface entre
programas externos e o servidor Web usado. Desta forma é possível ao
servidor Web gerar conteúdos com base em execuções de programas do
sistema. A sua execução é ilustrada na Figura~\ref{pic:cgi1}.

\begin{figure}[!hbp]
\begin{center}
\includegraphics[width=12cm]{cgi}
\end{center}
\caption{Esquema CGI}
\label{pic:cgi1}
\end{figure}

Quando um servidor Web recebe um pedido para um \emph{script} \ac{CGI},
ele executa-o como outro processo (i.e., um ambiente de execução
separado). No pedido \ac{HTTP} podem vir vários parâmetros que são
passados ao processo \ac{CGI} pelo servidor Web. Depois de terminada a
execução, o servidor Web recolhe a saída do processo e envia-a ao cliente
como se fosse uma página estática. Devido a isto uma das garantias que o
processo \ac{CGI} tem de oferecer é que a sua saída é código passível de
ser interpretado por clientes \ac{HTTP} -- normalmente isto é feito usando
\ac{HTML}.

A passagem de parâmetros a um \emph{script} \ac{CGI} pode ser feita no
próprio \ac{URL}:

\begin{comando}
http://dominio/\ldots/script?\emph{parâmetro1}=\emph{valor1}\&\emph{parâmetro2}=\emph{valor2}\ldots
\end{comando}

Esta notação corresponde a um pedido \texttt{GET}. É ainda possível passar
parâmetros utilizando pedidos \texttt{POST}. Neste caso os parâmetros vão
no cabeçalho do cabeçalho \ac{HTTP} e não no \ac{URL}.

Existe uma diferença de aplicação entre os dois que nem sempre é
respeitada: os pedidos \texttt{POST} só devem ser utilizados quando
implicam uma modificação nos dados do servidor (p.e., alterar a informação
contida numa base de dados) enquanto que os pedidos \texttt{GET} devem ser
utilizados quando apenas se acede a informação (p.e., aceder aos registos
de uma base de dados). Devido a esta diferença, um \texttt{browser}
diferencia ambos os pedidos. Se um utilizador efectuar um pedido
\texttt{GET} e depois recarregar a página tudo ocorre normalmente (já que
o pedido \texttt{GET} é suposto ser utilizado apenas em operações de
leitura), mas se o pedido for um \texttt{POST} o \emph{browser} pergunta
ao utilizador se quer repetir o pedido (já que a repetição de um pedido
que altera algo deve ser feita com mais certezas). A incorrecta utilização
de cada tipo de pedido leva a que a experiência de navegação de um
utilizador possa ficar algo incoerente.

\subsubsection{Estratégias de Desenvolvimento}\label{state}

Quando começou a ser usada a programação com CGI's, o conceito passava por
simplesmente desenvolver m programa que gerasse como saída código
\ac{HTML}. Como este desenvolvimento implicava, na prática, o conhecimento
de HTML, começaram a aparecer alternativas onde o código era escrito
dentro de etiquetas especiais de HTML (os exemplos mais difundidos desta
abordagem são o PHP\footnote{Linguagem \emph{open-source} bastante
difundida como meio de desenvolver páginas dinâmicas. É semelhante em
sintaxe a C e a Perl.} e o ASP\footnote{Linguagem desenvolvida pela
Microsoft para programação de páginas dinâmicas. Tal como o PHP é
caracterizado por permitir inclusão de código dentro do próprio HTML.}.

A linguagem \ac{Perl} é das mais utilizadas para programação dinâmica de
páginas. A abordagem utilizada depende do(s) módulo(s) que se usarem. Os
mais frequentes são:

\begin{description}
\item[CGI] Este módulo permite a criação de conteúdos HTML através do uso
de funções (métodos). É a forma mais aproximada ao \emph{CGI} tradicional.

\item[Mason] Este módulo implementa com \ac{Perl} uma abordagem semelhante
à utilizada em PHP ou ASP.

\item[HTML::Template] Com este módulo é possível especificar o conteúdo
das páginas em HTML com umas etiquetas especiais onde será inserida a
informação dinâmica. O \emph{script} \ac{CGI} carrega a página e
substitui as variáveis em cada execução. Permite uma clara separação entre
a parte computacional (\emph{script} \ac{CGI}) e o aspecto gráfico (código
HTML genérico). Existem outros módulos que usam uma aproximação
semelhante: o \texttt{Text::Template} e o \emph{toolkit}
\texttt{Template}.
\end{description}

\medskip

Em termos comportamentais, um script \ac{CGI} pode ser encarado como uma
máquina de estados. Uma máquina de estados é representada por um diagrama
de estados tal como o da Figura \ref{pic:state}.

\begin{figure}[!hbp]
\begin{center}
\includegraphics[height=3.5cm]{generic}
\end{center}
\caption{Diagrama de Estados}
\label{pic:state}
\end{figure}

Cada nó do diagrama representa um estado interno possível. A mudança de
estado faz-se com a ocorrência de eventos (que são representados por setas).
Existe um estado inicial definido por uma seta proveniente de um ponto.
Podem existir vários estados finais que marcam o fim da execução.

Num contexto de uma aplicação \ac{CGI}, cada estado representa uma acção
diferente que a aplicação vai executar (ao qual corresponde uma saída
diferente). As mudanças de estado fazem-se, geralmente, com a invocação da
aplicação com parâmetros diferentes. É frequente um dos parâmetros ser a
identificação do estado. A noção de estado final não é, normalmente,
considerada. Note-se que a aplicação \ac{CGI} pode estar dispersa por
vários \emph{scripts} diferentes de forma a facilitar uma reutilização do
código ou a definir uma estrutura lógica do mesmo.

Em \ac{Perl} existe o módulo \texttt{CGI::Application} que permite usar
esta noção de máquina de estado para servir de base à construção de
aplicações \ac{CGI}. Este módulo foi usado neste projecto pelo que será
referido com maior detalhe quando for discutida a implementação do módulo.

\subsection{Extracção de Informação da Web}
\label{teoriaExtraccao}
Quando, em 1989, Tim Berners Lee propôs o projecto \emph{World Wide
Web} no \ac{CERN}, provavelmente não estaria consciente do sucesso que o
mesmo teria uns anos mais tarde. De facto, não tardou até que aparecessem
os primeiros browsers\footnote{ou navegadores} e servidores Web
fazendo com que qualquer pessoa pudesse publicar conteúdos acessíveis a
toda a gente. 

Actualmente, o sucesso da Web é mais do que evidente. Um
estudo\footnote{http://news.netcraft.com/archives/web\_server\_survey.html}
recente da \emph{Netcraft}\footnote{http://www.netcraft.com}, empresa especialista
em questões relacionadas com a Web, concluia que em Janeiro de 2004
existiam mais de 46 milhões de \emph{websites}!  A
Figura~\ref{pic:netcraft} mostra a evolução dos vários servidores web ao
longo dos últimos anos.

\begin{figure}[!hbp]
\begin{center}
\includegraphics[width=14cm]{netcraft}
\end{center}
\caption{Evolução dos servidores web desde Outubro de 1995 até Janeiro de
2004}
\label{pic:netcraft}
\end{figure}

Perante este sucesso, tornou-se cada vez mais importante arranjar
mecanismos para extrair a informação que nos é disponibilizada via Web de uma
forma eficiente. Este é de facto um desafio actual sendo por isso objecto
de estudo de muitos investigadores.

Neste sentido, considerou-se ser uma mais valia para este projecto, a
inclusão de ferramentas que permitissem extrair informação acerca de eventos
históricos existente na Web. Em condições ideais, esta ferramenta
permitiria construir cronologias inteiras sem ter de inserir os eventos
manualmente. Contudo, verificou-se que a tarefa é algo complexa pelo que
se enumeram a seguir as principais dificuldades encontradas. 

\subsubsection{Problemas na extracção}

Um dos maiores problemas que a Web enfrenta actualmente resulta de uma
tendência que se está a generalizar entre os \emph{web developers} no
sentido de ignorarem os standards existentes. Uma vez que os browsers
actuais conseguem interpretar código \ac{HTML} ainda que este não seja
válido, é cada vez mais difícil encorajar os \emph{web developers} a
seguirem as especificações da \ac{W3C} para o desenvolvimento de
documentos \ac{HTML}. Dentro destes standards, destacam-se o
\ac{HTML}\footnote{recentemente substituído pelo XHTML} e o \ac{CSS}.

Este incumprimento pelos standards vigentes tem repercussões muito maiores
do que aquelas se podem imaginar. Surgem, por exemplo, enormes problemas de
acessibilidade impossibilitando o acesso aos conteúdos a pessoas com
deficiência. Urge pois, educar os \emph{developers} a terem em consideração 
aspectos como o da acessibilidade no desenvolvimento dos
websites\footnote{Consultar o \emph{Web Acessibility Iniciative da W3C} --
link na página~\pageref{www}.}

Um dos outros grandes problemas e que interessa mais referir nesta altura
está relacionado com a extracção de informação. Se os documentos \ac{HTML}
não seguem as especificações conhecidas, a tarefa de extrair
informação é muito mais complexa ou mesmo impossível implicando,
na maioria das vezes, fazer um trabalho de \emph{reverse engineering}.

\subsubsection{Extracção de informação Web em Perl}

Para extrair informação presente em páginas Web utilizando a linguagem
\ac{Perl}, é recomendável que se utilize um dos módulos \ac{CPAN} que
existem para esta finalidade, destacando-se os seguintes:

\begin{description}

\item[HTML::Parser]
Trata-se de um módulo para ser utilizado no parsing de documentos
\ac{HTML}. Objectos desta classe reconhecem tags \ac{HTML} e separam-nas do
conteúdo do documento propriamente dito. 

À medida que que o texto e as \emph{tags} vão sendo reconhecidas, são
invocados os respectivos \emph{handlers}.  Dentro destes destacamos os
métodos \emph{start} e \emph{end} que são invocados sempre que é
reconhecida uma abertura ou fecho de uma \emph{tag}\footnote{Ou etiqueta.}
\ac{HTML} respectivamente. Existe ainda o método \emph{text} que é
invocado sempre que é reconhecido um bloco de texto dentro de uma
\emph{tag}.

A extracção de um documento utilizando o HTML::Parser passa, por exemplo,
por ter uma variável de controlo que indique qual a \emph{tag} que está a
ser processada num determinado momento e recolher o texto limitado por essa
\emph{tag} caso seja necessário.

Uma desvantagem deste módulo prende-se com o facto de ele não 
interpretar os documentos \ac{HTML} como uma estrutura hierárquica (por
exemplo, uma árvore) mas simplesmente como um conjunto de \emph{tokens}.

Uma referência Web que contém a documentação da versão actual do
HTML::Parser está disponível na página~\pageref{www}.

\item[HTML::TreeBuilder]
Ao contrário do HTML::Parser, este módulo tem a particularidade de
construir uma árvore a partir do documento extraído. Depois da árvore
construída é possível não só processá-la para obter a informação desejada
mas também alterá-la de forma a poder gerar um novo documento \ac{HTML}.

Tomemos como exemplo o seguinte bloco de código \ac{HTML} no qual se
utiliza uma lista não ordenada\footnote{Do termo em inglês:
\emph{\textbf{u}norder \textbf{l}ist}.}.

\begin{verbatim}
<html
<head></head>
<body>
<ul>
<li>Ice cream.</li>
<li>Whipped cream.
<li>Hot apple pie <br>(mmm pie)</li>
</ul>
</body></html>
\end{verbatim}

Utilizando o HTML::TreeBuilder, obteríamos a seguinte árvore descrita na
Figura~\ref{pic:tree}.

\begin{figure}[!htp]
\begin{center}
\includegraphics[width=10cm]{tree}
\end{center}
\caption{Árvore HTML gerada}
\label{pic:tree}
\end{figure}

Note-se que nestas árvores \emph{HTML}\footnote{árvores construídas a
partir de documentos HTML}, existem dois tipos de nodos: \emph{nodos texto}
que se referem a strings sem tags e \emph{nodos elemento} que estão
associados às \emph{tags}. Neste caso, \texttt{Ice Cream} representa um nodo texto e
\texttt{ul} representa um nodo elemento. Convém também referir que os
nodos texto são sempre \emph{folhas da árvore}, ou seja, não possuem
nenhum nodo filho.

A utilização de árvores para o processamento de documentos \ac{HTML} é
recomendável principalmente nos casos em que o documento possui uma
estrutura bem definida. Assim, passam-se a manipular
árvores\footnote{tarefa que deverá ser trivial para um estudante na área
das ciências da computação} em vez de um conjunto de strings em que se
mistura informação estrutural (tags e atributos) com a informação do
documento propriamente dita.

Contudo, nos casos dos documentos mal formados\footnote{documentos que não
seguem as especificações existentes}, torna-se complicado construir a
árvore. De facto, tenta-se obter uma estrutura virtual de um documento que
não se encontra estruturado ou então mal estruturado.

Uma referência Web que contém a documentação da versão actual do
HTML::TreeBluider está disponível na página~\pageref{www}.

\item[Template::Extract]
Trata-se de um módulo que está especialmente vocacionado para o
processamento de páginas geradas automaticamente segundo um dado
padrão\footnote{ou template na terminologia inglesa}. 

Este tipo de páginas são conhecidas por \emph{páginas dinâmicas} uma vez 
que são geradas a partir de informação externa aos documentos (por
exemplo, uma base de dados). Desta forma, a actualização de uma
página pode envolver apenas operações de manipulação da base de dados e
não do próprio documento \ac{HTML}. Por este motivo, este tipo de páginas
tem registado um aumento considerável nas mais diversas áreas.

O Template::Extract surge como um módulo ``inverso'' ao
\emph{Template-Toolkit}\footnote{Referência Web disponível na
página~\pageref{www}.}. De facto, ao passo que este último constrói um
documento \ac{HTML} a partir de um dado template e de alguns dados, o
primeiro tenta extrair informação sendo fornecido um dado documento e o
seu template.

Tomemos pois, por exemplo, o seguinte bloco de código \ac{HTML} acerca da
história da \ac{WWW}:

\begin{verbatim}
<ul><li><i>1989</i>-Tim Berners-Lee proposes the World Wide Web project
to CERN.</li>
    <li><i>1993</i>-Students and staff at the University of Illinois
       create Mosaic.</li>
    <li><i>1994</i>-Jim Clark and Marc Andreesen found Netscape
       Communications.</li></ul>
\end{verbatim}

Aplicando o seguinte template

\begin{verbatim}
<ul>[% FOREACH record %]
<li><i>[% year %]</i>-[% event %]</li>[% /\s*/ %]
[% END %]</ul
\end{verbatim}

obtém-se a seguinte esta estrutura\footnote{utilizando o módulo
\emph{Data::Dumper}}

\begin{verbatim}
$VAR1 = {
 'record' =>
     [
       {
        'event' => 'Tim Berners-Lee proposes the World Wide Web project
to CERN.',
        'year' => '1989'
       },
       {
        'event' => 'Students and staff at the University of Illinois
create Mosaic.',
        'year' => '1993'
       },
       {
        'event' => 'Jim Clark and Marc Andreesen found Netscape
Communications.',
        'year' => '1994'
       }
     ]
};
\end{verbatim}

A notação utilizada nos templates é bastante simples. Sempre que se
pretende extrair uma determinada variável \verb+v+, é necessário colocar \verb+[% v %]+
no template. A directiva especial \verb+[% ... %]+ ignora tudo entre um
dado identificador e o seguinte. Mais recentemente, foi inserida a opção
de colocar expressões regulares na forma de \verb+[% // %]+. Por exemplo,
\verb+[% /\s*/ %]+, ignora zero ou mais espaços.
Para estruturas que se repetem, podem-se utilizar as directivas
\emph{FOREACH} e \emph{WHILE}.

Uma das desvantagens deste módulo é que obrigará, na maioria dos casos, o
utilizador a etiquetar o documento HTML. Desta forma, inviabiliza-se uma
automatização que consistiria em fazer o \emph{fetch} do documento e em
seguida o seu processamento, de uma forma transparente para o utilizador.

Uma referência Web que contém a documentação da versão actual do
Template::Extract está disponível na página~\pageref{www}.

Além disso, recomenda-se também a leitura dos seguintes artigos
sobre a utilização do módulo: \emph{O'Reilly Book Excerpts: Spidering
Hacks} e \emph{The 2003 Perl Advent Calendar:
Template::Extract}\footnote{Referências disponíveis na
página~\pageref{www}}.
\end{description}
