parse String -> Expression

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

parse String -> Expression

John Moore
Hi,
    I'm trying to find a way to parseRPN (Reverse Polish Numbers) to
expressions rather than to just numbers. e.g. I want the answer to be in the
form

(Multiply (Val 2) (Val 3)) rather than just the answer.



Are these anyway near the steps
parseRPN :: String->Expression

This is a lot more complicated then I thought.!!!

First do we have to read in a string is this (IsString)

 fromString :: String -> a

Then this goes on a stack

pushStack :: a -> Stack -> Stack (Takes a value and puts in on a stack)

Later we pop it off

popStack :: Stack -> (a,Stack) -- takes the value of the stack and leaves
the stack

Do we also have to define taking off the stack such as head(popstack) or
fst(popstack) if we do we would probably have  one for putting it onto a
stack.

Do we then turn the value into an Expression.?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20091108/4fec4429/attachment.html
Reply | Threaded
Open this post in threaded view
|

parse String -> Expression

Felipe Lessa
On Sun, Nov 08, 2009 at 05:53:48PM +0000, John Moore wrote:
> Hi,
>     I'm trying to find a way to parseRPN (Reverse Polish Numbers) to
> expressions rather than to just numbers. e.g. I want the answer to be in the
> form
>
> (Multiply (Val 2) (Val 3)) rather than just the answer.

You don't need to code all the parser by hand.  You can use, for
example, Parsec parsers.

Spoilers ahead!!!






If your data type is

data Expr a = Multiply (Expr a) (Expr a)
            | Val a

then you may write something like

expression :: Parser a -> Parser (Expr a)
expression valParser = spaces >> (mult <|> val)
  where
    expr = expression valParser
    mult = char "*" >> (Multiply <$> expr <*> expr)
    val  = Val <$> valParser

using Parsec for a concrete example.

HTH,

--
Felipe.
Reply | Threaded
Open this post in threaded view
|

parse String -> Expression

Felipe Lessa
On Sun, Nov 08, 2009 at 04:49:37PM -0200, Felipe Lessa wrote:
> You don't need to code all the parser by hand.  You can use, for
> example, Parsec parsers.

IOW, you may use the language's implicit stack instead of
building your own.

--
Felipe.
Reply | Threaded
Open this post in threaded view
|

parse String -> Expression

Daniel Fischer-4
In reply to this post by John Moore
Am Sonntag 08 November 2009 18:53:48 schrieb John Moore:
> Hi,
>     I'm trying to find a way to parseRPN (Reverse Polish Numbers) to
> expressions rather than to just numbers. e.g. I want the answer to be in
> the form
>
> (Multiply (Val 2) (Val 3)) rather than just the answer.
>

I'd suggest using something like

type Stack = [Expression]

parseRPN :: Parser Expression
parseRPN = rpn []

parseVal :: Parser Expression
parseVal = do
    num <- parseNumber
    return (Val num)

rpn :: Stack -> Parser Expression
rpn stack = (do
    char '+'
    case stack of
        (x:y:ts) -> rpn (Add x y:ts)
        _ -> parsecFail "BinOp requires two values on Stack")
    <|> (do
    char '*'
    case stack of
        (x:y:ts) -> rpn (Multiply x y:ts)
        _ -> parsecFail "BinOp requires two values on Stack")
    <|> ...
    <|> (do
    v <- parseVal
    rpn (v:stack))
    <|> (do
    eof
    case stack of
        [x] -> return x
        _ -> parsecFail "No parse")

-- You could also use the userstate of Parsec for the stack

>
>
> Are these anyway near the steps
> parseRPN :: String->Expression
>
> This is a lot more complicated then I thought.!!!
>
> First do we have to read in a string is this (IsString)
>
>  fromString :: String -> a
>
> Then this goes on a stack
>
> pushStack :: a -> Stack -> Stack (Takes a value and puts in on a stack)
>
> Later we pop it off
>
> popStack :: Stack -> (a,Stack) -- takes the value of the stack and leaves
> the stack
>
> Do we also have to define taking off the stack such as head(popstack) or
> fst(popstack) if we do we would probably have  one for putting it onto a
> stack.
>
> Do we then turn the value into an Expression.?