Computer Science 433
Programming Languages

Fall 2014, The College of Saint Rose

Home     Syllabus     Schedule

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. In order to earn full credit, you must show all of your work for 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.

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"

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 = 5

A GOTO statement looks like this:

70 GOTO 10

An IF/GOTO statement looks like this:

100 IF Y<>Z GOTO 150

Submission

Before 11:59 PM, Monday, September 15, 2014, submit your work for grading. Create and submit a single archive file (a .7z or .zip file containing all required files) using Submission Box under assignment "PS2".

Grading

This assignment will be graded out of 45 points.