% 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º 11\\ (Gramáticas Independentes de Contexto (3))}
\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 mp302f11.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 mp302f11.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 de Contexto em Haskell}

\begin{exercicio} 
Considere o tipo de dados \texttt{Parser}, que expressa o
comportamento de um parser (recursivo descendente), e as funções
\texttt{symbol} e \texttt{satisfy}.

\begin{code}
--
-- Combinadores de Parsing em Haskell
--
-- Métodos de Programação III
-- Universidade do Minho
-- 2001/2002
--
module Parser where

infixl 3 <|> ; infixl 4 <*>

type Parser simbolo resultado = [simbolo] -> [(resultado,[simbolo])]

symbol :: Eq a => a -> [a] -> [(a,[a])]
symbol _ []                  = []
symbol s (x:xs) | x == s     = [(s,xs)]
                | otherwise  = []

satisfy :: (s -> Bool) -> Parser s s
satisfy p []                 = []
satisfy p (x:xs) | p x       = [(x,xs)]
                 | otherwise = []
\end{code}

Responda às seguintes perguntas:
\begin{enumerate} 

\item Defina o tipo da função \texttt{symbol} em termos do tipo
\texttt{Parser}.

\item Defina "\textit{parsers}" para reconhecer os seguintes símbolos
e classes de símbolos:

\begin{enumerate}
\item O parser \texttt{simboloA} que processa o símbolo \texttt{A}.
\item O parser \texttt{espaco} que processa o símbolo espaço. Expresse
este parser em termos da função \texttt{symbol} e \texttt{satisfy}.
\item O Parser \texttt{digito} que processa um símbolo se este
pertencer à classe dos digitos.
\item O Parser \texttt{letraMaiusc} que processa um símbolo se este
pertencer à classe das letras maiúsculas.
\end{enumerate}

\item Generalize a função \texttt{symbol} de modo a processar
sequências de símbolos, usualmente chamadas \textit{tokens} de uma
linguagem, e não um símbolo apenas. Uma execução desta função
apresenta-se a seguir:

\small
\begin{verbatim}
   Main> token "while" "while (x>0) { ... }"
   [("while"," (x>0) { ... }")]
\end{verbatim}\normalsize

\begin{code}

\end{code}

\end{enumerate}

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

\section{Os Combinadores de Parsing}
O tipo \texttt{Parser} foi definido de modo a permitir que os parser
básicos definidos anteriormente possam ser facilmente combinados de
modo a formar parser mais poderosos. Esta é precisamente a ideia dos
combinadores de parsing: funções de ordem superior que combinam os
parsers que recebem como argumento e produzem um parser mais poderoso.

\begin{code}
succeed :: a -> Parser s a
succeed r xs = [(r,xs)]

(<|>) :: Parser s a -> Parser s a -> Parser s a
(p <|> q) xs = p xs ++ q xs
\end{code}

\begin{exercicio}
Re-escreva o parser \texttt{expaco} de modo a processar os símbolos
espaço, \textit{tab}, e \textit{newline}.

\begin{code}

\end{code}

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

\begin{exercicio}
Considere a seguinte gramática independente do contexto 
\small  $G=(\{"while","decl","if"\},\{X\},X,P)$, com 
\(
\begin{array}[t]{lclccl}
P = & \{ & P_0: & X & \rightarrow & "while"  \\ 
    &  , & P_1: &   & |           & "decl"   \\
    &  , & P_2: &   & |           & "if"     \\
    &  , & P_3: &   & |           & \epsilon \\
    & \} \\
\end{array} \)
\normalsize

Escreva uma função de parsing \texttt{parserX} que modela o parsing
da linguagem definida por $G$. Qual o tipo deste parser?  Quantas
soluções produz o parser ao processar a seguinte entrada \texttt{"decl
x;"}. Porquê?

\begin{code}

\end{code}

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

\begin{exercicio}
O combinador \texttt{<*>} expressa a ocorrência de uma sequência de
símbolos no lado direito das produções. O parser \texttt{<\$>}
permite alterar o valor do resultado de um parser.

\begin{code}
(<*>) :: Parser s (a -> r) -> Parser s a -> Parser s r 
(p <*> q) inp = [ ( f v , zs)
                | ( f   , ys ) <- p inp
                , (   v , zs ) <- q ys 
                ]

(<$>) :: (a -> r) -> Parser s a ->  Parser s r
(f <$> p) inp= [ (f r , rstinp) | (r, rstinp) <- p inp ]
\end{code}

Utilize este combinador para modelar as seguintes linguagens:

\begin{enumerate}
\item Um símbolo \texttt{a} seguido de um símbolo \texttt{b}

\item Dois espaços seguidos.

\item Implemente o parser \texttt{zeroOuMaisEspacos} para definir a linguagem 
cujas frases são zero ou mais espaços seguidos.

\begin{code}


\end{code}

\item Implemente o parser \texttt{umOuMaisEspacos} para definir a linguagem 
cujas frases são um ou mais espaços seguidos.

\begin{code}


\end{code}
\end{enumerate}

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

\begin{exercicio} 
Define dois novos combinadores para expressar as estrutura repetitivas
"\textit{zero ou mais vezes}" e "\textit{uma ou mais vezes}". Isto é,
defina os combinadores \texttt{zeroOuMais} e \texttt{umOuMais} que
recebem como argumento um parser e expressam a sua repetição. Ou por
outras palavras, generalize as funções \texttt{zeroEspacos} e
\texttt{umOuMaisEspaco}.
\begin{enumerate}

\item Expresse a função de parsing \texttt{umOuMaisEspacos} usando o
combinador \texttt{umOuMais}

\begin{code}


\end{code}
\item Defina a função de parsing \texttt{parseInt} para processar a
linguagem dos números inteiros.

\begin{code}


\end{code}
\end{enumerate}

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

\end{document}