% % 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$º$9} \\ \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} Considere o tipo de dados \texttt{Parser}, que expressa o comportamento de um parser (recursivo descendente), e as funções \texttt{symbol}, \texttt{satisfy} e \texttt{succeed}. \begin{code} -- -- Combinadores de Parsing em Haskell -- -- Métodos de Programação III -- 2000/2001 -- 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 recebm 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=(\{a\},\{A,B\},A,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 funcçã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} \medskip \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{build} permite alterar o valor do resultado de um parser. \begin{code} (<**>) :: Parser s a -> Parser s b -> Parser s (a,b) (p <**> q) xs = [ ( (y,z) , zs) | ( y , ys ) <- p xs , ( z , zs ) <- q ys ] build :: Parser s r -> (r -> c) -> Parser s c build p f 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. \item Implemente o parser \texttt{umOuMaisEspacos} para definir a linguagem cujas frases são um ou mais espaços seguidos. \end{enumerate} \begin{code} \end{code} \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} \item Defina a função de parsing \texttt{parseInt} para processar a linguagem dos números inteiros. \end{enumerate} \begin{code} \end{code} \end{exercicio} \end{document}