UMBC CMSC
331
Principles of Programming Languages
Spring 2010
Programming Assignment #1
·
In your first
programming assignment you will be writing a recursive descent parser in Java
for a simple language that reads in and evaluates arithmetic expressions with
function definitions. 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, but you can work alone if preferred. Groups will
be organized in class on Thursday 2/25.
Due Dates
§
Assigned 2/23 (Groups Formed 2/25) Due 3/9 (5 pt Bonus), 3/11 (No Bonus)
·
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>
| |
|
3.3 |
|
|
id “( “<expr> “)” | |
|
3.4 |
|
|
id “( “ id “)” = <expr> |
|
4 |
<expr> |
-> |
<term> { ( “*”
| “/“ ) <term> } |
|
5 |
<term
> |
-> |
<pow
> { ( “+” | “-” ) <pow
> } |
|
6 |
<pow > |
-> |
<fact >
{ “^” <fact> } |
|
7.1 |
<fact> |
-> |
“(“ <expr> “)” | |
|
7.2 |
|
|
id | |
|
7.3 |
|
|
number | |
|
7.4 |
|
|
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.
·
You must match and
evaluate the following programs. (Note that this is a necessary but not
sufficient condition for correctness).
{ //
Program 1
// arithmetic
42;
// prints 42
1 + 3;
// prints 4
a =
4;
// prints 4
a + a *
a; // prints 32
(((((((((((((((((( 1 ))))))))))
)))))))) +
(((((((((( 1 )))))))))) ;
// 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
y = 4 *x -
6; // prints
4
x = cos(x) ;
}
{ //
Program 6;
x = 3;
// prints 3.0
y = ( ((( 4 + x )))
* (( 2.3 ^ ( 2 + 1) * 3 ) / 6.2)) ;
f1(y) = y + 4;
f1(3);
// prints 7
f2(y) = x + y;
f2(3); // prints 6
}
The project will be graded using
the following criteria.
|
Scale |
Pts |
|
|
1 |
Doesn’t compile but design
is correct |
35 |
|
2 |
Compiles and runs on some
sample input |
10 |
|
3 |
Compiles and runs on all
sample input except function evaluation /definition |
10 |
|
4 |
Allows id of arbitrary length |
10 |
|
5 |
Evaluation of expression not
done inline line (i.e. done via tree and eval
approach from class) |
15 |
|
6 |
Implements Function Definition
and Evaluation (Rules 3.3 and 3.4) |
20 |
You must
mail me your jar file no latter than
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/) .
Try to use the Java API (see http://java.sun.com/j2se/1.5.0/docs/api/
) as much as possible. For example Use of the Regular Expression (see http://java.sun.com/docs/books/tutorial/extra/regex/) to
do the tokenization and HashMap classes will make
your implementation a lot easier. Note that you can not just use the StringTokenizer class for creating tokens.
If you are not
familiar with jar files see http://java.sun.com/docs/books/tutorial/jar/