Computer Science 340
Programming Languages

Fall 2019, Siena College

Home     Syllabus     Schedule

In this fairly short problem set, 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.

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

Submit a hard copy of your responses. Please keep a copy/photo of your submission for yourself if your responses are handwritten.

Grading

This assignment will be graded out of 30 points.