\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[portuges]{babel}
\usepackage{fullpage}
\renewcommand{\familydefault}{\sfdefault}

\title{Linguagens Formais e Compiladores - 2009/2 \\ Trabalho 1}
\author{João Paulo Pizani Flor \\ Daniel Ricardo dos Santos}
\date{16/11/2009}

\begin{document}
	\maketitle
	
	\section{Introdução}
		Neste relatório é descrita a implementação do primeiro trabalho prático da disciplina de Linguagens Formais e
		Compiladores, edição 2009/2. O objetivo principal do trabalho foi elaborar uma aplicação com interface gráfica
		que permitisse a manipulação de Autômatos Finitos, Gramáticas Regulares e Expressões Regulares. As seguintes
		operações deveriam ser suportadas:
		\begin{itemize}
			\item Edição, leitura e gravação de A.F, G.R e E.R
			\item Determinização de A.F.N.D
			\item Minimização de A.F.D
			\item Conversão de G.R para A.F e vice-versa
			\item Conversão de E.R para A.F
			\item Reconhecimento de sentenças em um A.F
		\end{itemize}
		
		Nas próximas seções serão apresentadas as ferramentas utilizadas (linguagem e bibliotecas) utilizadas na
		implementação e  a forma como os conceitos de autômato finito e gramática regular foram
		modelados na linguagem de programação.
		
		Também é comentado o formato para os arquivos gerados a partir do programa, é dada uma visão geral dos
		testes realizados sobre a implementação e, por fim, há as conclusões advindas das decisões tomadas
		para o desenvolvimento do trabalho.
		
	\section{Ferramentas utilizadas}
		A linguagem de programação \emph{Haskell} foi escolhida para a implementação deste trabalho. Haskell é uma
		linguagem de programação \emph{puramente funcional}, que utiliza tipagem forte e estática e possui avaliação
		não-estrita das expressões, ou seja, o valor de uma expressão só é calculado se e quando for preciso.
		
		Todas estas caracteríticas da linguagem pareceram se adaptar bem aos requisitos do trabalho e ao domínio
		das Linguagens Formais. Especialmente a utilização do paradigma funcional, que permitiu que as funções de
		transformação de autômatos e gramáticas ficassem muito semelhantes às definições matemáticas.
		
		Para a programação da interface gráfica foi utilizada biblioteca \emph{gtk2hs}, um binding do framework
		gráfico GTK para a liguagem Haskell. O desenho da interface em si foi feito através da ferramenta \emph{Glade},
		que gera um arquivo .xml com a descrição da interface a ser exibida. Este arquivo é lido em tempo de execução
		e a interface exibida a partir dele.
		
		Para a renderização dos diagramas de transição dos autômatos foi utilizada a ferramenta \emph{Graphviz},
		através do seu binding para a linguagem Haskell. Isso permitiu a exibição do diagrama de um autômato na tela
		e também o salvamento como um arquivo de imagem no formato PNG.
		
		Uma biblioteca bastante importante para o trabalho, e que será mais comentada a frente, foi o \emph{Parsec}
		\footnote{The Haskell Parser Combinator Library}. Ela permitiu que fossem programados parsers para o formato
		em que autômatos, gramáticas e expressões regulares são salvos em discos. Uma característica notável do Parsec
		é que a programação do parser de uma linguagem se assemelha muito à própria definição de uma gramática para
		essa linguagem.
		
	
	\section{Modelagem e Algoritmos-chave}
		Nesta seção serão dados mais detalhes sobre o funcionamento e a importância de alguns dos algoritmos-chave
		para o trabalho, e também será dada uma visão geral de como os conceitos de Autômato Finito e Gramática
		Regular foram modelados através de ADTs \footnote{do inglês \emph{Abstract Data Types}, significando tipos
		abstratos de dados}.
		
		Em geral a definição das estruturas de dados para representar tanto A.F's como G.R's são muito próximas
		das definições matemáticas destas entidades.
		
		\subsection{Autômato finito}
			Um autômato finito é representado por um tipo de dados, com exatamente os mesmos componentes que na
			definição matemática. A função de transição foi representada por uma estrutura de dados do tipo mapeamento,
			mais especificamente a implementação da biblioteca padrão de Haskell (Data.Map). O tipo de um
			estado (St) nada mais é que uma String, e o tipo símbolo (Sym) foi definido como um único caracter.
			\begin{verbatim}
				type St = String
				type Sym = Char
				
				type Delta = M.Map (St, Maybe Sym) (Set St)
				-- The transition function maps from St and Sym to a set of St's
			\end{verbatim}
			\newpage
			
			Abaixo segue o trecho de código definindo o tipo \emph{Automaton}:
			\begin{verbatim}
				data Automaton = FA { faAlphabet :: Set Sym,
                                      faStates :: Set St,
                                      faStart :: St,
                                      faFinals :: Set St,
                                      faDelta :: Delta } 
					             deriving Eq
			\end{verbatim}
			
			A expressão ``deriving Eq'', utilizada na definição, significa que dois autômatos podem ser comparados entre
			si para igualdade, e que a igualdade entre dois autômatos é inferida a partir da igualdade entre cada
			um de seus componentes. A igualdade entre autômatos foi bastante utilizada nos testes.
	
		
		\subsection{Gramática Regular}
			Na programação de um tipo de dados para Gramáticas Regulares foi necessário criar \emph{novos} tipos de
			dados para denotar símbolos terminais e não-terminais, ao invés de somente utilizar um \emph{typedef}. Isso
			foi necessário para expressar de forma correta o tipo de uma produção, que em seu lado direito deve
			diferenciar corretamente símbolos terminais e não-terminais entre si. Abaixo estão as definições para os
			tipos denotando símbolos terminais e não-terminais, respectivamente:
			\begin{verbatim}
			data TR = TR Char
				deriving Eq
			instance Show TR where
				show (TR c) = [c]

			data NTR = NTR String | Nul
				deriving Eq
			instance Show NTR where
				show (NTR s) = s
				show Nul = ""
			\end{verbatim}
			
			As expressões ``instance Show X ...'' servem para definir uma instância do tipo X para a \emph{classe} Show.
			A classe Show define como um certo tipo de dados será exibido como string, e no caso de um símbolo
			(terminal ou não-terminal), sua representação como string é ele próprio.
			
			Destaque para a definição de símbolo não-terminal (NTR), que pode tanto ser uma String OU (esta opção
			é denotada pelo símbolo $ | $ ) o valor Nul, que será omitido quando da impressão do NTR.
			
			Uma produção consiste de um lado esquerdo, que é um símbolo não-terminal, e um lado direito, que contém
			um símbolo terminal e um não-terminal (opcionalmente nulo). A definição do tipo de dados de uma gramática
			regular também é completamente análoga à definição matemática, e utiliza os tipos para símbolos terminais
			e não-terminais já mencionados.
			\begin{verbatim}
				type Prod = ( NTR , (TR,NTR) )
			
				data RGrammar = GR { rgAlphabet :: Set TR,
									 rgNT :: Set NTR,
									 rgStart :: NTR, 
									 rgProds :: Set Prod }
					            deriving Eq
			\end{verbatim}
			
		\subsection{Expressão Regular}
		    Uma expressão regular também foi modelada como um \emph{tipo abstrato de dados} nativo da linguagem Haskell,
		    e essa representaçã direta ajudou muito no tratamento das expressões. O tipo \emph{RegEx} possui a seguinte
		    definição:
		    \begin{verbatim}
                data RegEx
                    = Empty
                    | Epsilon
                    | Literal Char
                    | Or RegEx RegEx
                    | Then RegEx RegEx
                    | Star RegEx
                    deriving Show
		    \end{verbatim}
		    O tipo possui 6 \emph{construtores}: Empty, Epsilon, Literal, Or, Then e Star. Isso quer dizer, basicamente,
		    que há seis maneiras de se construir uma RegEx. Uma RegEx pode ser vazia, pode ser epsilon, pode ser um
		    caracter literal. Pode ser ainda a união ou concatenação de duas outras RegEx's ou o fechamento de uma RegEx 
		
		\subsection{Alguns algoritmos-chave}
			\subsubsection{Limit}
				Certamente, uma das funções mais importantes de todas desenvolvidas é a função \emph{limit}, que, como
				já mencionado na introdução, permitiu que vários dos algoritmos vistos em sala de aula (escritos em
				estilo tipicamente imperativo) fossem ``transformados'' para versões recursivas e puramente funcionais,
				sem	nenhum esforço. Abaixo vai a definição (notavelmente simples e elegante) da função limit:
				\begin{verbatim}
					limit :: Eq a => (a -> a) -> a -> a
					limit f s | s == next = s
					          | otherwise = limit f next
					            	where next = f s
				\end{verbatim}
				
				Pode-se perceber pela assinatura de tipo da função limit (primeira linha da definição) que ela é uma
				\emph{função de alta ordem}, pois ela toma uma função como parâmetro. O objetivo da função limit é
				calcular o valor ``limite'' de sucessivas aplicações de uma função sobre um valor inicial. O valor
				limite é o ponto em que o valor da aplicação atual e da próxima são iguais. Isso fica claro na
				definição recursiva, onde a igualdade entre o valor atual e o próximo é a condição de parada.
				
				O uso da função limit foi importante, por exemplo, na implementação da minimização da A.F's, onde o
				particionamento por classes de equivalência deve parar quando no passo atual não surgiu nenhuma nova
				classe.
				
			\subsubsection{Minimização de autômatos finitos}
				O algoritmo de minimização de autômatos finitos, inserido logo abaixo, consiste em criar as classes de
				equivalência e obter as transições do novo autômato determinístico através da tabela de transição do
				A.F.N.D, unindo os estados-alvo dos estados que constituem uma classe de equivalência.
				\begin{verbatim}
minimize' fa = newAutomaton newTrans newAcc newStart
  where newStart = foldStringSet $ getGrp minGroups oldStart
        newAcc = S.toList $ S.map (foldStringSet.(getGrp minGroups)) oldFinals
        newTrans = let ab' = S.toList ab
                        minGroups' = S.toList minGroups
                        in  concat [  [(foldStringSet g,s,[newTarget g s]) | s <- ab']  |  g <- minGroups']

        minGroups = getMinStates fa
        newTarget g s = let representative = S.findMin g
                            in foldStringSet $ getGrp minGroups (S.findMin $ transition d representative (Just s))

        (oldStart,oldFinals,d) = (faStart fa, faFinals fa, faDelta fa)
        ab = faAlphabet fa
		        \end{verbatim}
				
				As transições do A.F.D sendo produzido (newTrans) é definida da seguinte forma: Para cada uma das
				classes de equivalência calculadas existe um conjunto de \emph{transições de saída}. Os elementos
				desse conjunto são transições, todas com o mesmo estado de origem, uma para cada símbolo do alfabeto.
				Abaixo está a definição da função \emph{getMinStates}, o núcleo do algoritmo de minimização.
				\begin{verbatim}
getMinStates :: Automaton -> S.Set StateClass
getMinStates fa = limit partition'' $ S.filter (not.(S.null)) baseCase
-- The partition' algorithm doesn't work with an empty StateClass
    where partition'' = partition' fa

    baseCase = notFinals `S.insert` (S.singleton finals)
    (finals,notFinals) = S.partition isFinal stts

    isFinal s   = s `S.member` f
    (stts,f) = (faStates fa,  faFinals fa)
				\end{verbatim}
				
				A estratégia para obter o conjunto mínimo de classes de equivalência é a obtenção do limite da função
				partition', que recebe como argumento um conjunto de classes de equivalência e produz um conjunto
				de classes (possivelmente) mais subdividido. O código da função partition' está logo abaixo:
				\begin{verbatim}
partition' :: Automaton -> S.Set StateClass -> S.Set StateClass
partition' fa grs = setConcat $ S.map (partitionOne fa grs) grs
				\end{verbatim}
				
				A função partition somente aplica a função partitionOne sobre cada uma das atuais classes de
				equivalência, e agrupa os resultados para então retorná-los. A função partitionOne é a responsável por
				efetivamente dividir (possivelmente) uma classe de estados, baseando-se no critério de
				equivalência.				
				\begin{verbatim}
partitionOne :: Automaton -> S.Set StateClass -> StateClass -> S.Set StateClass
partitionOne fa grs g = let (eq,ne) = S.partition (equiv (S.findMin g)) g
                            in  (S.filter (not.(S.null)) (eq `S.insert` (S.singleton ne)))

    where equiv x y      = and $ zipWith sameGrp (allOutputs x) (allOutputs y)
          sameGrp        = (==) `on` (getGrp grs)
          allOutputs s   = S.toList $ S.unions [transition d s (Just sym) |  sym <- S.toList ab ]
          (d, ab)        = (faDelta fa, faAlphabet fa)
				\end{verbatim}

				O critério de equivalência é definido por ``equiv x y''. A definição diz que x e y são equivalente sse.
				para cada símbolo do alfabeto, os estados-alvos de x e de y estão na mesma classe de equivalência da
				iteração anterior.
							
			\subsection{Transformação de gramáticas regulares para autômatos finitos}
				O algoritmo de transformação de G.R para A.F estabelece que o autômato resultante deve um estado
				para cada símbolo não-terminal da gramática a ser convertida, além de um estado especial (denotado
				como \$) que deve ser um estado final. Abaixo está a definição da função de conversão:
				\begin{verbatim}
rgToFA :: RGrammar -> Automaton
rgToFA rg = newAutomaton trans ["$"] start
    where trans = unifyTransitions $ map buildTransition ps
        buildTransition (NTR nta, (TR t, NTR ntb)) = (nta,t,[ntb])
        buildTransition (NTR nta, (TR t, Nul)) = (nta,t,["$"])
        start = (\(NTR s)-> s) $ rgStart rg
        (ps,nts) = (rgProds rg, rgNT rg)
				\end{verbatim}
				
				O algoritmo constrói, para cada produção do tipo A -> aB, uma transição (A,a,[B]). Para cada produção
				do tipo A -> a (somente terminal no lado direito) é gerada uma transição para o estado de aceitação, na
				forma (A,a,[\$]). A função unifyTransitions serve para unificar todas as transições que
				compartilham o mesmo estado fonte e símbolo de entrada, e funciona conforme o exemplo abaixo:
				\[ (A,a,[E1]), (A,a,[E2]), ..., (A,a,[En])  \rightarrow  (A,a,[E1,E2,...,En]) \]
			
			
	\section{Abertura/Salvamento e formato dos arquivos}
		O formato definido para os arquivos salvos a partir do programa é o próprio formato texto gerado a partir
		da instância Show para cada um dos tipos de dados. Para realizar a leitura dos arquivos foi construído
		um \emph{parser}, tanto para a (meta)linguagem que denota um A.F quanto para a que denota uma G.R.
		Isso foi feito para impedir que arquivos (acidentalmente ou intencionalmente) mal-formados pudessem
		causar falhas na execução do programa.
		
		Para a construção deste parser foi utilizada a \emph{Parsec}, uma biblioteca Haskell com funções de alta ordem
		que permitem a programação de um parser de uma maneira que se assemelha bastante à própria definição de uma
		gramátic para a linguagem. Como exemplo está abaixo a programação do parser para reconhecer a
		metalinguagem que denota uma G.R. Observe que no próprio parser já está embutido o tratamento semântico
		dos não-terminais reconhecidos:
		\begin{verbatim}
			rgrammar = do
			    pgs <- prodGroup `sepEndBy1` groupSepr
			    return $ newGrammar (concat pgs)

			prodGroup = do
			    l <- nTerm
			    arrow
			    rs <- rHSides
			    return $ [(l,r) | r <- rs]

			arrow = between spaces spaces (string "->")
			groupSepr = newline

			rHSides = rHSide `sepBy` (char '|')

			rHSide = do
			    t <- lower
			    nt <- option Nul nTerm
			    return (TR t, nt)

			nTerm = do
			    x <- upper
			    xs <- many letter
			    return $ NTR (x:xs)
		\end{verbatim}
		
		Para o reconhecimento de um arquivo contendo um autômato finito foi utilizado um parser
		semelhante, que constrói o autômato a partir de uma lista de suas transições, seus estados finais e seu
		estado inicial. O parser completo que reconhece a descrição de um autômato pode ser encontrado no arquivo
		``FAComponentsParser.hs'', presente no diretório-raiz do trabalho.
		
		
	\section{Testes}
		Para o desenvolvimento do trabalho foi adotada a técnica de Desenvolvimento Guiado por Testes (TDD)
		\footnote{do inglês \emph{Test-driven development}}, onde antes de se desenvolver uma função, são
		escritos \emph{casos de teste}, ou seja, exemplos de valores de entrada e as saídas esperadas.
		
		Foram feitos testes para as funções de abertura e salvamento, para as operações de determinização e
		minimização e também para o reconhecimento de sentenças. Testes extensivos cobriram as operações de
		conversão entre o modelo interno representando um autômato e o componente de interface gráfica que
		representava a tabela de transição. Também foi testada a remoção de epsilon-transições e o
		completamento de autômatos incompletos.
		
		Ao total existem 77 casos de teste cobrindo essas operações. Eles estão sob o diretório \emph{Tests}
		e para executá-los todos em conjunto basta rodar no interpretador Haskell ou compilar o arquivo-fonte
		chamado ``AllTests.hs''
		

	\section{Conclusões}
		O fato de se utilizar uma linguagem com paradigma funcional ajudou bastante na elaboração dos algoritmos
		para manipular os autômatos e gramáticas. As definições formais destes dispositivos puderam ser aplicadas
		com poucas modificações, tanto na definição dos tipos de dados quanto nas funções que atuam sobre eles.
	
		Por outro lado, houve também algumas dificuldades advindas da escolha da linguagem. O desenvolvimento da
		interface gráfica, em particular, foi lento, principalmente no que se refere ao tratamento da tabela de
		trasição de estados. Grande parte dos algoritmos passados em aula estavam escritos utilizando de iteração, e
		não poderiam ser utilizados diretamente. Foi necessário então desenvolver alguns algoritmos por conta própria,
		e fazer uma pesquisa bibliográfica para encontrar algoritmos de manipulação de autômatos escritos em estilo
		\emph{recursivo}.
		
		Quase todos itens pedidos na especificação foram implementados. A única exceção é a transformação de A.F
		para G.R, que infelizmente não pôde ser elaborada.

		O trabalho serviu como ótima motivação para o estudo dos assuntos da disciplina, e para tornar mais
		concreto o conhecimento dos algoritmos de manipulação de linguagens regulares.

\end{document}
