UMBC CMSC 331 P2 Sp 06

UMBC CMSC 331

Principles of Programming Languages

Summer 2009

Programming Assignment #1

Due 11:59 on 6/22

Introduction

In your second programming assignment you will be writing a recursive descent parser in Java for a simple language that reads in and evaluates arithmetic expressions with assignment statements. The grammar for the language is described below.

You will need to employ the ideas about recursive descent parsing that we discussed in class including the ideas of building parser trees before evaluation. You also should consider using the ideas we discussed about tokenization and lookahead. The parser shall read form standard in and write to standard out.

You may develop on any platform you like but the Java version must be 1.6.

You may work in groups of up to three people.

Due Dates

§ The assignment is due NLT 11:59 PM on 6/22

The Grammar

Note: anything after a “//” in a line should be discarded as a comment

*Rule #*	*LHS*		*RHS*
1	<prog>	->	“{“ <sl> “}”
2	<sl>	->	<s> { “; “ <s> } “; “
3.1	<s>	->	id = <expr> \|\|
3.2			<expr>
4	<expr>	->	<term> { ( “+” \| “-“ ) <term> }
5	<term >	->	<pow > { ( “*” \| “/” ) <pow > }
6	<pow >	->	<fact > { “^” <fact> }
7	<fact>	->	“(“ <expr> “)” \| id \| number \| trig “(“ expr “)”

The values in strings are tokens that stand for their normal meanings. The values underlined are tokens with lexemes. The token id is any character followed by any number of digits or characters. The token number is a signed floating point number as in C++ or Java. The token trig has lexemes “cos” , “sin” and “tan”. Additionally there are comments that start with “//” and continue until the end of the line with the text of the comment.

All math happens in double. All trig functions are in radians. All numbers are signed but the sign and digits may not be separated by any space (+0.34 is valid - 0.3 is not a valid number token). All numbers have at least one digit to the left of the decimal sign, so .6 is not valid but 0.6 is valid)

All operations are left associative except for exponentiation which is right associative.

Sample Data

You must match and evaluate the following programs. (Note that this is a necessary but not sufficient condition for correctness).

{ // Program 1

// arithmetic

42.0; // prints 42.0

1 + 3.00; // prints 4.0

a = 4; // prints 4.0

a + a * a; // prints 20

a; // prints 20

// trig

sin(0); // print 0.0

sin(0.0); // prints 0.0

sin(3.14); // prints near 0.0

y = 1; // prints 1.0

}

{ // Program 2

3 ^ 2^2 ;

3 ^ 2^2 * 3 + 1;

x; // prints “semantic error x undefined

}

{ // Program 3;

x = 3; // prints 3.0

3*x; // prints 9.0

y; // prints “semantic error y undefined”

}

{ // Program 4;

x += 3; // print syntax error

}

{ // Program 5;

x = 3; // prints 3.0.0

y = 4 *x - 6; // prints 6.0

x = cos(x) ;

}

{ // Program 6;

x = 3; // prints 3.0

y = ( ((( 4 + x ))) * (( 2.3 ^ ( 2 + 1) * 3 ) / 6.2)) ;

}

Grading

The project will be graded using the following criteria.

Scale		Pts
1	Doesn’t compile but design is correct	40
2	Compiles and runs on some sample input	10
3	Compiles and runs on all sample input	15
4	Allows id of arbitrary length	15
5	Evaluation of expression not done inline line (i.e. done via tree and eval approach from class)	20

Submission

You must mail me your jar file[1] no latter than 11:59 PM on the dues dates listed above. Your jar file should be called Prog1.jar. Please do not assume access to any IDE for the person grading your project (e.g you should not assume that the grader has Eclipse or Netbeans or any other IDE). Mail them to the following address mailto:vick@umbc.edu?subject=P1_331_SU09 with the Subject Line “331 P2 SU 09”. Each jar file shall also contain a README file with any special instructions Failure to follow these instructions EXACTLY may result in your work not being accepted.

Tips

Remember that all i/o is from standard in and standard out. We discussed using System.out for standard out in class. The FAQ page (see http://userpages.umbc.edu/~vick/331/FAQ.htm) has a tip on how to use System.in. For more information on how to do i/o in Java see the Java Tutorial (http://java.sun.com/docs/books/tutorial/essential/io/). You may want to use the Regular Expression classes (see http://java.sun.com/docs/books/tutorial/extra/regex/) to do the tokenization. Note that you can not just use the StringTokenizer class easily.