” CSE 143编程 写作、 辅导Python，CS，JavaCSE 143: Computer Programming II Winter 2021Take-home Assessment 5: Grammar Solver due February 11, 2021 11:59pmThis assignment will assess your mastery of the following objectives: Implement a well-designed Java class to meet a given specification. Implement recursive methods to solve a naturally-recursive problem. Implement a public-private recursive pair. Choose an appropriate data structure to represent specified data. Follow prescribed conventions for code quality, documentation, and readability.Overview: Languages, Grammars, and BNFIn this assessment, you will write a class GrammarSolver that will be able to generate random sentences(or other output) from a set of Specially-formatted rules. These rules are called a grammar and are usedto define a language. Our grammars will be written in Backus-Naur Form (BNF).Formal LanguagesA formal language is a set of words and symbols along with a set of rules defining how those symbols maybe used together. These rules dictate what are considered valid constructions in the defined language.For example, in English, A boy threw the ball. is a valid sentence, but A threw boy ball the is not,despite consisting of the same words, because the words are put together in an invalid way.GrammarsA grammar is a way of describing the syntax and symbols of a formal language. Grammars have two typesof symbols (e.g., words, phrases, sentences): terminals and non-terminals. A terminal is a fundamentalword or symbol in the language. For example, in English, any single word would be considered a terminal.A non-terminal is a symbol That is used to define specific groups of symbols that may be used in thelanguage. In a grammar for English, we might have non-terminals such as adjective, noun phrase,and sentence to name a few.sentenceverbrunsobjectdogarticletheFor example, consider the following simple language: Terminals: The, a, cat, dog, runs, walks Non-terminals: sentence: article and object and verb article: the or a. object: cat or dog. verb: runs or walks.This language allows the following sentences:the cat runs the cat walks a cat runs a cat walksthe dog runs the dog walks a dog runs a dog walksPage 1 of 10Backus-Naur Form (BNF)Backus-Naur Form (BNF) is a specific format for specifying grammars. Each line of BNF looks like thefollowing:nonterminal::=rule|rule|…|ruleEach rule is some sequence of terminals or non-terminals separated by whitespace. The | characterseparates different possible rules for the same non-terminal. For example, the grammar specified abovewritten in BNF would look like:sentence::=article object verbarticle::=the|aobject::=cat|dogverb::=runs|walksNotice that the non-terminal sentence has a single option consisting of multiple non-terminals, whereasthe others non-terminals each consist of multiple options.Rules may be duplicated for the same non-terminal to make a particular expansion more likely than others.For example, suppose the above grammar were modified as follows:sentence::=article object verbarticle::=the|aobject::=cat|cat|dogverb::=runs|walksThis grammar would produce the same sentences as the original grammar, but sentences containing catwould be twice as likely to occur as sentences containing dog.In addition, for this assessment, you may assume the following about all BNF rules: Each line will contain exactly one occurrence of ::= which will be the separator between the nameof a non-terminal and its options. A pipe (|) will separate each option for a non-terminal. If there is only one option for a particularnon-terminal (like with sentence above), there will be no pipe on that line. Whitespace separates tokens but doesnt haven any special meaning. There will be at least onewhitespace character between each part of a single rule. Extra whitespace should be ignored. Symbols are case-sensistive. (For example, S would not be considered the same symbol as s.) A terminal is any symbol that does not appear on the left-hand side of a rule. The text before the ::= is not empty, does not contain a pipe (|) character, and does not containany whitespace. The text after the ::= will be nonempty.Program BehaviorIn this assessment you will write a class that accepts a list of rules for a grammar in Backus-Naur Formand allows the client to Randomly generate elements of the grammar. You will use recursion to implementthe core of your algorithm.Page 2 of 10We have provided you with a client program, GrammarMain.java, that handles the file processing anduser interaction. This program reads a BNF grammar input text file and passes its entire contents to youas a List of Strings. You will write a class GrammarSolver that generates random results based onthe rules provided.GrammarSolverYour GrammarSolver class should have the following constructor:public GrammarSolver(ListString rules)This constructor should initialize a new grammar over the given BNF grammar rules where each rulecorresponds to one line of text. You should use regular expressions (see below) to break apart therules and store them into a Map so that you can look up parts of the grammar efficiently later.You should not modify the list passed in. You should throw an IllegalArgumentException if thelist is empty or if there are two or more entries in the grammar for the same non-terminal.Your GrammarSolver should also implement the following public methods:public boolean grammarContains(String symbol)This method should return true if the given symbol is a non-terminal in the grammar and falseotherwise.For example, for the Grammar above, grammarContains(sentence) would return true andgrammarContains(foo) or grammarContains(boy) (boy is a terminal in the language)would return false.public String getSymbols()This method should return a string representation of the various nonterminal symbols from thegrammar as a sorted, comma-separated list enclosed in square bracketsFor example, calling getSymbols() for the previous grammar would give: [article, object,sentence, verb].public String[] generate(String symbol, int times)This method should generate times random occurrences of the given symbol and return them asa String[]. Each string generated should be compact in the sense that there should beexactly one space between each terminal and there should be no leading or trailing spaces.If times is negative, you should throw an IllegalArgumentException. If the String argumentpassed is not a non-terminal in your grammar you should throw an IllegalArgumentException.When generating a non-terminal symbol in your grammar, each of the rules on the right-hand sideof the grammar Should be applied with equal probability.⑧Each writtenrule shouldequally likely,but a rule mayoccur more oftenif it appearsas an optionmore than once.Page 3 of 10Sample Grammar and ExecutionsComplex BNF (sentence.txt)sentence::=nounp verbpnounp::=det adjs noun|propnounpropnoun::=Hadi|Jazmin|Ali|Spot|Fred|Elmoadjs::=adj|adj adjsadj::=big|green|wonderful|faulty|subliminal|pretentiousdet::=the|anoun::=dog|cat|man|university|father|mother|child|televisionverbp::=transverb nounp|intransverbtransverb::=taught|honored|waved to|helpedintransverb::=died|collapsed|laughed|weptExample Random Sentence DiagramsentenceverbpnounpnounchildadjsadjsadjwonderfuladjgreendetthetransverbhonorednounppropnounFredPartial Example Execution (user input underlined)Welcome to the cse143 random sentence generator.What is the name of the grammar file? sentence.txtAvailable symbols are:[adj, adjs, det, intransverb, noun, nounp, propnoun, sentence, transverb, verbp]What do You want generated (return to quit)? sentenceHow many do you want me to generate? 5Hadi found JazminSpot helped the big catElmo diedthe green mother weptthe subliminal green man laughedAvailable symbols are:[adj, adjs, det, intransverb, noun, nounp, propnoun, sentence, transverb, verbp]What do you want generated (return to quit)?More example program executions are found at the end of the spec.Page 4 of 10Implementation GuidelinesGrammarSolver ConstructorFor this assessment, you MUST represent your grammar using a Map, where the keys of the map arethe non-terminals of the grammar, and the values are the options for expansion the corresponding nonterminal.You should choose an appropriate data structure for the values in your Map to effectivelyrepresent the grammar rules and make the operations required by the class convenient and efficient.generate AlgorithmThe generate method will generate a random occurrence of a given non-terminal NT. You MUST usethe following recursive algorithm in your implementation of this method:Choose a random expansion rule R for the non-terminal NT. For each of the symbols in therule R, generate a random occurrence of that symbol. If the symbol is a terminal, the expansionis simply the symbol itself. If the symbol is a non-terminal, you should generate an expansionusing a recursive call.Remember that it is Acceptable to have a loop inside your recursion. (In fact, you will likely want one aspart of this algorithm!) The directory crawler program from class will serve as a good guide for how towrite this program. In that example, we iterated over the different files in a directory and used recursionto list the files in each subdirectory. For your GrammarSolver, you will iterate over the different symbolsin the chosen role and use recursion to generate an expansion for each symbol. You may also find thatyou will want to use a public/private pair for this recursive task.Testing Your SolutionWe are providing another tool that is linked on the section for this assignment to check the output ofyour generate method to make sure it is producing valid output.⑧Remember toremove anydebuggingcode when yousubmit.You can test that the correct whitespace is produced from generate by using some non-whitespacecharacter (e.g. ~) instead of spaces and inspecting the output visually.Splitting StringsIn this assignment, it will Be useful to know how to split strings apart in Java. In particular, you will needto split the various options for rules on the | character, and then, you will need to split the pieces of arule apart by spaces.To do this, you should use the split method of the String class, which takes a String delimiter(e.g. what to split by) as a parameter and returns your original large String as an array of smallerStrings.The delimiter String passed to split is called a regular expression, which are strings that use a particularsyntax to indicate patterns of text. A regular expression is a String that matches certain sequences.For instance, abc is a regular expression that matches a followed by b followed by c.You do not need to have a deep understanding of regular expressions to complete this assessment. Hereare some specific regular expressions that will help you with particular splitting steps for your class: Splitting Non-Terminals from Rules. Given a String, line, to split line based on where::= occurs, you could use the regular expression ::= (since you are looking for these literalcharacters). For example:String line = example::=foo bar |baz;String[] pieces = line.split(::=); // [example, foo bar |baz]Page 5 of 10 Splitting Different Rules. Given a String, rules, to split rules based on where the | characteris, it looks similar to the above, except, in regular expressions, | is a special character. So, we mustescape it (just like \n or \t). So, the regular expression is \\|. (Note that we need two slashesbecause Slashes themselves must be escaped in Strings.) For example:String rules = foo bar|baz |quux mumble;String[] pieces = rules.split(\\|); // [foo bar, baz , quux mumble] Splitting Apart a Single Rule. Given a String, rule, to split rule based on whitespace, wemust look for at least one whitespace. We can use \\s to indicate a single whitespace of anykind: \t, space, etc. And by adding + afterwards, the regular expression is interpreted as one ormore of whitespace. For example:String rule = the quick brown fox;String[] pieces = rule.split(\\s+); // [the, quick, brown, fox]Removing Whitespace from the Beginning and the End of a StringOne minor issue that comes up with splitting on whitespace as above is that if the String you are splittingbegins with a whitespace character, you will get an empty String at the front of the resulting array.Given a String, str, we can create a new String that omits all leading and trailing whitespace removed:String str = lots of spaces \t;String trimmedString = str.trim(); // lots of spacesDevelopment Strategy and HintsThe generate method is the most difficult, so we strongly suggest you write it last. Remember that itis helpful to tackle difficult methods using iterative development where you solve simple versions of theproblem first.Random programs can be difficult to validate correctness, and the generate method you will implementuses randomness to decide which rule for a given non-terminal to use. To help you debug and validateyour output, we have provided a grammar verifier tool on the course website that verifies your outputfollows the grammar rules (but ignores whitespace).If your recursive method has a bug, try putting a debug println that prints your parameter values tosee the calls being made.Code Quality GuidelinesIn addition to producing the behavior described above, your code should be well-written and meet allexpectations described in The grading guidelines, Code Quality Guide, and Commenting Guide. For thisassessment, pay particular attention to the following elements:SortedMapBecause we want you to guarantee the keys of your map are sorted, we will ask you to use theSortedMapK, V interface for this assignment instead of the MapK, V interface. The SortedMapinterface is essentially the same as the Map interface, except it requires the keys be sorted. This meansTreeMap is a valid SortedMap implementation, but HashMap is not. You can use all the same methodson a SortedMap as you could on a Map.Page 6 of 10Generic StructuresYou should always use generic structures. If you make a mistake in specifying type parameters, theJava compiler may warn you that you have unchecked or unsafe operations in your program. If youuse jGRASP, you may want to change your settings to see which line the warning refers to. Go toSettings/Compiler Settings/Workspace/Flags/Args and then uncheck the box next to Compileand type in: -Xlint:uncheckedData FieldsProperly encapsulate your objects by making data your fields private. Avoid unnecessary fields; usefields to store important data of your objects but not to store temporary values only used in one place.Fields should always be initialized inside a constructor or method, never at declaration.ExceptionsThe specified exceptions must be thrown correctly in the specified cases. Exceptions should be thrownas soon as possible, and no Unnecessary work should be done when an exception is thrown. Exceptionsshould be documented in comments, including the type of exception thrown and under what conditions.CommentingEach method should have a header comment including all necessary information as described in theCommenting Guide. Comments should be written in your own words (i.e. not copied and pasted fromthis spec) and should not include implemenation details.Running and SubmittingIf you believe your behavior is correct, you can submit your work by clicking the Mark button in the Edassessment. You will see the results of some automated tests along with tentative grades. These gradesare not final until you have received feedback from your TA.You may submit your work as often as you like until the deadline; we will always grade your most recentsubmission. Note the due date and time carefullywork submitted after the due time will not beaccepted.Getting HelpIf you find you are Struggling with this assessment, make use of all the course resources that are availableto you, such as: Reviewing relevant Examples from class Reading the textbook Visiting office hours Posting a question on the message boardCollaboration PolicyRemember that, while you are encouraged to use all resources at your disposal, including your classmates,all work you submit must be entirely your own. In particular, you should NEVER look at a solutionto this assessment from another source (a classmate, a former student, an online repository, etc.). Pleasereview the full policy in the syllabus for more details and ask the course staff if you are unclear on whetheror not a resource is OK to use.Page 7 of 10ReflectionIn addition to your code, you must submit answers to short reflection questions. These questions willhelp you think about what you learned, what you struggled with, and how you can improve next time.The questions are given in the file GrammarSolverReflection.txt in the Ed assessment; type yourresponses directly into that file.Page 8 of 10Sample Execution #1 (user input underlined)Welcome to the cse143 random sentence generator.What is the name of the grammar file? sentence.txtAvailable symbols to generate are:[adj, adjs, det, intransverb, noun, nounp, propnoun, sentence, transverb, verbp]What do you want generated (return to quit)? detHow many do you want me to generate? 5athetheatheAvailable symbols to generate are:[adj, adjs, det, intransverb, noun, nounp, propnoun, sentence, transverb, verbp]What do you want generated (return to quit)? nounpHow many do you want me to generate? 5Elmoa green big pretentious green pretentious subliminal universitythe pretentious catJazminthe pretentious subliminal motherAvailable symbols to generate are:[adj, adjs, det, intransverb, noun, nounp, propnoun, sentence, transverb, verbp]What do you want generated (return to quit)? sentenceHow many do you want Me to generate? 20a faulty dog laughedAli helped a wonderful dogSpot collapsedthe green father weptSpot laughedElmo taught Alithe subliminal green man honored Freda wonderful faulty big father laughedthe faulty faulty university taught the faulty dogElmo helped the green universityHadi helped the pretentious manthe pretentious man diedAli laughedthe pretentious subliminal child found HadiElmo wepta wonderful wonderful faulty child collapsedSpot found the subliminal subliminal pretentious universitythe green father helped the wonderful cata faulty television weptthe faulty mother laughedAvailable symbols to generate are:[adj, adjs, det, intransverb, noun, nounp, propnoun, sentence, transverb, verbp]What do you want generated (return to quit)?Page 9 of 10Sample Execution #2 (user input underlined)Welcome to the cse143 random sentence generator.What is the name of the grammar file? sentence2.txtAvailable symbols to generate are:[E, F1, F2, OP, T]What do you want generated (return to quit)? THow many do you want me to generate? 542- yxx( ( 1 ) )Available symbols to generate are:[E, F1, F2, OP, T]What do you want generated (return to quit)? EHow many do you Want me to generate? 10x – 10sin ( 1 + 92 + – 1 / 42 )max ( y , 92 )42 % 1- 429219242 – sin ( 1 )Available symbols to generate are:[E, F1, F2, OP, T]What do you want generated (return to quit)?Page 10 of 10如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
