Parsing de expressões

30 09 2007

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!

código aqui


Actions

Information

2 responses

10 11 2007
Hélder Pereira

Isso “à lá” MP3 ficava muito mais à pro.

10 11 2007
ulisses

Verdade! “mas eu não sei escrever” :S nunca tive o prazer de ter essa, como dizem, magnifica cadeira.

De qualquer das formas gosto desta solução por ser toda feita numa lista por compreensão. Brutal!

Mas sim… nada que se compare aos combinadores mágicos de MP3…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: