Capítulo 14 Parsers - DECOM · 2013. 3. 25. · Para indicar sucesso ou falha podemos usar o construtor de tipo Maybe do prelúdio: dataMaybe a =Nothing | Just a Portanto o tipo

1/75

Programação Funcional

Capítulo 14

Parsers

José Romildo Malaquias

Departamento de ComputaçãoUniversidade Federal de Ouro Preto

2012.2

2/75

1 Parsers

2 Definindo um tipo para parsers

3 Parsers básicos

4 Combinadores de parsers

5 Mônadas

6 Mais combinadores de parsers

7 Calculadora

3/75

Tópicos

1 Parsers


3 Parsers básicos


5 Mônadas


7 Calculadora

4/75

Análise sintática ou parsing

Análise sintática (também conhecida pelo termo em inglês parsing) é oprocesso de analisar um texto para determinar sua estrutura lógica.

O texto pode descrever, por exemplo, uma expressão aritmética, um programa decomputador, ou um banco de dados.

A análise sintática transforma o texto em uma estrutura de dados (em geral umaárvore) que

captura a hierarquia implícita no texto, eé conveniente para processamento posterior.

Por exemplo, a análise sintática de uma expressão aritmética pode produzir umaárvore com constantes nas folhas, e operadores nos nós internos.

1+2*3

+

1 ×

2 3

parsing

5/75

Parsers

Analisador sintático ou parser é um objeto que faz análise sintática de um textopara determinar a sua estrutura lógica.

Um parser transforma uma string em um valor de um determinado tipo.

texto parser estrutura de dados

6/75

Tópicos

1 Parsers


3 Parsers básicos


5 Mônadas


7 Calculadora

7/75

Como representar um parser em Haskell?

Definir o tipo polimórficoParser aou seja, o tipo dos parsers que transformam uma string em um valor do tipo a.

Definir uma função para aplicar um parser a uma string:

parse :: Parser a -> String -> a

Definir parsers básicos.

Definir combinadores de parsers, que permitem construir novos parsers usandoparsers mais simples.

8/75

Um parser é uma função

Um parser pode ser representado por uma função que recebe uma string eretorna um valor que é construído a partir da string.

type Parser a = String -> a

Como um parser é uma função, para aplicá-lo basta aplicar a função diretamenteà string de entrada:

parse :: Parser a -> String -> aparse p s = p s

9/75

Um parser é uma função (cont.)

Exemplo:parser para datas no formato: DD/MM/AAAAdata Data = MkData Int Int Int

deriving (Show)

import Data.Char (isDigit, digitToInt)

pData :: Parser Data

pData [d1,d2,’/’,m1,m2,’/’,a1,a2,a3,a4]| all isDigit [d1,d2,m1,m2,a1,a2,a3,a4] = MkData d m awhere

d = 10*(digitToInt d1) + (digitToInt d2)m = 10*(digitToInt m1) + (digitToInt m2)a = 1000*(digitToInt a1) + 100*(digitToInt a2) +

10*(digitToInt a3) + (digitToInt a4)

10/75

Um parser é uma função (cont.)

parse pData "18/11/2011" MkData 18 11 2011parse pData "18/11/2011 13:30" ERROparse pData "8/1/2012" ERROparse pData "d5/m9/2012" ERRO

11/75

O tipo dos parsers deve ser um novo tipo

A definição de tipo dada

type Parser a = String -> a

é inadequada porque queremos um novo tipo, distinto de todos os outros tipos,porém isomorfo ao tipo das funções de String em a.

Definindo o tipo dos parsers com newtype:

newtype Parser a = MkP (String -> a)

A função que aplica um parser a uma string pode ser definida como:

parse :: Parser a -> String -> aparse (MkP fun) s = fun s

12/75

O tipo dos parsers deve ser um novo tipo (cont.)

Exemplo:parser para datas no formato: DD/MM/AAAApData :: Parser DatapData = MkP f

wheref [d1,d2,’/’,m1,m2,’/’,a1,a2,a3,a4]| all isDigit [d1,d2,m1,m2,a1,a2,a3,a4] = MkData d m awhere

d = 10*(digitToInt d1) + (digitToInt d2)m = 10*(digitToInt m1) + (digitToInt m2)a = 1000*(digitToInt a1) + 100*(digitToInt a2) +


parse pData "18/11/2011" MkData 18 11 2011parse pData "18/11/2011 13:30" ERROparse pData "8/1/2012" ERROparse pData "d5/m9/2012" ERRO

13/75

Um parser pode não usar toda a entrada

A última definição dada para o tipo dos parsers

newtype Parser a = MkP (String -> a)

ainda não é adequada, pois ela não prevê a possibilidade de sequenciamento deparsers.

Um parser pode usar apenas parte (um prefixo) da string dada, devendo entãoretornar:

o valor construído a partir do prefixo, eo sufixo da string que não foi consumido.

Assim o resultado da função pode ser representado por um par.

newtype Parser a = MkP (String -> (a,String))

Isto permite a outro parser continuar a análise usando o restante da string(sufixo) que não foi utilizado.

Adaptando o tipo da função que aplica um parser a uma string:

parse :: Parser a -> String -> (a,String)parse (MkP fun) s = fun s

14/75

Um parser pode não usar toda a entrada (cont.)


wheref (d1:d2:’/’:m1:m2:’/’:a1:a2:a3:a4:resto)

| all isDigit [d1,d2,m1,m2,a1,a2,a3,a4]= (MkData d m a,resto)

whered = 10*(digitToInt d1) + (digitToInt d2)m = 10*(digitToInt m1) + (digitToInt m2)a = 1000*(digitToInt a1) + 100*(digitToInt a2) +


parse pData "18/11/2011" (MkData 18 11 2011,"")parse pData "18/11/2011 13:30" (MkData 18 11 2011," 13:30")parse pData "8/1/2012" ERROparse pData "d5/m9/2012" ERRO

15/75

Um parser pode suceder ou falhar

Um parser pode suceder ou falhar ao ser aplicado a uma string, uma vez quepode não ser possível construir um valor do tipo desejado a partir da stringusando o parser.

Assim é desejável que o resultado do parser indique a falha ou o sucesso,juntamente com o valor resultante quando houver sucesso.

Para indicar sucesso ou falha podemos usar o construtor de tipo Maybe doprelúdio:

data Maybe a = Nothing | Just a

Portanto o tipo dos parsers deve refletir esta possibilidade:

newtype Parser a = MkP (String -> Maybe (a,String))

A função que aplica um parser a uma string deve ter o seu tipo adaptado a estanova definição:

parse :: Parser a -> String -> Maybe (a,String)parse (MkP fun) s = fun s

ou de forma mais concisa:parse (MkP fun) = fun

16/75

Um parser pode suceder ou falhar (cont.)


wheref (d1:d2:’/’:m1:m2:’/’:a1:a2:a3:a4:resto)

| all isDigit [d1,d2,m1,m2,a1,a2,a3,a4]= Just (MkData d m a,resto)

whered = 10*(digitToInt d1) + (digitToInt d2)m = 10*(digitToInt m1) + (digitToInt m2)a = 1000*(digitToInt a1) + 100*(digitToInt a2) +

10*(digitToInt a3) + (digitToInt a4)f _ = Nothing

parse pData "18/11/2011" Just (MkData 18 11 2011,"")parse pData "18/11/2011 13:30" Just (MkData 18 11 2011," 13:30")parse pData "8/1/2012" Nothingparse pData "d5/m9/2012" Nothing

17/75

Tópicos

1 Parsers


3 Parsers básicos


5 Mônadas


7 Calculadora

18/75

Parser básico: failure

Um parser muito simples é aquele que sempre falha, independentemente da entrada.

failure :: Parser afailure = MkP ( \_ -> Nothing )

19/75

Parser básico: failure (cont.)

Exemplos:

parse failure "6123" Nothingparse failure "bom dia" Nothingparse failure "-89" Nothingparse failure "" Nothing

20/75

Parser básico: preturn

Outro parser muito simples é aquele que sempre sucede, resultando em um valorespecificado, independente da entrada.

preturn :: a -> Parser apreturn x = MkP ( \s -> Just (x,s) )

21/75

Parser básico: preturn (cont.)

Exemplos:

parse (preturn False) "6123" Just (False,"6123")parse (preturn ’#’) "bom dia" Justs (’#’,"bom dia")parse (preturn ()) "-89" Just ((),"-89")parse (preturn 18) "" Just (18,"")

22/75

Parser básico: preturn (cont.)

O método sobrecarregado return da classe Monad será utilizado em vez da funçãopreturn.

23/75

Parser básico: item

Outro parser muito simples é aquele que obtém o primeiro caracter da string deentrada.

item :: Parser Charitem = MkP ( \s -> case s of

x:xs -> Just (x,xs)"" -> Nothing

)

24/75

Parser básico: item (cont.)

Exemplos:

parse item "6123" Just (’6’,"123")parse item "bom dia" Just (’b’, "om dia")parse item "-89" Just (’-’, "89")parse item "" Nothing

25/75

Tópicos

1 Parsers


3 Parsers básicos


5 Mônadas


7 Calculadora

26/75

Combinando de parsers

Parsers mais simples podem ser combinados de diferentes maneiras para formarparsers mais complexos.

Combinadores de parsers são funções que recebem parsers como argumentos eproduzem novos parsers a partir deles.

27/75

Seqüenciamento de parsers

Uma das formas mais simples de combinar parsers é o seqüenciamento.

A função pseq recebe dois parsers e resulta em um novo parser que, quandoaplicado:

aplica o primeiro parser na string inicial, ese houver sucesso, aplica o segundo parser no resto da string, ese houver sucesso, retorna o par dos valores retornados por cada um dos parsers

28/75

Seqüenciamento de parsers (cont.)

pseq :: Parser a -> Parser b -> Parser (a,b)pseq p q =MkP (\s -> case parse p s of

Nothing -> NothingJust (x,s’) -> case parse q s’ of

Nothing -> NothingJust (y,s’’) -> Just ((x,y),s’’)

)

29/75


Exemplos:

parse (pseq item item) "6123" Just ((’6’,’1’),"23")

parse (pseq item (preturn 5)) "bom dia" Just ((’b’,5), "om dia")

parse (pseq item failure) "-89" Nothing

parse (pseq item item) "" Nothing

30/75


A função pbind recebe um parser e uma função, e resulta em um novo parserque, quando aplicado a uma string:

aplica o parser dado (primeiro argumento) à string inicial, ese houver sucesso, aplica a função dada (segundo argumento) ao resultado doprimeiro parser, obtendo um segundo parser, eaplica este segundo parser ao resto da string

Observe que:O primeiro argumento é um parser.O segundo argumento é uma função cujo resultado é um parser.Esta função é aplicada ao valor retornado pelo primeiro parser.Assim o valor produzido na aplicação do primeiro parser pode ser utilizado dameneira que for mais conveniente, através desta função.O segundo parser é o resultado da aplicação da função dada ao valor produzido peloprimeiro parser.O resultado final é o resultado do segundo parser.

31/75


pbind :: Parser a -> (a -> Parser b) -> Parser bpbind p f =

MkP (\s -> case parse p s ofNothing -> NothingJust (x,s’) -> parse (f x) s’

)

32/75


Exemplos:

parse (pbind item (\k -> return (toUpper k))) "h := 34;" Just (’H’," := 34;")

parse (pbind item (\_ -> item)) "-89078" Just (’8’,"9078")

parse (pbind item (\x -> preturn "FIM") "" Nothing

let myparser =pbind item

(\m -> pbind item (\n -> preturn [m,n]))in map (parse myparser) [":= 34;", ";"] [Just (":=", " 34;"), Nothing]

33/75


O método sobrecarregado (>>=) da classe Monad será utilizado em vez dafunção pbind aqui definida.

34/75

Tópicos

1 Parsers


3 Parsers básicos


5 Mônadas


7 Calculadora

35/75

Mônadas

Mônadas são estruturas que representam computações que podem serrealizadas em seqüência.

O prelúdio tem uma classe para as mônadas:class Monad m where

return :: a -> m a(>>=) :: m a -> (a -> m b) -> m b(>>) :: m a -> m b -> m bfail :: String -> m a

p >> q = p >>= \_ -> q

fail msg = error msg

36/75

Mônadas (cont.)

return xé uma computação que não faz nada e retorna o valor x

p >>= fé uma computação que executa a computação p e, em seguida, aplica a função fao resultado de p retornando uma segunda computação, que é então executada(permitindo assim o sequenciamento das duas computações)

p >> qé uma computação que executa p e q em seqüência; o resultado de p é ignorado

fail msgé uma computação que falha com a mensagem de erro msg

37/75

Mônadas (cont.)

O construtor de tipo IO, apresentado no capítulo sobre entrada e saída, é umamônada.

A expressão do estudada anteriormente pode ser utilizada com qualquer mônadapara execução de computações seqüenciais.

Se necessário, reveja a seção sobre a expressão do que foi apresentada nocapítulo sobre entrada e saída.

38/75

Parsers são mônadas

O construtor de tipo Parser é uma mônada e representa uma computação queconstrói um valor a partir de uma dada string.

return x é um parser que não usa a string de entrada e resulta no valor x.

A função (>>=) permite o seqüenciamento de dois parsers:p >>= f é um parser que, quando aplicado a uma string, primeiramente aplica oparser p a esta string. Caso esta aplicação suceda resultando em um valor x, afunção f é aplicada a x para obter o segundo parser da seqüência, que é entãoaplicado à string que restou da aplicação do primeir parser.

39/75

Parsers são mônadas (cont.)

instance Monad Parser wherereturn x = MkP ( \s -> Just (x,s) )

p >>= f = MkP ( \s -> case parse p s ofNothing -> NothingJust (x,s’) -> parse (f x) s’

)

Observe que os métodos return e (>>=) correspondem às funções preturn epbind apresentados anteriormente.

40/75


Exemplos:parse (return 8) "6123" Just (8,"6123")

parse (return "alpha") "x := 2 + 3" Just ("alpha","x := 2 + 3")

parse (return ()) "abc" Just ((),"abc")

parse (return (0,1)) "" Just ((0,1),"")

41/75


parse (item >>= \c -> return (ord c - ord ’0’)) "7123" Just (7,"123")

let p = item >>= \x ->return [x,x]

in parse p "2+3*4" Just ("22","+3*4")

let p = item >>= \x ->item >>= \y ->return (x,y)

in parse p "abcde" Just ((’a’, ’b’),"cde")

let p = item >>= \x ->item >>= \y ->return [x,y]

in parse p "a" Nothing

42/75


parse (item >> return 0) "abcd" Just (0,"bcd")

parse (item >> item) "abcd" Just (’b’,"cd")

parse (item >> item >> return ()) "abcd" Just ((),"cd")

parse (fail "unexpected character") "abcd" ERROR: unexpected character

43/75


{- usando a expressão do -}

let p = do x <- itemitemy <- itemreturn (x,y)

in parse p "2+3*4" Just ((’2’,’3’),"*4")

Esta expressão é expandida pelo compilador de Haskell para:

let p = item >>= \x ->item >>item >>= \y ->return (x,y)

in parse p "2+3*4"

44/75


Exercício 1

Defina o combinador de parser pseq apresentado anteriormente usando (>>=) ereturn.

45/75


Exercício 2

Defina a função psat :: (a -> Bool) -> Parser a -> Parser a que recebe umafunção f e um parser p e retorna um parser que, ao ser executado, executa o parser pe, havendo sucesso, aplica f ao seu resultado e verifica o valor obtido: se verdadeiro,o resultado de p é o resultado final; se falso, ocorre uma falha.Por exemplo:

parse (psat isAlpha item) "Java" Just (’J’,"ava")parse (psat isDigit item) "Java" Nothingparse (psat isDigit item) "56+3" Just (’5’,"6+3")parse (psat (==’#’) item) "#java" Just (’X’,"java")parse (psat (==’_’) item) "#java" Nothing

Use as funções (>>=) e return, e a expressão condicional if.

46/75


Exercício 3

Defina o parser lower :: Parser Char que procura por uma letra minúscula nocomeço da string de entrada.Por exemplo:

parse lower "alpha" Just (’a’,"lpha")parse lower "pi-12.3" Just (’p’,"i-12.3")parse lower "Pi-12.3" Nothingparse lower "12.3" Nothingparse lower "" Nothing

Use as funções psat e Data.Char.isLower.

47/75


Exercício 4

Defina o parser upper :: Parser Char que procura por uma letra minúscula nocomeço da string de entrada.Por exemplo:

parse upper "Alpha" Just (’A’,"lpha")parse upper "Pi-12.3" Just (’P’,"i-12.3")parse upper "pi-12.3" Nothingparse upper "12.3" Nothingparse upper "" Nothing

Use as funções psat e Data.Char.isUpper.

48/75


Exercício 5

Defina um parser upperLower :: Parser (Char,Char) que reconhece uma letramaiúscula seguida de uma letra minúscula.Por exemplo:

parse upperLower "Alpha" Just ((’A’,’l’),"pha")parse upperLower "Xy" Just ((’X’,’y’),"")parse upperLower "xYz" Nothingparse upperLower "H" Nothing

49/75


Exercício 6

Defina o parser digit :: Parser Int que procura por um dígito no começo da stringde entrada, retornando o valor numérico associado em caso de sucesso.Por exemplo:

parse digit "6483" Just (6,"483")parse digit "9+12" Just (9,"+12")parse digit "pi/3" Nothingparse digit "" Nothing

Use as funções psat, return e Data.Char.ord.

50/75


Exercício 7

Defina a função char :: Char -> Parser Char que recebe um caractere x everifica se x é o próximo item da string de entrada.Por exemplo:

parse (char ’J’) "Java" Just (’J’,"ava")parse (char ’J’) "Haskell" Nothingparse (char ’*’) "*pointer" Just (’*’,"pointer")parse (char ’*’) "alfa+1" Nothingparse (char ’&’) "" Nothing

Use a função psat e uma seção do operador (==).

51/75


Exercício 8

Defina a função string :: String -> Parser String que recebe uma string str eprocura por str no começo da string de entrada.Por exemplo:

parse (string "while") "while a>0" Just ("while"," a>0")parse (string "while") "if a>0" Nothingparse (string "do") "do c while a>0" Just ("do"," c while a>0")parse (string "do") "" Nothingparse (string "") "x := 1" Just ("","x := 1")

Use a função char e recursividade.

52/75

Tópicos

1 Parsers


3 Parsers básicos


5 Mônadas


7 Calculadora

53/75

Alternativas

A fim de podermos construir parsers mais sofisticados, precisamos de umoperador para combinar parsers alternativos.

O parser p <|> q aplica o parser p à string de entrada e, caso ele falhe, aplica oparser q à mesma string de entrada.

infixl 5 <|>(<|>) :: Parser a -> Parser a -> Parser ap <|> q =

MkP ( \s -> case parse p s ofNothing -> parse q sJust x -> Just x

)

54/75

Alternativas (cont.)

Exemplos:

parse (char ’a’ <|> char ’b’) "a=3" Just (’a’,"=3")

parse (char ’a’ <|> char ’b’) "b=4" Just (’b’,"=4")

parse (char ’a’ <|> char ’b’) "c=5" Nothing

parse (psat isAlpha item <|> psat isDigit) "b=4" Just (’b’,"=4")

parse (psat isAlpha item <|> psat isDigit) "9" Just (’9’,"")

parse (psat isAlpha item <|> psat isDigit item) "++" Nothing

55/75

Alternativas (cont.)

Exercício 9

Defina o parser alphaNum :: Parser Char que reconhece uma letra ou um dígito.Por exemplo:

parse alphaNum "Java" Just (’J’,"ava")parse alphaNum "pi" Just (’p’,"i")parse alphaNum "9*3" Just (’9’,"*3")parse alphaNum "-78" Nothingparse alphaNum "" Nothing

Use a função (<|>).

56/75

Repetições

Podemos definir um combinador de parser que repete um parser zero ou maisvezes.

O resultado é a lista dos resultados de cada aplicação do parser dado.

many :: Parser a -> Parser [a]many p =

do x <- p {- aplica parser pelo menos 1 vez -}xs <- many preturn (x:xs)

<|> {- ou -}return [] {- não aplica o parser -}

57/75

Repetições (cont.)

Exemplos:

parse (many (char ’*’)) "***p" Just ("***","p")parse (many lower) "pi/3" Just ("pi","3")parse (many digit) "8712+4" Just ([8,7,1,2],"+4")parse (many digit) "pi/3" Just ([],"pi/3")parse (many digit) "" Just ([],"")

58/75


Podemos definir um combinador de parser que repete um parser uma ou maisvezes.

O resultado é a lista dos resultados de cada aplicação do parser dado.

many1 :: Parser a -> Parser [a]many1 p = do x <- p

xs <- many preturn (x:xs)

59/75


Exemplos:

parse (many1 (char ’*’)) "***p" Just ("***","p")parse (many1 lower) "pi/3" Just ("pi","/3")parse (many1 digit) "8712+4" Just ([8,7,1,2],"+4")parse (many1 digit) "pi/3" Nothingparse (many1 digit) "IF a > 0" Nothingparse (many1 digit) "" Nothing

60/75


Exercício 10

Defina o parser natural :: Parser Integer que reconhece um número natural.Por exemplo:

parse natural "0" Just (0,"")parse natural "192+56" Just (192,"+56")parse natural "pi*4" Nothingparse natural "-981" Nothing

Use a função many1.

61/75


Exercício 11

Defina o parser identifier :: Parser String que reconhece um identificador.Considere que um identificador é formado por uma seqüência de letras, dígitosdecimais e sublinhados começando com uma letra.Por exemplo:

parse identifier "pi+3" Just ("pi","+3")parse identifier "alpha*(pi+3)" Just ("alpha","*(pi+3)")parse identifier "xy_23-k" Just ("xy_23","-k")parse identifier "J45+7" Just ("J45","+7")parse identifier "k" Just ("k","")parse identifier "5xy" Nothingparse identifier "_abc*3" Nothingparse identifier "" Nothing

Use as funções many e many1.

62/75


Exercício 12

Defina o combinador de parser many usando a função many1.

63/75

Ignorando brancos

Em muitas aplicações, espaços em branco (seqüências de espaços, mudançasde linha e tabuladores) pode aparecer entre tokens (símbolos comoidentificadores, números, palavras-chave, etc.) para tornar a leitura do texto maisfácil.

O parser space reconhece espaços em branco.

space :: Parser ()space =

many (satisfy isSpace item) >> return ()

A função isSpace está definida no módulo Data.Char.

64/75

Ignorando brancos (cont.)

O combinador de parser token ignora espaços em branco antes e depois doparser dado.

token :: Parser a -> Parser atoken p =

do spacex <- pspacereturn x

65/75

Ignorando brancos (cont.)

Exemplos:

parse space " xy ++" Just ((),"xy++")parse (token identifier) " xy ++" Just ("xy","++")parse (token natural) " 9876*78" Just (9876,"*78")parse (token (char "&")) " & xy" Just (’&’,"xy")

66/75

Tópicos

1 Parsers


3 Parsers básicos


5 Mônadas


7 Calculadora

67/75

Calculadora

Vamos implementar uma calculadora onde o usuário digita uma expressãoartimética e em seguida o valor da expressão é exibido.

Uma expressão aritmética pode seruma constante numérica,uma variável,uma operação binária (adição, subtração, multiplicação ou divisão) entre duasexpressões aritméticas, ouuma atribuição envolvendo uma variável e uma expressão aritmética.

Podemos representar as variáveis por strings.

type Variable = String

O tipo Operator representa um operador aritmético binário.

data Operator = Sum | Sub | Mul | Divderiving (Show)

O tipo Exp representa expressões aritméticas:

68/75

Calculadora (cont.)

data Exp = Con Double| Var Variable| Op Operator Exp Exp| Assign Variable Expderiving (Show)

A memória pode ser representa por uma lista de associações que associa umavariável com o seu valortype Memory = [(Variable,Double)]

69/75

Calculadora (cont.)

Exercício 13

Defina a função eval :: Memory -> Exp -> (Double,Memory) que recebe umamemória e uma expressão aritmética, e retorna um par formado pelo valor daexpressão aritmética, e pela nova memória após a avaliação da expressão.Observe que:

A memória é necessária para se obter o valor das variáveis que aparecem naexpressão aritmética.

Caso uma variável não esteja na memória, considere que o seu valor é zero.

O valor de uma expressão aritmética que é uma atribuição é o valor atribuído àvariável. Por exemplo, o valor da expressão x := 2+3 é 5.

O resulado é formado por um par contendo uma memória porque quando aexpressão aritmética sendo avaliada contém atribuições, uma nova memória éformada para refletir o efeito da atribuição.

70/75

Calculadora (cont.)

Exercício 14

Defina o parser pfactor :: Parser Exp que reconhece as formas primárias deexpressões aritméticas:

constantes numéricas

variáveis

aplicação do menos unário (operador prefixo que muda o sinal de umaexpressão)

expressões parentetizadas

71/75

Calculadora (cont.)

Exercício 15

Defina o parser pterm :: Parser Exp que reconhece as expressões aritméticas quepodem ser termos de uma adição ou subtração.Um termo é um fator seguido pelo resto do termo, sendo que o resto do termo podeser:

um operador multiplicativo (multiplicação ou divisão) seguido de outro fator e deoutro resto de termo, ou

vazio

72/75

Calculadora (cont.)

Exercício 16

Defina o parser pbasic :: Parser Exp que reconhece as expressões aritméticasbásicas que podem ser usadas em uma atribuiçãoEstas expressões são formadas por um termo seguido pelo resto da expressãobásica, sendo que o resto da expressão básica pode ser:

um operador aditivo (adição ou subtração) seguido de outro termo e de outroresto de expressão básica, ou

vazio

73/75

Calculadora (cont.)

Exercício 17

Defina o parser pexp :: Parser Exp que reconhece as expressões aritméticas maisgerais, incluindo atribuições.Uma expressão aritmética é uma atribuição ou uma expressão básica.

74/75

Calculadora (cont.)

Exercício 18

Defina a operação main :: IO () que lê as expressões fornecidas pelo usuário,calcula e exibe os seus valores.

75/75

Fim

Documents

Capítulo 14 Parsers - DECOM · 2013. 3. 25. · Para indicar sucesso ou falha podemos usar o construtor de tipo Maybe do prelúdio: dataMaybe a =Nothing | Just a Portanto o tipo