$30.00

## Description

For this assignment, you will devise two functions for analyzing regular

expressions using the RE data type created in class.

Create a file called Project.hs. At this top of this file, declare the module

module Project where

In the module, include this data declaration

data RE a — regular expressions over an alphabet defined by ‘a’

= Empty — empty regular expression

| Sym a — match the given symbol

| RE a :+: RE a — concatenation of two regular expressions

| RE a :|: RE a — choice between two regular expressions

| Rep (RE a) — zero or more repetitions of a regular expression

| Rep1 (RE a) — one or more repetitions of a regular expression

deriving (Show)

Define two functions which analyze regular expressions defined using this type.

– matchEmpty :: RE a -> Bool

This function returns true if the regular expression matches an empty

string. Note that the type does not include any constraints on the alphabet.

Among other things, this means that will not be able to use the matches

function we defined in class, as it requires ‘a’ to be an instance of Eq.

Some examples:

matchEmpty (Sym ‘a’) = False

matchEmpty (Rep (Sym ‘a’ :+: Sym ‘b’)) = True

matchEmpty (Rep1 (Sym ‘a’ :|: Empty)) = True

– firstMatches :: RE a -> [a]

Given a regular expression r, return a list of all symbols that occur first

in some string in the language described by r. You are not required to

eliminate duplicates (since nothing is known about the alphabet, doing so

would be impossible), but the list should be finite. No particular order

is required.

Some examples:

firstMatches (Sym ‘a’) = [‘a’]

firstMatches (Rep (Sym ‘a’ :|: Sym ‘b’)) = [‘a’, ‘b’]

firstMatches (Sym 1 :+: Sym 2) = [1]

firstMatches ((Sym 1 :|: Empty) :+: Sym 2) = [1,2]

Hand in the project by submitting Project.hs through Sakai.

Testing

——-

This literate Haskell file may be used to test your project. Copy it to the

same directory as your Project.hs and run it using

runghc hw4

Note that hw4.lhs refers to the types and functions defined in your Project

module, so it won’t compile unless all the definitions are there. If you wish

to test a partially written module, you can add dummmy definitions for any

functions you haven’t written yet, e.g.:

firstMatches :: RE a -> [a]

firstMatches = undefined

(The type signature is optional.)

> module Main where

>

> import Control.Exception (catch, ErrorCall(..), evaluate)

> import Project (RE(..), matchEmpty, firstMatches)

>

> a = Sym ‘a’

> b = Sym ‘b’

>

> tests =

> [ test “matchEmpty a” (matchEmpty a) False

> , test “matchEmpty a*b” (matchEmpty (Rep a :+: b)) False

> , test “matchEmpty (ab)*” (matchEmpty (Rep (a :+: b))) True

> , test “matchEmpty (a|e)+” (matchEmpty (Rep1 (a :|: Empty))) True

> , testBy seteq “firstMatches a” (firstMatches a) “a”

> , testBy seteq “firstMatches (a|b)*” (firstMatches (Rep (a :|: b))) “ab”

> , testBy seteq “firstMatches 12” (firstMatches (Sym 1 :+: Sym 2)) [1]

> , testBy seteq “firstMatches (1|e)2” (firstMatches ((Sym 1 :|: Empty) :+: Sym 2)) [1,2]

> ]

>

> testBy :: (Show a) => (a -> a -> Bool) -> String -> a -> a -> IO Bool

> testBy eq name got want = catch body (\(ErrorCall s) -> fail “ERROR” s)

> where

> body = do

> ok <- evaluate (eq got want)

> if ok

> then do

> putStrLn $ “PASS : ” ++ name

> return True

> else fail “FAIL ” (show got)

>

> fail msg txt = do

> putStrLn $ msg ++ “: ” ++ name

> putStrLn $ ” wanted: ” ++ show want

> putStrLn $ ” got: ” ++ txt

> return False

>

> test :: (Eq a, Show a) => String -> a -> a -> IO Bool

> test = testBy (==)

>

> seteq l1 l2 = all (`elem` l1) l2 && all (`elem` l2) l1

>

> runTests n f [] =

> putStrLn $ “Completed ” ++ show n ++ ” tests. ” ++ show f ++ ” failures.”

> runTests n f (t:ts) = do

> pass <- t

> runTests (n+1) (if pass then f else f + 1) ts

>

> main = runTests 0 0 tests