Please make sure you are familiar with the resources and policies outlined in the syllabus and the take-home assessments page.

A5 - Grammar Solver

Due by Thursday 02/10 at 11:59 pm.

Note: There is no intro video for this assignment. See the lecture from 2/4.

Specification Submit Code on Ed

You may submit any part of the assignment as many times as you want before the due date. To submit on EdStem, you should use the Mark button to submit your code. You can view your past submissions using the “Submissions” button.

Code Files

All files can also be downloaded here: a5.zip

Developing at Home

You are welcome to use Ed as your environment to work on the homework, but we recommend setting up a local environment following our Desktop Software instructions. This will allow you to work offline, and access the great debugger provided by jGrasp! You can download the code from Ed and when you want to submit, upload it again and then pressing Mark to submit.

Useful Resources

Tip

For this assignment, there is an output comparison tool, but it’s not the most useful since the strings you are generating are random. Instead, we have a Grammar Verifier that you can copy and paste your output for a particular rule to verify its correctness.

Frequently Asked Questions (FAQ)

Q: I am utterly confused about grammars, what this assignment is about?

A: In terms of this assignment, a grammar is a set of rules that corresponds to a symbol. For instance, the adj grammar relates to many different adjectives like purple, loud, sticky, and fake. To put it simply, one grammar has many rules. This relationship is also known as non-terminal to terminal. For this assignment, we want you to navigate through these grammars and create them. Notice that some grammars have grammars in their rule sets as well. Upon encountering this situation, remember that it is a grammar that needs to be generated as well.

Take a look at the decision tree in the assignment specifications, this should help give you a visualization of the problem at hand.

Q: What is a map? How do I use a map?

A: Look at the WordCounter program written during last Wednesday’s lecture and Friends program written during last Wednesday/Friday’s lecture. Remember that a Map stores a relationship between a pair (known as a key to value relationship). What kinds of things do you think you could pair up in this assignment? Take note that the assignment write up states that you will have to include a Map, TreeMap, and String split method in your solution.

Java has a more detailed definition of a Map on the Java API.

Q: What type of data should my Map store?

A: This aspect of the assignment is up to you to figure out. Remember how you’ll use the Map and how non-terminals relate to their rules.

Q: I’m having trouble breaking apart the String to get their parts.

A: The spec walks you through the exact lines of code you need to break up the Strings

Q: When I use String.split(), I get some empty strings in the array. Why?

A: A subtle point to this method is that empty strings will be taken into account when splitting a string. For example, the string " grammar " will be split into an array of ["", "grammar", ""]. Maybe there is something we can do to the String so that it takes care of this particular behavior?

Q: I try to split the String, but it doesn’t break it apart at the right places. Why not? A: Look out for whitespace. The assignment writeup tells you a great strategy for tackling this issue.

Q: How do I spot symbols if they don’t start/end with "<" and ">" like in sentences 2?

A: The "<" and ">" symbols are not special cases you should be concerned with. Treat them as you would any other symbol, word, or character.

Q: Spaces are in the wrong places in my output. Why?

A: Try using other characters like "_", "~", or "!" instead of spaces to find out where there’s extra whitespaces. Make sure to change it back to whitespace before submitting!

Q: How do I debug my recursive method?

A: Try using System.out.println to find out which grammars are being generated at certain points in your program. Try before and after your recursive step as well as in your base case.

Q: In my recursive case, why doesn’t it join together the various pieces correctly?

A: Remember that setting a String = to another variable within a recursive step will not translate in all instances of that method. Be sure to actively add onto your String and return that instead of reassigning it.

Q: My recursive method is really long and icky. How can I make it cleaner?

A: Remind yourself of the strategy in approaching recursive solutions. When are you stopping each recursive call? Make sure you’re not making any needless or redundant checks inside of your code.

Q: When I run sentence2.txt, I get really long math expressions? Is that okay?

A: Yes, that’s expected. Math can get really complicated sometimes!!