Analyze the given Haskell solution. Make an analysis report including description of each units (code fragment) functionality.

-- A very simple, recursive-descent, and predictive parser in Haskell.

-- 1. What type our parsing function should have? -- - Complete parser is of type :: String -> Int -- - Partial parser is of type :: String -> (Int, String) -- -- 2. How to distinguish between infix (+) and prefix (+)? -- - The factor-parsing function, parseFact, always assumes the optional prefix ones, -- and whatever comes after a factor, if any, is an infix one. -- -- 3. How we skip over space characters? -- - Parsing terms consumes the preceding and/or closing spaces. -- -- 4. How we can match opening and closing parentheses? -- - By using partial parsing (parseExpr) for expressions inside parentheses and -- checking the remaining unparsed string starts with the closing parenthesis. -- - For example, for "1 + 2", the first space will be consumed when parseFact parses -- the number "1" and the second space will be consumed when parseFact parses "2".

-- a global variable p = 10^9 + 7

parseFact :: String -> (Int, String) {- Factor ::= Number | [+-] Factor | '(' Expression ')' -} parseFact (' ':s) = parseFact s parseFact ('+':s) = parseFact s parseFact ('-':s) = let (i, s') = parseFact s in (-i, s') -- let ... in is an expression for introducing local variables. parseFact ('(':s) = case parseExpr s of -- case ... of is an expression for pattern matching. (i, ')':s') -> (i, s') _ -> error "unmatched '('" -- Here, _ is a wild-card pattern that matches anything. -- No need of forward declaration for parseExpr. parseFact s = case reads s of -- reads :: Read a => String -> [(a, String)] [(i, s')] -> (i, dropWhile (== ' ') s') -- The (== ' ') :: Char -> Bool is a section of the infix operator, (==). -- Functions are first-class citizens in Haskell, so that we can pass a function -- as an argument to another function. -- Ex. -- dropWhile (<0) [-1,0,1,2] == [0,1,2] -- dropWhile (>0) [-1,0,1,2] == [-1,0,1,2] -- We also had to consume trailing spaces after ')' previously!!! _ -> error "unable to read a number"

parseTerm :: String -> (Int, String) {- Term ::= Factor [*/] Term | Factor -} parseTerm s = let (i, s1) = parseFact s in case s1 of '*':s2 -> let (j, s3) = parseTerm s2 in ((i * j) `mod` p, s3) '/':s2 -> let (j, s3) = parseTerm s2 in ((i * inverse j) `mod` p, s3) -- Division by 0 will not lead to an error since 1/0 = 0^(p-2) = 0 in this -- implementation, so we should further match j against 0 and throw an error!!! _ -> (i, s1)

where power a b -- computes a^b (mod p) w/o having overflow in computing a^b | b == 0 = 1 | even b = let x = power a (b `div` 2) in (x*x) `mod` p | otherwise = (a * power a (b-1)) `mod` p -- "otherwise" is a synonym for False.

inverse a -- a^(-1) = a^(p-2) (mod p) (by Fermat's little theorem) = power a (p-2)

parseExpr :: String -> (Int, String) {- Expression ::= Term [+-] Expression | Term -} parseExpr s = let (i, s1) = parseTerm s in case s1 of '+':s2 -> let (j, s3) = parseExpr s2 in ((i + j) `mod` p, s3) '-':s2 -> let (j, s3) = parseExpr s2 in ((i - j) `mod` p, s3) _ -> (i, s1)

parse :: String -> Int parse s = let (i, s') = parseExpr s in if null s' then i else error "unknown operator"

{- Finally, we only need to write the main function, which will take the string to parse - from command-line argument or from stdin, as you wish!!!

main = undefined -}