Problem 1 Let us write a compiler that translates regular expressions to deterministic finite automata (DFAs).
2. Youcanfindthefollowingfiles:
• main.ml: Driver code with some test cases. You can add your own test cases here.
• regex.ml: The definition of regular expressions (the “source lan- guage” of our compiler).
• nfa.ml: NFA implementation (the “intermediate representation” of our compiler). Read nfa.mli to see how to use the NFA module.
• dfa.ml: DFA implementation (the “target language” of our com- piler). Read dfa.mli to see how to use the DFA module.
• trans.ml: Complete and submit this file.
3. Inregex.ml,regularexpressionisdefinedasfollows:
type alphabet = A | B
| Alpha of alphabet
| OR of t * t
| CONCAT of t * t
| STAR of t
where we assume Σ = {A, B}.
4. Intrans.ml,youcanfindcodebelow:
open Regex
exception Not_implemented
let regex2nfa : Regex.t -> Nfa.t
=fun _ -> raise Not_implemented (* TODO *)
let nfa2dfa : Nfa.t -> Dfa.t
=fun _ -> raise Not_implemented (* TODO *)
(* Do not modify this function *)
let regex2dfa : Regex.t -> Dfa.t
=fun regex ->
let nfa = regex2nfa regex in
let dfa = nfa2dfa nfa in
Code Help, Add WeChat: cstutorcs
let run_dfa : Dfa.t -> alphabet list -> bool
=fun _ _ -> raise Not_implemented (* TODO *)
Your job is to implement the functions:
• regex2nfa, which converts a regular expression into an equivalent NFA,
• nfa2dfa, which converts an NFA into an equivalent DFA, and • run dfa, which takes a DFA and a string (i.e., a sequence of input
symbols) and returns true (i.e., accept) or false (i.e., reject).
Once you complete the implementation, you can build and run the program as follows:
$ dune build main.exe; _build/default/main.exe
For the test cases in main.ml:
let testcases : (Regex.t * alphabet list) list =
(Empty, []);
(Epsilon, []);
(Alpha A, [A]);
(Alpha A, [B]);
(OR (Alpha A, Alpha B), [B]);
(CONCAT (STAR (Alpha A), Alpha B), [B]);
(CONCAT (STAR (Alpha A), Alpha B), [A;B]);
(CONCAT (STAR (Alpha A), Alpha B), [A;A;B]);
(CONCAT (STAR (Alpha A), Alpha B), [A;B;B]);
(CONCAT (CONCAT (STAR (CONCAT (Alpha A, Alpha A)),
STAR (CONCAT (Alpha B, Alpha B))), Alpha B), [B]);
(CONCAT (CONCAT (STAR (CONCAT (Alpha A, Alpha A)),
STAR (CONCAT (Alpha B, Alpha B))), Alpha B), [A;A;B]);
(CONCAT (CONCAT (STAR (CONCAT (Alpha A, Alpha A)),
STAR (CONCAT (Alpha B, Alpha B))), Alpha B), [B;B;B]);
(CONCAT (CONCAT (STAR (CONCAT (Alpha A, Alpha A)),
STAR (CONCAT (Alpha B, Alpha B))), Alpha B), [A;A;A;A;B;B;B]);
(CONCAT (CONCAT (STAR (CONCAT (Alpha A, Alpha A)),
STAR (CONCAT (Alpha B, Alpha B))), Alpha B), [A;A;A;B;B;B])
the correct output is the following:
Github
Problem 2 Let’s implement a top-down parser that was covered during class time. Please complete the parse.ml file from the template code below and submit it:
You can define a context-free grammar using OCaml data types as follows.
type symbol =
| T of string (* terminal symbol *)
| N of string (* nonterminal symbol *)
| Epsilon (* empty string *)
| End (* end marker *)
type production = symbol * symbol list
type cfg = symbol list * symbol list * symbol * production list
let cfg1 = (
[N “E”; N “E’”; N “T”; N “T’”; N “F”],
[T “+”; T “*”; T “(“; T “)”; T “id”],
(N “E”, [N “T”; N “E’”]);
(N “E’”, [T “+”; N “T”; N “E’”]);
(N “E’”, []);
(N “T”, [N “F”; N “T’”]);
(N “T’”, [T “*”; N “F”; N “T’”]);
(N “T’”, []);
(N “F”, [T “(“; N “E”; T “)”]);
(N “F”, [T “id”])
A string is represented as a list of symbols. For example, the string id + id ∗ id is expressed as follows (the last symbol in the string must be End): let s1 = [T “id”; T “+”; T “id”; T “*”; T “id”; End]
1. Let’swriteafunctioncheck_LL1thatcheckswhetherthegivengrammarbelongstoLL(1).check_LL1: cfg -> bool For example, check_LL1 cfg1 should return true for the following grammars.
let cfg2 = (
[N “S”; N “E”; N “E’”; N “T”; N “T’”; N “F”],
[T “+”; T “-“; T “*”; T “/”; T “id”; T “num”; T “(“; T “)”],
(N “S”, [N “E”]);
(N “E”, [N “T”; N “E’”]);
(N “E’”, [T “+”; N “T”; N “E’”]);
(N “E’”, [T “-“; N “T”; N “E’”]);
(N “E’”, []);
(N “T”, [N “F”; N “T’”]);
(N “T’”, [T “*”; N “F”; N “T’”]);
(N “T’”, [T “/”; N “F”; N “T’”]);
(N “T’”, []);
(N “F”, [T “id”]);
(N “F”, [T “num”]);
(N “F”, [T “(“; N “E” ;T “)”]);
let cfg3 = (
[N “X”; N “Y”; N “Z”],
[T “a”; T”c”; T”d”],
(N “X”, [N “Y”]);
(N “X”, [T “a”]);
(N “Y”, [T “c”]);
(N “Y”, []);
(N “Z”, [T “d”]);
(N “Z”, [N “X”; N “Y”; N “Z”])
let cfg4 = (
[N “S”; N “S’”; N “E”],
[T “a”; T “b”; T “e”; T “i”; T “t”],
(N “S”, [T “i”; N “E”; T “t”; N “S”; N “S’”]);
(N “S”, [T “a”]);
(N “S’”, [T “e”; N “S”]);
(N “S’”, []);
(N “E”, [T “b”])
check_LL1 cfg2 should return true, check_LL1 cfg3 should return false, and check_LL1 cfg4 should also return false.
2. Let’swriteafunctioncalledparsethattakesinagrammarandastringtoperformbottom-upparsing.
parse : cfg -> symbol list -> bool
When assuming that the grammar given as the first input of parse is LL(1), if the second input string belongs to the language specified by the grammar, it returns true; otherwise, false. For example, for the following strings…
parse cfg1 s1, parse cfg1 s2, parse cfg2 s1, and parse cfg2 s2 should each return true, false, true, and true respectively.
let s1 = [T “id”; T “+”; T “id”; T “*”; T “id”; End]
let s2 = [T “id”; T “/”; T “(“; T “num”; T “+”; T “id”; T “)”; End]
程序代写 CS代考 加微信: cstutorcs