% Este ficheiro contem um texto em Literate Haskell
%    Partes do ficheiro são texto em LaTeX e outras em Haskell
%    
%  Métodos de Programação III
%  2002/2003
%


\documentclass[12pt]{article}

\usepackage[portuges]{babel}
\usepackage[latin1]{inputenc}

%\usepackage{a4wide}
%\usepackage{graphics}
%\usepackage{graphicx}
%\usepackage{color}
\usepackage{alltt}
%\usepackage{latexsym}
%\usepackage[dvips]{epsfig}
%\usepackage{epic}
%\usepackage{eepic}

\parindent=0pt
\parskip=3pt

\def\Ipe#1{\def\IPEfile{#1}\input{#1}}
\def\hask{\textsf{Haskell}}
\def\hugs{\textsf{Hugs}}

\newenvironment{code}
{\vspace{0.3cm}
\textbf{Código Haskell} \hspace{1cm} \hrulefill \\ 
\smallskip 
\begin{center}
\begin{minipage}{.80\textwidth} 
\begin{alltt}\small}
{\end{alltt}
\end{minipage}
\end{center}
\hrule\smallskip
}

\newtheorem{exercicio}{Exercício}[section]

\title{Métodos de Programação III\\ LESI + LMCC (3º ano)}
\author{Ficha Teórico-Prática nº 10\\ (Gramáticas Independentes de Contexto (2))}
\date{Ano lectivo 2002/2003}
%\date{\today}

%-------------------- Inicio do Documento -------------------------------

\begin{document}

\maketitle

\noindent Este texto está escrito em \textbf{Literate Haskell}. Isto é, pode ser
interpretado como um documento \LaTeX\ ou como um puro programa na
linguagem \hask.\\
O documento é obtido "compilando"\  este ficheiro em
\LaTeX: \begin{center}\texttt{latex mp302f10.lhs}\end{center}
O programa \hask\ incluído neste
ficheiro é compilado/interpretado directamento pelos
compiladores/interpretadores de \hask, executando por exemplo o comando:
\begin{center}\texttt{hugs mp302f10.lhs}\end{center}
 Para isso o código \hask\
deve estar delimitado pelos comandos \verb@\@\texttt{begin\{code\}} e \verb@\@\texttt{end\{code\}}.\\\\
Responda às perguntas sobre \hask\ neste próprio
ficheiro para assim produzir o programa e a sua documentação.

%-------------------- 
\section{Gramáticas Independentes do Contexto}
Neste primeiro grupo pretende-se ainda testar mais alguns conceitos associados às gramáticas concretas.

\begin{exercicio} \label{exerc:email}
Considere uma linguagem para a escrita de mensagens de correio
electronico.  Uma mensagem de ``email'' é constituído por vários
campos, nomeadamente: o destinatário, o assunto, o conteúdo. Estes
campos são obrigatórios e são precedidos das palavras chave
\texttt{Para:}, \texttt{Assunto:} e \texttt{Conteúdo:}. Existem dois
campos optionais que permitem endereçar o email para outros
destinatários e a inclusão de anexos no email. Estes campos são
precedidos das palavras \texttt{CC:} e \texttt{Anexo:},
respectivamente. Os campos \texttt{Para:} e \texttt{CC:} são seguidos
por uma lista de emails separadas pelo separador \texttt{|}. O campos
\texttt{Assunto:} é seguido por uma string, terminada pelo caracter
\textit{newline}. O campo \texttt{Anexo:} é seguido de uma lista de
nomes de ficheiros separados por \texttt{;}. O Conteúdo é seguido por
um texto delimitado por aspas.  Por último, os campos podem aparecer
por uma ordem arbitrária numa frase da linguagem.

Responda às seguintes perguntas:
\begin{enumerate}

\item Escreva as expressões regulares \texttt{email},
\texttt{ficheiro}, \texttt{assunto}, \texttt{conteudo} que definem as
sequencias de caracteres que definem um endereço de email, o nome de
um ficheiro, o assunto e o texto entres aspas do conteudo,
respectivamente.

\item Escreva a gramática independente do contexto que defina esta
linguagem. Considere que as expressões regulares definidas
anteriormente são símbolos pseudo-terminais.
\end{enumerate}

\end{exercicio}
%--------------------

Considere a definição de recursivida em gramáticas:
\begin{itemize}

\item  {\it
  Uma gramática $G = (T,N,S,P)$ diz-se {\em recursiva à esquerda} se
  existir um $A \in N$ tal que existe uma derivação $A =>^* A\alpha$
  para alguma frase $\alpha$. 
}

\item {\it
  Uma gramática $G = (T,N,S,P)$ diz-se {\em recursiva à direita} se
  existir um $A \in N$ tal que existe uma derivação $A =>^* \alpha A$
  para alguma frase $\alpha$.
}

\end{itemize}

\begin{exercicio} \label{exerc:rec}
Diga justificando quais das seguintes gramáticas são 
\textit{ambiguas}, \textit{recursivas à esquerda} e \textit{recursivas
à direita}.
\begin{enumerate}

\item \small  $G=(\{a\},\{A,B\},A,P)$, com 
\(
\begin{array}[t]{lclccl}
P = & \{ & P_0: & A & \rightarrow & A B \\ 
    &  , & P_1: &   & |           & a   \\
    &  , & P_2: & B & \rightarrow & a B  \\
    &  , & P_3: &   & |           & \epsilon \\
    & \} \\
\end{array} \)
\normalsize

\item \small  $G=(\{a,b,c\},\{X,Y,Z\},A,P)$, com 
\(
\begin{array}[t]{lclccl}
P = & \{ & P_0: & X & \rightarrow & Z Y \\ 
    &  , & P_1: & Y & \rightarrow & a Y b \\
    &  , & P_2: &   & |           & a    \\
    &  , & P_3: & Z & \rightarrow & b  \\
    &  , & P_4: &   & |           & a c   \\
    &  , & P_5: &   & |           & \epsilon \\
    & \} \\
\end{array} \)
\normalsize

\item \small \begin{minipage}[t]{.40\textwidth} \label{exerc:expr}
\( \begin{array}[t]{l}
G=(T,N,S,P), \textit{com} \\
T = \{+,-,*,/,(,),num,var \} \\
N = \{ Expr \}    \\
S = Expr              \\
\end{array} \)
\end{minipage}
\begin{minipage}[t]{.45\textwidth} 
\( \begin{array}[t]{lclccl}
P = & \{ & Soma: & Expr & \rightarrow & Expr\ '+'\ Expr \\
    &  , & Mul:  &      & |           & Expr\ '*'\ Expr \\
    &  , & Div:  &      & |           & Expr\ '/'\ Expr \\
    &  , & Sub:  &      & |           & Expr\ '-'\ Expr \\  
    &  , & Prio: &      & |           & '('\ Expr\ ')' \\
    &  , & Num:  &      & |           & num \\
    &  , & Var:  &      & |           & var \\
    & \} \\
\end{array} \)
\end{minipage}
\normalsize

\end{enumerate}

\end{exercicio}
%--------------------

\section{Gramáticas Abstractas}

As \textbf{gramáticas abstractas} ``abstraem-se'' dos aspectos puramente
sintácticos das linguagens não-regulares. Assim, referências a \emph{palavras
chaves} e \emph{sinais de pontuação} não são incluídas nas gramáticas
abstractas. De igual modo, algumas propriedades das gramáticas, como
ambiguidade, recursividade à esquerda e direita e outras, que são
fundamentais no desenvolvimento de reconhecedores de frases concretas
da linguagens, não o são para as gramáticas abstractas.

\begin{exercicio} \label{exerc:abst}
Defina gramáticas independentes do contexto asbtractas para as
seguintes linguagens:

\begin{enumerate}

\item Considere a linguagem de expressões aritmeticas do exercício
anterior. Defina uma linguagem abstracta para representar expressões
abstractamente.

\item Considere a representação concreta de tabelas em HTML definida
na ficha anterior. Defina uma gramática asbtracta para definir
tabelas.

\end{enumerate}

\end{exercicio}
%--------------------

\section{Gramáticas Abstractas em Haskell}
A representação em Haskell de gramáticas abstracta faz-se de acordo
com as seguintes regras:

\begin{itemize}

\item Símbolos não-terminais induzem novos tipos indutivos em Haskell.\\
Por exemplo,
\( \begin{array}[t]{llcl}
P_0: X &   \rightarrow & Y \\
P_1:   &  | & Z \\
P_2: Y &  \rightarrow & int\ Y \\
P_3:   & |  & \epsilon \\
\end{array} \)

induz os seguintes tipos

\begin{verbatim}
   data X = ...
   data Y = ...
\end{verbatim}

\item Produções induzem funções construtoras de dados. O nome da
produção é o nome da função e o não-terminal no lado esquerdo é o tipo
do resultado da função. Isto é, a produção 
$P_0: \alpha\ \rightarrow\ \beta$ induz a função $P_0$ com o seguinte tipo 
$P_0 :: \beta\  \rightarrow\  \alpha$.\\
Por exemplo, os tipos anteriores terão os seguintes construtores:
\begin{verbatim}
   data X = P_0 Y
          | P_1 Z
   data Y = P_2 int Y
          | P_3 
\end{verbatim}

\item Símbolos pseudo-terminais induzem tipos primitivos do Haskell.\\
Assim, o símbolo pseudo-terminal $int$ induz um tipo primitivo do
Haskell $Int$, i.e., 
\begin{verbatim}
   type int = Int
\end{verbatim}

\end{itemize}

\begin{exercicio}
Implemente em Haskell as seguintes linguagens abstractas:
\begin{enumerate}

\item Linguagens  definidas no exercício~\ref{exerc:abst}.\\ 

\begin{code}

\end{code}

\item Linguagem abstracta para as mensagens de correio electrónico do
exercicio~\ref{exerc:email}.\\

\begin{code}

\end{code}

\end{enumerate}

\end{exercicio}
%--------------------

\begin{exercicio}
Considere o tipo de dados induzido pela gramática abstracta que define
expressões aritméticas do exercício~\ref{exerc:rec}.\ref{exerc:expr}. Derive o
catamorfismo para o tipo de dados e escreva a função catamórfica que
calcula a expressão.\\

\begin{code}

\end{code}

\end{exercicio}
%--------------------

\end{document}