% % 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 %include cfgLhs2TeX.fmt \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$º$11} \\ \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{Propriedades de Gramáticas Independentes do Contexto} Nsta ficha teórico-prática apresemtam-se funções que definem propriedades de símbolos não-termais, produções e das próprias gramáticas independentes do contexto. Estas funções são expressas em Haskell. Para tal define-se o módulo \textit{CfgProp}. \begin{code} -- -- Módulo de Propriedades de Gramáticas Independentes do Contexto -- -- Métodos de Programação III -- Universidade do Minho -- 2005/2006 -- module CfgProp where import List import Cfg \end{code} \subsection{Gramáticas Ambíguas} Uma gramática $G=(T,N,S,P)$ diz-se ambígua se existirem duas sequências de derivação diferentes para uma mesma frase $\alpha \in T^*$. A ambiguidade surge na escolha da produção a usar durante o processo de re-escrita de um símbolo não terminal. Isto é, num dado passo o processo de re-escrita de um símbolo não terminal existe mais do que uma produção possível que conduz à aceitação da frase. Logo existe ambiguidade em saber qual das diferentes alternativas (caminhos) seguir. \begin{exercicio} Considere a seguinte gramática independente de contexto $G_{exp} = (T,N,S,P)$, com: \( \begin{array}{l} T = \{ + , - , * , / , i , ( , ) \}, \\ N = \{ E \}, \\ S = E, \\ \begin{array}[t]{lclccl} P = & \{ & add: & E & \rightarrow & E\ +\ E \\ & , & sub: & & \mid & E\ -\ E \\ & , & plus: & & \mid & E\ *\ E \\ & , & div: & & \mid & E\ /\ E \\ & , & prio: & & \mid & (\ E\ ) \\ & , & numb: & & \mid & i \\ & \} \end{array} \\ \end{array} \) \noindent em que $i$ é um símbolo pseudo-terminal que representa a classe dos números inteiros. Responda às seguintes perguntas. \begin{enumerate} \item Prove que a gramática $G_{exp}$ é ambígua. Utilize para tal uma sequência de derivação LR. \item Prove que a gramática $G_{exp}$ é ambígua. Utilize para tal uma sequência de derivação LL. \end{enumerate} \end{exercicio} \begin{exercicio} Considere a gramática independente de contexto $g_4$ escrita em Haskell e apresentada a seguir. Responda às seguinte perguntas. \begin{enumerate} \item Prove que $"xwzwzx" \in {\cal L}(g_4)$ \item A gramática $g_{4}$ é ambígua? \end{enumerate} \end{exercicio} \begin{code} g_4 = Cfg ['x','y','z','w'] ['X','Y','Z','W'] 'S' [ ("p0",'X' |-> "xY") , ("p1",'Y' |-> "y") , ("p1",'Y' |-> "Zy") , ("p2",'Z' |-> "zW") , ("p3",'W' |-> "wz") , ("p4",'W' |-> "") ] \end{code} \subsection{Gramáticas Não Ambíguas} Uma gramática independente do contexto diz-se \textit{não ambígua} se para toda a frase da linguagem definida pela gramática existir uma única sequência de derivação para essa frase. Neste caso não existe qualquer ambiguidade na escolha do caminho a seguir. Neste secção apresentamos a definição formal de algumas funções sobre gramáticas que nos ajudarão posteriormente a provar que uma gramática é não ambígua. \subsection{Funções $First$ e $First_N$} A função $First$ calcula o conjunto de símbolos que iniciam derivações a partir de uma sequência de símbolos terminais e não terminais. A função \textit{First} de uma sequência de símbolos define-se do seguinte modo: \[ First : (N \cup T)^* \rightarrow 2^T \] \noindent com $First (\alpha)$ definido por, para $a \in T$ e $X \in N$: \begin{enumerate} \item Se $\alpha = a \alpha'$ então $First (\alpha) = \{ a\}$; \item Se $\alpha = A \alpha'\ \wedge\ A \rightarrow \beta_1\ \mid \cdots \mid\ \beta_n\ \wedge\ \forall_i\ \beta_i \not\Rightarrow^* \epsilon$ então \\ \[ First (\alpha) = \bigcup_{1 \leq i \leq n} First(\beta_i) \] \item Se $\alpha = A \alpha'\ \wedge\ A \rightarrow \beta_1\ \mid \cdots \mid\ \beta_n\ \wedge\ \exists_i\ \beta_i \Rightarrow^* \epsilon$ então\\ \[ First (\alpha) = First(\alpha') \cup \bigcup_{1 \leq i \leq n} First(\beta_i) \] \end{enumerate} A função $First_N$ determina o conjunto de símbolos que iniciam derivações a partir de um símbolo não terminal. A função $First_N$ de um símbolo não terminal define-se como: \[ \begin{array}{ll} First_{N} :& N \rightarrow 2^T \\ First_{N} (X): & \bigcup_{(X \rightarrow \alpha_i) \in P} First (\alpha_i) \end{array} \] \begin{exercicio} Considere de novo a gramática $g_{exp}$. Calcule os seguintes conjuntos: \begin{enumerate} \item $First(p_0)$ \item $First_N(E)$ \end{enumerate} \end{exercicio} \begin{exercicio} Considere de novo a gramática $g_4$. Calcule os conjuntos $First_N$ de todos os símbolos não terminais. \end{exercicio} A função \textit{First} escreve-se em Haskell seguindo directamente a sua definição formal. A função Haskell $first$ tem tipo: \begin{code} first :: Eq sy => Cfg sy -- grammar -> [sy] -- sequence of symbols -> [sy] -- First set \end{code} Na definição da função |first| temos de ter o cuidado de não voltar a considerar um símbolo não terminal que já o tenha sido antes. Para tal usamos uma função auxiliar |first'| que tem um parametro adicional onde são acumulados os símbolos já considerados. \begin{code} first g sy = nub $ first' g [] sy first' :: Eq sy => Cfg sy -- grammar -> [sy] -- accumulator: nonterminals visited so far -> [sy] -- sequence of symbols -> [sy] -- First set first' g _ [] = [] first' g v (h:t) | h `is_terminal` g = [h] | h `elem` v = first' g v t | nullable_nt g h = (first' g (h:v) t) `union` first_rhs g v h | otherwise = first_rhs g v h where first_rhs g v nt = concat $ map (first' g (nt:v)) (rhs_nt g nt) \end{code} A função $first_N$ define-se como um $map$ da função anterior pelos lados direitos das produções do símbolo dado. \begin{code} first_N :: Eq sy => Cfg sy -- grammar -> sy -- nonterminal -> [sy] -- First set first_N g nt = nub $ concat $ map (first g) (rhs_nt g nt) \end{code} \begin{exercicio} Utilize as definições Haskell para confirmar os resultados do exercício anterior. \end{exercicio} \section{Função $Follow$} A função $Follow$ de um símbolo não terminal calcula o conjunto de símbolos terminais que se podem seguir a uma derivação a partir do símbolo não terminal. A função $Follow$ de um símbolo não terminal define-se do seguinte modo: \[ \begin{array}{ll} Follow :& N \rightarrow 2^T \\ Follow (X): & \bigcup_{(Y \rightarrow \alpha X \beta) \in P} First (\beta) \cup \left\{ \begin{array}{ll} \emptyset & se\ \beta \not\Rightarrow^* \epsilon\\ Follow(Y) & se\ \beta \Rightarrow^* \epsilon \end{array} \right. \end{array} \] \begin{exercicio}\label{exerc:follow} Considere de novo as gramática $g_{exp}$ e $g_4$. Calcule o conjunto de símbolos $Follow$ para os símbolos não terminais destas gramáticas. \end{exercicio} \begin{exercicio} No cálculo da função \textit{Follow} de um símbolo não terminal é necessário identificar primeiro o conjunto de produções onde o símbolo não terminal ocorre no lados direito e as sequências de símbolos que se segue a cada ocorrência. Escreva em Haskell as seguintes funções sobre o tipo |Cfg|: \begin{enumerate} \item Função $rhs\_with\_nt$ que dado uma gramática e um símbolo não terminal, calcula o conjunto de produções (sem nome) em que esse símbolo ocorre no lado direito. \item Função $suffices$ que dado um símbolo não terminal e uma produção devolve a lista de sequências de símbolos que seguem as ocorrências do não terminal no lado direito da produção dada. Note que um símbolo não terminal pode ocorrer mais do que uma vez no lado direito de um produção. Associe a cada um dos elementos desta lista o lado esquerdo da produção onde o sufixo ocorreu. Um exemplo de execução desta função apresenta-se a seguir. \begin{verbatim} *CfgProp> suffices 'B' ('A' |-> ['B','C','B']) [('A',"CB"),('A',"")] \end{verbatim} \item Função $rhs\_suffices$ que dado uma gramática e um símbolo não terminal $X$ devolve as sequências de símbolos que seguem as ocorrências de $X$ nos lados direitos das produções de $P$. A estes sufixos são também associados ao símbolo não terminal do lado esquerdo de $P$. Por exemplo, se executarmos esta função sobre a gramática $g_3$ e o não terminal $B$ temos: \begin{verbatim} *CfgProp> rhs_suffices g_3 'B' [('A',"CB"),('A',""),('B',"b"),('C',"")] \end{verbatim} \end{enumerate} \end{exercicio} \begin{code} rhs_with_nt :: Eq sy => Cfg sy -> sy -> [[sy]] rhs_with_nt g nt = filter (elem nt . tail) (map snd (prods g)) suffices :: Eq sy => sy -> [sy] -> [(sy, [sy])] suffices nt (lhs : rhs) = rhs_suffices_nt rhs nt where rhs_suffices_nt [] _ = [] rhs_suffices_nt (h:t) nt | h == nt = (lhs,t) : rhs_suffices_nt t nt | otherwise = rhs_suffices_nt t nt rhs_suffices :: (Eq sy) => Cfg sy -> sy -> [(sy, [sy])] rhs_suffices g nt = concat $ map (suffices nt) (rhs_with_nt g nt) \end{code} A função \textit{Follow} escreve-se em Haskell seguindo de novo a sua definição formal. Porém, e tal como na definição da função |first| e |nullable|, temos de ter o cuidado de manter uma lista de símbolos não terminais já considerados de modo à definição da função terminar. O tipo da função |follow| é: \begin{code} follow :: Eq sy => Cfg sy -- grammar -> sy -- nonterminal -> [sy] -- Follow set \end{code} A função escreve-se em Haskell da seguinte forma: \begin{code} follow g nt = nub $ follow' g [] nt follow' :: Eq sy => Cfg sy -> [sy] -> sy -> [sy] follow' g v nt | nt `elem` v = [] | otherwise = concat $ map (follow'' g (nt:v)) (rhs_suffices g nt) follow'' :: (Eq sy) => Cfg sy -> [sy] -> (sy, [sy]) -> [sy] follow'' g v (l,r) | nullable g [] r = first g r `union` follow' g v l | otherwise = first g r \end{code} \begin{exercicio} Utilize a definição Haskell para verificar as soluções do exercício~\ref{exerc:follow}. \end{exercicio} \section{Função Lookahead} Como foi referido anteriormente, para uma gramática ser ambígua não pode existir ambiguidade na escolha da produção a utilizar em cada passo da derivação de uma frase. Um modo de garantir que uma gramática não possui ambiguidade na escolha da produção a utilizar, consiste no seguinte: sempre que se vai expandir um símbolo não terminal $A$, tenta-se {\em olhar para a frente}\footnote{Na terminologia inglesa designa-se por {\em Lookahead}.}, de modo a determinar quais os símbolos terminais que iniciam as várias alternativas. Caso estes inícios sejam dijuntos, então não existe ambiguidade na escolha do lado direito, pelo qual $A$ vai ser expandido. Formalmente, a função que permite "olhar para a frente", designada \textit{Lookahead}, define-se do seguinte modo: \[ \begin{array}{ll} Lookahead :& P \rightarrow 2^T \\ Lookahead (A \rightarrow \alpha): & First(\alpha) \cup \left\{ \begin{array}{ll} \emptyset & se\ \alpha \not\Rightarrow^* \epsilon\\ Follow(A) & se\ \alpha \Rightarrow^* \epsilon \end{array} \right. \end{array} \] E a sua escrita em Haskell segue directamente a definição formal. \begin{code} lookahead :: Eq sy => Cfg sy -- grammar -> [sy] -- production -> [sy] -- Lookahead set lookahead g p | nullable g [] (rhs p) = nub $ first g (rhs p) ++ follow g (lhs p) | otherwise = nub $ first g (rhs p) \end{code} \begin{exercicio} Considere de novo as gramática $g_{exp}$ e $g_4$. Calcule o conjunto de Lookaheads das produções de ambas as gramáticas. Utilize a definição da função em Haskell para confrmar estes resultados. \end{exercicio} \begin{exercicio} Escreva em Haskell as seguintes funções sobre o tipo de dados |Cfg|: \begin{enumerate} \item Função $lookaheads_nt$ que dado uma gramática e um símbolo não terminal devolve o conjunto de lokaheads das produções que tem o símbolo não terminal como lado esquerdo. \item Função $all\_lookaheads$ que dado uma gramática devolve os lookaheads de todas as produções. \end{enumerate} \end{exercicio} \begin{code} all_lookaheads g = map (lookahead g) (map snd (prods g)) lookaheads_nt g nt = map (lookahead g) (prods_nt g nt) \end{code} \section{Condição LL(1)} Para garantir que não há ambiguidade na escolha da produção, definimos a condição $LL(1)$. Uma gramática $G = (T,N,S,P)$ satisfaz a {\em condição LL(1)} se \[ \forall_{A \rightarrow \alpha_1, A \rightarrow \alpha_2 \in P} : Lookahead (A \rightarrow \alpha_1) \cap Lookahead (A \rightarrow \alpha_2) = \emptyset \] Que se define facilmente em Haskell do seguinte modo: \begin{code} ll_1_nt g nt = and (map (== []) (intersects xs)) where xs = lookaheads_nt g nt intersects [] = [] intersects (h:t) = (map (intersect h) t) ++ (intersects t) ll_1 :: Eq sy => Cfg sy -> Bool ll_1 g = and $ map (ll_1_nt g) (nonterminals g) \end{code} \begin{exercicio} Utilizando a definição formal da condição LL(1) e a sua representação em Haskell, responda às seguintes perguntas: \begin{enumerate} \item Prove, utilizando a definição formal, que a gramática $g_exp$ não é $LL(1)$. \item Prove, utilizando a definição formal, que a gramática $g_4$ não é $LL(1)$. \item Prove que a gramática $g_4$ é não ambígua. \item Prove que a gramática $g_exp$ é ambígua. \item Utilize a definição em Haskell para confirmar estes resultados. \end{enumerate} \end{exercicio} \end{document}