Assignment 2. Sets. For this assignment an interpreter has to be written for a calculator with the ”command-language” shown further down. All ”sentences” in this command- language are statements for...

there is a pdf explaining the assignment.there is skeleton that must be used.the interfaces also must be used like we made them. the classes can be modified


Assignment 2. Sets. For this assignment an interpreter has to be written for a calculator with the ”command-language” shown further down. All ”sentences” in this command- language are statements for operations with sets of arbitrary big natural num- bers. The calculator should be able to store an arbitrary number of variables (a variable being a combination of a name and a value). Proceed as follows: 1. Finish the specifications of the Identifier ADT and the Set ADT that can be found in the provided skeleton on Canvas. The type Identifier will be the type of the name and the type Set will be the type of the value of each variable stored by the calculator. 2. From the API use (1) the class BigInteger to implement the arbitrary big natural numbers and (2) the class HashMap to store the arbitrary number of variables. 3. Implement the class LinkedList according to the specification given in the ListInterface. The given class Node has to be used in the implementation of this class List. We provide a class ListTest which you must use to test your implementation. Instructions on how to use it are at the end of this document. 4. Implement the class Set with the class LinkedList. 5. Use instances of the class APException in case you want to throw an exception. 6. Make, using the objects, a design for the interpreter. Use the method of recursive descent (see the example at the end). 7. Get approval for the filled in interfaces, as well as the design of the inter- preter, at the meetings with the assistant. 8. Once your design and interfaces have been approved, and you have imple- mented the interfaces, you can start with programming. First, completely write-out the parser part of your design. Which means, write a program that reads lines of input, and does nothing in case of a correct command, but returns a clear error-message in case there are incorrect commands. 9. Only when the parser works, must you proceed to extend it to an inter- preter. The interpreter must recognize and execute commands written in the command-language specified below. With the aid of the command-language specified further down, we can manip- ulate the sets of natural numbers and the variables that are contained in the calculator. Only identifiers are allowed as names for variables. 1 There are four operators that can be used on sets in this language: + : A + B = {x|x ∈ A ∨ x ∈ B} union ∗ : A ∗B = {x|x ∈ A ∧ x ∈ B} intersection − : A−B = {x|x ∈ A ∧ x /∈ B} complement | : A |B = {x|x ∈ A + B ∧ x /∈ A ∗B} symmetric difference = {x|x ∈ (A + B)− (A ∗B)} The operator ’∗’ has a higher priority than ’+’, ’|’ and ’−’, whom have the same priority. The operators are left-associative. Example: A−B ∗ Set1 + D is to be evaluated as (A− (B ∗ Set1)) + D. There are two commands available. For each of those an example is given: 1. Set1 = A + B − Set1 ∗ (D + Set2) Calculate the set that is the result of the expression to the right of the ’=’-sign and associate the variable with the identifier Set1 with this Set. 2. ? Set1 + Set2 Calculate the set that is the result of the expression, and print the elements of this set on the standard output. Syntax command-language We use the EBNF-notation for describing the syntax-portion of the command- language grammar. Furthermore the signs ’<’ and="" ’="">’ are used for descriptions (for example ). program = { statement } ; A program is any arbitrary number of statements (commands) ended by the end of file. statement = assignment | print statement | comment ; A statement is an assignment-statement, a print-statement or a comment- line. assignment = identifier ’=’ expression ; An assignment statement is an identifier, followed by the ’=’ sign, after which there is an expression, followed by an end-of-line. print statement = ’?’ expression ; A print statement is a ’?’ followed by an expression and ended with an end-ofline. comment = ’/’

; A comment is a line of text that starts with the ’/’ -sign and is closed by an end-of-line. 2 identifier = letter { letter | number } ; An identifier starts with a letter and only consists of letters and numbers. expression = term { additive operator term } ; An expression is a term, followed by zero or more terms. All terms are separated by an additive-operator. term = factor { multiplicative operator factor } ; A term is a factor, followed by 0 or more factors. All factors are separated by a multiplicative-operator. factor = identifier | complex factor | set ; A factor is an identifier, a complex factor or a set. complex factor = ’(’ expression ’)’ ; A complex factor is an expression between round brackets. set = ’{’ row natural numbers ’}’ ; A set is a row of natural numbers between accolades. row natural numbers = [ natural number { ’,’ natural number } ] ; A row of natural numbers is empty or a summation of one or more nat- ural numbers separated by commas. additive operator = ’+’ | ’|’ | ’−’ ; An additive operator is a ’+’, a ’|’ or a ’−’ sign. multiplicative operator = ’∗’ ; A multiplicative operation is a ’∗’ -sign. natural number = positive number | zero ; A natural number is a positive number or zero. positive number = not zero { number } ; A positive number does not start with a zero, does not have a sign, and has 1 or more numbers. number = zero | not zero ; A number is a zero or not a zero. zero = ’0’ ; Zero is the number 0. not zero = ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ ; Not-zero is the number from the range 1 up to and including 9. letter = ’A’ | ’B’ | ’C’ | ’D’ | ’E’ | ’F’ | ’G’ | ’H’ | ’I’ | ’J’ | ’K’ | ’L’ | ’M’ | ’N’ | ’O’ | ’P’ | ’Q’ | ’R’ | ’S’ | ’T’ | ’U’ | ’V’ | ’W’ | ’X’ | ’Y’ | ’Z’ | ’a’ | ’b’ | ’c’ | ’d’ | ’e’ | ’f’ | ’g’ | ’h’ | ’i’ | ’j’ | ’k’ | 3 ’l’ | ’m’ | ’n’ | ’o’ | ’p’ | ’q’ | ’r’ | ’s’ | ’t’ | ’u’ | ’v’ | ’w’ | ’x’ | ’y’ | ’z’ ; A letter is a capital letter or a small letter. Remarks 1. Spaces in natural numbers and identifiers are not allowed. Elsewhere, spaces have no function and they can be added to any line to increase readability. 2. When a faulty statement is discovered, then a clear error message needs to be printed, followed by a new-line. Explanatory error messages like this are necessary in the test-phase to discover what the program exactly does (this is usually something else than what it should do). 3. The program has to read from standard input and write to standard out- put. The output must consist of one-line error-messages or one-line with numbers, separated with spaces and ending with an end-of-line after the last number. 4. Comments have to be ignored. 5. The method eval(String s) in class Interpreter should return null after an assignment, comment or when an exception is raised. The method should return the Set object after printing the result from the print-statement. 6. In order to use the JUnit tests we provided, it is important to not modify the package, method and class names from the skeleton. 7. Submissions that do not pass ALL of the JUnit tests in the skeleton will not be graded. Recursive descent We illustrate how to make a design by showing how a factor can be recognized with the method ”recursive descent”. ”recursive descent” means that the meth- ods that parse the input call each other recursively. We can, for example, design a method factor() that: 1. returns a set of natural numbers as the result of the function if there is grammatically correct input, and 2. gives an exception, and throws an APException if there is grammatically incorrect input. When the method factor() parses a complex factor, the right expression has to be parsed, for which a term has to be parsed, for which another correct factor has to be parsed. So after 3 calls in between, factor() is called again (in other words there is recursion). 4 A first sketch of the method factor() is: 1 Set factor () throws APException { 2 /* factor () reads , if possible , a correct factor of the input. 3 If this succeeds this factor is evaluated and the resulting 4 set is returned. 5 If this fails , then an error -message is given and a 6 APException is thrown. 7 */ 8 if (the next character is a letter) { 9 read an identifier 10 retrieve the set that belongs with that identifier 11 } 12 else if (the next character is ’{’) { 13 read a set 14 } 15 else if (the next character is ’(’) { 16 determine the set that is the result of the complex factor 17 } 18 else { 19 give a clear error -message 20 throw APException 21 } 22 RETURN the value of the set 23 } Also, pay attention to the similarity between the syntax-definition of a factor and the design of factor(). The syntax-rules are a very thorough analysis/de- scription of the input and only have to be converted to a Java during the design process. Importing the skeleton and running the tests Download the AP2-skeleton.zip from Canvas and do the following: Windows 10 users: Right-click the .zip file and select ”Extract All” in the context menu. Choose where you want to extract the .zip file and select ”Extract”. In Eclipse at the top-left of your screen, select File > Open Projects from File System... > Directory > AP2-skeleton folder > Finish. Mac OSX users: Double-click the .zip file to extract it. This will create a new folder con- taining the skeleton. In Eclipse at the top-left of your screen, select Eclipse > Open Projects from File System... > Directory > AP2-skeleton folder > Finish. To run the JUnit tests, all you have to do is open the test file and press the run button. You will only receive a grade for this assignment if ALL test cases pass! If you would like to learn more about JUnit and/or write your own test cases, you can find more information here: https://junit.org/junit5/docs/current/user- guide/. 5 https://junit