Vamos criar uma função que pega numa String, que tem representado ma expressão matemática, e passa para um determinado tipo de dados (Exp o).
A String que iremos passar á função para que seja processada será qualquer coisa do género:
"((1>=a) || (4==x))" e até "(2 -( ((1+3) * (4-x)) / 45))"
Comecemos então pelo inicio;
{-# OPTIONS -fglasgow-exts #-}
module ParserExp where
import Char
Escolhemos o nosso tipo de dados para representar, primeiro, os operadores:
data Ops = Add | Mul | Sim | Sub | Div
| OR_ | AND_ | NOT_ | GE_
| GT_ | LE_ | LT_ | EQ_ | NE_
deriving Eq
Acabamos de definir 14 operadores matemáticos; Adição, Multiplicação, Simétrico, Subtracção, Divisão, ou lógico, e lógico, negação, maior que, menor que, maior ou igual a, menor ou igual a, igual e diferente.
Passemos agora por definir as nossas expressões como uma árvore n-ária:
data Exp o = Const Int | Var String | Op o [Exp o]
Agora podemos ver que o tipo de dados escolhido encaixa perfeitamente no que pretendemos, vejamos:
"((1>=a) || (4==x))" pode ser representado comoOp OR_ [Op GE_ [Const 1, Var "a"], Op EQ_ [Const 4, Var "x"]]
Temos que criar uma classe para sabermos a aridade de cada operador:
class Opt o where
arity :: o -> Int
instance Opt Ops where
arity Add = 2
arity Mul = 2
arity Sim = 1
arity Sub = 2
arity Div = 2
arity OR_ = 2
arity AND_ = 2
arity NOT_ = 1
arity GE_ = 2
arity GT_ = 2
arity LE_ = 2
arity LT_ = 2
arity EQ_ = 2
arity NE_ = 2
De seguida fazemos as instancias de Show para os nossos tipos de dados, ficamos assim com:
instance Show Ops where
show Add = "+"
show Mul = "*"
show Sim = "Sim"
show Sub = "-"
show Div = "/"
show OR_ = "||"
show AND_ = "&&"
show NOT_ = "!"
show GE_ = ">="
show GT_ = ">"
show LE_ = "<="
show LT_ = " Show (Exp o) where
show (Const n) = show n
show (Var s) = s
show (Op o l)
| arity o == 2 = "(" ++ (show $ head l) ++ show o ++ (show $ last l) ++ ")"
| arity o == 1 = "(" ++ show o ++ (show $ head l) ++ ")"
Bom… vamos finalmente ao que nos interessa relamente, o nosso Parser!
Existe um tipo de dados em Haskell que foi pensado para parser, que é o ReadS, este apresenta a seguinte definição:
data ReadS a = String -> [(a,String)]
Ou seja, é fácil perceber que este tipo terá que ser a assinatura da nossa função, pois só desta forma conseguimos processar uma String, originando (sempre!) uma lista de tuplos em que a primeira parte do tuplo tem o nosso tipo desejado (árvore n-ária) e a segunda parte tem o resto da String que ainda não foi processada:
De lembrar que o nosso tipo de dados é (Exp Ops) e não apenas Exp.
Sendo assim temos:
readsExp :: ReadS (Exp Ops)
readsExp s =
[((leOp "~" [a]),p4) | ("(",p1) <- lex s,
("~",p2) <- lex p1,
(a,p3) <- readsExp p2,
(")",p4) <- lex p3] ++
[((leOp op [a,b]),p5) | ("(",p1) <- lex s,
(a,p2) <- readsExp p1,
(op,p3) <- lex p2,
op == "+" || op == "*" || op == "/" ||
op == "-" || op == "||" || op == "&&" ||
op == "==" || op == "!=" || op == "=" || op == "!" || op == ">" ||
op == "<",
(b,p4) <- readsExp p3,
(")",p5) <- lex p4 ] ++
[((Const ((read a)::Int)),sx) | (a,sx) <- lex s, all isDigit a] ++
[((Var a),sx) | (a,sx) [Exp Ops] -> Exp Ops
leOp o = Op (read o::Ops)
Acreditem que o nosso parser resume-se a estas 21 linhas (com indentação exagerada).
Aqui temos que dar os créditos ás listas por compreensão e depois á função lex que vem no Prelude. É incrível o poder desta função.
Aconselho a verem mais sobre esta função.
E finalmente temos a instancia de Read para Exp Ops:
instance Read (Exp Ops) where
readsPrec _ s = readsExp s
Apartir de agora sempre que quisermos fazer parsing a uma expressão utilizamos:
parsing :: String -> Exp Ops parsing = read
Ao usar a função parsing asseguramo-nos de que iremos receber sempre uma Exp Ops que é o desejado.
Este parser é bastante simples e como tal não faz reconhecimento de erros ou más formações na String recebida.
É tudo!
