M.P.I - 1998/99 - Trabalho Prático Nr. 4
[ DI/UM ]

Introdução

Este trabalho deve ser realizado por grupos com um máximo de três alunos. Deve ser entregue até ao dia 22 de Janeiro de 1999, na recepção do Departamento de Informática , e nele deve constar:

• a identificação dos membros do grupo (nome; número; turno prático e curso);
• listagem do código desenvolvido.

Objectivo

Um compilador é um programa que traduz uma linguagem dita de alto nível numa linguagem (dita de baixo nível ) que seja executável por uma máquina. Por exemplo, o gcc compila C/C++ em código objecto que corre numa variadade de arquitecturas.

Compiladores são normalmente programas complexos. Constam essencialmente de duas partes: o analisador sintático que lê o texto de entrada (o programa fonte a compilar) e cria uma sua representação interna, estruturada em árvore; e o gerador de código que converte essa representação interna em código executável. Note-se que tal representação intermédia pode ser usada para outros fins, por exemplo, para gerar uma listagem de qualidade ('pretty print') do programa fonte.

O projecto de compiladores é um assunto complexo que será assunto de outras disciplinas. Neste trabalho pretende-se apenas fazer uma introdução ao assunto, mostrando como tais programas se podem construir funcionalmente à custa de cata/ana/hilo-morfismos da linguagem em causa.

A Linguagem

Para cumprirmos o nosso objectivo, a linguagem deste trabalho terá que ser, naturalmente, muito simples: escolheu-se a das expressões aritméticas com inteiros, e.g. 1 + 2 , 3 * (4 + 5) etc.. Como representação interna adopta-se o seguinte tipo polinomial, igualmente simples:

data Expressao = Num Int
               | Bop Expressao Op Expressao
data Op = Op String

Ponto 1

Escreva as definições dos {cata, ana e hilo}-morfismos deste tipo de dados segundo o método ensinado nesta disciplina (recorde módulos como e.g. BTree.hs etc.).

Ponto 2

Como aplicação do módulo desenvolvido no ponto 1, defina como {cata, ana ou hilo}-morfismos as funções seguintes:

• calcula :: Expressao -> Int que calcula o valor de uma expressão;
• factoriza :: Int -> Expressão que converte um número natural num produto de factores primos.

Ponto 3

Em anexo é apresentado código Hugs 1.4 que permite declarar Expressao como instância da classe Read. Assim, read :: String -> Expressao pode ser vista como o analisador sintático do nosso minúsculo compilador de expressões aritméticas.

Analise o código apresentado, corra-o e escreva no seu relatório uma explicação do seu funcionamento, que deverá saber defender aquando da apresentação oral do relatório.

Valorização +: exprima este analisador sintático como um anamorfismo de String para Expressao.

Ponto 4

Defina como {cata, ana ou hilo}-morfismos as funções

• compile :: String -> Codigo - trata-se do compilador propriamente dito. Deverá ser gerado código posfixo para uma máquina elementar de 'stack'. O tipo Codigo pode ser definido à escolha. Dão-se a seguir exemplos de comportamentos aceitáveis para esta função:

  Tp4> compile "2+4"
  ["PUSH 2", "PUSH 4", "ADD"]
  Tp4> compile "3*(2+4)"
  ["PUSH 3", "PUSH 2", "PUSH 4", "ADD", "MUL"]
  Tp4> compile "(3*2)+4"
  ["PUSH 3", "PUSH 2", "MUL", "PUSH 4", "ADD"]
  Tp4>
  

• show :: Expressao -> String - gera a representação textual de uma Expressao pode encarar-se como o 'pretty printer' associado ao nosso compilador.

Ponto 5

Generalize o tipo Expressao de forma a admitir operadores unários (e.g. -5) e repita os exercícios dos pontos anteriores.

Anexos

A1 - Módulo Combinadores

module Combinadores where

depois :: (ReadS a) -> (ReadS b) -> ReadS (a,b)
depois _ _ [] = []
depois r1 r2 input = [((x,y),i2) | (x,i1) <- r1 input , 
                                   (y,i2) <- r2 i1]

readSeq :: (ReadS a) -> ReadS [a]
readSeq r input 
  = case (r input) of
    [] -> [([],input)]
    l -> concat (map continua l)
         where continua (a,i) = map (c a) (readSeq r i)
               c x (xs,i) = ((x:xs),i)                     

ou :: (ReadS a) -> (ReadS a) -> ReadS a
ou r1 r2 input = (r1 input) ++ (r2 input)

senao :: (ReadS a) -> (ReadS a) -> ReadS a
senao r1 r2 input = case (r1 input) of
                     [] -> r2 input
                     l  -> l

readConst :: String -> ReadS String
readConst c = (filter ((== c).fst)) . lex

pcurvos = parentesis '(' ')'
prectos = parentesis '[' ']'
chavetas = parentesis '{' '}'

parentesis :: Char -> Char -> (ReadS a) -> ReadS a
parentesis _ _ _ [] = []
parentesis ap pa r input 
  = do 
      ((_,(x,_)),c) <- ((readConst [ap]) `depois` (
                        r                `depois` (
                        readConst [pa])))           input
      return (x,c)

A2 - Expressões

import Combinadores

data Expressao = Num Int 
               | Bop Expressao Op Expressao 
               deriving Show
data Op = Op String deriving Show

-- Read para Exp's
readOp :: String -> [(Op,String)]
readOp input = do 
                 (x,y) <- lex input
                 return ((Op x),y)

readNum :: ReadS Expressao
readNum  = (map (\ (x,y) -> ((Num x), y))).reads

readBinOp :: ReadS Expressao
readBinOp = (map (\ ((x,(y,z)),t) -> ((Bop x y z),t))) .
                   ((readNum `ou` (pcurvos readExp))
                    `depois` (readOp `depois` readExp))

readExp :: ReadS Expressao
readExp = readBinOp `ou` (
          readNum `ou` (
          pcurvos readExp))

instance Read Expressao where
   readsPrec _ = readExp

Voltar à página principal de MP-I . Outras disciplinas leccionadas pelo DIUM