EECS 268:  Laboratory 6

EECS 268: 
Laboratory 6
Due: This lab is due one week from the start of your lab, even though that will be during Fall Break for some of you.

You are going to enter into an automated question and answer session in which – while the actual subject matter will be quite different – the responsiveness of answer to question will likely be somewhat reminiscent of current political dialog.

The Data File
We will use the grammars defined on these two data files:

•    Question grammar

•    Answer grammar

Project Specifications
Create a class Grammar whose required public methods should become clear as you read the rest of this lab specification. I suggest you pass the file name or the already opened std::ifstream instance into the constructor. The constructor implementation will then read the grammar and store its specifications in private instance variables.

When reading the grammars in the question and answer grammar files, observe the following assumptions:

1.    The data on the file is case sensitive. All string comparisons are to be case-sensitive. Note, for example, that FOO might be a nonterminal while Foo is a terminal symbol in a grammar.

2.    All symbols (terminal and non-terminal) are whitespace-delimited.

3.    Each production rule appears as a separate rewrite rule. That is, there are no alternation ("|") symbols used in production rules.

4.    To simplify reading and parsing of the grammar production rules, each production rule is terminated by a pound sign (anyone under 35 knows it is a hashtag ☺). This allows you to read production rules symbol by symbol without regard for where line breaks occur. The '#' is NOT to be considered as either a terminal or nonterminal. It must never appear in any strings generated from either grammar.

5.    The start symbol is the nonterminal in the first production rule in the file.

The Executive class is to create Grammar instances for each of the two grammars. After both Grammar instances have been created, the Executive queries each Grammar instance for (i) the set of nonterminal symbols, (ii) the set of terminal symbols, and (iii) the start symbol. (Hopefully needless to say, the Grammar instances must determine these algorithmically; do not just hard-wire the strings returned from these methods. We may test your programs with different grammars.) The Executive then produces a well-formatted display of this information for both grammars.

Then the Executive enters a loop, prompting the user for something to do. The choices are:

1.    A: The Executive asks the "question" Grammar instance to generate a question from its grammar and return it to the Executive. The question must be returned as a single std::string. The Executive then prints the question to the screen and asks the "answer" Grammar instance to generate an answer from its grammar. Again, the answer must be returned as a single std::string, and the Executive then prints this answer.

2.    Q: Quit the program.

Implementation Hints and Notes
Whenever either Grammar instance is asked to generate a string from its grammar, it begins with the start symbol, it randomly chooses a rewrite rule for the start symbol, and then continues randomly choosing rewrite rules for each nonterminal until a result consisting of only terminal symbols results. To make the handling of the rewrite rules in the Grammar classes a bit more manageable as well as the generation of strings by applying rewrite rules, you are free to use the std::vector class, both to store the rewrite rules and as intermediate storage for generated strings in the language. I would strongly suggest that you use an additional class (say, ProductionRule), and have the Grammar class store a std::vector<ProductionRule>.

But don't forget that the result returned to the Executive must be a single std::string as stated above.

To prevent strings of infinite length being generated by recursive rewrite rules, limit your depth of recursion to 8. If and when you encounter that depth, select an alternative for each remaining nonterminal by selecting a rule whose right-hand side does not contain the nonterminal being rewritten. If you do so, the grammars you will be given are guaranteed to terminate quickly with a collection of only terminal symbols.

There is no need to try to prevent nonsense answers (that's part of the fun) or to prevent answers with redundant words. See the sample dialog below.

Sample Dialog
This shows only the output from the looping; not the required reporting of terminals, nonterminals, and start symbol. Characters in bold are what you type at the prompt; other characters are produced by your Executive.

Enter command: A

What tree is popular?

All are good.

Enter command: A

What car is next?

Either red or Chrysler or spring or Chrysler or oak.

Enter command: A

What season is popular?

None are bad.

Enter command: A

What color is good?

Either Iron Man Imperial Stout or blue.

Enter command: Q

Grading Criteria
Grades will be assigned according to the following criteria:

•    Correct implementation of the Executive class: 25%

•    Correct implementation of the Grammar class: 50%

•    Code design: 15%

•    Code style and documentation: 10%

Submission
Once you have created the tarball with your submission files, email it to your TA. The email subject line must look like "[EECS 268] SubmissionName":

[EECS 268] Lab 06

Note that the subject should be exactly like the line above. Do not leave out any of the spaces, or the bracket characters ("[" and "]").

In the body of your email, include your name and student ID.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

QuestionGrammer.txt

QUESTION What OBJECT is ADJECTIVE ? #

OBJECT color #

OBJECT tree #

OBJECT car #

OBJECT season #

OBJECT beer #

ADJECTIVE good #

ADJECTIVE popular #

ADJECTIVE bad #

ADJECTIVE next #

 

AnswerGrammer.txt

ANSWER ANSWER_CHOICE . #

ANSWER_CHOICE EITHER_A #

ANSWER_CHOICE ALL_A #

ANSWER_CHOICE NONE_A #

EITHER_A Either OBJECT or REM_EITHER #

REM_EITHER OBJECT #

REM_EITHER OBJECT or REM_EITHER #

ALL_A All are DESCRIPTION #

NONE_A None are DESCRIPTION #

OBJECT red #

OBJECT green #

OBJECT blue #

OBJECT oak #

OBJECT maple #

OBJECT Fiat #

OBJECT Chrysler #

OBJECT Toyota #

OBJECT Iron Man Imperial Stout #

OBJECT Bartertown Brown #

OBJECT spring #

OBJECT summer #

OBJECT fall #

OBJECT winter #

DESCRIPTION good #

DESCRIPTION bad #

DESCRIPTION the same #