Page 1 of 6 EECS 293 Software Craftsmanship 2018 Fall Semester Programming Assignment 4 Due at the beginning of your discussion session on September 24-28,
c/c++代写,java代写,python代写,matlab代写,作业代写,留学生作业代写
Page 1 of 6 EECS 293 Software Craftsmanship 2018 Fall Semester Programming Assignment 4 Due at the beginning of your discussion session on September 24-28, 2018 Reading Read Chapter 5 and Section 19.6 in Code Complete. Grading Guidelines Starting with this assignment, an automatic C (or less) is triggered by: • Any routine with complexity greater than 4, or by • Any piece of code that is essentially repeated. Programming First, make all the changes discussed in your discussion section. Additionally, you should refactor your code to make sure that it adopts the principles covered in the reading assignments. Parsing: Concept of Opera�ons Parsing is the process of converting a Boolean list into a Boolean tree. The process looks somewhat involved at first, but it turns out to be intuitive. Parsing has one argument, which is the Boolean list to be converted. Parsing uses another internal symbol list, called the working list. At each step, one symbol from the input list is copied to the working list. At this point, the parsing process will examine the last few symbols of the working list, and if they match against a pattern, apply a reduction. A reduction takes the last symbols of the working Page 2 of 6 list and replaces them with a new symbol. The following table gives the list of reductions, in decreasing order of priority. If the last elements of the working list have the following types: Replace them with: VARIABLE A new TERM containing that VARIABLE OPEN, EXPRESSION, CLOSE A new TERM containing that EXPRESSION NOT, TERM A new NOT EXPRESSION containing that TERM TERM A new EXPRESSION containing that TERM EXPRESSION AND EXPRESSION A new AND EXPRESSION containing those two sub-expression EXPRESSION OR EXPRESSION A new OR EXPRESSION containing those two sub-expression To summarize, the parsing algorithm is: Algorithm PARSE (Boolean list input) Argument: a Boolean list containing the input Return value: the corresponding Boolean expression, or a state denoting failure. working list ← new empty list for each symbol s in the input do append s to the working list repeatedly try to match the last symbols of the working list against a reduction pattern, choosing the highest priority pattern over the lower priority patterns if there is a match then replace the last symbols of the working list with the reduced symbol. if the working list contains a single expression then return it else return an error Page 3 of 6 As an example, on the Boolean list a ∧ (¬ b ∨ c), the algorithm works as follows: Working list Explanation VARIABLE Insert first symbol a in the working list TERM Apply the first reduction: replace the VARIABLE a new TERM containing the VARIABLE a EXPRESSION Reduction replaces the TERM with an EXPRESSION EXPRESSION AND No more reduction applies, append second symbol to the working list EXPRESSION AND OPEN No reduction applies, append next symbol EXPRESSION AND OPEN NOT No reduction applies, append next symbol EXPRESSION AND OPEN NOT VARIABLE No reduction applies, append VARIABLE b, which is the next symbol EXPRESSION AND OPEN NOT TERM Replace VARIABLE b with a new TERM containing VARIABLE b EXPRESSION AND OPEN EXPRESSION Replace NOT TERM with a new EXPRESSION containing it (this reduction has higher priority over the reduction of a TERM into an EXPRESSION) EXPRESSION AND OPEN EXPRESSION OR No reduction applies, append next symbol EXPRESSION AND OPEN EXPRESSION OR VARIABLE No reduction applies, append VARIABLE c, which is the next symbol EXPRESSION AND OPEN EXPRESSION OR TERM Reduce VARIABLE c to a new term EXPRESSION AND OPEN EXPRESSION OR EXPRESSION Reduce the term to a new EXPRESSION EXPRESSION AND OPEN EXPRESSION Reduce EXPRESSION OR EXPRESSION to a new EXPRESSION containing the conjunction of the two sub-expressions. Page 4 of 6 EXPRESSION AND OPEN EXPRESSION CLOSE No reduction applies, append the last symbol EXPRESSION AND TERM Reduce OPEN EXPRESSION CLOSE with a TERM containing that EXPRESSION EXPRESSION AND EXPRESSION Reduce the second TERM to a new EXPRESSION EXPRESSION Reduce EXPRESSION AND EXPRESSION to a new EXPRESSION containing the disjunction of the two sub-expressions At this point, there is no more input and no further reduction can be applied. Therefore, the parsing process terminates correctly and returns the single expression remaining in the working list, which corresponds to the tree representation shown in the picture. The next sections introduce the classes that support the algorithm for parsing. Reduc�ons To support the parser, create a new package-private final class Reduction containing the two private final fields: • List pattern, which represents the type of the elements of the working list to be matched against the reduction, and • Function>, TreeSymbol> reduction, which is the replacement operation The Reduction has a private constructor and a static final build method that creates a new reduction with the given pattern and reduction, or throws a NullPointerException with an appropriate message. The Reduction has the following final methods: • int size() returns the length of the pattern, • boolean matches(List typeList) returns true if the typeList contains the same number of types as the pattern, and the types match. Page 5 of 6 • Symbol apply(List symbolList) returns the new symbol that replaces symbolist, and which is obtained by applying the reduction. This method assumes that the symbolList match the pattern. Parse State The public final class State encodes the result of the parsing process. It contains the following private final fields: • boolean correct which is true if and only if the parsing outcome is correct, and • List workingList, which represents the final working list The private constructor sets the private fields, and package-private static final State build(List workingList) method returns a new state, which is correct if and only if the working list contains a single EXPRESSION. The State has the following public final methods: • isCorrect() returns whether the parse state is correct, • getWorkingList() returns a copy of the private working list, and • getExpression() returns the final expression if the state is correct. If the final expression is not correct, the behavior is unpredictable and may involve an arbitrary return value or exception. Parser The parser brings it all together. Create a public final class Parser with a public static final State parse(BooleanList input) that implements the parser. The parser implements the parsing algorithm, and can use Reduction and State. Further details are left to you. General Considera�ons These classes may contain as many auxiliary private methods as you see fit, and additional helper classes may be defined. Page 6 of 6 You should write JUnit tests to make sure that your primary methods work as intended. However, we will revisit testing later on in the course, so extensive testing is not yet recommended. Similarly, your code should have a reasonable number of comments, but documentation is going to be the topic of a future assignment. As a general guideline at this stage of the course, comments and tests should be similar to those accepted in EECS 132. Submission Bring a copy to discussion to display on a projector. Additionally, submit an electronic copy of your program to Canvas. In addition to your code, include a README file explaining how to compile and run the code. The code should be handed in a zip, tar.bz2, or tar.gz archive. Archives in 7z cannot be accepted.
留学生作业代写,cs作业代写,cs代写,作业代写,北美cs作业代写,澳洲cs作业代写,加拿大cs作业代写,cs作业代写价格,靠谱cs作业代写,程序代写