align-toparrow-leftarrow-rightbackbellblockcalendarcamerachatcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-crosscrosseditfacebookglobegoogleimagesinstagramlocation-pinmagnifying-glassmailmoremuplabelShape 3 + Rectangle 1outlookpersonplusImported LayersImported LayersImported Layersshieldstartwitteryahoo

Hoodlums Message Board › Homework: Expression parser

Homework: Expression parser

Peter M.
peter_marks
Group Organizer
London, GB
Post #: 24
This month's homework is to complete the parser for the arithmetic expression language that we started working on at this month's meetup. I've pasted the code as we left it at the end of the session here.

For those who didn't make the session, we defined the Parser type as a function from a string to maybe a parsed value and a string of unconsumed input. This allows us to handle failure (although not very well) and, using the <*> operator, chain parsers together. This is sometimes called an applicative parser (see Functor and Applicative). We'll cover monadic parsers at the next meetup. We also built some primitive parsers to parse characters. Together with the Functor and Applicative instances and an instance of Alternative (which you'll need to write) these should give us all the building blocks we need.

I suggest you just try parsing the expressions as produced by the pretty printer; that is, all operations are surrounded by brackets, so you don't need to deal with precedence.

If you are feeling more ambitious, you can try:

- tidying up the code for the primitive parsers and Functor and Applicative instances using fromMaybe, maybe (spot the catamorphism), and the Applicative operators on Maybes (however we'll do a better job of this with monads at the next session)

- adding error reporting, perhaps using the Result type or a variation of it

- parsing expressions without brackets (and therefor handling precedence)

Have fun and do ask questions in reply to this message if you need any assistance.


Peter

Duncan M.
user 9754203
London, GB
Post #: 1
Hi all,

Here's my attempt. No real error handling yet, but it does parse expressions without brackets with correct operator precedence etc.

Any comments?

best,
Duncan
Tim W.
user 12343318
London, GB
Post #: 3
I've produced a simple example using just Applicative Parsing, which I haven't tried before. I really like the point-free style when compared to monadic parsing. If I get time before next week, I'll try and extend it to cover the more advanced features.

Example use:
*Expressions> parseExpr "((123 + 1) * (2/x))"
Just (Op Mult (Op Sum (Term 123) (Term 1)) (Op Div (Term 2) (Var "x")))

EDIT: It only needed a small update to handle expressions without brackets with correct precedence. I've borrowed the 'chain'l operator from Duncan's code but changed it to use Applicative parsing instead of monadic parsing.
Peter M.
peter_marks
Group Organizer
London, GB
Post #: 25
Hi Duncan

Your parser library looks pretty comprehensive. I see you used lists to store alternative parses and have built your applicative operations out of monadic ones. I'm intending to talk more about that at the next session.


Peter
Peter M.
peter_marks
Group Organizer
London, GB
Post #: 26
Hi Tim

Looks good - pretty much what I had in mind.

That said, there are a few functions in the Applicative module that you have reimplemented and some that allow you to make slight simplifications. Also, I think your digitP and symbolCharP would be more neatly implemented on top of a predP that parsed a character matching a given predicate. This would be another primitive parser... in fact you could easily build charP and anyCharP on top of predP.

Perhaps working through these changes would make a good start to our next session?


Peter
Tim W.
user 12343318
London, GB
Post #: 4
Thanks Peter. Yes it would be good to work through these changes. I'm also interested in what monadic parsing can give us over this applicative parser, perhaps context sensitive errors?
Duncan M.
user 9754203
London, GB
Post #: 2
Thanks Peter, and nice code, Tim! Much cleaner than mine, I think.

I hadn't quite understood the focus on applicatives in the meeting; it wasn't until reading the posts on here that I realised the distinction! Before getting into the monadic parsing, I did get most of the way to a working applicative parser, but found left-association hard to achieve --- indeed, I think Tim's current code parses in a right-associative manner.

I've my git repo to include an applicative version that I think does left-association correctly, but looks pretty ugly, and doesn't really follow an applicative style (i.e. I think I'm effectively taking a monadic approach, by passing the value calculated from the left-hand terms on to the rest of the computation...). Is there a way to do this in a solely applicative style?

Looking forward to catching up tonight.

Duncan
A former member
Post #: 1
I guess it's a bit late now, but here's my attempt anyway. Stole <* and *> from Tim/Duncan...
Peter M.
peter_marks
Group Organizer
London, GB
Post #: 27
I've posted the versions of the parser we worked on at the meetup.

Tim's original, our tidied up version, and the monadic version.
Powered by mvnForum

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy