homework help: upn parser

[Graham Klyne]

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