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

HW04_part1.hs (Let me know if text file need instead of picture of this file)

HW04_part2.hs (Let me know if text file need instead of picture of this file)

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.) Homework 4 part 1 - Match regular expressions using backtracing search -- Simple Regular Expressions with exp1 exp2, expl I exp2, -- null string (epsilon), $(end of string), dot (any single character), -- optional expr (? exp), and Kleene star data RegExpRnull Rend Rany Rch Char Ror RegExp Rand RegExp RegExp -- concatenation Ropt RegExp Rstar RegExp -- empty string epsilon -- $ at end of string? -- . any one character --a specific character -- alternation RegExp -- ? optional expression -Kleene star deriving Eq, Show) -- A match result 0K str1 str2 means that strl matched the expression and -str2 was leftover. Note str1 ++ str2 should be the string passed to match. data Mresult FAIL OK String String deriving (Eq, Show) -- Matching takes a regular expression and a string and either fails or -returns the string that matched and the string that was leftover. match:: RegExp String -> Mresult -- You fill in STUBS below -Matching empty string always succeeds, with empty string as the matched string match Rnull str- FAIL -- STUB -Match Rend str succeeds iff we're at the end of the string (str is null) match Rend str = FAIL-_ STUB Match Rany string matches the first character of the string (failing if string is null) match Rany strFAIL -- STUE -- Match a character succeeds iff the string begins with the character match (Rch chl) str = FAIL -- STUB -- Match (Ror rl r2) string matches rl against string and also r2 against string -- and fails if both fail, returns the successful result if exactly one succeeds, -- and returns the result with the longer match if both succeed match (Ror rexpl rexp2) str FAIL -- STUB -- Match (Rand rl r2) string matches r1 and (if it succeeds) matches r2 against - the string leftover from rl. If r2 succeeds then the Rand returns the -- concatenation of the matches from rl and r2. match (Rand rexpl rexp2 ) str FAIL-_ STUB -- Matching an optional expression is like matching (rexp null) match (Ropt rexp) str = FAIL-STUB matching rexp* is like matching ((rexp rexp*nul), but to avoid infinite -recursion, if rexp matches null, we stop with the base case (matching null) -we also stop with the base case if rexp fails to match. match (Rstar rexp) strFAIL-STUB _ UTILITY FUNCTIONS extend match1 takes a successful search result (OK match2 left2) and returns a successful search result with the concatenation of match1 and match2. -- (extend matchl on a failed result also fails.) extend matchl FAILSTUB --mkAnd string reg expr that sea r ches for the characters of the string in sequence mkAnd (c : cs} = Rand (Rch c) (mkAnd Cs) --mk0r string reg expr that matches any character of the string mkor (c: "") - Rch c mkOr (c : cs) = Ror (Rch c) (mkOr cs) Homework 4 part 2 -- Match regular expressions using nondeterministic search -- In contrast to part 1, here, matching returns a list of all the -possible successful results. -- Simple Regular Expressions with exp1 exp2, exp1I exp2, -null string (epsilon), $ (end of string), dot (any single character), -- optional expr (? exp), and Kleene star data RegExp Rnu Rend Rany Rch Char Ror RegExp RegExp Rand RegExp RegExp Ropt RegExp Rstar RegExp -- e empty string epsilon -- at end of string? -- . any one character -- a specific character -- | alternation -- concatenation -- ? optional expression -- * Kleene star deriving (Eq, Show) -- A match result [OK strl str21 is a list of success pairs where strl is -- the prefix that matched and str2 is the suffix that was leftover. A list of length 0 indicates no successful matches. A list of length > 1 _ indicates that multiple matches exist. (E.., matching ("a" l "ab") with "abc" -returns two results, one matching "a" (and leaving "bc") and one matching -- "ab" and leaving "c". For each OK str1 str2 result, str1 ++ str2 should be the original string passed to match. data Mresult 0K String String deriving (Eq, Show) type Mresults = [IM result] Matching takes a regular expression and a string and either fails or -- returns the string that matched and the string that was leftover. matchRegExp String ->Mresults -- You fill in STUBS below. Many are basically the same as in the -- backtracking search case -Matching empty string always succeeds, with empty string as the matched string match Rnull str = [] -- STUB -- Match Rend str succeeds iff we're at the end of the string (str is null) match Rend str = [] -- STUB -- Match Rany string matches the first character of the string (failing if string is null) match Rany str = [] -- STUB -- Match a character succeeds iff the string begins with the character match (Rch ch1) str = [] -- STUB Match (Ror rl r2) string matches r1 against string and also r2 against string -- and combines the results from both matches match (Ror rexp1 rexp2) str= [] --STUB -Match (Rand r1 r2) string first matches r1; for every successful result, -- it follows that particulra result with a match against r2. ALl the -- results (across all the results of r1) are collected and returned match (Rand rexp1 rexp2) str = []-STUB -- Matching an optional expression is like matching (rexp null) match (Ropt rexp) str = [] -- STUB -- matching rexp* is like matching ((rexp rexp) I null), but the -nondeterministic treatment of or means that we combine all the -results of successful matches for exp^ n for all n. (exp^n being --n concatenations of exp with epsilon for exp 0.) match (Rstar rexp ) str [] --STUB -- UTILITY FUNCTIONS -- (Add whatever utiltiy functions you deem fit) -- STUB 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.) Homework 4 part 1 - Match regular expressions using backtracing search -- Simple Regular Expressions with exp1 exp2, expl I exp2, -- null string (epsilon), $(end of string), dot (any single character), -- optional expr (? exp), and Kleene star data RegExpRnull Rend Rany Rch Char Ror RegExp Rand RegExp RegExp -- concatenation Ropt RegExp Rstar RegExp -- empty string epsilon -- $ at end of string? -- . any one character --a specific character -- alternation RegExp -- ? optional expression -Kleene star deriving Eq, Show) -- A match result 0K str1 str2 means that strl matched the expression and -str2 was leftover. Note str1 ++ str2 should be the string passed to match. data Mresult FAIL OK String String deriving (Eq, Show) -- Matching takes a regular expression and a string and either fails or -returns the string that matched and the string that was leftover. match:: RegExp String -> Mresult -- You fill in STUBS below -Matching empty string always succeeds, with empty string as the matched string match Rnull str- FAIL -- STUB -Match Rend str succeeds iff we're at the end of the string (str is null) match Rend str = FAIL-_ STUB Match Rany string matches the first character of the string (failing if string is null) match Rany strFAIL -- STUE -- Match a character succeeds iff the string begins with the character match (Rch chl) str = FAIL -- STUB -- Match (Ror rl r2) string matches rl against string and also r2 against string -- and fails if both fail, returns the successful result if exactly one succeeds, -- and returns the result with the longer match if both succeed match (Ror rexpl rexp2) str FAIL -- STUB -- Match (Rand rl r2) string matches r1 and (if it succeeds) matches r2 against - the string leftover from rl. If r2 succeeds then the Rand returns the -- concatenation of the matches from rl and r2. match (Rand rexpl rexp2 ) str FAIL-_ STUB -- Matching an optional expression is like matching (rexp null) match (Ropt rexp) str = FAIL-STUB matching rexp* is like matching ((rexp rexp*nul), but to avoid infinite -recursion, if rexp matches null, we stop with the base case (matching null) -we also stop with the base case if rexp fails to match. match (Rstar rexp) strFAIL-STUB _ UTILITY FUNCTIONS extend match1 takes a successful search result (OK match2 left2) and returns a successful search result with the concatenation of match1 and match2. -- (extend matchl on a failed result also fails.) extend matchl FAILSTUB --mkAnd string reg expr that sea r ches for the characters of the string in sequence mkAnd (c : cs} = Rand (Rch c) (mkAnd Cs) --mk0r string reg expr that matches any character of the string mkor (c: "") - Rch c mkOr (c : cs) = Ror (Rch c) (mkOr cs) Homework 4 part 2 -- Match regular expressions using nondeterministic search -- In contrast to part 1, here, matching returns a list of all the -possible successful results. -- Simple Regular Expressions with exp1 exp2, exp1I exp2, -null string (epsilon), $ (end of string), dot (any single character), -- optional expr (? exp), and Kleene star data RegExp Rnu Rend Rany Rch Char Ror RegExp RegExp Rand RegExp RegExp Ropt RegExp Rstar RegExp -- e empty string epsilon -- at end of string? -- . any one character -- a specific character -- | alternation -- concatenation -- ? optional expression -- * Kleene star deriving (Eq, Show) -- A match result [OK strl str21 is a list of success pairs where strl is -- the prefix that matched and str2 is the suffix that was leftover. A list of length 0 indicates no successful matches. A list of length > 1 _ indicates that multiple matches exist. (E.., matching ("a" l "ab") with "abc" -returns two results, one matching "a" (and leaving "bc") and one matching -- "ab" and leaving "c". For each OK str1 str2 result, str1 ++ str2 should be the original string passed to match. data Mresult 0K String String deriving (Eq, Show) type Mresults = [IM result] Matching takes a regular expression and a string and either fails or -- returns the string that matched and the string that was leftover. matchRegExp String ->Mresults -- You fill in STUBS below. Many are basically the same as in the -- backtracking search case -Matching empty string always succeeds, with empty string as the matched string match Rnull str = [] -- STUB -- Match Rend str succeeds iff we're at the end of the string (str is null) match Rend str = [] -- STUB -- Match Rany string matches the first character of the string (failing if string is null) match Rany str = [] -- STUB -- Match a character succeeds iff the string begins with the character match (Rch ch1) str = [] -- STUB Match (Ror rl r2) string matches r1 against string and also r2 against string -- and combines the results from both matches match (Ror rexp1 rexp2) str= [] --STUB -Match (Rand r1 r2) string first matches r1; for every successful result, -- it follows that particulra result with a match against r2. ALl the -- results (across all the results of r1) are collected and returned match (Rand rexp1 rexp2) str = []-STUB -- Matching an optional expression is like matching (rexp null) match (Ropt rexp) str = [] -- STUB -- matching rexp* is like matching ((rexp rexp) I null), but the -nondeterministic treatment of or means that we combine all the -results of successful matches for exp^ n for all n. (exp^n being --n concatenations of exp with epsilon for exp 0.) match (Rstar rexp ) str [] --STUB -- UTILITY FUNCTIONS -- (Add whatever utiltiy functions you deem fit) -- STUB