Haskell Programming: Simply answer the question (Code)
HW04_part2.hs (Let me know if text file need instead of picture of this file)
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. E.g. matching (a |ab) with "abc" should succeed with both disjuncts and return [OK "a" "bc", OK "ab" "c" ]. (In part l, you should return OK "ab" "c", the longer of the two match results.) The regular expression data structure stays the same as in part 1. The result type changes: data Mresult OK string String deriving (Eq, Show) type Mresults[Mresult So match returns an Mresults, which is a list of OK. A list of empty indicates a match failed, so we don't need FAIL anymore 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. Le., for each result OK r3 s3 of exp2 with s1, we generate OK ( + 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 (aab) b with "abbc" . The recursive match of ( a l ab) with "abbc" returns two results, [OK "" "bbe", OK" ab" "bc"J . Take OK "a" "bbc" and match for b with "bbc". This gives us [OK "b" "bc"], 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"]. . So match ( a | ab) b with "abbc" 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 expl search that the exp2 search follows Example: . Matching (a 1 aa) with "aaaaaa" yields [OK "a" "aaaaa", OK "aa" "aaaa"] . matching (a l aa ) ( aal a) with "aaaaaa" yields [OK "aa" "aaaa", OK "aaa" "aaa", "aaa" Note OK "aaa" "aaa" appears twice here - don't worry about t. (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 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 expl. exp2, exp xp2, -null string (epsilon), $ (end of string), dot (any single character), -- optional expr. (? exp), and Kleene star data RegEXpRnull Rend | Rany | Rch Char | Ror RegExp. RegEXp | Rand RegExp RegExp -- e empty string epsilon -- at end of string? --. any one character -- a specific character -- | alternation -- concatenation -- ? optional expression Ropt RegEXp | Rstar RegExp deriving (Eq, Show) Kleene star -- A match result [0K str1 str2] is a list of success pairs where strl is _ the prefix that matched and str2 is the suffix that was leftove r . _ A list of length 0 indicates no successful matches. A list of length 1 indicates that multiple matches exist. (.g., matching ("a" "ab") with "abc" -returns two results, one matching "a" (and leaving "bc") and one matching -"ab" and leaving ..". For each 0K str1 str2 result, str1 ++ str2 should -be the original string passed to match data Mresult= 0K String String deriving (Eq, Show) type Mresults.= [Mresult] -Matching takes a regular expression and a string and either fails or -- returns the string that matched and the string that was leftover. matchRegEp -> StringMresults -You fill in STUBS below. Many are basically the same as in the -- backtracking sea rch case -Matching empty string always succeeds, with empty string as the matched string match Rull 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 Bany. str= [] --STUB -- Match a character succeeds iff the string begins with the character match (Bshch1) str [] --STUB Match (Ror, rl r2) string matches rl against string and also r2 against string -- and combines the results from both matches match (Bar. rexpirexR2) str= [] --STUB -- Match (Rand rl r2) string first matches rl; for every successful result, it follows that pacticulra result with a match against r2. All the -- results (across all the results of rl) are collected and returned match (Rand rexp1 rexp2) str [] -- STUB -Matching an optional expression is like matching (rexp. I null) match (BRP.t.rexp) str_ []STUB -- matching rexpx is like matching ((rexp. rexpxnull), 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 exp0.) match (Rstarrexp) str - []-STUB UTILITY FUNCTIONS -- (Add whatever Htiltiy functions you deem fit) -- STUB 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. E.g. matching (a |ab) with "abc" should succeed with both disjuncts and return [OK "a" "bc", OK "ab" "c" ]. (In part l, you should return OK "ab" "c", the longer of the two match results.) The regular expression data structure stays the same as in part 1. The result type changes: data Mresult OK string String deriving (Eq, Show) type Mresults[Mresult So match returns an Mresults, which is a list of OK. A list of empty indicates a match failed, so we don't need FAIL anymore 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. Le., for each result OK r3 s3 of exp2 with s1, we generate OK ( + 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 (aab) b with "abbc" . The recursive match of ( a l ab) with "abbc" returns two results, [OK "" "bbe", OK" ab" "bc"J . Take OK "a" "bbc" and match for b with "bbc". This gives us [OK "b" "bc"], 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"]. . So match ( a | ab) b with "abbc" 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 expl search that the exp2 search follows Example: . Matching (a 1 aa) with "aaaaaa" yields [OK "a" "aaaaa", OK "aa" "aaaa"] . matching (a l aa ) ( aal a) with "aaaaaa" yields [OK "aa" "aaaa", OK "aaa" "aaa", "aaa" Note OK "aaa" "aaa" appears twice here - don't worry about t. (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 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 expl. exp2, exp xp2, -null string (epsilon), $ (end of string), dot (any single character), -- optional expr. (? exp), and Kleene star data RegEXpRnull Rend | Rany | Rch Char | Ror RegExp. RegEXp | Rand RegExp RegExp -- e empty string epsilon -- at end of string? --. any one character -- a specific character -- | alternation -- concatenation -- ? optional expression Ropt RegEXp | Rstar RegExp deriving (Eq, Show) Kleene star -- A match result [0K str1 str2] is a list of success pairs where strl is _ the prefix that matched and str2 is the suffix that was leftove r . _ A list of length 0 indicates no successful matches. A list of length 1 indicates that multiple matches exist. (.g., matching ("a" "ab") with "abc" -returns two results, one matching "a" (and leaving "bc") and one matching -"ab" and leaving ..". For each 0K str1 str2 result, str1 ++ str2 should -be the original string passed to match data Mresult= 0K String String deriving (Eq, Show) type Mresults.= [Mresult] -Matching takes a regular expression and a string and either fails or -- returns the string that matched and the string that was leftover. matchRegEp -> StringMresults -You fill in STUBS below. Many are basically the same as in the -- backtracking sea rch case -Matching empty string always succeeds, with empty string as the matched string match Rull 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 Bany. str= [] --STUB -- Match a character succeeds iff the string begins with the character match (Bshch1) str [] --STUB Match (Ror, rl r2) string matches rl against string and also r2 against string -- and combines the results from both matches match (Bar. rexpirexR2) str= [] --STUB -- Match (Rand rl r2) string first matches rl; for every successful result, it follows that pacticulra result with a match against r2. All the -- results (across all the results of rl) are collected and returned match (Rand rexp1 rexp2) str [] -- STUB -Matching an optional expression is like matching (rexp. I null) match (BRP.t.rexp) str_ []STUB -- matching rexpx is like matching ((rexp. rexpxnull), 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 exp0.) match (Rstarrexp) str - []-STUB UTILITY FUNCTIONS -- (Add whatever Htiltiy functions you deem fit) -- STUB
