homework help: upn parser
Graham Klyne
GK at ninebynine.org
Mon Dec 15 10:06:57 EST 2003
At 13:12 14/12/03 +0100, Max Hoffmann wrote:
>Dear Haskell cafe members,
> I am somebody one could well call a bloody beginner but the elegance of
>functional programming and am therefore truly interested to learn more about
>Haskell.
>
>Now I have an assignment to write a parsing function to convert a string of
>a mathematical expression into a tree in UPN style to evaluate it
>afterwards.
>So my evaluating function looks like this:
>
>data Op = Plus|Minus|Times|Div|Fac
> deriving(Show,Eq)
>data OpTree = Term OpTree Op OpTree
> |Number Float
> |E
> deriving(Show,Eq)
>eval(Number z) = z
>eval(Term li op re)
> |op == Plus= (eval li) + (eval re)
> |op == Minus= (eval li) - (eval re)
> |op == Times= (eval li) * (eval re)
> |op == Div= (eval li) / (eval re)
>
>And I tried to write a parsing function but I got stuck in the very
>beginning. So far I wrote:
>
>--parsing
>parsing :: String->[OpTree]
>parsing (a:b:c:xs) t
> |isDigit b = ((parsing xs)) ((Term (read a) c (read b)):t)
>
>And the Hugs compiler gives me so many error messages, that I have no clue
>how to get rid of this mess. Could anybody give me a hint where my error is
>and whether I am right in the general direction.
It's almost clear from the parsing type signature what you hope to achieve,
but I can't really figure what you're trying to do in the code. So I offer
a couple of indirect suggestions:
(1) are you sure you want
parsing :: String->[OpTree]
and not:
parsing :: String->OpTree
(i.e. why a *list* of OpTrees?)
(2) pick and code a really simple case first, and then figure out how to
generalize it. I've found this approach has helped me in coding some
complex algorithms. E.g. to parse 2+2, the following is based on your code
and yields the expected result under Hugs:
[[
import Data.Char
data Op = Plus|Minus|Times|Div|Fac
deriving(Show,Eq)
data OpTree = Term OpTree Op OpTree
|Number Float
|E
deriving(Show,Eq)
eval:: OpTree -> Float
eval(Number z) = z
eval(Term li op re)
|op == Plus= (eval li) + (eval re)
|op == Minus= (eval li) - (eval re)
|op == Times= (eval li) * (eval re)
|op == Div= (eval li) / (eval re)
--parsing
parsing :: String->OpTree
parsing (a:'+':c:"")
| isDigit a && isDigit c = Term (Number (read [a])) Plus (Number (read
[c]))
test1 = eval (parsing "2+2") -- 4.0
]]
That's far from what you need to achieve, but it's maybe a toe-hold on the way.
(3) To handle the issue of parsing a construct consisting of a sequence of
things from a string, look at the prelude function lex (in PreludeText),
and type ReadS, so see how they deal with:
(a) parsing a value from the front of a string, and return both the value
and the remainder of the string, and
(b) the fact that parsing is not, in general, deterministic: at any point
in the process there may be more than one possible way to continue the
parse. Hint: uses a list to return all possible parses.)
HTH.
#g
------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact
More information about the Haskell-Cafe
mailing list