% % 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{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}{}[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 Trabalho Prático N$º$2} \\ \textbf{\small Um Interpretador para a Linguagem \textsc{Calculadora}} \end{tabular} } \author{\small Grupo: \begin{tabular}[t]{lll} 55436 & LESI & Ana \\ 40000 & MCC & Tó \\ 33333 & MCC & Zé \\ \end{tabular} } \date{} %-------------------- Inicio do Documento ------------------------------- \begin{document} \maketitle Neste trabalho prático pretende-se que os alunos implementem um interpretador para uma linguagem muito simples: A linguagem \textsc{Calculadora}. O programa a desenvolver deverá utilizar as técnicas leccionadas nesta cadeira, bem como nas duas cadeiras de Métodos de Programação que a antecederam, nomeadamente: combinadores de parsing, árvores, e funções que efectuam recursividade (travessias) em árvores (e.g., catamorfismos). \bigskip \noindent \begin{tabular}{rl} \hline \\ \textbf{Entrega da Trabalho:} & data é \textit{22/12/00} \\ \\ \textbf{Constituição dos Grupos:} & Os grupos terão obrigatoriamente \textbf{3 elementos} \\ \\ \textbf{Linguagem de Prog.:} & Haskell \\ & (embora não aconselhado o trabalho poderá ser feito em C) \\ \\ \hline \end{tabular} \bigskip O enúnciado do trabalho prático está escrito em \textbf{literate Haskell}. Isto é, pode ser interpretado como um documento \LaTeX\ ou como um puro programa na linguagem Haskell. Resolva este trabalho prático neste mesmo ficheiro de modo a implementar o programa e a sua documentação. \section{A linguagem \textsc{Calculadora}} A linguagem \textsc{Calculadora} é uma linguagem para definir expressões aritméticas muito simples. Basicamente as frases tem a seguinte forma: \medskip \begin{center} \texttt{PRINT WHERE } \end{center} \medskip \noindent onde \texttt{} é uma expressão aritmética cujos operadores são \texttt{+}, \texttt{-}, \texttt{*} e \texttt{/} e os operandos são números (inteiros) ou identificadores. O bloco \texttt{} é uma lista de declarações de identificadores da forma: \medskip \begin{center} \texttt{ = } \end{center} \medskip As declarações são separadas pelo separador \texttt{;}. Uma frase concreta nesta linguagem tem a seguinte forma: \medskip \begin{center} \texttt{PRINT 1 + x * 4 - y WHERE x = 2 ; y = 7} \end{center} \medskip Pretende-se construir um programa que dada uma frase nesta linguagem interprete a expressão aritmética e produza como resultado o valor dessa expressão. \section{Gramáticas Independentes do Contexto} A gramática independente de contexto que define a \textit{estrutura concreta} de uma frase na linguagem \textsc{Calculadora} é a seguinte: \medskip \( \begin{array}{l} G = (T,N,S,P), com \\ T = \{ '+','-','*','/','+','(',')','=',';',"PRINT","WHERE",int,id\}, \\ N = \{ calc , ... \}, \\ S = calc, \\ \begin{array}[t]{lclccl} P = & \{ & prodcalc: & calc & \rightarrow & "PRINT"\ exp\ "WHERE"\ decls \\ & , & p_1: & exp & \rightarrow & ... \\ & , & ... & & & \\ & \} \end{array} \\ \end{array} \) \medskip A estrutura abstracta da linguagem é definida pela seguinte gramática abstracta: \medskip \( \begin{array}{l} G=(T,N,S,P), com \\ T = \{ int,id\}, \\ N = \{ Calc , ... \}, \\ S= Calc, \\ \begin{array}[t]{lclccl} P = & \{ & Calc: & Calc & \rightarrow & Exp\ Decls \\ & , & ExpAdd: & Exp & \rightarrow & ... \\ & , & ... & & & \\ & \} \\ \end{array} \end{array} \) \subsection{A Gramática Abstracta em Haskell} Aplicando as regras de conversão de gramáticas abstractas para tipos de dados indutivos em Haskell, apresentadas na ficha teórico-prática nº8, obtemos os seguintes tipos de dados e respectivos construtores: \begin{code} module Calculadora where import Parser data Calc = Calc Exp Decls data Exp = ... data Decls = ... \end{code} \subsection{Parsing da Linguagem \textsc{Calculadora} com Combinadores} O parser para a linguagem \textsc{Calculadora} obtém-se convertendo a gramática concreta em combinadores de parsing, de acordo com as regras definidas na ficha teórico-prática nº10. As funções semânticas usadas nos combinadores são os construtores da árvore asbtracta. Assim temos os seguinte parser: \begin{code} parsecalc :: Parser Char Calc parsecalc = prodcalc <$> token "PRINT" <*> parseexp <*> token "WHERE" <*> parsedecls where prodcalc a b c d = Calc b d parseexp = ... \end{code} \medskip \section{Interpretador da Linguagem \textsc{Calculadora}} Um dos objectivos do nosso programa é efectuar o cálculo da expressão aritmética, i.e., interpretar essa expressão. Como o resultado do parser de uma frase é uma árvore do tipo \texttt{Calc}, temos agora de construir uma função que recursivamente faz uma travessia nessa árvore e sintetiza o valor da expressão. Isto é, esta função é um catamorfismo sobre o tipo de dados \texttt{Calc}. De seguida apresentamos esta função catamórfica usando recursividade explicita (ou o catamorfismo): \begin{code} calcula :: Calc -> Integer calcula (Calc e d) = ... \end{code} \section{Extras ao trabalho prático} \begin{enumerate} \item Validação semântica: Implemente a regra semântica da linguagem que diz que um identificador usado na expressão aritmética tem que estar declarado na parte das declarações. \item Parameterização do Parser: Generalize o parser da linguagem \textsc{Calculadora} de modo a ser parameterizado com as funções semânticas. Assim, será possível instanciar o parser não só com as funções que constroem a árvore abstracta (o que já acontece), mas também com qualquer outro tipo de funções. Por exemplo, com as funções aritméticas e assim efectuar os cálculos sem construir a árvore intermédia. \item Implementação de um compilador: O programa proposto implementa um interpretador da linguagem. Propõe-se como extra desenvolver um compilador para o assembly MSP e utilizar o ambiente winMSP para interpretar o assembly gerado pelo compilador. Para tal, defina a gramática asbtracta do código MSP a ser produzido, converta-a num tipo de dados indutivo em Haskell e escreva a função \texttt{show} que transforma a estrutura abstracta na representação concreta do MSP. \end{enumerate} \end{document}