Homework #1 - CSE130 Programming Languages



Date Assigned: Monday, 2 July 2007
Date Due: Monday, 9 July 2007 (by 11:59 pm)
Required Solution Files: hw1.scm, MiniLispScanner.java

Readings

Text Exercises

Complete excercises 1.3, 1.11, 1.12, 1.16, putting all solutions in hw1.scm.

To help get you started, there is an outline provided for you. Login to your ieng6 account (you can find your account information on-line with the Account Lookup Tool at acs.ucsd.edu) and execute the following commands:

$ cd ~
$ mkdir hw1
$ cd hw1
$ cp ~/../public/hw1.scm .

Interpreter: Write a Lisp-like Scanner

In Java, finish the implementation of a Lisp-like scanner, where the grammar for the tokens is below. Note:
  1. Non-terminals in the grammar are capitalized
  2. Special rule descriptions are in [...]'s, for brevity
  3. This is a different grammar than the Lisp slide presented in class
  4. The symbol "::=" is used instead of "→"
  5. The notation { x } means "zero or more of x"
Identifier ::= Initial {Subsequent}
Identifier ::= +
Identifier ::= -

Initial ::= Letter
Initial ::= ! | $ | % | & | * | / | : | < | = | > | ? | ~ | _ | ^

Subsequent ::= Initial | Digit | . | + | - | @

Letter ::= a | b | c | ... | z | A | B | C | ... Z

Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Punctuation ::= (
Punctuation ::= )
Punctuation ::= .

Boolean ::= # t
Boolean ::= # f

String ::= " {StringElement} "

StringElement ::= [any character other than " or \]
StringElement ::= \"
StringElement ::= \\
StringElement ::= \n

Integer ::= + Num
Integer ::= - Num
Integer ::= Num

Num ::= Digit {Digit}

WhiteSpace = [space, tab, or newline or carriage return and any ";"s
              with characters following for the rest of the line]

EOF ::= [when the end of the file is reached]

Error ::= [special token for dealing with invalid input]

For the String token you must interpret \n as a newline and translate it (as with the \" and \\ cases).

The scanner should not return a token when it recognizes WhiteSpace. Instead, it should continue reading and return the next token (which may be EOF). Note that spaces cannot appear within any of the other tokens. For example, the token -10 is a valid Integer, while - 10 is actually an Identifier (-) followed by an Integer (10).

To help get you started, some code is already provided for you on ieng6:

$ cd ~
$ mkdir interpreter
$ cd interpreter
$ cp -r ~/../public/interpreter/cse130 .
Then, edit the cse130/scanner/MiniLispScanner.java source file and complete the scanner. The classes for the token types are provided and you should only need to edit cse130/scanner/MiniLispScanner.java.

Turning It In

Execute the following commands to turn in both required files:

$ cd ~
$ ~/../public/bin/bundleHW1

Note: Only your hw1.scm and MiniLispScanner.java files will be turned in. Any changes you've made to auxiliary files will not be reflected.

Grading

The Text Exercise section (hw1.scm) is worth 60 points: The Interpreter Scanner (MiniLispScanner.java) is worth 20 points:

Running The Autograder

To run the autograder for the Text Exercise section enter the following command in the directory that contains your hw1.scm file:

$ ~/../public/bin/autograder-hw1.pl hw1.scm
Test #1:
(exercise1.3 1 2 3) => 13
Expected -> 13
PASS

Test #2:
(exercise1.3 1 3 2) => 13
Expected -> 13
PASS

Test #3:
(exercise1.3 2 1 3) => 5
Expected -> 13
>>> FAIL

  [...]

Test #51:
(fast-expt-iter 7 35) => 378818692265664781682717625943
Expected -> 378818692265664781682717625943
PASS

Total Tests: 51
PASSED: 48
FAILED: 3

Additionally, your program will be inspected by the grader and subject to additional tests. Your programs must compute according to the requirements and not just echo the output expected by the autograder. Programs that take this "short cut" will receive zero credit.

To run the autograder for the interpreter, enter the following commands:

$ cd ~/interpreter
$ javac cse130/scanner/*.java
$ ~/../public/bin/autograder-scanner.pl