CSCI 316: TinyJ Assignment 1
Assignment Overview
To be submitted no later than: Thursday, December 4. [Note: If mars fails to operate normally or becomes inaccessible at any time after 6 p.m. on this due date, the submission deadline will not be extended. Try to submit no later than noon that day, and on an earlier day if possible. Tiny J Assignment 2 will be provided to you on or before Wednesday, November 26.] This assignment counts 1.5% towards your grade if the grade is computed using rule A.
Assigned Problems
Language Description
The TinyJ language is an extremely small subset of Java. Every valid TinyJ program is a valid Java program, and has the same semantics whether it is regarded as a TinyJ or a Java program. The syntax of TinyJ is given by the EBNF specification that is shown below. In this EBNF specification each terminal is a token of TinyJ, and each nonterminal <X> denotes the set of all sequences of tokens that are syntactically valid for the TinyJ construct X. In particular, a piece of source code is a syntactically valid TinyJ program if and only if its sequence of tokens belongs to the language generated by this EBNF specification. A piece of source code is a valid TinyJ program if and only if it is both a syntactically valid TinyJ program and a valid Java 8 program, with a few exceptions: TinyJ does not allow non-decimal (i.e., hexadecimal, octal, or binary) or long integer literals, underscores in integer literals, method name overloading, program arguments, printing of Boolean values, “return;” statements within the main() method, escape sequences other than \n, and ints that are beyond the range 231-216 = 2,147,418,112.
Reserved words of TinyJ are shown in boldface in this EBNF specification. Some names used by Java library packages, classes, and their methods (e.g., java, Scanner, and nextInt) are reserved words of TinyJ, as is main. Otherwise, IDENTIFIER here means any Java identifier consisting of ASCII characters.
TinyJ EBNF Specification
<cprogram> ::= [<importStmt>] class IDENTIFIER '{' {<dataFieldDecl>}
<mainDecl> {<methodDecl>} '}'
<importStmt> ::= import java . util . Scanner ;
<dataFieldDecl> ::= static <varDecl>
<varDecl> ::= int <singleVarDecl> { , <singleVarDecl>} ;
| Scanner IDENTIFIER = new Scanner '(' System . in ')' : :=
<singleVarDecl> ::= IDENTIFIER { '[' ']' } [ = <expr3> ]
<mainDecl> ::= public static void main '(' String IDENTIFIER '[' ']' ')'
<compoundStmt>
<methodDecl> ::= static ( void | int {'[' ']'}) IDENTIFIER
'(' <parameterDeclList> ')' <compoundStmt>
<parameterDeclList> ::= [<parameterDecl> { , <parameterDecl> }]
<parameterDecl> ::= int IDENTIFIER {'[' ']'} : :=
<compoundStmt> ::= '{' { <statement> } '}'
<statement> ::= ; | return [<expr3>] ; | <varDecl> | <assignmentOrInvoc>
| <compoundStmt> | <ifStmt> | <whileStmt> | <outputStmt>
<assignmentOrInvoc> ::= IDENTIFIER ( { '['<expr3>']' } = <expr3> ; | <argumentList> ; )
<argumentList> ::= '('[<expr3>{,<expr3>}]')'
<ifStmt> ::= if '(' <expr7> ')' <statement> [else <statement>]
<whileStmt> ::= while '(' <expr7> ')' <statement>
<outputStmt> ::= System . out . ( print '(' <printArgument> ')';
| println '(' [<printArgument>] ')'; )
<printArgument> ::= CHARSTRING | <expr3>
<expr7> ::= <expr6> { '|' <expr6> }
<expr6> ::= <expr5> { & <expr5> }
<expr5> ::= <expr4> { (== | !=) <expr4> }
<expr4> ::= <expr3> [ (> | < | >= | <=) <expr3> ]
<expr3> ::= <expr2> { (+ | -) <expr2> }
<expr2> ::= <expr1> { (* | / | %) <expr1> }
<expr1> ::= '(' <expr7> ')' | (+|-|!) <expr1> | UNSIGNEDINT | null
| new int '[' <expr3> ']' { '[' ']' }
| IDENTIFIER ( . nextInt '(' ')' | [<argumentList>] {'[' <expr3> ']'} )
This is the first of three TinyJ assignments. After completing all three assignments you will have a program that can compile any TinyJ program into a simple virtual machine code, and then execute the virtual machine code it has generated. (Execution should produce the same run-time behavior as you would get if you compiled the same TinyJ program using javac into a .class file and then executed that .class file using a Java VM.) There will be exam questions relating to the TinyJ assignments.
Goals
TinyJ Assignment 1 will not deal with compilation of TinyJ programs, nor with execution of virtual machine code, but only with syntax analysis of TinyJ programs. The goal of TinyJ Assignment 1 is to complete a program that will:
- (a) Determine if the sequence of tokens of its input file belongs to
<program>(as defined by the above EBNF rules), and - (b) Output a parse tree of the sequence of tokens of its input file, if that sequence belongs to
<program>.
Regarding (a), note that the sequence of tokens of the input file belongs to <program> if, and only if, the input file is a syntactically valid TinyJ program. However, a syntactically valid TinyJ program may still contain errors like “undeclared variable” or “array index out of range”. A “sideways” representation of ordered trees, described below, will be used for (b).
Parse Tree Representation
A Sideways Representation of an Ordered Rooted Tree T
If T has just one node, then representation of T = the unique node of T
Otherwise, representation of T = the root of T
representation of the 1st subtree of the root of T
representation of the 2nd subtree of the root of T
...
representation of the last subtree of the root of T ... node has no more children
In this sideways representation, sibling nodes always have the same indentation, but each non-root node is further indented than its parent; the indentation of a node is proportional to the depth of that node in the tree. Here are the “ordinary” and the “sideways” representations of a tree:
<expr4> <expr4>
| <expr3>
<expr3> <expr2>
/ | \ <expr1>
<expr2> + <expr2> UNSIGNEDINT
/ / | \ ... node has no more children
<expr1> <expr1> * <expr1> ... node has no more children
| | | +
UNSIGNEDINT IDENTIFIER UNSIGNEDINT <expr2>
<expr1>
IDENTIFIER
... node has no more children
*
<expr1>
UNSIGNEDINT
... node has no more children
... node has no more children
... node has no more children
... node has no more children
Submission Instructions
Installation and Setup
Do 1 and 2, and optionally 3 – 8, before our class on Wednesday, November 26 (and preferably before our class on Monday, November 24). Remember that Unix/Linux file and command names are case-sensitive when following the instructions below!
Installation on mars:
- Login to your
xxxxx_yyyy316 marsaccount and enter the following command at thexxxxx_yyyy316@mars:~$prompt:
/home/faculty/ykong/TJ1setup
IMPORTANT: The 1 in TJ1setup is the digit 1, not the letter l.
- Wait for “TJ1setup done” to appear on the screen. Then enter the following at the
xxxxx_yyyy316@mars:~$prompt:
java -cp TJ1solclasses:. TJ1asn.TJ CS316ex12.java 12.sol
Note the period after the colon in this command. This command executes the reference solution to this assignment with CS316ex12.java as the input file and 12.sol as the output file. A listing of CS316ex12.java should be displayed on the screen, and 12.sol should contain a sideways representation of the program’s parse tree afterwards. There should not be any error message. To view the parse tree, you can use less 12.sol or just open 12.sol in an editor.
Optional Installation on PC/Mac:
The following 6 steps are needed only if you are interested in the possibility of doing TinyJ assignments on your PC or Mac rather than mars. (Important: Regardless of where you do the assignments, you must test your code in your xxxxx_yyyy316 mars account and submit each assignment on mars using that account.) Many students in previous semesters were able to do the TinyJ assignments on a PC or Mac, but I do not guarantee that you will be able to do so: Students who try to do the assignments on a PC or Mac must be prepared to switch to working in their xxxxx_yyyy316 accounts on mars if they run into difficulties.
- Open a powershell / terminal window on your PC / Mac and enter the following at its prompt:
javac -version
If you get an error message after entering javac -version, or if the major version number that is printed is older than 11, install a new version of the Java JDK—e.g., JDK 25 from https://www.oracle.com/technetwork/java/javase/downloads/index.html. (After installing the JDK on a PC, update the PC’s System PATH environment variable so its first directory is the directory that contains the JDK’s javac executable; for a typical installation of JDK 25, C:\Program Files\Java\jdk-25\bin is the directory that should be added to your PC’s System PATH. See, e.g., https://www.computerhope.com/issues/ch000549.htm if you don’t know how to edit your PC’s System PATH.)
- In the powershell / terminal window, enter the following:
mkdir ~/316java
- Make
~/316javayour working directory by entering the following in the powershell / terminal window:
cd ~/316java
- This step assumes your PC / Mac is connected to the qwifi-secured wireless network or connected to the Queens College VPN. Use an scp or sftp client to copy
TJ1asn.jarfrom the home directory of yourxxxxx_yyyy316account on mars into the~/316javafolder. If~/316javais your working directory in the powershell / terminal window (see step 5), you can do this by entering the following in that window:
scp xxxxx_yyyy316@mars.cs.qc.cuny.edu:TJ1asn.jar .
Here xxxxx_yyyy316 means your mars username. Note the space followed by a period at the end of this command!
- Enter the following two commands in the powershell / terminal window:
jar xvf TJ1asn.jar
javac -cp . TJ1asn/TJ.java
- Enter the appropriate one of the following commands in the powershell / terminal window:
On a PC:
java -cp "TJ1solclasses;." TJ1asn.TJ CS316ex12.java 12.sol
On a Mac:
java -cp TJ1solclasses:. TJ1asn.TJ CS316ex12.java 12.sol
This command executes the reference solution to this assignment with CS316ex12.java as the input file and 12.sol as the output file. A listing of CS316ex12.java should be displayed on the screen, and 12.sol should contain a sideways representation of the program’s parse tree afterwards. There should not be any error message. To view the parse tree, you can enter the command more 12.sol on a PC or less 12.sol on a Mac.
Important Files Available After Installation
Step 1 puts 16 files named CS316exk.java (k = 0 – 15) into the home directory of your xxxxx_yyyy316 account on mars. These are all valid TinyJ source files. If you did step 7, it will have put copies of the same 16 files on your PC or Mac.
From your TJ1asn directory on mars:
OutputFileHandler.java.txt
Parser.java.txt
SourceFileErrorException.java.txt
TJ.java.txt
From your TJlexer directory on mars (the l in TJlexer is the letter l, not the digit 1):
LexicalAnalyzer.java.txt
SourceHandler.java.txt
Symbols.java.txt
These are the source files of the program, with line numbers added. (The actual source files (without line numbers) are in the same directories and have the same names, but their extension is .java.) The files can be viewed on mars using the less file viewer — for example, enter the command less TJ1asn/Parser.java.txt to view Parser.java.txt, and enter the command less TJlexer/Symbols.java.txt to view Symbols.java.txt.
If you have done steps 3 – 8 above, the same files will be in ~/316java/TJ1asn and ~/316java/TJlexer on your PC or Mac; they can be viewed using less on a Mac (e.g., enter less ~/316java/TJ1asn/Parser.java.txt in a terminal window on a Mac to view Parser.java.txt) and can be viewed using, e.g., Notepad++ or VS Code on a PC.
How to Execute the Reference Solution
You should be able to execute the reference solution to this assignment on mars by entering the following command:
java -cp TJ1solclasses:. TJ1asn.TJ <TinyJ-source-file-name> <output-file-name>
Your current working directory has to be your home directory for this to work.
If you have done steps 3 – 8 on a Mac, then the above command should also work in a terminal window on your Mac if your working directory is ~/316java (see step 5). If you have done steps 3 – 8 on a PC, then the following similar command (which has ;. instead of :.) should work in a powershell window on your PC if ~/316java is your working directory:
java -cp "TJ1solclasses;." TJ1asn.TJ <TinyJ-source-file-name> <output-file-name>
See steps 2 and 8 above for concrete examples of these commands!
Assignment Implementation
How to Do TinyJ Assignment 1
The file TJ1asn/Parser.java is incomplete. It was produced by taking a complete version of that file and replacing parts of the code with comments of the following two forms:
/* ???????? */
or (in two places):
/* ????????
default: throw ...
*/
To complete this assignment, replace every such comment in TJ1asn/Parser.java with appropriate code, and recompile the file. On mars, you can use nano, vim, or emacs to edit the file; nano or vim could also be used on a Mac in a terminal window. If you are working on your PC, do not use Notepad as your editor; you can use Notepad++ or VS Code. (For the second type of comment, the appropriate code should include the default: throw ... statement.)
Do not put Parser.java or Parser.class into any directory other than TJ1asn. Do not change or move other .java and .class files.
To recompile TJ1asn/Parser.java after editing it, enter the following command:
javac -cp . TJ1asn/Parser.java
IMPORTANT: If you are doing this on mars, your current working directory has to be your home directory. If you are doing this on your PC or Mac (in a powershell / terminal window), your working directory has to be ~/316java (see installation step 5); otherwise javac will not be able to find other classes that are used in Parser.java.
How to Test Your Solution
To test your completed version of Parser.java, first recompile it using javac -cp . TJ1asn/Parser.java and then execute TJ1asn.TJ with each of the 16 files CS316exk.java (k = 0 – 15) as the TinyJ source file and k.out as the output file, as follows:
java -cp . TJ1asn.TJ CS316ex<k>.java <k>.out
If you are doing this on mars, your current working directory has to be your home directory. If you are doing this on your PC or Mac (in a powershell / terminal window), your working directory has to be ~/316java (see installation step 5).
If your program is correct then in each case the output file k.out should be identical to the output file k.sol that is produced by running the reference solution with the same source file. On mars or a Mac, you can use diff -c to compare the output files produced by your and the reference solutions:
diff -c <k>.sol <k>.out > <k>.dif
On a PC, you can use fc.exe /n instead:
fc.exe /n <k>.sol <k>.out > <k>.dif
This outputs to k.dif the differences between k.sol and k.out. (You can view k.dif using the command less k.dif on mars or a Mac, or using the command more k.dif on a PC.) If your solution is correct, then the file k.dif should contain nothing if it was produced by diff -c or contain “FC: no differences encountered” if it was produced by fc.exe /n.
Submission Instructions
How to Submit
This assignment is to be submitted no later than the due date stated in the Assignment Overview section. [Note: If mars fails to operate normally or becomes inaccessible at any time after 6 p.m. on the due date, the submission deadline will not be extended. Try to submit no later than noon that day, and on an earlier day if possible.] To submit:
-
Add a comment at the beginning of your completed version of
Parser.javathat gives your name and the names of the students you worked with (if any). As usual, you may work with up to two other students, but see the remarks about this on page 3 of the first-day announcements document. -
Leave your completed version of
Parser.javain theTJ1asndirectory of yourxxxxx_yyyy316account on mars. When two or three students work together, each of the students must leave his/her completed file in his/herTJ1asndirectory on mars. If you did this assignment on your PC / Mac, you can copy the fileTJ1asn/Parser.javafrom that machine to yourTJ1asndirectory on mars by following the instructions below. -
Enter the following command at the
xxxxx_yyyy316@mars:~$prompt:
less TJ1asn/Parser.java
Check that this displays the beginning of your final version of Parser.java (including the comment you added in step 1)! If you copied Parser.java from your PC / Mac to mars, then be sure to test your code on mars — see the How to Test Your Solution section above.
- Enter the following command at the
xxxxx_yyyy316@mars:~$prompt:
submit_TJ_asn1
Note: If your submitted version of Parser.java cannot even be compiled without error on mars, then you will receive no credit at all for your submission!
The paragraph on page 3 of the 1st-day-announcements document that begins with “If when I compute a student’s course grade…” explains how you can verify that this assignment has been submitted.
Copying Files from PC/Mac to mars
NOTE: The steps below assume you have already done installation step 1 from the Installation and Setup section. If you haven’t, then do installation step 1 before following the instructions below.
(i) Open a powershell / terminal window on your PC / Mac and enter the following command at its prompt:
cd ~/316java
(ii) This step assumes your PC/Mac is connected to the qwifi-secured wireless network or connected to the QC VPN. Enter the following command in the powershell / terminal window (where xxxxx_yyyy316 means the username of your mars account for this course):
scp TJ1asn/Parser.java xxxxx_yyyy316@mars.cs.qc.cuny.edu:TJ1asn
You will be asked to enter the password of your xxxxx_yyyy316 mars account.
IMPORTANT: After doing (i) and (ii), be sure to also do steps 3 and 4 of the submission instructions above. The assignment will NOT be submitted until you do step 4!