AST and parsing in Haskell

Question

I have a task and I can’t understand how to determine the answer.

Appointment

Write the function exp:: [String] -> (AST, [String])

AST :

• If x is a number, it should say Number x .
• If it is "+" og a "-", he should say Atom x .
• If it reads "(", then all the content behind it (("until it appears") should be List [AST] .

so that the outputs are:

 exp (token "(hi (4) 32)") > (List [Atom "hi", List [Number 4], Number 32], []) exp (token "(+ 3 42 654 2)") > (List [Atom "+", Number 3, Number 42, Number 654, Number 2], []) exp (token "(+ 21 444) junk") > (List [Atom "+", Number 21, Number 444], ["junk"]) 

that I still

I already have a token function, token :: String -> [String] , which makes a list.

Example:

 `token "( + 2 ( + 2 3 ) )" > ["(","+","2","(","+","2","3",")",")"]` 

The exp function is as follows:

 exp :: [String] -> (AST, [String]) exp [] = error "Empty list" exp (x:xs) | x == ")" = error "" | x == "(" = let (e, ss') = exp xs in (List [getAst xs], ss') | x == "+" = let (e, ss') = exp xs in (Atom (read x), ss') | x == "-" = let (e, ss') = exp xs in (Atom (read x), ss') | otherwise = exp xs` 

where is the getAst function:

 getAst :: [String] -> AST getAst [] = error "" getAst (x:xs) | x == ")" = error "" | x == "(" = (List [getAst xs]) | isAtom x = (Atom x) | isNum x = (Number (read x)) | otherwise = getAst xs` 

(And yes, I'm new to Haskell ..)

Answer 1

I think I can help you a little.

There seems to be a problem, you should be able to do this simply by looking at the next input / token and decide where to go.

some assumptions

The way data is represented as [String] -> (Ast, [String]) I assume this is a general parser where the parser tries to read some parts of the input and return the processed / converted output along with the rest of the input that it did not convert ( so only two parafaxes of the tuple - Ast and the rest of the input).

type AST

since you did not enable it, I assumed that this:

 data Ast = Number Int | Atom String | List [Ast] deriving Show 

some things i will need

I need a few things:

 import Prelude hiding (exp) import Control.Applicative ((<$>)) import Data.Maybe (fromJust, isJust) 

I need to hide exp as we want to use this as a function name.

Then I want fmap over a Maybe , so I include the statement from Control.Applicative . This is true if you have not seen it before:

 f <$> Nothing = Nothing f <$> Just a = Just (fa) 

I need helpers for Maybe :

• isJust to check that for Just _
• and fromJust to get a from Just a

Finally, I need this helper function to read more secure:

 tryRead :: (Read a) => String -> Maybe a tryRead input = case readsPrec 0 input of (a,_):_ -> Just a _ -> Nothing 

Here we try to read the number - returing Just n if n is a number and Nothing otherwise.

first go

The following is an incomplete problem:

 exp :: [String] -> (Ast, [String]) exp (lookat:rest) | isJust number = (fromJust number, rest) | lookat == "(" = parseList rest [] where number = Number <$> tryRead lookat parseList :: [String] -> [Ast] -> (Ast, [String]) parseList inp@ (lookat:rest) acc | lookat == ")" = (List (reverse acc), rest) | otherwise = let (el, rest') = exp inp in parseList rest' (el:acc) 

As you can see, I'm just a lookat based lookat , but with a slight twist:

In case I see the number, I return the number and the list of remainder tokens. In case I see a ( , I run another parseList parser.

parseList will do the same: - it looks at the first token - if the token is equal ) , it ends the current list (battery technology is used for this) and returns. - if it does not use the existing exp parser to get list items recursively.

Here is an example of execution:

 λ> let input = ["(", "2", "(", "3", "4", ")", "5", ")"] λ> exp input (List [Number 2,List [Number 3,Number 4],Number 5],[]) 

Todo

There are some borderline cases that you need to solve (what if there are no input tokens?).

And, of course, you must add a case for Atom - to complete this exception.

complete solution

ok - after 3 hours the OP did not check again, so I think I can post the full solution. I hope I have not forgotten about any cases with edges, and this confidence is not the most effective implementation ( tokens comes to mind), but the examples that OP gave to everyone correspond to:

 module Ast where import Prelude hiding (exp) import Control.Applicative ((<$>)) import Data.Char (isSpace, isControl) import Data.Maybe (fromJust, isJust) data Ast = Number Int | Atom String | List [Ast] | Empty deriving Show type Token = String main :: IO () main = do print $ parse "(hi (4) 32)" print $ parse "(+ 3 42 654 2)" print $ parseAst . tokens $ "(+ 21 444) junk" parse :: String -> Ast parse = fst . parseAst . tokens parseAst :: [Token] -> (Ast, [Token]) parseAst [] = (Empty, []) parseAst (lookat:rest) | isJust number = (fromJust number, rest) | lookat == "(" = parseList rest [] | otherwise = (Atom lookat, rest) where number = Number <$> tryRead lookat parseList :: [Token] -> [Ast] -> (Ast, [Token]) parseList [] _ = error "Syntax error: `)` not found" parseList inp@ (lookat:rest) acc | lookat == ")" = (List (reverse acc), rest) | otherwise = let (el, rest') = parseAst inp in parseList rest' (el:acc) tokens :: String -> [Token] tokens = split "" where split tok "" = add tok [] split tok (c:cs) | c == '(' || c == ')' = add tok $ [c] : split "" cs | isSpace c || isControl c = add tok $ split "" cs | otherwise = split (tok ++ [c]) cs add "" tks = tks add t tks = t : tks tryRead :: (Read a) => Token -> Maybe a tryRead input = case readsPrec 0 input of (a,_):_ -> Just a _ -> Nothing 

run example

 λ> :main List [Atom "hi",List [Number 4],Number 32] List [Atom "+",Number 3,Number 42,Number 654,Number 2] (List [Atom "+",Number 21,Number 444],["junk"])