Haskell Programming (Not any other language): Simply answer the question (Code)

For this assignment, you'll be modifying and extending our earlier implementation of matching regular expressions against strings. In addition to the expressions we already have: e (empty string), a specified character, alternation and concatenation, we'll add . for end of string: a match of S with the empty string succeeds and matches the empty string; a match of S against any non-empty string fails. . . for any single character: dot matches any one character in the alphabet . ? for optional expression : exp ? is like (exp l e): The expression or empty string (note it always succeeds) . Kleene star: exp* s like (exp exp*) | E. However, if exp matches but returns the empty string as the match then just succeed with that. This is to avoid infinite recursion on expressions like e. In addition, there's a change to how expl | exp2 should behave: If both sides succeed, we want the result with the longer matching string. E.g., a match of ("a" |"ab") "abc" should succeed with "ab" (and leftover "c"). The way we were doing it before (skip exp2 if expI succeeds) can fail to return the longest match, which is now our goal Part 1. Backtracking Search This is a extension and modification to the earlier backtracking search program. There are two data structures data RegExp (the regular expressions) data Mresult - FAIL | OK String String deriving (Eq, Show) An unsuccessful match should return FAIL. A successful result OK strl str2 means that strl matched the expression and str2 was leftover. Note strl + str2 should equal the string passed to match. E.g., matching (Rch 'a') against "abc" should yield OK "a" "bc". There's a skeleton program Hw04_partl.hs - it compiles but its match always returns FAIL. You should replace the stub code with your implementation. Part 2. Nondeterministic Search For this version of match, instead of returning a single result FAIL or OK, you should return a list of all successful search results. Eg., matching ( a | ab) with "abc" should succeed with both disjuncts and return [OK "a" "bc", OK "ab" "c" ] . (in part 1 , you should return OK "ab" "", the longer of the two match results.) The regular expression data structure stays the same as in part 1. The result type changes data MresultOK String String deriving (Eq, Show) type Mresults [Mresult] So match returns an Mresults, which is a list of OK need FAIL anymore. A list of empty indicates a match failed, so we don't Except for the slightly different data structures, many of the cases behave the same as in Part 1, but not all: Alternation, expl | exp2, becomes easy: Run match on both expressions and concatenate the lists of results. Concatenation, expl exp2, however, is much harder now. 1. Say matching expl returns 2 results, [OK rl s, OK r2 s2]. 2. For OK rl sl, we have to concatenate rI with each result of matching exp2 with s. L.e., for each result OK r3 s3 of exp2 with s1, we generate OK (rl ++ r3) s3. Similarly, for OK r2 s2, we have to concatenate r2 with each result of matching exp2 with s2. 4. Finally, we can concatenate the results of steps 2 and 3 Example: match (a |ab) b with "abbc". . The recursive match of ( a | ab ) with "abbc" returns two results. [OK "" "bbe", OK "ab" "bc"]. . Take OK "a" "bbc" and match for b with "bbe". This gives us [OK "b" "bc"1, which we extend to [OK "ab" "bc" Take OK "ab" "bc" and match for b with "bc". This gives us [OK "b" "c"], which we extend to [OK "abb" "c"j. . So match ( a l ab) b with "abbe" returns [OK "ab" "be", "abb" "c"] Note in this example, the match of exp2 returned only one result. Remember, if it returns many results, then each of those results has to be concatenated with the match of the particular exp/ search that the exp2 search follows . Example: . Matching (a l aa) with "aaaaaa" yields [OK "a" "aaaaa", OK "aa" "aaaa" . matching (a l aa ) ( aa l a) with "aaaaaa" yields [OK "aa" "aaaa", OK "aaa" "aaa", "aaa" Note OK "aaa" "aaa" appears twice here-don't worry about it. (Don't look for duplicate results.) Once again, there's a skeleton, HW04_part2.hs with stub code that you should replace. (Currently, its match always returns the empty list of results.) For this assignment, you'll be modifying and extending our earlier implementation of matching regular expressions against strings. In addition to the expressions we already have: e (empty string), a specified character, alternation and concatenation, we'll add . for end of string: a match of S with the empty string succeeds and matches the empty string; a match of S against any non-empty string fails. . . for any single character: dot matches any one character in the alphabet . ? for optional expression : exp ? is like (exp l e): The expression or empty string (note it always succeeds) . Kleene star: exp* s like (exp exp*) | E. However, if exp matches but returns the empty string as the match then just succeed with that. This is to avoid infinite recursion on expressions like e. In addition, there's a change to how expl | exp2 should behave: If both sides succeed, we want the result with the longer matching string. E.g., a match of ("a" |"ab") "abc" should succeed with "ab" (and leftover "c"). The way we were doing it before (skip exp2 if expI succeeds) can fail to return the longest match, which is now our goal Part 1. Backtracking Search This is a extension and modification to the earlier backtracking search program. There are two data structures data RegExp (the regular expressions) data Mresult - FAIL | OK String String deriving (Eq, Show) An unsuccessful match should return FAIL. A successful result OK strl str2 means that strl matched the expression and str2 was leftover. Note strl + str2 should equal the string passed to match. E.g., matching (Rch 'a') against "abc" should yield OK "a" "bc". There's a skeleton program Hw04_partl.hs - it compiles but its match always returns FAIL. You should replace the stub code with your implementation. Part 2. Nondeterministic Search For this version of match, instead of returning a single result FAIL or OK, you should return a list of all successful search results. Eg., matching ( a | ab) with "abc" should succeed with both disjuncts and return [OK "a" "bc", OK "ab" "c" ] . (in part 1 , you should return OK "ab" "", the longer of the two match results.) The regular expression data structure stays the same as in part 1. The result type changes data MresultOK String String deriving (Eq, Show) type Mresults [Mresult] So match returns an Mresults, which is a list of OK need FAIL anymore. A list of empty indicates a match failed, so we don't Except for the slightly different data structures, many of the cases behave the same as in Part 1, but not all: Alternation, expl | exp2, becomes easy: Run match on both expressions and concatenate the lists of results. Concatenation, expl exp2, however, is much harder now. 1. Say matching expl returns 2 results, [OK rl s, OK r2 s2]. 2. For OK rl sl, we have to concatenate rI with each result of matching exp2 with s. L.e., for each result OK r3 s3 of exp2 with s1, we generate OK (rl ++ r3) s3. Similarly, for OK r2 s2, we have to concatenate r2 with each result of matching exp2 with s2. 4. Finally, we can concatenate the results of steps 2 and 3 Example: match (a |ab) b with "abbc". . The recursive match of ( a | ab ) with "abbc" returns two results. [OK "" "bbe", OK "ab" "bc"]. . Take OK "a" "bbc" and match for b with "bbe". This gives us [OK "b" "bc"1, which we extend to [OK "ab" "bc" Take OK "ab" "bc" and match for b with "bc". This gives us [OK "b" "c"], which we extend to [OK "abb" "c"j. . So match ( a l ab) b with "abbe" returns [OK "ab" "be", "abb" "c"] Note in this example, the match of exp2 returned only one result. Remember, if it returns many results, then each of those results has to be concatenated with the match of the particular exp/ search that the exp2 search follows . Example: . Matching (a l aa) with "aaaaaa" yields [OK "a" "aaaaa", OK "aa" "aaaa" . matching (a l aa ) ( aa l a) with "aaaaaa" yields [OK "aa" "aaaa", OK "aaa" "aaa", "aaa" Note OK "aaa" "aaa" appears twice here-don't worry about it. (Don't look for duplicate results.) Once again, there's a skeleton, HW04_part2.hs with stub code that you should replace. (Currently, its match always returns the empty list of results.)