%
% 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
%  2000/2001
%


\documentclass[12pt]{article}
\usepackage{a4wide}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{color}
\usepackage{alltt}
\usepackage{portuges}

\usepackage[latin1]{inputenc}
\usepackage{latexsym}


\usepackage[dvips]{epsfig}
\usepackage{epic}
\usepackage{eepic}


\def\Ipe#1{\def\IPEfile{#1}\input{#1}}

\newenvironment{code}
{\textbf{Solução} \hspace{1cm} \hrulefill \\ 
\smallskip 
\begin{center}
\begin{minipage}{.80\textwidth} 
\begin{alltt}\small}
{\end{alltt}
\end{minipage}
\end{center}
\hrule\smallskip
}


\newtheorem{exercicio}{}[section]

\title{\sf Métodos de programação III \\
\begin{tabular}{c}
{\small LMCC \& LESI}, {\small Universidade do Minho} \\
{\small Ano lectivo 2000/2001}  \\
{\small Ficha Teórico-Prática N$º$10} \\ 
\end{tabular}
}

\author{}
\date{}


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

\begin{document}

\maketitle


Este texto está escrito em \textbf{literate Haskell}. Isto é, pode ser
interpretado como um documento \LaTeX\ ou como um puro programa na
linguagem Haskell.  Responda às perguntas sobre Haskell neste próprio
ficheiro e assim produzir o programa e a sua documentação.


\section{Gramáticas Independentes de Contexto em Haskell}


\begin{exercicio}

Defina combinadores de parsing para as seguintes linguagens:

\begin{enumerate} 

\item A linguagem usual para definir strings nas linguagens de
programação. Uma string é uma sequência de caracteres iniciada e
terminada pelo caracter \texttt{"}.

\item Usualmente os espaços são consumidos e ignorados durante o
parsing de um texto. Re-escreva o combinador \texttt{token} de modo a
consumir os espaços que possam ocorrer antes do token. Utilize para
tal, a função de parsing feita na aula anterior que define a
ocorrência de zero ou mais espaçõs: \texttt{zeroOuMaisEspacos}.

\end{enumerate}

\end{exercicio}

\begin{code}
import Parser

string :: Parser Char [Char]

parser_string inp = 
   case string inp of
          []          -> ""
          (x:xs)      -> case x of
                           (res,[]) -> res
                           _        -> ""
main = do s <- readFile "input"
          putStr (parser_string s)

-- token' :: [Char] -> Parser Char [Char]

\end{code}


\begin{exercicio}

Considere de novo a linguagem HTML e a sua notação para descrever
tabelas. A gramática independente do contexto para definir a estrutura
concreta desta linguagem foi definida na ficha-teórica nº8. A
gramática abstracta e o tipo de dados isomórfico foi definido na
ficha-teórica nº9. Re-escreva a gramática concreta da linguagem com
combinadores de Parsing. O resultado do parser é a árvore construída
usando os construtores do tipo de dados induzidos pela gramática
abstracta. De seguida apresenta-se a gramática concreta para a
linguagem das tabelas HTML:

\medskip

\small \begin{minipage}[t]{.90\textwidth} 
\begin{tabular}[t]{l}
G=(T,N,S,P), \textit{com} \\
T = \{\verb@"<table>"@,\verb@"</table>"@,\verb@"<tr>"@,\verb@"</tr>"@,\verb@"<td>"@,\verb@"</td>"@,texto \} \\
N = \{ Tabela , Linhas , Linha , Colunas , Coluna , Elemento \}    \\
S = Tabela              \\
\end{tabular} \\
\end{minipage} \\
\begin{minipage}[t]{.90\textwidth} 
\begin{tabular}[t]{lclccl}
P = & \{ & Tabela:   & Tabela   & $\rightarrow$ & \verb@"<table>"@ Linhas \verb@"</table>"@\\
    &  , & NoLinhas: & Linhas   & $\rightarrow$ & \\
    &  , & CLinhas:  &          & $|$           &  Linha Linhas \\
    &  , & Linha:    & Linha    & $\rightarrow$ & \verb@"<tr>"@ Colunas \verb@"</tr>"@  \\  
    &  , & NoCols:   & Colunas  & $\rightarrow$ & \\
    &  , & CCols:    &          & $|$           & Coluna Colunas \\
    &  , & Coluna:   & Coluna   & $\rightarrow$ & \verb@"<td>"@ Elemento \verb@"</td>"@ \\
    &  , & Texto:    & Elemento & $\rightarrow$ & texto \\
    &  , & TabAnin:  &          & $|$           & Tabela \\   
    & \} \\
\end{tabular} 
\end{minipage}
\normalsize

\medskip

E o tipo de dados calculado a partir da gramática abstracta está já
escrito na solução do exercício.

\end{exercicio}


\begin{code}
data Tabela = Tabela Linhas
     deriving Show
data Linhas = NoLinhas
            | CLinhas Linha Linhas
     deriving Show
data Linha = Linha Colunas
     deriving Show
data Colunas = NoCols
             | CCols Coluna Colunas
     deriving Show
data Coluna = Coluna Elemento
     deriving Show
data Elemento = Texto String
              | TabAnin Tabela
     deriving Show


-- tabela :: Parser Char Tabela

\end{code}


A função que lê uma tabela HTML de um ficheiro (com nome
\texttt{inputTabela}) e escreve o resultado na saída apresenta-se a
seguir.

\begin{code}
runparser_table :: [Char] -> Maybe Tabela
runparser_table inp = 
   case tabela inp of
        []      -> Nothing
        (x:xs)  -> case x of
                        (ast,[]) -> (Just ast)
                        _        -> Nothing

showResTable :: Maybe Tabela -> String
showResTable (Nothing )    = ""
showResTable (Just tabela) = show tabela

mainTabela :: IO ()
mainTabela = do s <- readFile "inputTabela"
                putStr (showResTable (runparser_table s))
\end{code}



\begin{exercicio} 

Considere a gramática independente do contexto que define uma
representação concreta de expressões aritméticas. 

\small \begin{minipage}[t]{.40\textwidth} 
\( \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

Será possível implementar directamente esta gramática usando
combinadores de parsing? Porquê? Defina uma gramática concreta
equivalente, para a qual podemos construir combinadores de parsing.
Determine a gramática asbtracta, escreva os tipos de dados abstractos
do Haskell e defina o catamorfismo sobre esse tipo de
dados. Implemente os combinadores de parsing de modo a construirem a
estrutura de dados que representa a expressão aritmética processada.

\end{exercicio}

\begin{code}

\end{code}

\begin{exercicio}

Construa a seguintes funções:

\begin{enumerate}

\item
Defina uma função showLateX para o tipo de dados \texttt{Tabela} de
modo a "mostrar" as tabelas asbtractas na notação (concreta) do
\LaTeX. Use a função show para mostrar o resultado do parser e assim
obter um conversor de tabelas HTML para tabelas em \LaTeX.

\item
Considere os parsers construídos nos dois exercícios
anteriores. Generalise esse parsers de modo a ser possível instanciar
esses parsers com diferentes semânticas. Isto é, parameterize esses
parsers com as funções que são aplicadas durante o reconhecimento
sintático.

\end{enumerate}

\end{exercicio}


\end{document}