数据结构与算法代写 | Assignment 3

本次Java代写是关于Java语法生成器相关的assignment

Introduction

Computers have revolutionized student life. In addition to providing no end of entertainment and distractions, computers also have also facilitated all sorts of student work from English papers to Calculus. One important area of student labor that has been painfully neglected is the task of filling up space in papers, Ph.D. dissertations, extension requests, etc. with important sounding and somewhat grammatically correct random sequences. An area which has been neglected, that is, until now…

The “Random Sentence Generator” is a handy and marvelous piece of technology (that you’re going to build!) to create random sentences from a pattern known as a grammar. A grammar is a template that describes the various combinations of words that can be used to form valid sentences. There are profoundly useful grammars available to generate extension requests, generic Star Trek plots, your average James Bond movie, “Dear John” letters, and more. You can even create your own grammar. Fun for the whole family!

Let’s show you the value of this practical and wonderful tool that is generating excuses for late homework:

Example/Tactic #1: Wear down the TA’s patience.

I need an extension because I used up all my paper and then my dorm burned down and then I didn’t know I was in this class and then I lost my mind and

then my karma wasn’t good last week and on top of that my dog ate my notes and as if that wasn’t enough I had to finish my doctoral thesis this week and

then I had to do laundry and on top of that my karma wasn’t good last week

and on top of that I just didn’t feel like working and then I skied into a tree and

then I got stuck in a blizzard at Tahoe and on top of that I had to make up a lot of documentation for the Navy in a big hurry and as if that wasn’t enough I thought I already graduated and as if that wasn’t enough I lost my mind and

Fall 2021 Page 2 of 6

in addition I spent all weekend hung-over and then I had to go to the Winter Olympics this week and on top of that all my pencils broke.

Tactic #2: Plead innocence.

I need an extension because I forgot it would require work and then I didn’t know I was in this class.

Tactic #3: Honesty.

I need an extension because I just didn’t feel like working

Background

What is a grammar?

A grammar is just a set of rules for some language, be it English, a programming language, or an invented language. For now, we will introduce to you a particular kind of grammar called a Context Free Grammar (CFG). Here is an example of a simple grammar:

The Poem grammar:

{

“grammarTitle”: “Poem Generator”,

“grammarDesc”: “A grammar that generates poems. “,

“start”:[

“The <object> <verb> tonight.”

],

“object”: [

“waves”,

“big yellow flowers”,

“slugs”

],

“verb”: [

“sigh <adverb>”,

“portend like <object>”,

“die <adverb>”

],

adverb: [ “warily”,

“grumpily”

]

}

According to this grammar, two possible poems are “The big yellow flowers sigh warily tonight.” and “The slugs portend like waves tonight.”.

Fall 2021 Page 3 of 6

Essentially, the strings in brackets (<>) are variables which expand according to the rules in the grammar. More precisely, each string in brackets is known as a “non-terminal”. A non-terminal is a placeholder that will expand to another sequence of words when generating a poem. In contrast, a “terminal” is a normal word that is not changed to anything else when expanding the grammar. The name “terminal” is supposed to conjure up the image that it is a dead-end— no further expansion is possible from here.

A definition consists of a non-terminal and its set of “productions” or “expansions”. There will always be at least one and potentially several productions that are expansions for the non-terminal. A production is just a sequence of words, some of which may be non-terminals. A production can be empty (i.e., an empty array) which makes it possible for a non-terminal to expand to nothing.

Expanding the grammar

Once you have read in the grammar, you will be able to produce random expansions from it. You begin with a single non-terminal with the “Start” label. For a non-terminal, consider its definition, which will contain a set of productions. Choose one of the productions at random. Take the words from the chosen production in sequence, (recursively) expanding any which are themselves non-terminals as you go.

Begin with a start production and expand it to generate a random sentence. Note that the algorithm to traverse the data structure and print the terminals is extremely recursive.

Modelling the grammar

The grammar model will be provided in a JSON file.

• The JSON file will specifically have 2 keys: o “start” which will contain a list of non-terminals to start with o “grammarTitle” which is a user-readable name for the grammar.

• The file will optionally include:

o a “grammarDesc” key, where the value is a user-friendly description of the grammar.

• All other keys will be a non-terminal, with the values being an array of strings with a production for that non-terminal.

• Your code can assume that the grammar files are syntactically correct (i.e. have a start and grammarTitle definition, have the correct punctuation and format as described above, don’t have some sort of endless recursive cycle in the expansion, etc.).

• The one error condition (in regard to the grammar) you should catch reasonably is the case where a non-terminal is used but not defined.

o It is fine to catch this when expanding the grammar and encountering the undefined non-terminal rather than attempting to check the consistency of the entire grammar while reading it.

• The names of non-terminals should be considered case-insensitively, matching “Adj” and “adj”, for example.