% % 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 % Universidade do Minho % 2005/2006 % \documentclass[12pt]{article} %include lhs2TeX.fmt %include lhs2TeX.sty %format |-> = "\longmapsto" %format nullable_nt = "\textbf{nullable\_nt}" %format nullable_nt' = "\textbf{nullable\_nt'}" %format nullable = "\textbf{nullable}" %format nullable_g = "\textbf{nullable\_g}" %format derives = "\textbf{derives}" %format derives_nt' = "\textbf{derives\_nt'}" %format derives_nt = "\textbf{derives\_nt}" %format lhs = "\textbf{lhs}" %format rhs = "\textbf{rhs}" %format is_terminal = "\textbf{is\_terminal}" %format isEmpty = "\textbf{isEmpty}" %format emptyProds = "\textbf{emptyProds}" %format selProd = "\textbf{selProd}" %format sizeProd = "\textbf{sizeProd}" %format prods_nt = "\textbf{prods\_nt}" %format rhs_nt = "\textbf{rhs\_nt}" \usepackage{a4wide} \usepackage{graphics} \usepackage{graphicx} \usepackage{color} \usepackage{alltt} \usepackage[portuges]{babel} \usepackage[latin1]{inputenc} \usepackage{latexsym} \usepackage[dvips]{epsfig} \usepackage{epic} \usepackage{eepic} \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 2005/2006} \\ {\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 para assim produzir o programa e a sua documentação. \section{Gramáticas Independentes do Contexto em Haskell} \begin{exercicio} Escreva em Haskell o tipo de dados que modela gramáticas independentes do contexto em Haskell. \end{exercicio} \begin{code} -- -- Módulo de Gramáticas Independentes do Contexto em Haskell -- -- Métodos de Programação III -- Universidade do Minho -- 2005/2006 -- module Cfg where data Cfg sy = Cfg { terminals :: [sy] , nonterminals :: [sy] , root :: sy , prods :: [(String,[sy])] } deriving (Show,Read) \end{code} \begin{exercicio} Escreva em Haskell a função $\longmapsto$ que imita o operador BNF "deriva em". Esta função recebe como argumentos o lado esquerdo e o lado direito de uma produção e constrói a produção respectiva. Para tornar a escrita da gramáticas o mais parecida possível com BNF, defina este operador de modo a ser usado em notação infixa, isto é entre os seus dois argumentos. \end{exercicio} \begin{code} (|->) :: sy -> [sy] -> [sy] l |-> r = l : r \end{code} \begin{exercicio} Considere a seguinte gramática independente de contexto $g_1 = (T,N,S,P)$, com: \( \begin{array}{l} T = \{ a , b , c \}, \\ N = \{ S , A , B \}, \\ \begin{array}[t]{lclccl} P = & \{ & p_0: & S & \rightarrow & A\ B\ c \\ & , & p_1: & A & \rightarrow & a \\ & , & p_2: & & \mid & \epsilon \\ & , & p_3: & B & \rightarrow & b \\ & , & p_4: & & \mid & \epsilon \\ & \} \end{array} \\ \end{array} \) Modele esta gramática em Haskell. \end{exercicio} \begin{code} g_1 = Cfg ['a','b','c'] ['S','A','B'] 'S' [ ("p0",'S' |-> ['A','B','c']) , ("p1",'A' |-> ['a']) , ("p2",'A' |-> []) , ("p3",'B' |-> ['b']) , ("p4",'B' |-> []) ] \end{code} \begin{exercicio} Escreva em Haskell as seguintes funções sobre o tipo $Cfg$: \begin{enumerate} \item Funções |lhs| e |rhs| que dada uma produção (sem nome), devolvem o seu lado esquerdo/direito, repectivamente. \item Pedicado |is_terminal| que verifica se um símbolo é símbolo terminal da gramática ou não. \item Função que devolve o tamanho de uma produção. O tamanho de um produção define-se como o número de ocorrências de símbolos da gramática no lado direito da produção. \item Predicato |isEmpty| que verifica se uma produção é nula ou não. \item Função |emptyProds| que dada um gramática devolve o conjunto de produções nulas. \item Função |selProd| que dado uma gramática e o nome de uma produção devolve a produção com esse nome. \end{enumerate} \end{exercicio} \begin{code} lhs = head rhs = tail is_terminal sy g = sy `elem` (terminals g) sizeProd = length . rhs isEmpty = null . rhs emptyProds g = filter isEmpty (map snd (prods g)) selProd g n = filter ((== n) . fst) (prods g) \end{code} \begin{exercicio} Considere a gramática $G$ do exercício $1.1$ da ficha teórico-prática nº9. Modela esta gramática em Haskell e responda às três primeiras alíneas desse exercício usando agora as definições Haskell introduzidas. \end{exercicio} \begin{code} g_2 = Cfg ['a','b','c'] ['A','B','C'] 'A' [ ("P0",'A' |-> ['B','a','C']) , ("P1",'A' |-> []) , ("P2",'B' |-> ['b','B']) , ("P3",'B' |-> []) , ("P4",'C' |-> ['c']) , ("P5",'C' |-> []) , ("P6",'C' |-> ['C','c']) ] alinea_1 = root g_2 alinea_2 = lhs $ snd $ head $ (selProd g_2 "P1") alinea_3 = rhs $ snd $ head $ (selProd g_2 "P6") \end{code} \begin{exercicio} Escreva em Haskell as seguintes funções sobre o tipo $Cfg$: \begin{enumerate} \item Função |prods_nt| que dada uma gramatica e um símbolo não terminal calcula o conjunto de produções (sem nome) em que o não terminal dado é o lado esquerdo. \item Função |rhs_nt| que dada uma gramatica e um símbolo não terminal calcula o conjunto de lados direitos em que o não terminal dado é o lado esquerdo. \end{enumerate} \end{exercicio} \begin{code} prods_nt :: Eq sy => Cfg sy -> sy -> [[sy]] prods_nt g nt = filter ((==) nt . lhs) (map snd (prods g)) rhs_nt :: Eq sy => Cfg sy -> sy -> [[sy]] rhs_nt g nt = map tail (prods_nt g nt) \end{code} \section{Símbolos Não Terminais Anuláveis} Uma propriedade importante dos símbolos não terminais é o facto de derivarem ou não a frase nula. Formalmente um símbolo não $X \in N$ diz-se anulável sse existir um sequência de derivação a partir de $X$ que deriva em $\epsilon$, isto é, $X \Rightarrow^* \epsilon$ Considere a seguinte definição em Haskell de não terminal anulável. \begin{code} nullable_nt :: (Eq sy) => Cfg sy -> sy -> Bool nullable_nt g nt = nullable_nt' g [] nt \end{code} Um não terminal é anulável sse existir um seu lado direito em que todos os símbolos sejam anuláveis \begin{code} nullable_nt' :: Eq sy => Cfg sy -> [sy] -> sy -> Bool nullable_nt' g v nt = or $ map (nullable g v) (rhs_nt g nt) \end{code} Uma sequência de símbolos é anulável s a sequencia de símbolos é a sequência vazia ou todos os símbolos da sequência são anuláveis. Por outro lado, a sequência não é vazia se contiver um símbolo terminal ou já tiver sido visitado (ex. prods recursivas). \begin{code} nullable :: Eq sy => Cfg sy -> [sy] -> [sy] -> Bool nullable g _ [] = True nullable g v (h:t) | h `is_terminal` g = False | h `elem` v = False | otherwise = (nullable_nt' g (h:v) h) && (nullable g v t) \end{code} \begin{exercicio} Considere a seguinte gramática $g_3$ definida em Haskell. Responda às seguintes perguntas: \begin{enumerate} \item Prove utilizando a definição formal que o axioma de $G$ deriva a string nula. \item Utilize a definição Haskell para provar que os símbolos \texttt{A}, \texttt{B}, \texttt{C} e \texttt{E} são anuláveis. \item Considere o símbolo não terminal \texttt{D} e sua produção. Este símbolo é anulável? É possível a partir de \texttt{D} derivar alguma frase? \end{enumerate} \end{exercicio} \begin{code} g_3 = Cfg ['a','b','c','d'] ['A','B','C','D','E'] 'A' [ ("P0",'A' |-> ['B','C','B']) , ("P1",'A' |-> ['a','D']) , ("P2",'B' |-> ['b','B','b']) , ("P3",'B' |-> []) , ("P4",'C' |-> ['B']) , ("P5",'C' |-> ['c','C']) , ("P6",'D' |-> ['d','D']) ] \end{code} \begin{exercicio} Uma gramática $G$ diz-se anulável se aceitar a frase nula, isto é, $\epsilon \in {\cal L}(G)$. Escreva em Haskell a função |nullable_g| que indica se uma gramática é anulável ou não. \end{exercicio} \begin{code} nullable_g :: Eq sy => Cfg sy -> Bool nullable_g g = nullable_nt g (root g) \end{code} \section{Símbolos Não Terminais Úteis} Um símbolo não terminal diz-se útil se verificar duas condições: \begin{enumerate} \item For acessível a partir do axioma da gramática. Isto é, se existir uma derivação $S \Rightarrow^* \alpha X \beta$, com $\alpha, \beta \in (T \cup N)*$. \item For possivel iniciar a partir dele uma sequência de derivação que produz uma sequência de símbolos do vocabulário da gramática, isto é, $X \Rightarrow^* \alpha_i$, com $\alpha_i \in T$. \end{enumerate} \begin{exercicio} Considere a gramática \texttt{g\_3}. Diga quais os símbolos úteis de \texttt{g\_3}. \end{exercicio} \begin{exercicio} Escreva em Haskell a função |derives_nt| que verifica se um símbolo deriva uma sequência de símbolos terminais ou não. \end{exercicio} \begin{code} derives g _ [] = True derives g v (h:t) | h `is_terminal` g = derives g v t | h `elem` v = False | otherwise = (derives_nt' g (h:v) h) && (derives g v t) derives_nt' g v nt = or $ map (derives g v) (rhs_nt g nt) derives_nt :: Eq sy => Cfg sy -> sy -> Bool derives_nt g nt = derives_nt' g [] nt \end{code} \end{document}