Pattern matcher Objective: Implement a function which matches pattern with data. This function should return "NIL" if it fails to match, "t" if it succeeds but finds NO variables in the pattern, and an association list of variable bindings in the case where it succeeds AND finds variables in the pattern. For example, given the argument pattern: (a b c) and data: (a b d), the function would return "NIL". given the argument pattern: (a b c) and data: (a b c), the function would return "t" An association list is a list of pairs. The first element of list is a symbol, the name of a pattern variable. The second element of list is the data element found to match the variable during pattern matching. For example, given the argument pattern: (?a ?b c) and data: (1 2 c), the function would return an association list ((?a 1) (?b 2)) Notice that here we use interrogation mark "?" in front of a word to represent a variable. The pattern consists of parentheses, variables, and symbols, while the data consists of only parentheses and symbols. There are some special marks in the pattern: Interrogation mark "?" can match anything (a single unit, i.e atom or list) without binding data to a variable. For example, given the argument pattern: (? ? c) and data: (a b c), the function would return "t". given the argument pattern: (? ? ?) and data: (a (a b) ((a b c))), the function would return "t". Kleene Star "*" matches 0 or more elements without binding data to a variable. For example, given the argument pattern: (a * b) and data: (a x x x b), the function would return "t". given the argument pattern: (a * ?x) and data: (a b), the function would return an association list (?x b) Notice that there may be more than one possible binding, and you have to enumerate all of them. For example, given the argument pattern: (a * ?x *) and data: (a b c d), the function would return a list of association lists (((?x b)) ((?x c)) ((?x d))) ************************************************************************************ NOTICE: Even if you are using some languages other than LISP, your output should also be a String in LISP format. You can define your input format, but it should be well documented and give more than 3 different test cases to shown how to use your program ************************************************************************************* Here are some samples of inputs and the corresponding outputs: pattern: () data: () output: t pattern: (ai) data: (ai) output: t pattern: (ai cs) data: (ai cs) output: t pattern: (cs ai) data: (ai cs) output: NIL pattern: (1 2 3 0) data: (1 2 3 4 0) output: NIL pattern: (? mudd) data: (seely mudd) output: t pattern: (?first ?middle mudd) data: (seely w mudd) output: ((?middle w) (?first seely)) pattern: (? ?x ? ?y ?) data: (Warren Buffet Is A Good Man) output: NIL pattern: (School Of Engineering and Applied Science) data: (School Of Engineering) output: NIL pattern: (* School Of Engineering and Applied Science) data: (The Fu Foundation School Of Engineering and Applied Science) output: t pattern: (The * School Of Engineering and Applied Science) data: (The Fu Foundation School Of Engineering and Applied Science) output: t pattern: (The * School Of Engineering and Applied Science) data: (The School Of Engineering and Applied Science) output: t pattern: (* 3 ?x 4 *) data: (3 5 4) output: ((?x 5)) pattern: ( ?x (1 2) ?y (4 5)) data: (c (1 2) d (4 5)) output: ((?y d)(?x c)) pattern: (?y ?z (c v)) data: (8 gh (c v) ) output: ((?z gh)(?y 8)) pattern: (((get) me) out) data: (get (me (out))) output: NIL pattern: (A * B) data: (A A A A A B) output: t pattern: (?x * ?y) data: (A A A A A B) output: ((?y b)(?x a))