CFGI(Automata)
sandeep@45
DescriptionforCFGI.docx
Assignment Title:
This is for the course is a CFGI (Context Free Grammar Interpreter). The CFGI take as input a CFG and a string to parse and gives an output whether the test string is either accepted or rejected in the following way:
0. Production Rule Input Step:
For each production rule, two parts need to be given as input. The left-hand nonterminal of each production and the right-hand side consisting of both terminals and nonterminials are input for each rule one at a time. Use ε to fill in as an empty text field corresponding to NULL symbol.
Use | (left pipe symbol) for “OR”. Also make sure that the input is case-sensitive and whitespace is not ignored. So for the input, the following format is suggested to input each production rule one at a time for all production rules. Repeat the same process for each production rule.
|
$ |
→
+ : Click here to enter another production
1. Verification Step:
For each production rule entered, display it to verify. For example, you may want to display “S
→ NaBba is the rule you want to add?” to confirm. Also after all production rules are entered, you should list all rules of the grammar to confirm the final CFG.
2. Testing/Output Step:
In this step, you will input test strings one per line. An empty line will corresponds to the empty string. For each input string, the output should be either YES THE STRING IS ACCEPTED BY THE GRAMMAR or NO THE STRING IS NOT ACCEPTED BY THE GRAMMAR. You may
consider using the following type of window to accept the test string and show the test result as output.
Assignment Implementation Requirements:
1. The CFG should have 15-20 rules with moderate complexity on the right hand side.
2. Show at least 10 test cases for which 7 are correct strings and 3 are incorrect strings. For each test string, include a derivation tree to prove whether it is accepted or rejected.
3. You may choose to use any high level computer language of your choice. For example, you may use C++, Java, Java script, Mat Lab, Python or any combination of them.
4. If you get to borrow a part of your code from existing code developed by someone else, you must specify the source as reference. Unless you provide the reference, your code will be considered plagiarized and will result in a grade of 0 for the assignment. You cannot use other source for the entirety of your implementation, but you may use up to 50%. Thus you must specify which parts you have borrowed and which parts you have done on your own.
Deliverables:
1. Copy of source code with reference on how much is your own work.
2. Derivation tree for each testing string showing whether it is accepted or rejected.
3. Screen capture of your test output.
4. The above three should be compiled into one Word file to upload.
