Computer Science 433

Programming Languages

Fall 2012, The College of Saint Rose

In this assignment, you will be completing some problems related to syntax, grammars, and parse trees.

You may work alone or with a partner on these problems.

Textbook Problems

Reverse Polish Notation

Reverse Polish notation (RPN) is a common name for postfix mathematical expressions. Such notation lends itself to a stack-based evaluation and is used by the PostScript printer language and some old calculators. It has the advantage that it can specify any expression that can be specified in the usual (infix) notation without the need for parentheses to enforce order of operations.

If we are given an expression in RPN we would evaluate it as follows.

- Start with an empty stack.
- Evaluate the expression from left to right. Each step of the
way:
- if a number is encountered, push it onto the stack
- if an operator is encountered, pop 2 numbers from the stack, apply the operator to those numbers, push the result onto the stack

- If the expression is valid, there should be a single number left on the stack.

So for the expression

9 7 12 - *

we start with the empty stack. We then push `9`, push `7`, push
`12`, so our stack consists of `[ 9 7 12 ]`. We encounter the
`-` operator, pop the `12` and the `7` from the stack,
calculate `7 - 12 = -5` and push the result, giving a stack of `[ 9
-5 ]`. We then encounter the `*` operator, pop the `-5` and
`9` from the stack, calculate `5 * -9 = -45` and push the
result, giving a stack of `[ -45 ]`. Now there are no more tokens
on the input, so the value at the top of the stack contains our
result, `-45`.

`5 8 19 + * 2 3 + 5 7 * / 7 * 12 + 9 / 3 23 2 3 + 5 7 * / 3 4 + * 1 - 9 9 * 8 7 * * 5 5 * * 4 - `

`5 - 3 * 2 + 7 10 * 3 * 9 / 4 (5 + 8) / (9 -3) 5 + 8 / 9 - 3 `

`3 4 + 9 3 - 4 * *
`

A Grammar for BASIC

Considered this grammar for a subset of the BASIC language.

<program> => <lines> <lines> => <line> | <line> <lines> <line> => <line-number> <stmt> \n <line-number> => integer-literal <stmt> => REM string-literal | PRINT <print-expr> | INPUT <variable> | LET <assignment> | END <variable> => <integer-var> | <string-var> <integer-var> => integer-variable-name <string-var> => integer-variable-name$ <print-expr> => "string-literal" | <variable> <assignment> => <integer-var> = integer-literal | <string-var> = "string-literal"

`10 REM THIS IS FUN!20 LET X = 830 PRINT X`

Three types of BASIC statements that are not included are the
`IF/THEN` construct, the standard `GOTO` statement, and the
`IF/GOTO` construct

An `IF/THEN` looks like this:

30 IF X>5 THEN LET X = X - 5

A `GOTO` statement looks like this:

70 GOTO 10

An `IF/GOTO` statement looks like this:

100 IF Y<>Z GOTO 150

Submission

To submit this assignment, send a single PDF file with your responses
as an attachment to *terescoj AT strose.edu* by 11:59 PM, Tuesday, September 25, 2012.

Please include a meaningful subject line (something like "CS433 Program/Problem Set 3 Submission").

Grading

This assignment will be graded out of 35 points, as broken down by the numbered questions throughout this document.