Lab 4 - Parser - COMP2100/6442 Skip navigation COMP2100/6442 ANU College of Engineering & Computer Science Search query Search ANU web, staff & maps Search COMP2100/6442 Exams menu Search query Search ANU web, staff & maps Search Search COMP2100/6442 labs Overview Lab 1 - Install Lab 2 - Git / SSH Lab 3 - Trees Lab 4 - Parser Lab 5 - Android 1 Lab 6 - Android 2 Lab 7 - Persistent Data Lab 8 - PHP Lab 9 - Lab Test 1 Lab Test 2 related sites Wattle Lab 4 - Parser The partial code for this lab can be found here. Task 1 - Tokenizer [0.5 marks] The main objective of this part is to implement a simple tokenizer. The input of the tokenizer is a string. Your goal is to break down the character stream and return a sequence of tokens. First, take a look at ‘Token.java’ and understand the types of tokens we want to extract from a string. There are 7 types of tokens: INT: a decimal 32-bit unsigned integer (e.g. 4869) ADD: a single add character (+) SUB: a single minus character (-) MUL: a single star character (*) DIV: a single slash character (/) LBRA: a single left round bracket (() RBRA: a single right round bracket ()) Our main tokenizer class, MyTokenizer.java, inherits abstract class Tokenizer.java which has three methods in it: hasNext(), current(), and next(). MyTokenizer.java implements Tokenizer.java. Specifically, MyTokenizer.java defines two additional private fields: _buffer and currentToken. _buffer will keep the string that we want to tokenize, and currentToken keeps a Token instance which is extracted by next() method. Read the comments to understand the details of how these function should work. Check the constructor of MyTokenizer, which will initially save the input string to _buffer and extract the first token using next(). Check the implementation of hasNext() and current() in MyTokenizer. Now your job is to implement the missing part of next() method. Initially, the tokenizer provided only works with tokens that are: “+” token and the “-“ token. It is also able to consume white space, which normally a tokenizer would do. Modify the next() implementation such that it deals with the tokens “*”, “/”, “(“, “)” and unsigned integer. Before implementing the actual method, please go and check the test cases in TokenizerTest.java. Test cases are one of the best ways to define the requirements of the code. You may want to check the example code used in the classroom lecture. The implementation is slightly different from the example code since we introduced Token class in this task. Therefore, instead of returning a string from current() now the tokenizer will return Token class which contains the type information as well as the surface form (string) or the token. This way of implementation is more object-oriented. Remind: Please implement your code within a block indicated by comments; ‘YOUR CODE STARTS HERE’ and ‘YOUR CODE ENDS HERE’ for each task. Task 2 - Parser [0.5 marks] The main objective of this part is to implement a simple parser. To complete the second task, you first need to complete Task 1. Once you’ve implemented tokenizer, import your tokenizer implementations (java files) into task2. Now the goal of this task is to implement a parser for the following grammar: ::= | + | -
::= | * | /
::= | ( )
Try to understand the grammar and implement a parser which could parse this grammar. Go through Exp.java , AddExp.java , IntExp.java , SubExp.java, DivExp.java, MultExp.java files: Check the implementations of show() and evaluate() methods. show() method is designed to return the content of parsed expression, and evaluate() method will evaluate and execute the expression and return the result. Go through ParserTest.java: ParserTest is a JUnit test class, which defines the proper behaviour of the parser through a set of examples. Read the code and try to understand what are the requirements of the parser. Implement missing parts of Parser.java: Parser class contains three parsing methods: parseExp(), parseTerm(), and parseFactor(). Now your job is to implement these three methods. If you don’t know what you need to implement, please go and check the code that we used in the classroom here. The grammar used in the classroom was slightly simpler than the grammar above, but the structure of the code is almost similar. If you are still unconfident aboutree/master/_labst the parser, please go over the lecture and ask help from tutors. Remind: Please implement your code within a block indicated by comments; ‘YOUR CODE STARTS HERE’ and ‘YOUR CODE ENDS HERE’ for each task. Submission Guideline Assignment deadline: 7 April 2019, 11:55pm Submission mode: Electronic, via Wattle (Lab 4) Submission format (IMPORTANT): Upload your final version of MyTokenizer.java (for task 1) and Parser.java (for task 2) to Wattle. Do not change the file names. Do not upload any other files. Do not upload a folder (your submission should be two java files). The answers will be marked by an automated marker. Do not change the structure of the source code including class name, package structure, etc. You are only allowed to edit the designated code segment indicated in the comments. Do not import packages outside of the standard java SE package. The list of available packages can be found here: https://docs.oracle.com/en/java/javase/12/docs/api/index.html* You may use standard libraries to complete the tasks, but it is not allowed to use external libraries. Violation of the submission format will have their assignment not evaluated by an autograder and get zero marks. Updated: / Responsible Officer: / Page Contact: Contact ANU Copyright Disclaimer Privacy Freedom of Information +61 2 6125 5111 The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906 You appear to be using Internet Explorer 7, or have compatibility view turned on. Your browser is not supported by ANU web styles. » Learn how to fix this » Ignore this warning in future
