Analyze the given Haskell solution. Make an analysis report including descriptio
ID: 3605030 • Letter: A
Question
Analyze the given Haskell solution. Make an analysis report including description of each unit’s (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
-}
Explanation / Answer
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
-}